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.
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]
[embedded content]
Popular summary
► 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.
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Automotive / EVs, Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- ChartPrime. Elevate your Trading Game with ChartPrime. Access Here.
- BlockOffsets. Modernizing Environmental Offset Ownership. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-08-16-1087/
- :is
- :not
- :where
- 1
- 10
- 10th
- 11
- 12
- 13
- 14
- 15%
- 16
- 17
- 19
- 1985
- 1996
- 1999
- 20
- 2000
- 2005
- 2006
- 2008
- 2011
- 2014
- 2018
- 2020
- 2022
- 2023
- 50
- 51
- 7
- 77
- 8
- 9
- a
- above
- ABSTRACT
- access
- accuracy
- accurate
- ACM
- across
- added
- addition
- address
- affiliations
- Alexander
- algorithms
- All
- an
- and
- Andrew
- Anniversary
- annual
- answers
- Anthony
- applicable
- approach
- ARE
- arise
- AS
- At
- Aug
- author
- authors
- b
- based
- BE
- between
- Beyond
- bound
- bounds
- Break
- Breaking
- broad
- but
- by
- cambridge
- CAN
- capacities
- careful
- carefully
- case
- Channel
- class
- codes
- comment
- Commons
- Communication
- complete
- computation
- computations
- computer
- Computer Engineering
- computer science
- computers
- computing
- Conference
- Connecting
- connection
- constant
- content
- copyright
- correlated
- could
- Daniel
- data
- David
- Den
- depth
- directly
- discuss
- during
- edition
- electrical engineering
- embedded
- enable
- Engineering
- error
- establishing
- Ether (ETH)
- existing
- extends
- For
- Foundations
- from
- fundamental
- Gates
- harvard
- here
- holders
- howard
- HTTPS
- i
- IEEE
- if
- illinois
- implementation
- improving
- in
- includes
- Including
- india
- Indian
- information
- innovations
- Institute
- institutions
- interesting
- International
- IT
- JavaScript
- joint
- journal
- Keep
- known
- Languages
- large
- Last
- Leads
- Leave
- leonard
- License
- limits
- List
- London
- lower
- Machines
- mark
- Martin
- mathematical
- May..
- mechanical
- Michael
- minimum
- model
- models
- Modern
- Month
- Natural
- necessary
- New
- nicholas
- Noah
- Noise
- normal
- number
- obtain
- obtained
- of
- omar
- on
- open
- Operations
- operators
- or
- original
- our
- pages
- Paper
- Paul
- Peter
- physical
- Physical Sciences
- Physics
- plato
- Plato Data Intelligence
- PlatoData
- practically
- presence
- press
- principle
- principles
- problems
- Proceedings
- Programming
- propagation
- provide
- published
- publisher
- publishers
- Quantum
- Quantum Computer
- quantum computing
- quantum information
- qubits
- Questions
- R
- rapid
- Rate
- recently
- references
- registered
- relevant
- reliable
- remains
- represented
- required
- Requirements
- resource
- Results
- review
- Richard
- robustness
- royal
- russian
- s
- Science
- SCIENCES
- Series
- Series A
- set
- Signal
- Size
- small
- smaller
- Society
- solution
- Space
- statistical
- Successfully
- such
- sufficient
- suitable
- Symposium
- system
- techniques
- Technology
- than
- that
- The
- their
- then
- theoretical
- theory
- These
- this
- threshold
- tighter
- Title
- to
- tolerance
- Transactions
- turing
- two
- under
- Universal
- university
- updated
- URL
- USA
- volume
- W
- want
- was
- we
- WELL
- What
- What is
- which
- whose
- william
- with
- Wolf
- year
- youtube
- zephyrnet