Quantum Circuits: Fanout, Parity, and Counting
read the original abstract
We propose definitions of QAC^0, the quantum analog of the classical class AC^0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC^0[q], where n-ary Mod-q gates are also allowed. We show that it is possible to make a `cat' state on n qubits in constant depth if and only if we can construct a parity or Mod-2 gate in constant depth; therefore, any circuit class that can fan out a qubit to n copies in constant depth also includes QACC^0[2]. In addition, we prove the somewhat surprising result that parity or fanout allows us to construct Mod-q gates in constant depth for any q, so QACC^0[2] = QACC^0. Since ACC^0[p] != ACC^0[q] whenever p and q are mutually prime, QACC^0[2] is strictly more powerful than its classical counterpart, as is QAC^0 when fanout is allowed.
This paper has not been read by Pith yet.
Forward citations
Cited by 6 Pith papers
-
Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
A fermionic permutation protocol on 2D nearest-neighbor grids achieves the optimal O(sqrt(N)) depth with O(N sqrt(N)) gates, no ancillas, and extends to Jordan-Wigner, Bravyi-Kitaev, and Parity encodings via Hilbert-c...
-
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
The 2D HLF problem lies in QNC^0 but not in AC^0, with an exponential average-case correlation lower bound against AC^0 circuits.
-
(Non-)Traversable Quantum Phase Transitions
Proposes classifying quantum phase transitions by whether they are traversable via finite counterdiabatic driving protocols or nontraversable due to infinite geometric distance in the ground-state manifold.
-
Quantum Fanout Gates in Constant Depth via Resonance Engineering
Resonance engineering with Jaynes-Cummings interactions realizes constant-depth n-qubit fanout gates with linear error scaling.
-
Efficient Simulation of Sparse, Non-Local Fermion Models
An auxiliary-fermion encoding removes Jordan-Wigner strings for sparse non-local fermion models, achieving asymptotically optimal Trotter circuit depth on qubits after one-time state preparation.
-
Space-Time Tradeoffs of Pauli-Based Computation in Distributed qLDPC Architectures
Large qLDPC blocks in distributed quantum computing enable Pauli-based computation to run up to 10x faster than surface codes for optimization algorithms by using spare nodes to bypass serialization bottlenecks.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.