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.

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.

[embedded content]

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}<br /> }

► 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-08-16 16:51:57). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch Crossref cited-by data during last attempt 2023-08-16 16:51:56: Could not fetch cited-by data for 10.22331/q-2023-08-16-1087 from Crossref. This is normal if the DOI was registered recently.

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.

Generative Data Intelligence

A Converse for Fault-tolerant Quantum Computation

Abstract

Popular summary

► BibTeX data

► References

Cited by

New Law In Oklahoma Safeguards Citizens’ Rights To Own Bitcoin – CryptoInfoNet

Bitget’s New ‘Trade to Mine’ Promotion Lets Traders Keep All Trading Fees

Latest Intelligence

Wondra: Redefining The Blueprint For Metaverse 2.0 – CryptoInfoNet

Expert Says Bitcoin Price Has Topped And Is In Exponential Decay, Why This Is Not A Bad Thing

BlockDAG Excels With $1 A Day Proposition With X1 Mobile Mining App, Surpassing ETH & TRON’s Market Enthusiasm

Whales Buy 237B SHIB, Ethereum Classic Rises, Analysts Pick New Gaming Token for Massive Gains

Top Coinbase Lawyer Asserts That Ethereum Is a Commodity As Consensys Launches ETH-Related Lawsuit Against SEC – The Daily Hodl

JPMorgan Chase and Bank of America Suffer $4,500,000,000 in Losses As ‘Unrecoverable Debt’ Soars: Report – The Daily Hodl

Chat with us