A Converse for Fault-tolerant Quantum Computation

Uthirakalyani G; Anuj K. Nayak; Avhishek Chatterjee

doi:10.22331/q-2023-08-16-1087

A Converse for Fault-tolerant Quantum Computation

Uthirakalyani G¹, Anuj K. Nayak², and Avhishek Chatterjee¹

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

Published:	2023-08-16, volume 7, page 1087
Eprint:	arXiv:2211.00697v4
Doi:	https://doi.org/10.22331/q-2023-08-16-1087
Citation:	Quantum 7, 1087 (2023).

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

Abstract

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.

Popular summary

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

@article{G2023conversefault,
  doi = {10.22331/q-2023-08-16-1087},
  url = {https://doi.org/10.22331/q-2023-08-16-1087},
  title = {A {C}onverse for {F}ault-tolerant {Q}uantum {C}omputation},
  author = {G, Uthirakalyani and Nayak, Anuj K. and Chatterjee, Avhishek},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1087},
  month = aug,
  year = {2023}
}

► 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.
https://doi.org/10.1145/258533.258579

[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.
https://doi.org/10.1109/18.850671

[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.
https://doi.org/10.1007/BF01011339

[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.
https://doi.org/10.1109/FOCS.2006.50

[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.
https://doi.org/10.1098/rspa.1985.0070

[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.
https://doi.org/10.1098/rspa.1992.0167

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

[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.
https://doi.org/10.1109/FOCS.2018.00076

[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.
https://doi.org/10.48550/arXiv.2202.00119

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

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

[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.
https://doi.org/10.1007/978-3-540-70575-8_69

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

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

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

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

[17] Alexander A Razborov. "An upper bound on the threshold quantum decoherence rate". Quantum Information & Computation, 4(3):222–228, 2004.
https://doi.org/10.48550/arXiv.quant-ph/0310136
arXiv:quant-ph/0310136

[18] Peter W Shor. "Fault-tolerant quantum computation". In Proceedings of 37th Conference on Foundations of Computer Science, pages 56–65. IEEE, 1996.
https://doi.org/10.1109/SFCS.1996.548464

[19] Andrew M Steane. "Error correcting codes in quantum theory". Physical Review Letters, 77(5):793, 1996.
https://doi.org/10.1103/PhysRevLett.77.793

[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.
https://doi.org/10.1103/PhysRevA.71.042328

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", arXiv:2301.02158, (2023).

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.