dorsal/arxiv
View SchemaLimitations of Noisy Reversible Computation
| Authors | D. Aharonov, M. Ben-Or, R. Impagliazzo, N. Nisan |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9611028 |
| URL | https://arxiv.org/abs/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.
{
"annotation_id": "feb083b4-a661-4048-ba25-b38166e799c9",
"date_created": "2026-03-02T18:02:37.966000Z",
"date_modified": "2026-03-02T18:02:37.966000Z",
"file_hash": "e7467c1ee4b9cbff1a830d64fecce8a815265702f84065d04938e42b98215fd1",
"private": false,
"record": {
"abstract": "Noisy computation and reversible computation have been studied separately,\nand it is known that they are as powerful as unrestricted computation. We study\nthe case where both noise and reversibility are combined and show that the\ncombined model is weaker than unrestricted computation. In our noisy reversible\ncircuits, each wire is flipped with probability p each time step, and all the\ninputs to the circuit are present in time 0. We prove that any noisy reversible\ncircuit must have size exponential in its depth in order to compute a function\nwith high probability. This is tight as we show that any circuit can be\nconverted into a noise-resistant reversible one with a blow up in size which is\nexponential in the depth. This establishes that noisy reversible computation\nhas the power of the complexity class NC^1.\n We extend this to quantum circuits(QC). We prove that any noisy QC which is\nnot worthless, and for which all inputs are present at time 0, must have size\nexponential in its depth. (This high-lights the fact that fault tolerant QC\nmust use a constant supply of inputs all the time.) For the lower bound, we\nshow that quasi-polynomial noisy QC are at least powerful as logarithmic depth\nQC, (or QNC^1). Making these bounds tight is left open in the quantum case.",
"arxiv_id": "quant-ph/9611028",
"authors": [
"D. Aharonov",
"M. Ben-Or",
"R. Impagliazzo",
"N. Nisan"
],
"categories": [
"quant-ph"
],
"title": "Limitations of Noisy Reversible Computation",
"url": "https://arxiv.org/abs/quant-ph/9611028"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e9003709-19b9-4202-b359-1622622fb16e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}