A Converse for Fault-tolerant Quantum Computation

Uthirakalyani G1, Anuj K. Nayak2, and Avhishek Chatterjee1

1Department of Electrical Engineering, Indian Institute of Technology Madras, Chennai, India.
2Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, USA.

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


As techniques for fault-tolerant quantum computation keep improving, it is natural to ask: what is the fundamental lower bound on space overhead? In this paper, we obtain a lower bound on the space overhead required for $\epsilon$-accurate implementation of a large class of operations that includes unitary operators. For the practically relevant case of sub-exponential depth and sub-linear gate size, our bound on space overhead is tighter than the known lower bounds. We obtain this bound by connecting fault-tolerant computation with a set of finite blocklength quantum communication problems whose accuracy requirements satisfy a joint constraint. The lower bound on space overhead obtained here leads to a strictly smaller upper bound on the noise threshold for noise that are not degradable. Our bound directly extends to the case where noise at the outputs of a gate are non-i.i.d. but noise across gates are i.i.d.

Quantum fault-tolerance mitigates noise in gate based quantum circuits by careful addition of redundant qubits or ancillas. It is well known that if sufficient number of ancillas are added carefully and the noise in the circuit is small, then quantum fault-tolerance can enable almost accurate quantum computation. Two questions that naturally arise here are: what is the minimum number of ancillas that is necessary for reasonably accurate quantum computation and what is the minimum noise beyond which fault-tolerance is not useful? In this paper, we address these questions by establishing a connection between quantum computation and finite resource (block-length) quantum communication. Our answers (bounds) to these questions are non-asymptotic and tighter than existing results, and are applicable to a broad class of noise models including correlated noise at a gate.

► BibTeX data

► References

[1] Dorit Aharonov and Michael Ben-Or. "Fault-tolerant quantum computation with constant error". In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 176–188, 1997.

[2] Howard Barnum, Emanuel Knill, and Michael A. Nielsen. "On quantum fidelities and channel capacities". IEEE Transactions on Information Theory, 46(4):1317–1329, 2000.

[3] Paul Benioff. "The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines". Journal of Statistical Physics, 22(5):563–591, 1980.

[4] Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, and Falk Unger. "New limits on fault-tolerant quantum computation". In Proceedings of the 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 411–419. IEEE, 2006.

[5] David Deutsch. "Quantum theory, the Church–Turing principle and the universal quantum computer". Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985.

[6] David Deutsch and Richard Jozsa. "Rapid solution of problems by quantum computation". Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439(1907):553–558, 1992.

[7] William S Evans and Leonard J Schulman. "Signal propagation and noisy circuits". IEEE Transactions on Information Theory, 45(7):2367–2373, 1999.

[8] Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. "Constant overhead quantum fault tolerance with quantum expander codes". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 2018.

[9] Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi. "A lower bound on the space overhead of fault-tolerant quantum computation". In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), 2022.

[10] Daniel Gottesman. "Fault-tolerant quantum computation with constant overhead". Quantum Information & Computation, 14(15-16):1338–1372, 2014.

[11] Aram W Harrow and Michael A Nielsen. "Robustness of quantum gates in the presence of noise". Physical Review A, 68(1):012308, 2003.

[12] Julia Kempe, Oded Regev, Falk Unger, and Ronald de Wolf. "Upper bounds on the noise threshold for fault-tolerant quantum computing". In International Colloquium on Automata, Languages, and Programming, pages 845–856. Springer, 2008.

[13] Sumeet Khatri and Mark M Wilde. "Principles of quantum communication theory: A modern approach". arXiv preprint arXiv:2011.04672, 2020.

[14] A Yu Kitaev. "Quantum computations: algorithms and error correction". Russian Mathematical Surveys, 52(6):1191, 1997.

[15] Michael A. Nielsen and Isaac L. Chuang. "Quantum Computation and Quantum Information: 10th Anniversary Edition". Cambridge University Press, 2010.

[16] Nicholas Pippenger. "Reliable computation by formulas in the presence of noise". IEEE Transactions on Information Theory, 34(2):194–197, 1988.

[17] Alexander A Razborov. "An upper bound on the threshold quantum decoherence rate". Quantum Information & Computation, 4(3):222–228, 2004.

[18] Peter W Shor. "Fault-tolerant quantum computation". In Proceedings of 37th Conference on Foundations of Computer Science, pages 56–65. IEEE, 1996.

[19] Andrew M Steane. "Error correcting codes in quantum theory". Physical Review Letters, 77(5):793, 1996.

[20] Shashank Virmani, Susana F Huelga, and Martin B Plenio. "Classical simulability, entanglement breaking, and quantum computation thresholds". Physical Review A, 71(4):042328, 2005.

Cited by

[1] Uthirakalyani G., Anuj K. Nayak, Avhishek Chatterjee, and Lav R. Varshney, "Limits of fault tolerance on resource-constrained quantum circuits for classical problems", Physical Review A 108 5, 052425 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-15 09:28:46) and SAO/NASA ADS (last updated successfully 2024-04-15 09:28:47). The list may be incomplete as not all publishers provide suitable and complete citation data.