{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,22]],"date-time":"2023-11-22T16:59:07Z","timestamp":1700672347330},"reference-count":20,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T00:00:00Z","timestamp":1692144000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003845","name":"Indian Institute of Technology Madras","doi-asserted-by":"crossref","award":["New Faculty Initiation Grant"],"award-info":[{"award-number":["New Faculty Initiation Grant"]}],"id":[{"id":"10.13039\/501100003845","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Department of Science and Technology, India","award":["DST\/INSPIRE\/04\/2016\/001171"],"award-info":[{"award-number":["DST\/INSPIRE\/04\/2016\/001171"]}]},{"name":"Science and Engineering Research Board, Department of Science and Technology, India","award":["SERB\/SRG\/2019\/001809"],"award-info":[{"award-number":["SERB\/SRG\/2019\/001809"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation, USA","doi-asserted-by":"crossref","award":["PHY-2112890"],"award-info":[{"award-number":["PHY-2112890"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03F5;<\/mml:mi><\/mml:math>-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.<\/jats:p>","DOI":"10.22331\/q-2023-08-16-1087","type":"journal-article","created":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T16:55:05Z","timestamp":1692204905000},"page":"1087","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["A Converse for Fault-tolerant Quantum Computation"],"prefix":"10.22331","volume":"7","author":[{"given":"Uthirakalyani","family":"G","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Indian Institute of Technology Madras, Chennai, India."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anuj K.","family":"Nayak","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avhishek","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Indian Institute of Technology Madras, Chennai, India."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2023,8,16]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u2013188, 1997.","DOI":"10.1145\/258533.258579"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Howard Barnum, Emanuel Knill, and Michael A. Nielsen. \"On quantum fidelities and channel capacities\". IEEE Transactions on Information Theory, 46(4):1317\u20131329, 2000.","DOI":"10.1109\/18.850671"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u2013591, 1980.","DOI":"10.1007\/BF01011339"},{"key":"3","doi-asserted-by":"publisher","unstructured":"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&apos;06), pages 411\u2013419. IEEE, 2006.","DOI":"10.1109\/FOCS.2006.50"},{"key":"4","doi-asserted-by":"publisher","unstructured":"David Deutsch. \"Quantum theory, the Church\u2013Turing principle and the universal quantum computer\". Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97\u2013117, 1985.","DOI":"10.1098\/rspa.1985.0070"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u2013558, 1992.","DOI":"10.1098\/rspa.1992.0167"},{"key":"6","doi-asserted-by":"publisher","unstructured":"William S Evans and Leonard J Schulman. \"Signal propagation and noisy circuits\". IEEE Transactions on Information Theory, 45(7):2367\u20132373, 1999.","DOI":"10.1109\/18.796377"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/FOCS.2018.00076"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Omar Fawzi, Alexander M\u00fcller-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.","DOI":"10.48550\/arXiv.2202.00119"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. \"Fault-tolerant quantum computation with constant overhead\". Quantum Information & Computation, 14(15-16):1338\u20131372, 2014.","DOI":"10.48550\/arXiv.1310.2984"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Aram W Harrow and Michael A Nielsen. \"Robustness of quantum gates in the presence of noise\". Physical Review A, 68(1):012308, 2003.","DOI":"10.1103\/PhysRevA.68.012308"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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\u2013856. Springer, 2008.","DOI":"10.1007\/978-3-540-70575-8_69"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Sumeet Khatri and Mark M Wilde. \"Principles of quantum communication theory: A modern approach\". arXiv preprint arXiv:2011.04672, 2020.","DOI":"10.48550\/arXiv.2011.04672"},{"key":"13","doi-asserted-by":"publisher","unstructured":"A Yu Kitaev. \"Quantum computations: algorithms and error correction\". Russian Mathematical Surveys, 52(6):1191, 1997.","DOI":"10.1070\/RM1997v052n06ABEH002155"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. \"Quantum Computation and Quantum Information: 10th Anniversary Edition\". Cambridge University Press, 2010.","DOI":"10.1017\/CBO9780511976667"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Nicholas Pippenger. \"Reliable computation by formulas in the presence of noise\". IEEE Transactions on Information Theory, 34(2):194\u2013197, 1988.","DOI":"10.1109\/18.2628"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Alexander A Razborov. \"An upper bound on the threshold quantum decoherence rate\". Quantum Information & Computation, 4(3):222\u2013228, 2004.","DOI":"10.48550\/arXiv.quant-ph\/0310136"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Peter W Shor. \"Fault-tolerant quantum computation\". In Proceedings of 37th Conference on Foundations of Computer Science, pages 56\u201365. IEEE, 1996.","DOI":"10.1109\/SFCS.1996.548464"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Andrew M Steane. \"Error correcting codes in quantum theory\". Physical Review Letters, 77(5):793, 1996.","DOI":"10.1103\/PhysRevLett.77.793"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Shashank Virmani, Susana F Huelga, and Martin B Plenio. \"Classical simulability, entanglement breaking, and quantum computation thresholds\". Physical Review A, 71(4):042328, 2005.","DOI":"10.1103\/PhysRevA.71.042328"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-08-16-1087\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T16:55:17Z","timestamp":1692204917000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-08-16-1087\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,16]]},"references-count":20,"URL":"https:\/\/doi.org\/10.22331\/q-2023-08-16-1087","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,16]]},"article-number":"1087"}}