Classical simulability, entanglement breaking, and quantum computation thresholds
Open accessAbstract
We investigate the amount of noise required to turn a universal quantum gate set into one that can be efficiently modeled classically. This question is useful for providing upper bounds on fault-tolerant thresholds, and for understanding the nature of the quantum-classical computational transition. We refine some previously known upper bounds using two different strategies. The first one involves the introduction of bientangling operations, a class of classically simulable machines that can generate at most bipartite entanglement. Using this class we show that it is possible to sharpen previously obtained upper bounds in certain cases. As an example, we show that under depolarizing noise on the controlled-NOT gate, the previously known upper bound of 74% can be sharpened to around 67%. Another interesting consequence is that measurement-based schemes cannot work using only two-qubit nondegenerate projections. In the second strand of the work we utilize the Gottesman-Knill theorem on the classically efficient simulation of Clifford group operations. The bounds attained using this approach for the $\ensuremath{\pi}∕8$ gate can be as low as 15% for general single-gate noise, and 30% for dephasing noise.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The effect of disorder in both the decay rate and the asymptotic saturation value can, in general, be understood from established techniques such as Fermi Golden's rule, and random matrices.
“The effect of disorder in both the decay rate and the asymptotic saturation value can, in general, be understood from established techniques such as Fermi Golden's rule, and random matrices [191].”
From Can one trust quantum simulators? (2012) · cites this paper as [191]
For the regimes of disorder studied, the time dependent fidelity decays with a rate roughly proportional to the strength of the disorder squared.
“For the regimes of disorder that we studied, we observe that the time dependent fidelity decays with a rate roughly proportional to the strength of the disorder squared (typical of a Fermi golden rule [191]).”
From Can one trust quantum simulators? (2012) · cites this paper as [191]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Three qubits can be entangled in two inequivalent ways
Dür, W., Vidal, G., & Cirac, J. I. (2000) · Physical Review A · doi:10.1103/physreva.62.062314 · Cited by 3,384 · see citing works
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368 · see citing works
Gottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860 · see citing works
Linear transformations which preserve trace and positive semidefiniteness of operators
Jamiołkowski, A. (1972) · Reports on Mathematical Physics · doi:10.1016/0034-4877(72)90011-0 · Cited by 1,512 · see citing works
Vidal, G., & Tarrach, R. (1999) · Physical Review A · doi:10.1103/physreva.59.141 · Cited by 601 · see citing works
Classical simulation of noninteracting-fermion quantum circuits
Terhal, B. M., & DiVincenzo, D. P. (2002) · Physical Review A · doi:10.1103/physreva.65.032325 · Cited by 329 · see citing works
Bound on distillable entanglement
Rains, E. M. (1999) · Physical Review A · doi:10.1103/physreva.60.179 · Cited by 326 · see citing works
Quantum Circuits That Can Be Simulated Classically in Polynomial Time
Valiant, L. G. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539700377025 · Cited by 311 · see citing works
Quantum Information and Quantum Computation
Divincenzo, D. P. (2014) · Cited by 264 · see citing works
Entangling Operations and Their Implementation Using a Small Amount of Entanglement
Cirac, J. I., Dür, W., Kraus, B., & Lewenstein, M. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.544 · Cited by 244 · see citing works
Holevo, A. S. (1998) · Russian Mathematical Surveys · doi:10.1070/rm1998v053n06abeh000091 · Cited by 224 · see citing works
Rigorous treatment of distillable entanglement
Rains, E. M. (1999) · Physical Review A · doi:10.1103/physreva.60.173 · Cited by 216 · see citing works
Quantum computation by measurement and quantum memory
Nielsen, M. A. (2003) · Physics Letters A · doi:10.1016/s0375-9601(02)01803-0 · Cited by 210 · see citing works
Robustness of quantum gates in the presence of noise
Harrow, A. W., & Nielsen, M. A. (2003) · Physical Review A · doi:10.1103/physreva.68.012308 · Cited by 164 · see citing works
Generalized robustness of entanglement
Steiner, M. (2003) · Physical Review A · doi:10.1103/physreva.67.054305 · Cited by 164 · see citing works
QUANTUM COMPUTATION BY MEASUREMENTS
Leung, D. (2004) · International Journal of Quantum Information · doi:10.1142/s0219749904000055 · Cited by 123 · see citing works
Dynamical description of quantum computing: Generic nonlocality of quantum noise
Alicki, R., Horodecki, M., Horodecki, P., & Horodecki, R. (2002) · Physical Review A · doi:10.1103/physreva.65.062101 · Cited by 111 · see citing works
Quantum to classical phase transition in noisy quantum computers
Aharonov, D. (2000) · Physical Review A · doi:10.1103/physreva.62.062311 · Cited by 108 · see citing works
Fermionic Linear Optics and MatchgatesPreprint
Knill, E. H. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0108033 · Cited by 95 · see citing works
Measurement-Based Quantum Turing Machines and their UniversalityPreprint
Perdrix, S., & Jorrand, P. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0404146 · Cited by 25 · see citing works
Polynomial Simulations of Decohered Quantum ComputersPreprint
Aharonov, D., & Ben-Or, M. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9611029 · Cited by 12 · see citing works
Universal quantum computation with two- and three-qubit projective measurementsPreprint
Fenner, S., & Zhang, Y. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0111077 · Cited by 12 · see citing works
Flagged first, then by citations
Research works printed but not linked: 9
- ͓2͔ R. Jozsa and N. Linden, e-print quant-ph/0201143; · arXiv
- D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan, e-print quant-ph/9611028. See also D. Aharonov, Phys. Rev. A 62, 062311 ͑2000͒ for related work. · arXiv
- ͓5͔ A. Razborov, e-print quant-ph/0310136. · arXiv
- ͓6͔ S. Bravyi and A. Kitaev, e-print quant-ph/0403025. · arXiv
- ͓7͔ B. W. Reichardt, e-print quant-ph/0411036. · arXiv
- ͓9͔ D. Gottesman, Ph.D. thesis, California Institute of Technology, 1997. For recent improvements see also S. Aaronson and D. Gottesman, e-print quant-ph/0406196. · arXiv
- ͓20͔ D. Aharanov and M. Ben-Or, e-print quant-ph/9906129; · arXiv
- B. M. Terhal and G. Burkard, e-print quant-ph/0402104; · arXiv
- M. Nielsen and C. M. Dawson, e-print quant-ph/0405134. · arXiv
Cited by
Sorted by citations
Horodecki, R., Horodecki, P., Horodecki, M., & Horodecki, K. (2009) · Reviews of Modern Physics · doi:10.1103/revmodphys.81.865 · Cited by 10,118 · see citing works
Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing
Howard, M., & Campbell, E. T. (2017) · Physical Review Letters · doi:10.1103/physrevlett.118.090501 · Cited by 390 · see citing works
Can one trust quantum simulators?
Hauke, P., Cucchietti, F. M., Tagliacozzo, L., Deutsch, I., & Lewenstein, M. (2012) · Reports on Progress in Physics · doi:10.1088/0034-4885/75/8/082401 · Cited by 315 · see citing works
Achieving quantum supremacy with sparse and noisy commuting quantum computations
Bremner, M. J., Montanaro, A., & Shepherd, D. J. (2017) · Quantum · doi:10.22331/q-2017-04-25-8 · Cited by 191 · see citing works
Quantum Universality from Magic States Distillation Applied to CSS Codes
Reichardt, B. W. (2005) · Quantum Information Processing · doi:10.1007/s11128-005-7654-8 · Cited by 143 · see citing works
Efficient Classical Simulation of Random Shallow 2D Quantum Circuits
Napp, J. C., Placa, R. L. L., Dalzell, A. M., Brandão, F. G. S. L., & Harrow, A. W. (2022) · Physical Review X · doi:10.1103/physrevx.12.021021 · Cited by 140 · see citing works
An Introduction to Entanglement Theory
Plenio, M. B., & Virmani, S. (2014) · Springer eBooks · doi:10.1007/978-3-319-04063-9_8 · Cited by 126 · see citing works
Self-citationRobustness of Magic and Symmetries of the Stabiliser Polytope
Heinrich, M., & Gross, D. (2019) · Quantum · doi:10.22331/q-2019-04-08-132 · Cited by 114 · see citing works
Qudit versions of the qubit π/8 gate
Howard, M., & Vala, J. (2012) · Physical Review A · doi:10.1103/physreva.86.022316 · Cited by 109 · see citing works
A Reversible Theory of Entanglement and its Relation to the Second Law
Brandão, F. G. S. L., & Plenio, M. B. (2010) · Communications in Mathematical Physics · doi:10.1007/s00220-010-1003-1 · Cited by 102 · see citing works
Self-citationEntanglement of multiparty-stabilizer, symmetric, and antisymmetric states
Hayashi, M., Markham, D., Murao, M., Owari, M., & Virmani, S. (2008) · Physical Review A · doi:10.1103/physreva.77.012104 · Cited by 91 · see citing works
Self-citationRobustness of Magic and Symmetries of the Stabiliser Polytope
Heinrich, M., & Gross, D. (2019) · Kölner Universitäts PublikationsServer (Universität zu Köln) · Cited by 73 · see citing works
New Limits on Fault-Tolerant Quantum Computation
Buhrman, H., Cleve, R., Laurent, M., Linden, N., Schrijver, A., & Unger, F. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.50 · Cited by 60 · see citing works
Quantum simulation of interacting high-dimensional systems: The influence of noise
Dür, W., Bremner, M. J., & Briegel, H. J. (2008) · Physical Review A · doi:10.1103/physreva.78.052325 · Cited by 41 · see citing works
A reversible theory of entanglement and its relation to the second law
Brandão, F., & Plenio, M. B. (2010) · UCL Discovery (University College London) · Cited by 35 · see citing works
Self-citationQuantum universality by state distillationPreprint
Reichardt, B. W. (2009) · doi:10.5555/2012098.2012105 · Cited by 30 · see citing works
Error-detection-based quantum fault tolerance against discrete Pauli noisePreprint
Reichardt, B. W. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0612004 · Cited by 32 · see citing works
Tight Noise Thresholds for Quantum Computation with Perfect Stabilizer Operations
van Dam, W., & Howard, M. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.170504 · Cited by 25 · see citing works
Macchiavello, C., & Rossi, M. A. C. (2013) · Physical Review A · doi:10.1103/physreva.88.042335 · Cited by 24 · see citing works
Quantum universality by state distillation
Reichardt, B. W. (2009) · Quantum Information and Computation · doi:10.26421/qic9.11-12-7 · Cited by 24 · see citing works
Quantum simulation of partially distinguishable boson sampling
Moylett, A. E., & Turner, P. S. (2018) · Physical Review A · doi:10.1103/physreva.97.062329 · Cited by 22 · see citing works
Multipartite entangled states, symmetric matrices and error-correcting codes
Feng, K., Jin, L., Xing, C., & Yuan, C. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2700866 · Cited by 22 · see citing works
Rudolph, T., & Virmani, S. (2005) · New Journal of Physics · doi:10.1088/1367-2630/7/1/228 · Cited by 19 · see citing works
Self-citationUpper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing
Kempe, J., Regev, O., Unger, F., & de Wolf, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_69 · Cited by 16 · see citing works
Howard, M., & Vala, J. (2012) · Physical Review A · doi:10.1103/physreva.85.022304 · Cited by 16 · see citing works
Spectral properties versus magic generation in T -doped random Clifford circuits
Szombathy, D., Valli, A., Moca, C. P., Asbóth, J. K., Farkas, L., Rakovszky, T., & Zaránd, G. (2025) · Physical Review Research · doi:10.1103/557f-6tpb · Cited by 15 · see citing works
Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers
Plenio, M. B., & Virmani, S. (2010) · OPen Access Repositorium der Universität Ulm (OPARU) (Ulm University) · doi:10.18725/oparu-46600 · Cited by 15 · see citing works
Self-citationQuantum universality by distilling certain one- and two-qubit states with stabilizer operationsPreprint
Reichardt, B. W. (2006) · arXiv (Cornell University) · Cited by 13 · see citing works
Transitions in Computational Complexity of Continuous-Time Local Open Quantum Dynamics
Trivedi, R., & Cirac, J. I. (2022) · Physical Review Letters · doi:10.1103/physrevlett.129.260405 · Cited by 10 · see citing works
Generalized state spaces and nonlocality in fault-tolerant quantum-computing schemes
Ratanje, N., & Virmani, S. (2011) · Physical Review A · doi:10.1103/physreva.83.032309 · Cited by 11 · see citing works
Self-citationUpper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers
Plenio, M. B., & Virmani, S. (2010) · New Journal of Physics · doi:10.1088/1367-2630/12/3/033012 · Cited by 15 · see citing works
Self-citationShutty, N., Wootters, M. K., & Hayden, P. M. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00028 · Cited by 6 · see citing works
Upper bounds on the noise threshold for fault-tolerant quantum computing
Kempe, J., Regev, O., Unger, F., & de Wolf, R. (2010) · Quantum Information and Computation · doi:10.26421/qic10.5-6-1 · Cited by 6 · see citing works
Bounding fault-tolerant thresholds for purification and quantum computation
Kay, A. (2008) · Physical Review A · doi:10.1103/physreva.77.052319 · Cited by 5 · see citing works
Ares, L., Pinske, J., Hinrichs, B., Kolb, M., & Sperling, J. (2025) · Physical Review A · doi:10.1103/hcj7-8zlg · Cited by 5 · see citing works
Separability Lindblad equation for dynamical open-system entanglement
Pinske, J., Ares, L., Hinrichs, B., Kolb, M., & Sperling, J. (2025) · Physical Review A · doi:10.1103/kd3b-bfxq · Cited by 5 · see citing works
A Review of Formal Methods in Quantum-Circuit Verification
Govindankutty, A. (2026) · Electronics · doi:10.3390/electronics15051125 · Cited by 4 · see citing works
Unbreakable and breakable quantum censorship
Pinske, J., & Sperling, J. (2024) · Physical Review A · doi:10.1103/physreva.109.052408 · Cited by 4 · see citing works
van Dam, W. (2007) · Nature Physics · doi:10.1038/nphys585 · Cited by 4 · see citing works
A Lower Bound on the Space Overhead of Fault-Tolerant Quantum ComputationPreprint
Fawzi, O., Müller‐Hermes, A., & Shayeghi, A. (2022) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2022.68 · Cited by 7 · see citing works
Constructions of k-Uniform States in Heterogeneous Systems
Feng, K., Jin, L., Xing, C., & Yuan, C. (2023) · IEEE Transactions on Information Theory · doi:10.1109/tit.2023.3282221 · Cited by 3 · see citing works
Wigner’s theorem for stabilizer states and quantum designs
Obst, V., Heimendahl, A., Singal, T., & Gross, D. (2024) · Journal of Mathematical Physics · doi:10.1063/5.0222546 · Cited by 3 · see citing works
Detection methods to rule out completely co-positive and bi-entangling operations
Macchiavello, C., & Rossi, M. A. C. (2013) · Journal of Physics Conference Series · doi:10.1088/1742-6596/470/1/012005 · Cited by 3 · see citing works
A Converse for Fault-tolerant Quantum Computation
Uthirakalyani, G., Nayak, A. K., & Chatterjee, A. (2023) · Quantum · doi:10.22331/q-2023-08-16-1087 · Cited by 2 · see citing works
Generalised versions of separable decompositions applicable to bipartite entangled quantum states
Anwar, H., Jevtic, S., Rudolph, O., & Virmani, S. (2019) · New Journal of Physics · doi:10.1088/1367-2630/ab3adc · Cited by 1 · see citing works
Self-citationFault-tolerance in two-dimensional topological systems
Anderson, J. T. (2012) · UNM’s Digital Repository (University of New Mexico)
Noise in quantum and classical computation & non-locality
Unger, F. (2008) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands
Separability of Solutions to a Schrödinger Equation
Wang, W., Cao, H., Guo, Z., & Yu, B. (2014) · Communications in Theoretical Physics · doi:10.1088/0253-6102/62/2/06
Efficient classical simulation of cluster state quantum circuits with alternative inputs
Atallah, S., Garn, M., Jevtic, S., Tao, Y., & Virmani, S. (2024) · Quantum · doi:10.22331/q-2024-02-06-1243
Self-citationEntangling power of nonentangling channels
Pinske, J., Sperling, J., & Mølmer, K. (2026) · Physical Review A · doi:10.1103/vy93-dnc8
Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
Cichy, S., Faehrmann, P. K., Bittel, L., Eisert, J., & Pashayan, H. (2026) · Physical Review A · doi:10.1103/jj2r-y777 · Cited by 1 · see citing works
- Authors
- Virmani, S., Huelga, S. F., & Plenio, M. B.
- Affiliations
- University of Hertfordshire (GB)
- Imperial College London (GB)
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2005-04-19
- Volume
- 71
- Issue
- 4
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2090829264
- Cited by
- 51
- References
- 18
- Citations by year
- 2026: 3 · 2025: 3 · 2024: 3 · 2023: 2 · 2022: 3 · 2020: 1 · 2019: 3 · 2018: 1 · 2017: 3 · 2014: 2 · 2013: 2 · 2012: 4
- FWCI
- 3.86
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Spiral (Imperial College London) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Leverhulme Trust
- Nuffield Foundation
- Royal Society
- Royal Commission for the Exhibition of 1851
- Deutscher Akademischer Austauschdienst (DAAD 19-02)
- Engineering and Physical Sciences Research Council
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- classical simulability, entanglement breaking, fault-tolerant threshold, quantum-to-classical transition, depolarizing noise, CNOT gate, measurement-based quantum computation, Gottesman-Knill theorem, Clifford group, dephasing noise, universal quantum gate set
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
