Papers for

quantum hardware architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Quantum circuit amplitude calculations are either easy or very hard

A Dichotomy for Exact Quantum Circuit Amplitudes

Abstract: We classify the complexity of exactly computing computational-basis amplitudes for circuits over any fixed finite library of unitary qubit gates, with each gate allowed to act on any ordered tuple of distinct wires. Exact evaluation is polynomial-time computable if all gates permute the computational basis up to phases, all preserve product states, or all become Clifford under a common diagonal one-qubit unitary change of basis on every wire. For every other library, the problem is $\#\mathrm P$-hard under polynomial-time Turing reductions. Our proof connects circuit amplitudes to the Boolean Holant classification of tensor contractions on arbitrary graphs. For an algebraic library containing a nonmonomial gate and an entangling gate, we show how to simulate the joint use of a symmetric maximally entangled state and its adjoint at polynomial cost, using only amplitude queries over the original library. This lets us evaluate unrestricted contractions of the resulting gate and boundary tensors. Unitarity and the computational-basis boundaries then restrict the tractable cases to the three forms above. Algebraic specialization extends the dichotomy to arbitrary fixed complex gate entries under a symbolic exact-output convention.

Tue 17 NovComputational Complexity
The gist
The paper shows which quantum circuits let you calculate exact probabilities quickly and which ones are much harder to solve. The authors classify all fixed sets of quantum gates into three kinds where computations are easy: those that just shuffle basis states with phases, those that keep states separate, and those changing to a special Clifford form. Any other set makes exact calculations as hard as counting problems known to be very difficult. Their proof builds connections between quantum circuits and tensor graph computations.
Open → 2611.22899v1

Essential unitarity ensures information preservation in higher-order quantum computing

Essential Unitarity for Higher-Order Quantum Computation (Extended Abstract)

Abstract: We develop a boundary-centric semantic framework for higher-order quantum computation, building on the Kelly-Laplaza description of compact closure and Abramsky's execution account. In the semantic carrier Perm(C), morphisms are complex-linear combinations of polarized boundary linkings, composed by execution. Finite-family addresses provide coherent control over finite-level quantum registers (qudits) while retaining the multiplicative boundary structure. We identify essential unitarity, a boundary condition extending ordinary unitarity to higher-order interfaces. On positive qudit registers it coincides with ordinary matrix unitarity; at higher order it expresses preservation of information across the full polarized boundary. We define a unit-free coherent quantum core generated bymultiplicative wiring, unitary gates on positive qudit registers, and contextual coherent control, and prove that every one of its morphisms is essentially unitary. The framework realizes an applied coherent quantum switch and the unitary stages of equal-ratio one-slot supermap dilations with explicit memory. Complete proofs appear in the full version of this paper.

Wed 4 NovLogic in Computer Science
The gist
Quantum computers use special building blocks called unitary operations to process information without loss. This paper extends the idea of unitarity to more complex, higher-order quantum systems that manage information across multiple layers. The authors introduce a new framework that guarantees these advanced quantum operations preserve information correctly, even when they interact in complicated ways. This work helps better understand and design quantum programs that involve controlling other quantum programs.
Open → 2611.06137v1

Quantum mixing of bosonic inputs reveals conditional independence structure

A Conditional Quantum Kac-Bernstein Theorem

Abstract: We establish a conditional quantum Kac-Bernstein theorem for mixing of two independent, finite-mode bosonic inputs with quantum memories. We characterize exactly when the outputs are conditionally independent given both memories. Each input then decomposes into orthogonal memory sectors sharing a common Gaussian state on the physical system and a bosonic memory factor, up to sector-dependent physical displacements. In particular, triviality of the common bosonic factor implies separability of the inputs, as occurs whenever either memory has finite-dimensional support.

Tue 3 NovInformation Theory
The gist
This paper solves a puzzle about how combining two special quantum inputs, called bosonic inputs that each have a memory, behaves when they come together. The authors found a precise condition for when the outputs from mixing these inputs act independently if you know each input’s memory. They showed that each input can be split into parts that share a common simple state plus a memory part, with some shifts depending on the part. In particular, if the common part is trivial, then the two inputs are completely separate, especially if one memory is limited in size.
Open → 2611.04363v1

Distributed quantum computing simulator models execution strategies and success rates

SeQUeNCe.DQC: Full-stack Simulation of Distributed Quantum Computing

Abstract: Distributed quantum computing (DQC) connects multiple quantum processing units to overcome the scale limits of monolithic hardware. We introduce SeQUeNCe.DQC, a new top-level module within the SeQUeNCe package that compiles monolithic circuits into topology-aware execution plans and coordinates their execution using SeQUeNCe's existing quantum-network modules and protocols. We validate SeQUeNCe.DQC by reproducing a two-node trapped-ion Grover experiment in simulation and comparing success probabilities with the reported 71% benchmark. We then evaluate how compiler strategy, topology, and memory capacity jointly govern distributed circuit execution time and success rate. In these experiments, our hybrid compilers successfully identified mixed TeleGate/TeleData execution plans that outperformed pure gate-teleportation strategies. By capturing the physical overhead of distributed quantum primitives, SeQUeNCe.DQC provides a rigorous platform for co-designing DQC software and hardware architectures.

Thu 29 OctNetworking and Internet ArchitectureDistributed, Parallel, and Cluster Computing
The gist
Building big quantum computers is hard, so scientists connect smaller quantum chips to work together. The authors created SeQUeNCe.DQC, a tool that turns regular quantum programs into plans that match the connections between these chips. They tested their tool by simulating an experiment and matched its success rates. They also showed how different ways of compiling and the computer’s layout affect how fast and well these programs run. This tool helps design better software and hardware for connected quantum computers.
Open → 2610.39476v1

Quantum query complexity lower bounds under query noise models

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Abstract: We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity (\(\fbs\)). For a negligent oracle that applies the correct query with probability \(1-p\), we prove a lower bound in terms of \(\fbs(f,0^n)\). We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function \(f\) can be transformed into a partial function \(f'\) whose negligent query complexity essentially preserves the quantum query complexity of \(f\). This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of \(\fbs(f)\) for partial functions in this model. For two other models, we obtain general lower bounds in terms of \(\fbs(f)\) for all Boolean functions. For hybrid algorithms using \(Q\) coherent and \(C\) classical queries, we prove the tradeoff \(C+Q^2=Ω(\fbs(f))\). For an IID dephasing noisy model where each query dephases the query-index register at rate \(p\) independently, we prove \(Ω\!\left(p\,\fbs(f)\right)\) queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by \(\fbs(f)\). Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.

Wed 30 SeptComputational Complexity
The gist
Quantum computers often get information by asking questions (queries) to an oracle. This paper looks at how noisy or imperfect these questions can affect the power of quantum algorithms. The authors find ways to measure and bound how hard it is to solve problems when queries can be wrong or partially corrupted. Surprisingly, some quantum speed advantages survive even with noisy queries. They also provide formulas and methods to understand how various noise types affect quantum query complexity.
Open → 2610.00506v1

Quantum oracle types shape complexity class separations differently

A Separation Between Types of Quantum Oracle Separations

Abstract: Recent works have demonstrated that quantum oracles have subtle behavior, as access to inverse, conjugate or controlled queries can exponentially change the query complexity of certain tasks. Inspired by these works, we introduce the notion of meta-complexity of quantum relativization. We ask: for any two quantum complexity classes, under which "types" of quantum oracles are they equal or separated? Different pantheons of oracles (or quantum oracle types, e.g. unitary vs state, poly- vs superpoly-dimensional, closed under inverse or not) form a partially ordered set based on their power in separating complexity classes. Moreover, two oracle pantheons A and B are separated if there exists a pair of complexity classes that are separated under an oracle from pantheon A but yet the complexity classes are equivalent under all oracles from pantheon B. We show that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes $\mathsf{PostBQP}$ and $\mathsf{PreciseBQP}$, the exponentially precise variant of $\mathsf{BQP}$. Both classes equal $\mathsf{PP}$ in the unrelativized setting. Within our taxonomy, they remain equal relative to real or polynomial-dimensional unitary oracles and whenever inverse or conjugate access is supplied. In contrast, we give a separation relative to forward-only complex diagonal unitaries of superpolynomial dimension, as well as a separation relative to single-qubit state-preparation oracles. We view this as a test case for the meta-complexity of oracles which underscores the subtlety inherent to the relativization of quantum complexity classes.

Wed 30 SeptComputational Complexity
The gist
Some problems in quantum computing involve different categories called complexity classes that describe how hard tasks are. This paper finds that the kind of quantum oracle—or special query tool—used can change whether two classes are considered the same or different. The authors classify various types of quantum oracles and show that some make two particular classes, PostBQP and PreciseBQP, appear equal, while others can separate them. This shows that the details of quantum oracles matter a lot when studying quantum complexity.
Open → 2609.38704v1

Quantum circuits achieve fastest possible depth for single qubit gates

Depth-Optimal Quantum Compilation

Abstract: We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant $δ>0$, it $\varepsilon$-approximates an arbitrary single-qubit gate using $O(\log^{1+δ}(1/\varepsilon))$ clean ancillae, Hadamard and $T$ single-qubit gates, $O(\log(1/\varepsilon))$-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, $T$, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth $O(\log\log(1/\varepsilon))$, and we prove a matching $Ω(\log\log(1/\varepsilon))$-depth lower bound. Overall, we establish that $Θ(\log\log(1/\varepsilon))$-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis. These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-$d$ QAC circuit can be simulated in depth $O(d)$ using only Hadamard, $X$, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity$\notin$QAC$^0$ to proving a Parity lower bound against circuits consisting only of Hadamard, $X$, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.

Mon 28 SeptComputational Complexity
The gist
Quantum computers use circuits made of gates to perform tasks, but making these circuits as short as possible (in depth) is important for efficiency. This paper shows that synthesizing any single-qubit gate can be done with a constant-depth circuit if you allow certain multi-qubit gates, which is faster than previously thought possible. However, if you only use small-width gates, then the circuit depth must grow slowly as gate accuracy improves. The authors also connect these findings to how quantum circuits decide certain problems, simplifying the study of their complexity.
Open → 2609.34659v1