Quantum Circuits with Unbounded Fan-out
arXiv:quant-ph/0208043 · doi:10.4086/toc.2005.v001a005
Abstract
We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNCf^0) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[q], and Counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetical operations, phase estimation, and the quantum Fourier transform with arbitrary moduli can also be approximated in constant depth.
20 pages, 9 figures, STACS'2003. v3: rewritten from scratch, new co-author, everything put into constant depth (including quantum Fourier transform). v4: polished a lot
References in corpus (2)
Cited by in corpus (51)
- Instantaneous Quantum Computation
- Simulating chemistry efficiently on fault-tolerant quantum computers
- Hierarchy of topological order from finite-depth unitaries, measurement and feedforward
- Efficient Long-Range Entanglement using Dynamic Circuits
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- Enhancing Generative Models via Quantum Correlations
- Asymmetric blockade and multi-qubit gates via dipole-dipole interactions
- Quantum Fourier Transform using Dynamic Circuits
- Extensive characterization of a family of efficient three-qubit gates at the coherence limit
- Optimal State Transfer and Entanglement Generation in Power-law Interacting Systems
- Approximating many-body quantum states with quantum circuits and measurements
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- Interpretable Quantum Advantage in Neural Sequence Learning
- State preparation by shallow circuits using feed forward
- Measurement-Based Long-Range Entangling Gates in Constant Depth
- Completely positive classical structures and sequentializable quantum protocols
- Compact quantum algorithms for time-dependent differential equations
- Depth-efficient proofs of quantumness
- An analysis of the trade-off between spatial and temporal resources for measurement-based quantum computation
- Low-depth unitary quantum circuits for dualities in one-dimensional quantum lattice models
- On the Need for Large Quantum Depth
- Unitary Entanglement Construction in Hierarchical Networks
- Distributed Quantum Computing: Applications and Challenges
- Measurement-based infused circuits for variational quantum eigensolvers
- Parallel Quantum Algorithm for Hamiltonian Simulation
- Power of Uninitialized Qubits in Shallow Quantum Circuits
- Robust sparse IQP sampling in constant depth
- Computational Distinguishability of Quantum Channels
- Quantum Complexity for Discrete Logarithms and Related Problems
- Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
- Efficient eigenvalue determination for arbitrary Pauli products based on generalized spin-spin interactions
- Quantum Complexity: restrictions on algorithms and architectures
- Realizing Lattice Surgery on Two Distance-Three Repetition Codes with Superconducting Qubits
- Distinguishing Short Quantum Computations
- Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
- Realization of Constant-Depth Fan-Out with Real-Time Feedforward on a Superconducting Quantum Processor
- Unconditional quantum magic advantage in shallow circuit computation
- Reducing Circuit Depth in Quantum State Preparation for Quantum Simulation Using Measurements and Feedforward
- Possibilistic simulation of quantum circuits by classical circuits
- Quantum Lower Bounds for Fanout
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
- Reducing circuit depth with qubitwise diagonalization
- Achieving computational gains with quantum error-correction primitives: Generation of long-range entanglement enhanced by error detection
- 3XOR Games with Perfect Commuting Operator Strategies Have Perfect Tensor Product Strategies and are Decidable in Polynomial Time
- Efficient Generation of Multi-partite Entanglement between Non-local Superconducting Qubits using Classical Feedback
- Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
- Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions
- Universal Quantum Circuits
- Quantum Circuit Design for Decoded Quantum Interferometry
- Catalytic -rotations in constant -depth
- Linear optical fan-out gates using fewer ancillary single photons with enhanced success probability