IDEAS home Printed from https://ideas.repec.org/a/nat/natcom/v15y2024i1d10.1038_s41467-024-54864-0.html
   My bibliography  Save this article

Unconditional quantum magic advantage in shallow circuit computation

Author

Listed:
  • Xingjian Zhang

    (Tsinghua University
    The University of Hong Kong)

  • Zhaokai Pan

    (Tsinghua University)

  • Guoding Liu

    (Tsinghua University)

Abstract

Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of “magic” states—the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality—quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation.

Suggested Citation

  • Xingjian Zhang & Zhaokai Pan & Guoding Liu, 2024. "Unconditional quantum magic advantage in shallow circuit computation," Nature Communications, Nature, vol. 15(1), pages 1-10, December.
  • Handle: RePEc:nat:natcom:v:15:y:2024:i:1:d:10.1038_s41467-024-54864-0
    DOI: 10.1038/s41467-024-54864-0
    as

    Download full text from publisher

    File URL: https://www.nature.com/articles/s41467-024-54864-0
    File Function: Abstract
    Download Restriction: no

    File URL: https://libkey.io/10.1038/s41467-024-54864-0?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. 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.
    2. V. V. Sivak & A. Eickbusch & B. Royer & S. Singh & I. Tsioutsios & S. Ganjam & A. Miano & B. L. Brock & A. Z. Ding & L. Frunzio & S. M. Girvin & R. J. Schoelkopf & M. H. Devoret, 2023. "Real-time quantum error correction beyond break-even," Nature, Nature, vol. 616(7955), pages 50-55, April.
    3. Zhongchu Ni & Sai Li & Xiaowei Deng & Yanyan Cai & Libo Zhang & Weiting Wang & Zhen-Biao Yang & Haifeng Yu & Fei Yan & Song Liu & Chang-Ling Zou & Luyan Sun & Shi-Biao Zheng & Yuan Xu & Dapeng Yu, 2023. "Beating the break-even point with a discrete-variable-encoded logical qubit," Nature, Nature, vol. 616(7955), pages 56-60, April.
    4. B. Hensen & H. Bernien & A. E. Dréau & A. Reiserer & N. Kalb & M. S. Blok & J. Ruitenberg & R. F. L. Vermeulen & R. N. Schouten & C. Abellán & W. Amaya & V. Pruneri & M. W. Mitchell & M. Markham & D. , 2015. "Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres," Nature, Nature, vol. 526(7575), pages 682-686, October.
    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. Fernando Valadares & Ni-Ni Huang & Kyle Timothy Ng Chu & Aleksandr Dorogov & Weipin Chua & Lingda Kong & Pengtao Song & Yvonne Y. Gao, 2024. "On-demand transposition across light-matter interaction regimes in bosonic cQED," Nature Communications, Nature, vol. 15(1), pages 1-7, December.
    2. Yao Lu & Aniket Maiti & John W. O. Garmon & Suhas Ganjam & Yaxing Zhang & Jahan Claes & Luigi Frunzio & Steven M. Girvin & Robert J. Schoelkopf, 2023. "High-fidelity parametric beamsplitting with a parity-protected converter," Nature Communications, Nature, vol. 14(1), pages 1-11, December.
    3. X. L. He & Yong Lu & D. Q. Bao & Hang Xue & W. B. Jiang & Z. Wang & A. F. Roudsari & Per Delsing & J. S. Tsai & Z. R. Lin, 2023. "Fast generation of Schrödinger cat states using a Kerr-tunable superconducting resonator," Nature Communications, Nature, vol. 14(1), pages 1-10, December.
    4. Suhas Ganjam & Yanhao Wang & Yao Lu & Archan Banerjee & Chan U Lei & Lev Krayzman & Kim Kisslinger & Chenyu Zhou & Ruoshui Li & Yichen Jia & Mingzhao Liu & Luigi Frunzio & Robert J. Schoelkopf, 2024. "Surpassing millisecond coherence in on chip superconducting quantum memories by optimizing materials and circuit design," Nature Communications, Nature, vol. 15(1), pages 1-13, December.
    5. Bingzhi Zhang & Junyu Liu & Xiao-Chuan Wu & Liang Jiang & Quntao Zhuang, 2024. "Dynamical transition in controllable quantum neural networks with large depth," Nature Communications, Nature, vol. 15(1), pages 1-12, December.
    6. Sofia Priazhkina & Samuel Palmer & Pablo Martín-Ramiro & Román Orús & Samuel Mugel & Vladimir Skavysh, 2024. "Digital Payments in Firm Networks: Theory of Adoption and Quantum Algorithm," Staff Working Papers 24-17, Bank of Canada.
    7. Hu, Jie-Ru & Zhang, Zuo-Yuan & Liu, Jin-Ming, 2024. "Implementation of three-qubit Deutsch-Jozsa algorithm with pendular states of polar molecules by optimal control," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 635(C).
    8. Maryam Moghimi & Herbert W. Corley, 2020. "Information Loss Due to the Data Reduction of Sample Data from Discrete Distributions," Data, MDPI, vol. 5(3), pages 1-18, September.
    9. Martin Ringbauer & Marcel Hinsche & Thomas Feldker & Paul K. Faehrmann & Juani Bermejo-Vega & Claire L. Edmunds & Lukas Postler & Roman Stricker & Christian D. Marciniak & Michael Meth & Ivan Pogorelo, 2025. "Verifiable measurement-based quantum random sampling with trapped ions," Nature Communications, Nature, vol. 16(1), pages 1-9, December.
    10. Yulong Dong & Jonathan A. Gross & Murphy Yuezhen Niu, 2025. "Optimal low-depth quantum signal-processing phase estimation," Nature Communications, Nature, vol. 16(1), pages 1-9, December.
    11. Jesús Fernández-Villaverde & Isaiah J. Hull, 2023. "Dynamic Programming on a Quantum Annealer: Solving the RBC Model," NBER Working Papers 31326, National Bureau of Economic Research, Inc.
    12. Jake Rochman & Tian Xie & John G. Bartholomew & K. C. Schwab & Andrei Faraon, 2023. "Microwave-to-optical transduction with erbium ions coupled to planar photonic and superconducting resonators," Nature Communications, Nature, vol. 14(1), pages 1-9, December.
    13. Jin Ming Koh & Tommy Tai & Ching Hua Lee, 2024. "Realization of higher-order topological lattices on a quantum computer," Nature Communications, Nature, vol. 15(1), pages 1-14, December.
    14. T. Brown & E. Doucet & D. Ristè & G. Ribeill & K. Cicak & J. Aumentado & R. Simmonds & L. Govia & A. Kamal & L. Ranzani, 2022. "Trade off-free entanglement stabilization in a superconducting qutrit-qubit system," Nature Communications, Nature, vol. 13(1), pages 1-7, December.
    15. Daniel Christian Lawo & Rana Abu Bakar & Abraham Cano Aguilera & Filippo Cugini & José Luis Imaña & Idelfonso Tafur Monroy & Juan Jose Vegas Olmos, 2024. "Wireless and Fiber-Based Post-Quantum-Cryptography-Secured IPsec Tunnel," Future Internet, MDPI, vol. 16(8), pages 1-22, August.
    16. 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.
    17. Thorsten B. Wahl & Bo Han & Benjamin Béri, 2024. "Topologically ordered time crystals," Nature Communications, Nature, vol. 15(1), pages 1-8, December.
    18. Yang, Yan-Han & Yang, Xue & Luo, Ming-Xing, 2023. "Device-independently verifying full network nonlocality of quantum networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 617(C).
    19. Zenghui Bao & Yan Li & Zhiling Wang & Jiahui Wang & Jize Yang & Haonan Xiong & Yipu Song & Yukai Wu & Hongyi Zhang & Luming Duan, 2024. "A cryogenic on-chip microwave pulse generator for large-scale superconducting quantum computing," Nature Communications, Nature, vol. 15(1), pages 1-9, December.
    20. Ryan Snodgrass & Vincent Kotsubo & Scott Backhaus & Joel Ullom, 2024. "Dynamic acoustic optimization of pulse tube refrigerators for rapid cooldown," Nature Communications, Nature, vol. 15(1), pages 1-8, 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:15:y:2024:i:1:d:10.1038_s41467-024-54864-0. 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.