REVIEW 6 cited by
Quantum Circuits: Fanout, Parity, and Counting
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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.
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.
-
Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
New quantum circuits for Hamming weight and symmetric Boolean functions: O(log n) depth with sublinear ancillas (all-to-all), optimal Θ(√n) depth with O(log^2 n) ancillas (2D), and constant depth with O(n^{1+ε}) ancil...
-
(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.
-
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.
-
Optimizing sparse quantum state preparation with measurement and feedforward
Two new sparse quantum state preparation algorithms achieve O(n log d) and O(n) circuit depth with O(d) ancilla qubits and O(dn) size.
Discussion (0). Continue with ORCID to comment.