IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v14y2023i1d10.1038_s41467-023-41217-6.html
   My bibliography  Save this article

The complexity of NISQ

Author

Listed:
  • Sitan Chen

    (University of California, Berkeley
    Harvard University)

  • Jordan Cotler

    (Harvard University)

  • Hsin-Yuan Huang

    (CAltech
    CAltech)

  • Jerry Li

    (Microsoft Research AI)

Abstract

The recent proliferation of NISQ devices has made it imperative to understand their power. In this work, we define and study the complexity class NISQ, which encapsulates problems that can be efficiently solved by a classical computer with access to noisy quantum circuits. We establish super-polynomial separations in the complexity among classical computation, NISQ, and fault-tolerant quantum computation to solve some problems based on modifications of Simon’s problems. We then consider the power of NISQ for three well-studied problems. For unstructured search, we prove that NISQ cannot achieve a Grover-like quadratic speedup over classical computers. For the Bernstein-Vazirani problem, we show that NISQ only needs a number of queries logarithmic in what is required for classical computers. Finally, for a quantum state learning problem, we prove that NISQ is exponentially weaker than classical computers with access to noiseless constant-depth quantum circuits.

Suggested Citation

  • Sitan Chen & Jordan Cotler & Hsin-Yuan Huang & Jerry Li, 2023. "The complexity of NISQ," Nature Communications, Nature, vol. 14(1), pages 1-6, December.
    • Handle: RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-41217-6
    DOI: 10.1038/s41467-023-41217-6
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/s41467-023-41217-6
    File Function: Abstract
    Download Restriction: no
    File URL: https://libkey.io/10.1038/s41467-023-41217-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Dorit Aharonov & Jordan Cotler & Xiao-Liang Qi, 2022. "Quantum algorithmic measurement," Nature Communications, Nature, vol. 13(1), pages 1-9, December.
    2. Xiao Xue & Maximilian Russ & Nodar Samkharadze & Brennan Undseth & Amir Sammak & Giordano Scappucci & Lieven M. K. Vandersypen, 2022. "Quantum logic with spin qubits crossing the surface code threshold," Nature, Nature, vol. 601(7893), pages 343-347, January.
    3. 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, 2019. "Quantum supremacy using a programmable superconducting processor," Nature, Nature, vol. 574(7779), pages 505-510, October.
    4. Abhinav Kandala & Antonio Mezzacapo & Kristan Temme & Maika Takita & Markus Brink & Jerry M. Chow & Jay M. Gambetta, 2017. "Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets," Nature, Nature, vol. 549(7671), pages 242-246, September.
    5. S. Debnath & N. M. Linke & C. Figgatt & K. A. Landsman & K. Wright & C. Monroe, 2016. "Demonstration of a small programmable quantum computer with atomic qubits," Nature, Nature, vol. 536(7614), pages 63-66, August.
    6. J. Zhang & G. Pagano & P. W. Hess & A. Kyprianidis & P. Becker & H. Kaplan & A. V. Gorshkov & Z.-X. Gong & C. Monroe, 2017. "Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator," Nature, Nature, vol. 551(7682), pages 601-604, November.
    7. Alberto Peruzzo & Jarrod McClean & Peter Shadbolt & Man-Hong Yung & Xiao-Qi Zhou & Peter J. Love & Alán Aspuru-Guzik & Jeremy L. O’Brien, 2014. "A variational eigenvalue solver on a photonic quantum processor," Nature Communications, Nature, vol. 5(1), pages 1-7, September.
    8. K. Wright & K. M. Beck & S. Debnath & J. M. Amini & Y. Nam & N. Grzesiak & J.-S. Chen & N. C. Pisenti & M. Chmielewski & C. Collins & K. M. Hudek & J. Mizrahi & J. D. Wong-Campos & S. Allen & J. Apisd, 2019. "Benchmarking an 11-qubit quantum computer," Nature Communications, Nature, vol. 10(1), pages 1-6, December.
    9. William J. Huggins & Bryan A. O’Gorman & Nicholas C. Rubin & David R. Reichman & Ryan Babbush & Joonho Lee, 2022. "Unbiasing fermionic quantum Monte Carlo with a quantum computer," Nature, Nature, vol. 603(7901), pages 416-420, March.
    10. John Clarke & Frank K. Wilhelm, 2008. "Superconducting quantum bits," Nature, Nature, vol. 453(7198), pages 1031-1042, June.
    11. Matthias C. Caro & Hsin-Yuan Huang & M. Cerezo & Kunal Sharma & Andrew Sornborger & Lukasz Cincio & Patrick J. Coles, 2022. "Generalization in quantum machine learning from few training data," Nature Communications, Nature, vol. 13(1), pages 1-11, December.
    12. Akito Noiri & Kenta Takeda & Takashi Nakajima & Takashi Kobayashi & Amir Sammak & Giordano Scappucci & Seigo Tarucha, 2022. "Fast universal quantum gate above the fault-tolerance threshold in silicon," Nature, Nature, vol. 601(7893), pages 338-342, January.
    13. Hsin-Yuan Huang & Michael Broughton & Masoud Mohseni & Ryan Babbush & Sergio Boixo & Hartmut Neven & Jarrod R. McClean, 2021. "Power of data in quantum machine learning," Nature Communications, Nature, vol. 12(1), pages 1-9, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Elies Gil-Fuster & Jens Eisert & Carlos Bravo-Prieto, 2024. "Understanding quantum machine learning also requires rethinking generalization," Nature Communications, Nature, vol. 15(1), pages 1-12, December.
    2. Dylan Herman & Cody Googin & Xiaoyuan Liu & Alexey Galda & Ilya Safro & Yue Sun & Marco Pistoia & Yuri Alexeev, 2022. "A Survey of Quantum Computing for Finance," Papers 2201.02773, arXiv.org, revised Jun 2022.
    3. Matthias C. Caro & Hsin-Yuan Huang & Nicholas Ezzell & Joe Gibbs & Andrew T. Sornborger & Lukasz Cincio & Patrick J. Coles & Zoë Holmes, 2023. "Out-of-distribution generalization for learning quantum dynamics," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    4. Ajagekar, Akshay & You, Fengqi, 2022. "Quantum computing and quantum artificial intelligence for renewable and sustainable energy: A emerging prospect towards climate neutrality," Renewable and Sustainable Energy Reviews, Elsevier, vol. 165(C).
    5. Brian Paquelet Wuetz & Merritt P. Losert & Sebastian Koelling & Lucas E. A. Stehouwer & Anne-Marije J. Zwerver & Stephan G. J. Philips & Mateusz T. Mądzik & Xiao Xue & Guoji Zheng & Mario Lodari & Ser, 2022. "Atomic fluctuations lifting the energy degeneracy in Si/SiGe quantum dots," Nature Communications, Nature, vol. 13(1), pages 1-8, December.
    6. Laura Lewis & Hsin-Yuan Huang & Viet T. Tran & Sebastian Lehner & Richard Kueng & John Preskill, 2024. "Improved machine learning algorithm for predicting ground state properties," Nature Communications, Nature, vol. 15(1), pages 1-8, December.
    7. Abha Naik & Esra Yeniaras & Gerhard Hellstern & Grishma Prasad & Sanjay Kumar Lalta Prasad Vishwakarma, 2023. "From Portfolio Optimization to Quantum Blockchain and Security: A Systematic Review of Quantum Computing in Finance," Papers 2307.01155, arXiv.org.
    8. Yulin Chi & Jieshan Huang & Zhanchuan Zhang & Jun Mao & Zinan Zhou & Xiaojiong Chen & Chonghao Zhai & Jueming Bao & Tianxiang Dai & Huihong Yuan & Ming Zhang & Daoxin Dai & Bo Tang & Yan Yang & Zhihua, 2022. "A programmable qudit-based quantum processor," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    9. D. Zhu & Z. P. Cian & C. Noel & A. Risinger & D. Biswas & L. Egan & Y. Zhu & A. M. Green & C. Huerta Alderete & N. H. Nguyen & Q. Wang & A. Maksymov & Y. Nam & M. Cetina & N. M. Linke & M. Hafezi & C., 2022. "Cross-platform comparison of arbitrary quantum states," Nature Communications, Nature, vol. 13(1), pages 1-6, December.
    10. Eric R. Anschuetz & Bobak T. Kiani, 2022. "Quantum variational algorithms are swamped with traps," Nature Communications, Nature, vol. 13(1), pages 1-10, December.
    11. Junyu Liu & Minzhao Liu & Jin-Peng Liu & Ziyu Ye & Yunfei Wang & Yuri Alexeev & Jens Eisert & Liang Jiang, 2024. "Towards provably efficient quantum algorithms for large-scale machine-learning models," Nature Communications, Nature, vol. 15(1), pages 1-6, December.
    12. Mario E Rivero-Angeles, 2021. "Quantum-based wireless sensor networks: A review and open questions," International Journal of Distributed Sensor Networks, , vol. 17(10), pages 15501477211, October.
    13. Matthias C. Caro & Hsin-Yuan Huang & M. Cerezo & Kunal Sharma & Andrew Sornborger & Lukasz Cincio & Patrick J. Coles, 2022. "Generalization in quantum machine learning from few training data," Nature Communications, Nature, vol. 13(1), pages 1-11, December.
    14. He, Zhimin & Deng, Maijie & Zheng, Shenggen & Li, Lvzhou & Situ, Haozhen, 2023. "GSQAS: Graph Self-supervised Quantum Architecture Search," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 630(C).
    15. Sofiene Jerbi & Lukas J. Fiderer & Hendrik Poulsen Nautrup & Jonas M. Kübler & Hans J. Briegel & Vedran Dunjko, 2023. "Quantum machine learning beyond kernel methods," Nature Communications, Nature, vol. 14(1), pages 1-8, December.
    16. Brian Paquelet Wuetz & Davide Degli Esposti & Anne-Marije J. Zwerver & Sergey V. Amitonov & Marc Botifoll & Jordi Arbiol & Amir Sammak & Lieven M. K. Vandersypen & Maximilian Russ & Giordano Scappucci, 2023. "Reducing charge noise in quantum dots by using thin silicon quantum wells," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    17. Tom Struck & Mats Volmer & Lino Visser & Tobias Offermann & Ran Xue & Jhih-Sian Tu & Stefan Trellenkamp & Łukasz Cywiński & Hendrik Bluhm & Lars R. Schreiber, 2024. "Spin-EPR-pair separation by conveyor-mode single electron shuttling in Si/SiGe," Nature Communications, Nature, vol. 15(1), pages 1-8, December.
    18. Samson Wang & Enrico Fontana & M. Cerezo & Kunal Sharma & Akira Sone & Lukasz Cincio & Patrick J. Coles, 2021. "Noise-induced barren plateaus in variational quantum algorithms," Nature Communications, Nature, vol. 12(1), pages 1-11, December.
    19. Ran Xue & Max Beer & Inga Seidler & Simon Humpohl & Jhih-Sian Tu & Stefan Trellenkamp & Tom Struck & Hendrik Bluhm & Lars R. Schreiber, 2024. "Si/SiGe QuBus for single electron information-processing devices with memory and micron-scale connectivity function," Nature Communications, Nature, vol. 15(1), pages 1-7, December.
    20. Alexander McCaskey & Eugene Dumitrescu & Mengsu Chen & Dmitry Lyakh & Travis Humble, 2018. "Validating quantum-classical programming models with tensor network simulations," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-19, December.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:nat:natcom:v:14:y:2023:i:1:d:10.1038_s41467-023-41217-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.nature.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.