Nonadaptive fault-tolerant verification of quantum supremacy with noise

Theodoros Kapourniotis and Animesh Datta

Department of Physics, University of Warwick, Coventry CV4 7AL, United Kingdom

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Quantum samplers are believed capable of sampling efficiently from distributions that are classically hard to sample from. We consider a sampler inspired by the classical Ising model. It is nonadaptive and therefore experimentally amenable. Under a plausible conjecture, classical sampling upto additive errors from this model is known to be hard. We present a trap-based verification scheme for quantum supremacy that only requires the verifier to prepare single-qubit states. The verification is done on the same model as the original sampler, a square lattice, with only a constant overhead. We next revamp our verification scheme in two distinct ways using fault tolerance that preserves the nonadaptivity. The first has a lower overhead based on error correction with the same threshold as universal quantum computation. The second has a higher overhead but an improved threshold ($1.97\%$) based on error detection. We show that classically sampling upto additive errors is likely hard in both these schemes. Our results are applicable to other sampling problems such as the Instantaneous Quantum Polynomial-time (IQP) computation model. They should also assist near-term attempts at experimentally demonstrating quantum supremacy and guide long-term ones.

The considerable experimental efforts being directed towards building quantum computers rest on the belief that they are more powerful than classical computers. Formal mathematical proof for this belief has, however, been rather limited. `Quantum computational supremacy' (QCS) is the ability of a quantum computer to perform a task beyond the capability of any classical computer. Crucially, QCS has been proven for solving easier problems that do not require all the powers of a universal quantum computer.

Two challenges plague experimental demonstration of QCS. The first is our limited trust in the experimental devices to produce the correct output, especially in the regime where predictions via classical simulation of the same system are impossible. The second is the presence of noise in each device which, if not dealt with, accumulates and overwhelms the computation, introducing errors. In both cases the output can be statistically far from the correct one, which prohibits the demonstration of QCS.

Our paper provides a scheme which resolves both challenges by verifying that the outputs of the experiment are sufficiently close to the desired distribution. The distribution we sample from comes from the 2D Ising model, a mathematical model of magnetism that has many applications in statistical physics and is an instance of a QCS task. Our analysis only requires that single qubit states can be prepared reliably, and the experimentalist possesses devices with noise rates below 1.97%. The latter permits larger noise levels than required for universal quantum computing. Our scheme is based on building trust in the correctness of a large computation by checking the correctness of small computations and takes a constant amount of time independent of the size of the lattice in the Ising model. It can therefore be used to prove the correct operation of a QCS demonstrator before building a universal quantum computer becomes possible.

► BibTeX data

► References

[1] Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory of Computing, 9 (1): 143–252, 2013. ISSN 1557-2862. 10.4086/​toc.2013.v009a004.

[2] Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. In LIPIcs-Leibniz International Proceedings in Informatics, volume 79. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. 10.4230/​LIPIcs.CCC.2017.22.

[3] Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. On the implausibility of classical client blind quantum computing. arXiv preprint arXiv:1704.08482, 2017. URL https:/​/​​abs/​1704.08482.

[4] Dorit Aharonov, Michael Ben-Or, and Elad Eban. Interactive proofs for quantum computations. In Proceedings of Innovations in Computer Science 2010, ICS2010, pages 453–, 2010. URL http:/​/​​ICS2010/​content/​paper/​Paper_35.pdf.

[5] Leandro Aolita, Christian Gogolin, Martin Kliesch, and Jens Eisert. Reliable quantum certification of photonic state preparations. Nature communications, 6, 2015. 10.1038/​ncomms9498.

[6] Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, and Alain Tapp. Authentication of quantum messages. In Foundations of Computer Science, 2002. Proceedings. The 43rd Annual IEEE Symposium on, pages 449–458. IEEE, 2002. 10.1109/​SFCS.2002.1181969.

[7] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. Architectures for quantum simulation showing a quantum speedup. Phys. Rev. X, 8: 021010, Apr 2018. 10.1103/​PhysRevX.8.021010.

[8] K. Binder and A. P. Young. Spin glasses: Experimental facts, theoretical concepts, and open questions. Rev. Mod. Phys., 58: 801–976, Oct 1986. 10.1103/​RevModPhys.58.801.

[9] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14 (6): 595, 2018. 10.1038/​s41567-018-0124-x.

[10] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. " quantum supremacy" and the complexity of random circuit sampling. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. 10.4230/​LIPIcs.ITCS.2019.15.

[11] Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Phys. Rev. A, 71: 022316, Feb 2005. 10.1103/​PhysRevA.71.022316.

[12] Michael Bremner, Ashley Montanaro, and Daniel Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters, 117, 8 2016a. ISSN 0031-9007. 10.1103/​PhysRevLett.117.080501.

[13] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2126): 459–472, feb 2011. ISSN 1364-5021. 10.1098/​rspa.2010.0301.

[14] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, Aug 2016b. 10.1103/​PhysRevLett.117.080501.

[15] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1: 8, April 2017. ISSN 2521-327X. 10.22331/​q-2017-04-25-8.

[16] Anne Broadbent. How to verify a quantum computation. Theory of Computing, 14 (11): 1–37, 2018. 10.4086/​toc.2018.v014a011.

[17] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on, pages 517–526. IEEE, 2009. 10.1109/​FOCS.2009.36.

[18] Iulia Buluta and Franco Nori. Quantum simulators. Science, 326 (5949): 108–111, 2009. ISSN 0036-8075. 10.1126/​science.1177838.

[19] Andrew M Childs, Debbie W Leung, and Michael A Nielsen. Unified derivations of measurement-based schemes for quantum computation. Physical Review A, 71 (3): 032318, 2005. 10.1103/​PhysRevA.71.032318.

[20] Marcus Cramer, Martin B Plenio, Steven T Flammia, Rolando Somma, David Gross, Stephen D Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomography. Nature communications, 1: 149, 2010. 10.1038/​ncomms1147.

[21] Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev. A, 80: 012304, Jul 2009. 10.1103/​PhysRevA.80.012304.

[22] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452–4505, 2002. 10.1063/​1.1499754.

[23] David P. DiVincenzo. The physical implementation of quantum computation. Fortschritte der Physik, 48 (9-11): 771–783, 2000. ISSN 1521-3978. 10.1002/​1521-3978(200009)48:9/​11<771::AID-PROP771>3.0.CO;2-E.

[24] Vedran Dunjko, Joseph F Fitzsimons, Christopher Portmann, and Renato Renner. Composable security of delegated quantum computation. In Advances in Cryptology–ASIACRYPT 2014, pages 406–425. Springer, 2014. 10.1007/​978-3-662-45608-8_22.

[25] Eddie Farhi. Quantum supremacy through the quantum approximate optimization algorithm. In APS Meeting Abstracts, 2017. URL http:/​/​​abs/​2017APS..MARA19004F.

[26] Samuele Ferracin, Theodoros Kapourniotis, and Animesh Datta. Reducing resources for verification of quantum computations. Phys. Rev. A, 98: 022323, Aug 2018. 10.1103/​PhysRevA.98.022323.

[27] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21 (6): 467–488, 1982. ISSN 1572-9575. 10.1007/​BF02650179.

[28] Joseph F Fitzsimons. Private quantum computation: an introduction to blind quantum computing and related protocols. npj Quantum Information, 3 (1): 23, 2017. 10.1038/​s41534-017-0025-3.

[29] Joseph F Fitzsimons and Elham Kashefi. Unconditionally verifiable blind quantum computation. Physical Review A, 96 (1): 012303, 2017. 10.1103/​PhysRevA.96.012303.

[30] Austin G Fowler and Kovid Goyal. Topological cluster state quantum computing. Quantum Information and Computation, 9 (9-10): 0721–0738, 2009. 10.26421/​QIC9.9-10.

[31] Keisuke Fujii. Quantum Computation with Topological Codes: from qubit to topological fault-tolerance, volume 8. Springer, 2015. 10.1007/​978-981-287-996-7.

[32] Keisuke Fujii. Noise threshold of quantum supremacy. 2016. URL https:/​/​​abs/​1610.03632.

[33] Keisuke Fujii and Masahito Hayashi. Verifiable fault tolerance in measurement-based quantum computation. Phys. Rev. A, 96: 030301, Sep 2017. 10.1103/​PhysRevA.96.030301.

[34] Keisuke Fujii and Tomoyuki Morimae. Commuting quantum circuits and complexity of ising partition functions. New Journal of Physics, 19 (3): 033003, 2017. 10.1088/​1367-2630/​aa5fdb.

[35] Takeshi Fukuhara, Adrian Kantian, Manuel Endres, Marc Cheneau, Peter Schausz, Sebastian Hild, David Bellem, Ulrich Schollwock, Thierry Giamarchi, Christian Gross, Immanuel Bloch, and Stefan Kuhr. Quantum dynamics of a mobile spin impurity. Nat Phys, 9 (4): 235–241, apr 2013. ISSN 1745-2473. 10.1038/​nphys2561.

[36] Xun Gao, Sheng-Tao Wang, and L.-M. Duan. Quantum Supremacy for Simulating a Translation-Invariant Ising Spin Model. Physical Review Letters, 118 (4): 040502, jan 2017. ISSN 0031-9007. 10.1103/​PhysRevLett.118.040502.

[37] I. M. Georgescu, S. Ashhab, and Franco Nori. Quantum simulation. Rev. Mod. Phys., 86: 153–185, Mar 2014. 10.1103/​RevModPhys.86.153.

[38] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi. Verification of quantum computation: An overview of existing approaches. Theory of computing systems, pages 1–94, 2018. 10.1007/​s00224-018-9872-3.

[39] Leslie Ann Goldberg and Heng Guo. The complexity of approximating complex-valued ising and tutte partition functions. Computational Complexity, 26 (4): 765–833, 2017. 10.1007/​s00037-017-0162-2.

[40] D Hangleiter, M Kliesch, M Schwarz, and J Eisert. Direct certification of a class of quantum simulations. Quantum Science and Technology, 2 (1): 015004, mar 2017. ISSN 2058-9565. 10.1088/​2058-9565/​2/​1/​015004.

[41] Aram W. Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, sep 2017. ISSN 0028-0836. 10.1038/​nature23458.

[42] Masahito Hayashi and Tomoyuki Morimae. Verifiable measurement-only blind quantum computing with stabilizer testing. Phys. Rev. Lett., 115: 220502, Nov 2015. 10.1103/​PhysRevLett.115.220502.

[43] M. Hein, J. Eisert, and H. J. Briegel. Multiparty entanglement in graph states. Phys. Rev. A, 69: 062311, Jun 2004. 10.1103/​PhysRevA.69.062311.

[44] Ernst Ising. Beitrag zur theorie des ferromagnetismus. Zeitschrift für Physik A Hadrons and Nuclei, 31 (1): 253–258, 1925.

[45] Theodoros Kapourniotis, Elham Kashefi, and Animesh Datta. Blindness and verification of quantum computation with one pure qubit. In LIPIcs-Leibniz International Proceedings in Informatics, volume 27. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014. 10.4230/​LIPIcs.TQC.2014.176.

[46] Theodoros Kapourniotis, Vedran Dunjko, and Elham Kashefi. On optimising quantum communication in verifiable quantum computing, 2015. In Proceedings of the 15th Asian Quantum Information Science Conference (AQISC 2015), Seoul, Korea, pages 25–28, 2015. URL https:/​/​​file/​d/​0BxR7G6Hj7VPtZ2Y4cHQ1aDcxRlU/​view.

[47] Elham Kashefi and Petros Wallden. Optimised resource construction for verifiable quantum computation. Journal of Physics A: Mathematical and Theoretical, 50 (14): 145306, 2017. 10.1088/​1751-8121/​aa5dac.

[48] J Kelly, R Barends, A G Fowler, A Megrant, E Jeffrey, T C White, D Sank, J Y Mutus, B Campbell, Yu Chen, Z Chen, B Chiaro, A Dunsworth, I.-C. Hoi, C Neill, et al. State preservation by repetitive error detection in a superconducting quantum circuit. Nature, 519 (7541): 66–69, mar 2015. ISSN 0028-0836. 10.1038/​nature14270.

[49] T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, et al. Entanglement in a quantum annealing processor. Phys. Rev. X, 4: 021041, May 2014. 10.1103/​PhysRevX.4.021041.

[50] Ludovico Latmiral, Nicolò Spagnolo, and Fabio Sciarrino. Towards quantum supremacy with lossy scattershot boson sampling. New Journal of Physics, 18 (11): 113008, 2016. 10.1088/​1367-2630/​18/​11/​113008.

[51] T. D. Lee and C. N. Yang. Statistical theory of equations of state and phase transitions. ii. lattice gas and ising model. Phys. Rev., 87: 410–419, Aug 1952. 10.1103/​PhysRev.87.410.

[52] U. Mahadev. Classical verification of quantum computations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 259–267, Oct 2018. 10.1109/​FOCS.2018.00033.

[53] Atul Mantri, Tommaso F Demarie, and Joseph F Fitzsimons. Universality of quantum computation with cluster states and (x, y)-plane measurements. Scientific reports, 7: 42861, 2017. 10.1038/​srep42861.

[54] Damian Markham and Alexandra Krause. A simple protocol for certifying graph states and applications in quantum networks. arXiv preprint arXiv:1801.05057, 2018. URL https:/​/​​abs/​1801.05057.

[55] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham. Efficient quantum pseudorandomness with simple graph states. Phys. Rev. A, 97: 022333, Feb 2018. 10.1103/​PhysRevA.97.022333.

[56] Jacob Miller, Stephen Sanders, and Akimasa Miyake. Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification. Physical Review A, 96 (6): 062320, 2017. 10.1103/​PhysRevA.96.062320.

[57] Daniel Mills, Anna Pappa, Theodoros Kapourniotis, and Elham Kashefi. Information theoretically secure hypothesis test for temporally unstructured quantum computation. QPL/​IQSA, 2017. URL https:/​/​​papers/​QPL_2017_paper_42.pdf.

[58] Tomoyuki Morimae. Hardness of classically sampling the one-clean-qubit model with constant total variation distance error. Physical Review A, 96 (4): 040302, 2017. 10.1103/​PhysRevA.96.040302.

[59] Tomoyuki Morimae and Takeshi Koshiba. Impossibility of secure cloud quantum computing for classical client. Quantum Information and Computation 19, 0214-0221, 2019. 10.26421/​QIC19.3-4.

[60] Sam Pallister, Noah Linden, and Ashley Montanaro. Optimal verification of entangled states with local measurements. Physical review letters, 120 (17): 170502, 2018. 10.1103/​PhysRevLett.120.170502.

[61] Borja Peropadre, Alan Aspuru-Guzik, and Juan Jose Garcia-Ripoll. Spin models and boson sampling. 2015. URL https:/​/​​abs/​1509.02703.

[62] John Preskill. Quantum computing and the entanglement frontier. 2012. URL https:/​/​​abs/​1203.5813.

[63] R Raussendorf, J Harrington, and K Goyal. Topological fault-tolerance in cluster state quantum computation. New Journal of Physics, 9 (6): 199, 2007. 10.1088/​1367-2630/​9/​6/​199.

[64] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Phys. Rev. Lett., 86: 5188–5191, May 2001. 10.1103/​PhysRevLett.86.5188.

[65] Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496 (7446): 456–460, 2013. 10.1038/​nature12035.

[66] Lucile Savary and Leon Balents. Quantum spin liquids: a review. Reports on Progress in Physics, 80 (1): 016502, 2017. 10.1088/​0034-4885/​80/​1/​016502.

[67] Dan Shepherd and Michael J Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 465 (2105): 1413–1439, 2009. ISSN 1364-5021. 10.1098/​rspa.2008.0443.

[68] Justin B Spring, Benjamin J Metcalf, Peter C Humphreys, W Steven Kolthammer, Xian-Min Jin, Marco Barbieri, Animesh Datta, Nicholas Thomas-Peter, Nathan K Langford, Dmytro Kundys, James C Gates, Brian J Smith, Peter G R Smith, and Ian A Walmsley. Boson sampling on a photonic chip. Science (New York, N.Y.), 339 (6121): 798–801, feb 2013. ISSN 1095-9203. 10.1126/​science.1231692.

[69] Larry Stockmeyer. On Approximation Algorithms for # P. SIAM Journal on Computing, 14 (4): 849–861, nov 1985. ISSN 0097-5397. 10.1137/​0214060.

[70] B.M. Terhal and D.V. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games. Quantum Information and Computation, 4 (2): 134 – 45, 2004. ISSN 1533-7146. 10.26421/​QIC4.2.

Cited by

[1] Kazuki Akimoto, Shunji Tsuchiya, Ryosuke Yoshii, and Yuki Takeuchi, "Passive verification protocol for thermal graph states", Physical Review A 106 1, 012405 (2022).

[2] Samuele Ferracin, Theodoros Kapourniotis, and Animesh Datta, "Accrediting outputs of noisy intermediate-scale quantum computing devices", New Journal of Physics 21 11, 113038 (2019).

[3] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", Physical Review Research 2 3, 033444 (2020).

[4] Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi, and Damian Markham, "Efficient verification of Boson Sampling", Quantum 5, 578 (2021).

[5] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).

[6] Dominik Leichtle, Luka Music, Elham Kashefi, and Harold Ollivier, "Verifying BQP Computations on Noisy Devices with Minimal Overhead", PRX Quantum 2 4, 040302 (2021).

[7] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, and Hartmut Neven, "Simulation of low-depth quantum circuits as complex undirected graphical models", arXiv:1712.05384, (2017).

[8] Yuki Takeuchi and Tomoyuki Morimae, "Verification of Many-Qubit States", Physical Review X 8 2, 021060 (2018).

[9] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert, "Anticoncentration theorems for schemes showing a quantum speedup", Quantum 2, 65 (2018).

[10] Jacob Miller, Stephen Sanders, and Akimasa Miyake, "Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification", Physical Review A 96 6, 062320 (2017).

[11] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi, "Verification of quantum computation: An overview of existing approaches", arXiv:1709.06984, (2017).

[12] Samuele Ferracin, Theodoros Kapourniotis, and Animesh Datta, "Reducing resources for verification of quantum computations", Physical Review A 98 2, 022323 (2018).

[13] Alexandru Gheorghiu, Matty J. Hoban, and Elham Kashefi, "A simple protocol for fault tolerant verification of quantum computation", Quantum Science and Technology 4 1, 015009 (2019).

[14] Daniel Mills, Anna Pappa, Theodoros Kapourniotis, and Elham Kashefi, "Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)", arXiv:1803.00706, (2018).

The above citations are from Crossref's cited-by service (last updated successfully 2024-03-02 13:11:12) and SAO/NASA ADS (last updated successfully 2024-03-02 13:11:13). The list may be incomplete as not all publishers provide suitable and complete citation data.