Limitations of Noisy Reversible Computation
arXiv:quant-ph/9611028
Abstract
Noisy computation and reversible computation have been studied separately, and it is known that they are as powerful as unrestricted computation. We study the case where both noise and reversibility are combined and show that the combined model is weaker than unrestricted computation. In our noisy reversible circuits, each wire is flipped with probability p each time step, and all the inputs to the circuit are present in time 0. We prove that any noisy reversible circuit must have size exponential in its depth in order to compute a function with high probability. This is tight as we show that any circuit can be converted into a noise-resistant reversible one with a blow up in size which is exponential in the depth. This establishes that noisy reversible computation has the power of the complexity class NC^1. We extend this to quantum circuits(QC). We prove that any noisy QC which is not worthless, and for which all inputs are present at time 0, must have size exponential in its depth. (This high-lights the fact that fault tolerant QC must use a constant supply of inputs all the time.) For the lower bound, we show that quasi-polynomial noisy QC are at least powerful as logarithmic depth QC, (or QNC^1). Making these bounds tight is left open in the quantum case.
13 pages
References in corpus (2)
Cited by in corpus (29)
- Topological quantum memory
- Efficient Distributed Quantum Computing
- Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
- Quantum accuracy threshold for concatenated distance-3 codes
- Quantum Computation
- Hardware for Dynamic Quantum Computing
- Introduction to Quantum Algorithms
- Entropic proofs of Singleton bounds for quantum error-correcting codes
- Classical algorithm for simulating experimental Gaussian boson sampling
- Relative Entropy Convergence for Depolarizing Channels
- How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation
- Noise and the frontier of quantum supremacy
- Level Reduction and the Quantum Threshold Theorem
- Fault Tolerant Quantum Computation with Constant Error
- Error-detection-based quantum fault tolerance against discrete Pauli noise
- Entropy Production of Doubly Stochastic Quantum Channels
- Achieving fault tolerance against amplitude-damping noise
- Quantum Computers: Noise Propagation and Adversarial Noise Models
- Optimal Quantum Circuits for Nearest-Neighbor Architectures
- A game of quantum advantage: linking verification and simulation
- Detrimental Decoherence
- A lower bound on the space overhead of fault-tolerant quantum computation
- Quantitative Treatment of Decoherence
- An introduction to reliable quantum computation
- Limitations of Noisy Quantum Devices in Computational and Entangling Power
- Sufficient condition on noise correlations for scalable quantum computing
- How Quantum Computers Can Fail
- Thoughts on Noise and Quantum Computation
- The robustness of magic state distillation against errors in Clifford gates