Document Open Access Logo

A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Authors Omar Fawzi, Alexander Müller-Hermes, Ala Shayeghi

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.68.pdf
  • Filesize: 0.72 MB
  • 20 pages

Document Identifiers

Author Details

Omar Fawzi
  • Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France
Alexander Müller-Hermes
  • Institut Camille Jordan, Université Claude Bernard Lyon 1, 69622 Villeurbanne cedex, France
  • Department of Mathematics, University of Oslo, Norway
Ala Shayeghi
  • Univ Lyon, ENS Lyon, UCBL, CNRS, Inria, LIP, F-69342, Lyon Cedex 07, France

Funding

  • Fawzi, Omar: European Research Council Project AlgoQIP (grant no. 851716).
  • Müller-Hermes, Alexander: The European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Action TIPTOP (grant no. 843414).
  • Shayeghi, Ala: European Research Council Project AlgoQIP (grant no. 851716).

Acknowledgements

We would like to thank Cambyse Rouzé for helpful discussions.

Cite AsGet BibTex

Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi. A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.68

Abstract

The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel 𝒩 and any quantum fault tolerance schemes against i.i.d. noise modeled by 𝒩, we prove a lower bound of max{Q(𝒩)^{-1}n,α_𝒩 log T} on the number of physical qubits, for circuits of length T and width n. Here, Q(𝒩) denotes the quantum capacity of 𝒩 and α_𝒩 > 0 is a constant only depending on the channel 𝒩. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and in the case of unital noise, we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman and Hassidim (2013).

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Hardware → Quantum error correction and fault tolerance
Keywords
  • Fault-tolerant quantum computation
  • quantum error correction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 176-188, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258533.258579.
  2. D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan. Limitations of noisy reversible computation. Technical Report arXiv:9611028 [quant-ph], arXiv.org, https://arxiv.org/abs/quant-ph/9611028, 1996. Google Scholar
  3. Panos Aliferis, Daniel Gottesman, and John Preskill. Quantum accuracy threshold for concatenated distance-3 codes. Quantum Info. Comput., 6(2):97-165, March 2006. Google Scholar
  4. Panos Aliferis, Daniel Gottesman, and John Preskill. Accuracy threshold for postselected quantum computation. Quantum Info. Comput., 8(3):181-244, March 2008. Google Scholar
  5. Panos Aliferis and John Preskill. Fault-tolerant quantum computation against biased noise. Phys. Rev. A, 78:052331, November 2008. URL: https://doi.org/10.1103/PhysRevA.78.052331.
  6. Panos Aliferis and John Preskill. Fibonacci scheme for fault-tolerant quantum computation. Phys. Rev. A, 79:012332, January 2009. URL: https://doi.org/10.1103/PhysRevA.79.012332.
  7. H. Barnum, E. Knill, and M.A. Nielsen. On quantum fidelities and channel capacities. IEEE Transactions on Information Theory, 46(4):1317-1329, July 2000. URL: https://doi.org/10.1109/18.850671.
  8. Salman Beigi and Peter W Shor. On the complexity of computing zero-error and holevo capacity of quantum channels. arXiv preprint arXiv:0709.2090, 2007. Google Scholar
  9. Michael Ben-Or, Daniel Gottesman, and Avinatan Hassidim. Quantum refrigerator. arXiv preprint arXiv:1301.1995, 2013. Google Scholar
  10. Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters. Mixed-state entanglement and quantum error correction. Physical Review A, 54(5):3824-3851, November 1996. URL: https://doi.org/10.1103/physreva.54.3824.
  11. Mary Beth Ruskai, Stanislaw Szarek, and Elisabeth Werner. An analysis of completely-positive trace-preserving maps on m2. Linear Algebra and its Applications, 347(1):159-187, 2002. URL: https://doi.org/10.1016/S0024-3795(01)00547-X.
  12. Peter Brooks and John Preskill. Fault-tolerant quantum computation with asymmetric bacon-shor codes. Phys. Rev. A, 87:032310, March 2013. URL: https://doi.org/10.1103/PhysRevA.87.032310.
  13. Benjamin J. Brown, Katharina Laubscher, Markus S. Kesselring, and James R. Wootton. Poking holes and cutting corners to achieve clifford gates with the surface code. Phys. Rev. X, 7:021029, May 2017. URL: https://doi.org/10.1103/PhysRevX.7.021029.
  14. Benjamin J. Brown, Daniel Loss, Jiannis K. Pachos, Chris N. Self, and James R. Wootton. Quantum memories at finite temperature. Rev. Mod. Phys., 88:045005, November 2016. URL: https://doi.org/10.1103/RevModPhys.88.045005.
  15. Dagmar Bruss, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello, and John A. Smolin. Optimal universal and state-dependent quantum cloning. Phys. Rev. A, 57:2368-2378, April 1998. URL: https://doi.org/10.1103/PhysRevA.57.2368.
  16. Harry Buhrman, Richard Cleve, Monique Laurent, Noah Linden, Alexander Schrijver, and Falk Unger. New limits on fault-tolerant quantum computation. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 411-419, 2006. URL: https://doi.org/10.1109/FOCS.2006.50.
  17. Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549(7671):172-179, September 2017. URL: https://doi.org/10.1038/nature23460.
  18. Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10(3):285-290, 1975. URL: https://doi.org/10.1016/0024-3795(75)90075-0.
  19. Toby S Cubitt, Jianxin Chen, and Aram W Harrow. Superactivation of the asymptotic zero-error classical capacity of a quantum channel. IEEE transactions on information theory, 57(12):8114-8126, 2011. URL: https://doi.org/10.1109/TIT.2011.2169109.
  20. Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43(9):4452-4505, 2002. URL: https://doi.org/10.1063/1.1499754.
  21. R. L. Dobrushin. Central limit theorem for nonstationary markov chains. i. Theory of Probability & Its Applications, 1(1):65-80, 1956. URL: https://doi.org/10.1137/1101006.
  22. Runyao Duan. Super-activation of zero-error capacity of noisy quantum channels. arXiv preprint arXiv:0906.2527, 2009. Google Scholar
  23. Runyao Duan, Simone Severini, and Andreas Winter. Zero-error communication via quantum channels, noncommutative graphs, and a quantum lovász number. IEEE Transactions on Information Theory, 59(2):1164-1174, 2012. URL: https://doi.org/10.1109/TIT.2012.2221677.
  24. W.S. Evans and L.J. Schulman. Signal propagation and noisy circuits. IEEE Transactions on Information Theory, 45(7):2367-2373, 1999. URL: https://doi.org/10.1109/18.796377.
  25. W.S. Evans and L.J. Schulman. On the maximum tolerable noise of k-input gates for reliable computation by formulas. IEEE Transactions on Information Theory, 49(11):3094-3098, 2003. URL: https://doi.org/10.1109/TIT.2003.818405.
  26. Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 743-754. IEEE, 2018. Google Scholar
  27. Daniel Gottesman. Fault-tolerant quantum computation with constant overhead. Quantum Info. Comput., 14(15-16):1338-1372, November 2014. Google Scholar
  28. Jérémie Guillaud and Mazyar Mirrahimi. Repetition cat qubits for fault-tolerant quantum computation. Phys. Rev. X, 9:041053, December 2019. URL: https://doi.org/10.1103/PhysRevX.9.041053.
  29. Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14(12):123011, December 2012. URL: https://doi.org/10.1088/1367-2630/14/12/123011.
  30. Julia Kempe, Oded Regev, Falk Uunger, and Ronald de Wolf. Upper bounds on the noise threshold for fault-tolerant quantum computing. Quantum Info. Comput., 10(5):361-376, May 2010. Google Scholar
  31. A Yu Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191-1249, December 1997. URL: https://doi.org/10.1070/rm1997v052n06abeh002155.
  32. A.Yu. Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. URL: https://doi.org/10.1016/S0003-4916(02)00018-0.
  33. E. Knill. Quantum computing with realistically noisy devices. Nature, 434(7029):39-44, March 2005. URL: https://doi.org/10.1038/nature03350.
  34. Emanuel Knill, Raymond Laflamme, and Wojciech H. Zurek. Resilient quantum computation: error models and thresholds. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):365-384, January 1998. URL: https://doi.org/10.1098/rspa.1998.0166.
  35. Debbie Leung and Graeme Smith. Continuity of quantum channel capacities. Communications in Mathematical Physics, 292(1):201-215, May 2009. URL: https://doi.org/10.1007/s00220-009-0833-1.
  36. Rex AC Medeiros and Francisco M De Assis. Quantum zero-error capacity. International Journal of Quantum Information, 3(01):135-139, 2005. URL: https://doi.org/10.1142/S0219749905000682.
  37. Alexander Müller-Hermes, Daniel Stilck França, and Michael M Wolf. Relative entropy convergence for depolarizing channels. Journal of Mathematical Physics, 57(2):022202, 2016. URL: https://doi.org/10.1063/1.4939560.
  38. Jeonghoon Park and Soojoon Lee. Zero-error classical capacity of qubit channels cannot be superactivated. Physical Review A, 85(5):052321, 2012. URL: https://doi.org/10.1103/PhysRevA.85.052321.
  39. Stefano Pirandola. End-to-end capacities of a quantum communication network. Communications Physics, 2(1):51, May 2019. URL: https://doi.org/10.1038/s42005-019-0147-3.
  40. Maxim Raginsky. Strictly contractive quantum channels and physically realizable quantum computers. Phys. Rev. A, 65:032306, February 2002. URL: https://doi.org/10.1103/PhysRevA.65.032306.
  41. Robert Raussendorf and Jim Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Phys. Rev. Lett., 98:190504, May 2007. URL: https://doi.org/10.1103/PhysRevLett.98.190504.
  42. Alexander A. Razborov. An upper bound on the threshold quantum decoherence rate. Quantum Info. Comput., 4(3):222-228, May 2004. Google Scholar
  43. Mary Beth Ruskai. Beyond strong subadditivity? improved bounds on the contraction of generalized relative entropy. Reviews in Mathematical Physics, 6(05a):1147-1161, 1994. URL: https://doi.org/10.1142/s0129055x94000407.
  44. Pradeep Kiran Sarvepalli, Andreas Klappenecker, and Martin Rötteler. Asymmetric quantum codes: constructions, bounds and performance. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465(2105):1645-1672, 2009. URL: https://doi.org/10.1098/rspa.2008.0439.
  45. ME Shirokov and Tatiana Shulman. On superactivation of zero-error capacities and reversibility of a quantum channel. Communications in Mathematical Physics, 335(3):1159-1179, 2015. URL: https://doi.org/10.1007/s00220-015-2345-5.
  46. Peter W. Shor. Scheme for reducing decoherence in quantum computer memory. Phys. Rev. A, 52:R2493-R2496, October 1995. URL: https://doi.org/10.1103/PhysRevA.52.R2493.
  47. Peter W. Shor. Fault-tolerant quantum computation. In Proceedings of 37th Conference on Foundations of Computer Science, pages 56-65, 1996. URL: https://doi.org/10.1109/SFCS.1996.548464.
  48. A. M. Steane. Error correcting codes in quantum theory. Phys. Rev. Lett., 77:793-797, July 1996. URL: https://doi.org/10.1103/PhysRevLett.77.793.
  49. Barbara M. Terhal. Quantum error correction for quantum memories. Rev. Mod. Phys., 87:307-346, April 2015. URL: https://doi.org/10.1103/RevModPhys.87.307.
  50. David K. Tuckett, Stephen D. Bartlett, and Steven T. Flammia. Ultrahigh error threshold for surface codes with biased noise. Phys. Rev. Lett., 120:050505, January 2018. URL: https://doi.org/10.1103/PhysRevLett.120.050505.
  51. S. Virmani, Susana F. Huelga, and Martin B. Plenio. Classical simulability, entanglement breaking, and quantum computation thresholds. Phys. Rev. A, 71:042328, April 2005. URL: https://doi.org/10.1103/PhysRevA.71.042328.
  52. Chenyang Wang, Jim Harrington, and John Preskill. Confinement-higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory. Annals of Physics, 303(1):31-58, 2003. URL: https://doi.org/10.1016/S0003-4916(02)00019-2.
  53. David S. Wang, Austin G. Fowler, and Lloyd C. L. Hollenberg. Surface code quantum computing with error rates over 1%. Physical Review A, 83(2), February 2011. URL: https://doi.org/10.1103/physreva.83.020302.
  54. John Watrous. Semidefinite programs for completely bounded norms. arXiv preprint arXiv:0901.4709, 2009. Google Scholar
  55. John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. URL: https://doi.org/10.1017/9781316848142.
  56. Xing-Can Yao, Tian-Xiong Wang, Hao-Ze Chen, Wei-Bo Gao, Austin G. Fowler, Robert Raussendorf, Zeng-Bing Chen, Nai-Le Liu, Chao-Yang Lu, You-Jin Deng, and et al. Experimental demonstration of topological error correction. Nature, 482(7386):489-494, February 2012. URL: https://doi.org/10.1038/nature10770.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact