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.
 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.
 Howard Barnum, Emanuel Knill, and Michael A. Nielsen. "On quantum fidelities and channel capacities". IEEE Transactions on Information Theory, 46(4):1317–1329, 2000.
 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.
 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.
 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.
 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.
 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.
 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.
 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.
 Sumeet Khatri and Mark M Wilde. "Principles of quantum communication theory: A modern approach". arXiv preprint arXiv:2011.04672, 2020.
 A Yu Kitaev. "Quantum computations: algorithms and error correction". Russian Mathematical Surveys, 52(6):1191, 1997.
 Alexander A Razborov. "An upper bound on the threshold quantum decoherence rate". Quantum Information & Computation, 4(3):222–228, 2004.
 Shashank Virmani, Susana F Huelga, and Martin B Plenio. "Classical simulability, entanglement breaking, and quantum computation thresholds". Physical Review A, 71(4):042328, 2005.
The above citations are from SAO/NASA ADS (last updated successfully 2023-09-22 10:07:29). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2023-09-22 10:07:28).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.