research-article

On the need for large Quantum depth

Authors:

Ching-Yi LaiAuthors Info & Claims

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

Pages 902 - 915

https://doi.org/10.1145/3357713.3384291

Published: 22 June 2020 Publication History

Abstract

Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation.

Indeed, Jozsa conjectured that “Any quantum polynomial-time algorithm can be implemented with only O(logn) quantum depth interspersed with polynomial-time classical computations.” This can be formalized as asserting the equivalence of BQP and “BQNC ^BPP”. On the other hand, Aaronson conjectured that “there exists an oracle separation between BQP and BPP ^BQNC .” BQNC ^BPP and BPP ^BQNC are two natural and seeming incomparable ways of hybrid classical-quantum computation.

In this work, we manage to prove Aaronson’s conjecture and disproves Jozsa’s conjecture relative to an oracle. In fact, we prove a stronger statement that for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1 in the presence of classical computation. Thus, our results show that relative to oracles, doubling the quantum circuit depth indeed gives the hybrid model more power, and this cannot be traded by classical computation.

References

[1]

Scott Aaronson. 2005. Ten Semi-Grand Challenges for Quantum Computing Theory. ( 2005 ). https://www.scottaaronson.com/writings/qchallenge.html

[2]

Scott Aaronson. 2010. BQP and the Polynomial Hierarchy. In Proceedings of the Forty-second ACM Symposium on Theory of Computing (STOC '10). ACM, New York, NY, USA, 141-150. https://doi.org/10.1145/1806689.1806711

Digital Library

[3]

Scott Aaronson. 2011. Projects aplenty. https://www.scottaaronson.com/blog/ ?p= 663. ( 2011 ).

[4]

Scott Aaronson. 2019. Personal communication. ( 2019 ).

[5]

Scott Aaronson and Lijie Chen. 2017. Complexity-Theoretic Foundations of Quantum Supremacy Experiments. In Proceedings of the 32nd Computational Complexity Conference (CCC '17). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, Article Article 22, 67 pages.

Digital Library

[6]

Andris Ambainis, Mike Hamburg, and Dominique Unruh. 2018. Quantum security proofs using semi-classical oracles. IACR Cryptology ePrint Archive 2018 ( 2018 ), 904.

[7]

Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graf, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hofmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jefrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Riefel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. 2019. Quantum supremacy using a programmable superconducting processor. Nature 574, 7779 ( 2019 ), 505-510.

[8]

Nir Bitansky, Ran Canetti, Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai, Omer Paneth, and Alon Rosen. 2014. The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator. In Advances in Cryptology-CRYPTO 2014, Juan A. Garay and Rosario Gennaro (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 71-89.

[9]

Nai-Hui Chia, Kai-Min Chung, and Ching-Yi Lai. 2019. On the Need for Large Quantum Depth. ( 2019 ). arXiv:arXiv: 1909.10303

[10]

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. 2003. Exponential Algorithmic Speedup by a Quantum Walk. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing (STOC '03). Association for Computing Machinery, New York, NY, USA, 59-68. https://doi.org/10.1145/780542.780552

Digital Library

[11]

R. Cleve and J. Watrous. 2000. Fast parallel circuits for the quantum Fourier transform. In Proceedings 41st Annual Symposium on Foundations of Computer Science. 526-536.

[12]

Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger. 2018. Random Oracles and Non-uniformity. In EUROCRYPT (1). Springer, 227-258. https://doi. org/10.1007/978-3-319-78381-9_9

[13]

Matthew Coudron and Sanketh Menda. 2019. Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle). ( 2019 ). arXiv:arXiv: 1909.10503

[14]

Matthew Coudron and Sanketh Menda. 2019. Personal communication. ( 2019 ).

[15]

Peter Hoyer and Robert Spalek. 2005. Quantum Fan-out is Powerful. Theory of Computing 1 ( 01 2005 ), 81-103.

[16]

IBM. 2017. IBM Announces Advances to IBM Quantum Systems & Ecosystem. ( 2017 ). https://www-03.ibm.com/press/us/en/pressrelease/53374.wss

[17]

Richard Jozsa. 2005. An introduction to measurement based quantum computation. Quantum Information Processing 199 (09 2005 ).

[18]

Julian Kelly. 2018. A Preview of Bristlecone, Google's New Quantum Processor. https://ai.googleblog.com/ 2018 /03/a-preview-of-bristlecone-googlesnew.html. ( 2018 ).

[19]

Cristopher Moore and Martin Nilsson. 1998. Parallel Quantum Computation and Quantum Codes. ( 1998 ). arXiv:arXiv:quant-ph/9808027

[20]

D. R. Simon. 1994. On the Power of Quantum Computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (SFCS '94). IEEE Computer Society, USA, 116-123. https://doi.org/10.1109/SFCS. 1994.365701

Digital Library

[21]

Barbara M. Terhal and David P. DiVincenzo. 2004. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. Quantum Information & Computation 4, 2 ( 2004 ), 134-145. http://dblp.uni-trier.de/db/ journals/qic/qic4.html#TerhalD04

[22]

Dominique Unruh. 2007. Random Oracles and Auxiliary Input. In Advances in Cryptology-CRYPTO 2007, Alfred Menezes (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 205-223.

[23]

Dominique Unruh. 2015. Revocable Quantum Timed-Release Encryption. J. ACM 62, 6, Article 49 ( Dec. 2015 ), 76 pages.

Digital Library

Cited By

Dwivedi ARasmusson ARicherme PIyengar S(2024)Quantum Nuclear Dynamics on a Distributed Set of Ion-Trap Quantum Computing SystemsJournal of the American Chemical Society10.1021/jacs.4c07670146:43(29355-29363)Online publication date: 16-Oct-2024
https://doi.org/10.1021/jacs.4c07670
Dwivedi ALopez-Ruiz MIyengar S(2024)Resource Optimization for Quantum Dynamics with Tensor Networks: Quantum and Classical AlgorithmsThe Journal of Physical Chemistry A10.1021/acs.jpca.4c03407128:32(6774-6797)Online publication date: 5-Aug-2024
https://doi.org/10.1021/acs.jpca.4c03407
Iyengar SSaha DDwivedi ALopez-Ruiz MKumar AZhang JRicard TRicherme PSabry A(2024)Quantum Algorithms for the Study of Electronic Structure and Molecular Dynamics: Novel Computational ProtocolsComprehensive Computational Chemistry10.1016/B978-0-12-821978-2.00139-2(228-251)Online publication date: 2024
https://doi.org/10.1016/B978-0-12-821978-2.00139-2
Show More Cited By

Index Terms

On the need for large Quantum depth
1. Theory of computation
  1. Computational complexity and cryptography
    1. Quantum complexity theory

Recommendations

Quantum Depth in the Random Oracle Model
STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

We give a comprehensive characterisation of the computational power of shallow quantum circuits combined with classical computation. Specifically, for classes of search problems, we show that the following statements hold, relative to a random oracle: ...
On the Need for Large Quantum Depth
Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of ...
Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits

We study the quantum complexity class $${\mathsf{QNC}^\mathsf{0}_\mathsf{f}}$$QNCf0 of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 2020

1429 pages

ISBN:9781450369794

DOI:10.1145/3357713

General Chairs:
Konstantin Makarychev
Northwestern University, USA
,
Yury Makarychev
Toyota Technological Institute at Chicago, USA
,
Madhur Tulsiani
Toyota Technological Institute at Chicago, USA
,
Gautam Kamath
University of Waterloo, Canada
,
Program Chair:
Julia Chuzhoy
Toyota Technological Institute at Chicago, USA

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 June 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Academia Sinica Career Development Award,
YoungScholar Fellowship Program by Ministry of Science and Tech-nology in Taiwan,
MOST QC project,

Conference

STOC '20

Sponsor:

SIGACT

STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing

June 22 - 26, 2020

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
219
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)2

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dwivedi ARasmusson ARicherme PIyengar S(2024)Quantum Nuclear Dynamics on a Distributed Set of Ion-Trap Quantum Computing SystemsJournal of the American Chemical Society10.1021/jacs.4c07670146:43(29355-29363)Online publication date: 16-Oct-2024
https://doi.org/10.1021/jacs.4c07670
Dwivedi ALopez-Ruiz MIyengar S(2024)Resource Optimization for Quantum Dynamics with Tensor Networks: Quantum and Classical AlgorithmsThe Journal of Physical Chemistry A10.1021/acs.jpca.4c03407128:32(6774-6797)Online publication date: 5-Aug-2024
https://doi.org/10.1021/acs.jpca.4c03407
Iyengar SSaha DDwivedi ALopez-Ruiz MKumar AZhang JRicard TRicherme PSabry A(2024)Quantum Algorithms for the Study of Electronic Structure and Molecular Dynamics: Novel Computational ProtocolsComprehensive Computational Chemistry10.1016/B978-0-12-821978-2.00139-2(228-251)Online publication date: 2024
https://doi.org/10.1016/B978-0-12-821978-2.00139-2
Lai CKuo KLiao B(2024)Syndrome decoding by quantum approximate optimizationQuantum Information Processing10.1007/s11128-024-04568-723:11Online publication date: 1-Nov-2024
https://doi.org/10.1007/s11128-024-04568-7
Li HQiu DLuo LMateus P(2024)Exact distributed quantum algorithm for generalized Simon’s problemActa Informatica10.1007/s00236-024-00455-x61:2(131-159)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00236-024-00455-x
Khatami MMendes UWiebe NKim P(2023)Gate-based quantum computing for protein designPLOS Computational Biology10.1371/journal.pcbi.101103319:4(e1011033)Online publication date: 12-Apr-2023
https://doi.org/10.1371/journal.pcbi.1011033
Arora AColadangelo ACoudron MGheorghiu ASingh UWaldner HSaha BServedio R(2023)Quantum Depth in the Random Oracle ModelProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585153(1111-1124)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585153
Ganti IIyengar S(2023)Quantum Computing with DartboardsThe Journal of Physical Chemistry A10.1021/acs.jpca.3c04262127:37(7853-7857)Online publication date: 7-Sep-2023
https://doi.org/10.1021/acs.jpca.3c04262
Iyengar SZhang JSaha DRicard T(2023) Graph-| Q ⟩⟨ C |: A Quantum Algorithm with Reduced Quantum Circuit Depth for Electronic Structure The Journal of Physical Chemistry A10.1021/acs.jpca.3c04261127:44(9334-9345)Online publication date: 31-Oct-2023
https://doi.org/10.1021/acs.jpca.3c04261
Huang HBroughton MCotler JChen SLi JMohseni MNeven HBabbush RKueng RPreskill JMcClean J(2022)Quantum advantage in learning from experimentsScience10.1126/science.abn7293376:6598(1182-1186)Online publication date: 10-Jun-2022
https://doi.org/10.1126/science.abn7293
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents