Limitations of Noisy Reversible Computation
Open accessThe DOI matches its OpenAlex record; 10 of the 10 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Quantum Theory: Concepts and Methods
Peres, A., & Ballentine, L. E. (1995) · American Journal of Physics · doi:10.1119/1.17946 · Cited by 2,561
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284
Two-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069
Modern Quantum Mechanics, Revised Edition
Sakurai, J. J., & Commins, E. D. (1995) · American Journal of Physics · doi:10.1119/1.17781 · Cited by 710
Fault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513 · cited 5×
“Again, we contrast this with the result of [3], which enables two encoded states to remain efficiently distinguishable for time that scales exponentially with system size 4 .”
InfluentialQuantum advantage with noisy shallow circuits
Bravyi, S., Gosset, D., König, R., & Tomamichel, M. (2020) · Nature Physics · doi:10.1038/s41567-020-0948-z · Cited by 144 · cited 1×
“Clifford circuits are also desirable since they propagate Pauli errors nicely making it easier to track errors throughout the circuit, a property which has led to several fault-tolerant implementations of noisy logical Clifford circuits [17, 15, 8, 11].”
Threshold Accuracy for Quantum Computation
Knill, E., Laflamme, R., & Zurek, W. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9610011 · Cited by 99
Spacetime codes of Clifford circuits
Delfosse, N., & Paetznick, A. (2023) · arXiv · doi:10.48550/arxiv.2304.05943 · Cited by 10 · cited 1×
“Clifford circuits are also desirable since they propagate Pauli errors nicely making it easier to track errors throughout the circuit, a property which has led to several fault-tolerant implementations of noisy logical Clifford circuits [17, 15, 8, 11].”
Cited by
Dennis, E., Kitaev, A., Landahl, A., & Preskill, J. (2002) · Journal of Mathematical Physics · doi:10.1063/1.1499754 · Cited by 1,768
Quantum optimization using variational algorithms on near-term quantum devices
Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., Filipp, S., Fuhrer, A., Gambetta, J. M., Ganzhorn, M., et al. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aab822 · Cited by 744
Fault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631
Self-citationQuantum accuracy threshold for concatenated distance-3 code
Aliferis, P., Gottesman, D., & Preskill, J. (2006) · Quantum Information and Computation · doi:10.26421/qic6.2-1 · Cited by 412
An introduction to quantum error correction and fault-tolerant quantum computation
Gottesman, D. (2010) · Proceedings of Symposia in Applied Mathematics · doi:10.1090/psapm/068/2762145 · Cited by 370
Metadata
- Authors
- Aharonov, D., Ben-Or, M., Impagliazzo, R., & Nisan, N.
- Venue
- arXiv (Cornell University)
- Publisher
- Cornell University
- Published
- 1996-11-17
- ISSN
- 2331-8422 (ISSN-L)
- OpenAlex
- W1679863022
- Cited by
- 53
- References
- 10
- Type
- posted content
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Limitations of Noisy Reversible Computation. https://app.cochat.ai/papers/10.4230/lipics.ccc.2026.38
- The paper
- Aharonov, D., Ben-Or, M., Impagliazzo, R., & Nisan, N. (1996). Limitations of Noisy Reversible Computation. arXiv (Cornell University). https://doi.org/10.4230/lipics.ccc.2026.38
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.