{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:30:15Z","timestamp":1762918215053},"reference-count":37,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T00:00:00Z","timestamp":1618876800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"UK Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/R043957\/1, EP\/S005021\/1, EP\/T001062\/1"],"award-info":[{"award-number":["EP\/R043957\/1, EP\/S005021\/1, EP\/T001062\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ERC","award":["ERC Consolidator Grant 615307-QPROGRESS"],"award-info":[{"award-number":["ERC Consolidator Grant 615307-QPROGRESS"]}]},{"name":"NWO","award":["Gravitation-grant Quantum Software Consortium, 024.003.037, and QuantERA ERA-NET Cofund project QuantAlgo 680-91-034"],"award-info":[{"award-number":["Gravitation-grant Quantum Software Consortium, 024.003.037, and QuantERA ERA-NET Cofund project QuantAlgo 680-91-034"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Suppose we want to implement a unitary U<\/mml:mi><\/mml:math>, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math>, which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> equals the intended U<\/mml:mi><\/mml:math>, or is significantly different in a worst-case norm. In this paper we consider two special cases where relatively efficient and lightweight procedures exist for this task.First, we give an efficient procedure under the assumption that U<\/mml:mi><\/mml:math> and U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> (both of which we can now apply as a black-box) are either equal, or differ significantly in only one k<\/mml:mi><\/mml:math>-qubit gate, where k<\/mml:mi>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math> (the k<\/mml:mi><\/mml:math> qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that U<\/mml:mi><\/mml:math> and U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> are Clifford<\/mml:mtext><\/mml:mrow><\/mml:math> circuits which are either equal, or different in arbitrary ways (the specification of U<\/mml:mi><\/mml:math> is now classically given while U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> can still only be applied as a black-box). Both procedures only need to run U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> a constant number of times to detect a constant error in a worst-case norm. We note that the Clifford result also follows from earlier work of Flammia and Liu, and da Silva, Landon-Cardinal, and Poulin.In the Clifford case, our error-detection procedure also allows us efficiently to learn (and hence correct) U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> if we have a small list of possible errors that could have happened to U<\/mml:mi><\/mml:math>; for example if we know that only O<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math> of the gates of U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math> are wrong, this list will be polynomially small and we can test each possible erroneous version of U<\/mml:mi><\/mml:math> for equality with U<\/mml:mi>~<\/mml:mo><\/mml:mover><\/mml:mrow><\/mml:math>.<\/jats:p>","DOI":"10.22331\/q-2021-04-20-436","type":"journal-article","created":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T14:43:55Z","timestamp":1618929835000},"page":"436","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit"],"prefix":"10.22331","volume":"5","author":[{"given":"Noah","family":"Linden","sequence":"first","affiliation":[{"name":"School of Mathematics, University of Bristol"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronald","family":"de Wolf","sequence":"additional","affiliation":[{"name":"QuSoft, CWI and University of Amsterdam, the Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2021,4,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov and Michael Ben-Or. Fault tolerant quantum computation with constant error rate. SIAM Journal on Computing, 38(4):1207\u20131282, 2008. Earlier version in STOC'97. quant-ph\/9611025.","DOI":"10.1137\/S0097539799359385"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Gorjan Alagic, Andrew M. Childs, Alex B. Grilo, and Shih-Han Hung. Non-interactive classical verification of quantum computation. In Proceedings of 18 International Conference on Theory of Cryptography (TCC), volume 3, pages 153\u2013180, 2020. arxiv:1911.08101.","DOI":"10.1007\/978-3-030-64381-2_6"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of 30th ACM STOC, pages 10\u201320, 1998. quant-ph\/9806029.","DOI":"10.1145\/276698.276708"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Frank Arute, ..., and John Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574:505\u2013510, 2019. arxiv:1910.11333.","DOI":"10.1038\/s41586-019-1666-5"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Pablo Arrighi and Louis Salvail. Blind quantum computation. International Journal of Quantum Information, 4(05):883\u2013898, 2006. quant-ph\/0309152.","DOI":"10.1142\/S0219749906002171"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510\u20131523, 1997. quant-ph\/9701001.","DOI":"10.1137\/S0097539796300933"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, September 26, 2001. quant-ph\/0102001.","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Proceedings of 50th IEEE FOCS, pages 517\u2013526, 2009. quant-ph\/0807.4154.","DOI":"10.1109\/FOCS.2009.36"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter H\u00f8yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series, pages 53\u201374. 2002. quant-ph\/0005055.","DOI":"10.1090\/conm\/305\/05215"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Lukas Burgholzer, Richard Kueng, and Robert Wille. Random stimuli generation for the verification of quantum circuits. In Proceedings of the 26th Asia and South Pacific Design Automation Conference, pages 767\u2013772, 2021. arxiv:2011.07288.","DOI":"10.1145\/3394885.3431590"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A, 80:012304, 2009. quant-ph\/0606161.","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Wim van Dam, Fr\u00e9d\u00e9ric Magniez, Michele Mosca, and Miklos Santha. Self-testing of universal and fault-tolerant sets of quantum gates. SIAM Journal on Computing, 37(2):611\u2013629, 2007. Earlier version in STOC'00. quant-ph\/9904108.","DOI":"10.1137\/S0097539702404377"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Marcus da Silva, Oliver Landon-Cardinal, and David Poulin. Practical characterization of quantum devices without tomography. Physical Review Letters, 107:210404, 2011. arxiv:1104.3835.","DOI":"10.1103\/PhysRevLett.107.210404"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Joseph Emerson, Robert Alicki, and Karol \u017byczkowski. Scalable noise estimation with random unitary operators. Journal of Optics B: Quantum and Semiclassical Optics, 7(10):S347, 2005. quant-ph\/0503243.","DOI":"10.1088\/1464-4266\/7\/10\/021"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi. Quantum certification and benchmarking. Nature Reviews Physics, 2:382\u2013390, 2020. arxiv:1910.06343.","DOI":"10.1038\/s42254-020-0186-4"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Andreas Elben, Beno\u0131\u0302t Vermersch, Rick van Bijnen, Christian Kokail, Tiff Brydges, Christine Maier, Manoj K. Joshi, Rainer Blatt, Christian F. Roos, and Peter Zoller. Cross-platform verification of intermediate scale quantum devices. Physical Review Letters, 124:010504, 2020. arxiv:1909.01282.","DOI":"10.1103\/PhysRevLett.124.010504"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106:230501, 2011. arxiv:1104.4695.","DOI":"10.1103\/PhysRevLett.106.230501"},{"key":"17","unstructured":"Rusins Freivalds. Probabilistic machines can use less running time. In Proceedings of 7th IFIP Congress, pages 839\u2013842, 1977."},{"key":"18","doi-asserted-by":"publisher","unstructured":"David Gross. Hudson's theorem for finite-dimensional quantum systems. Journal of Mathematical Physics, 47:122107, 2006. quant-ph\/0602001.","DOI":"10.1063\/1.2393152"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Pawe\u0142 Horodecki, Micha\u0142 Horodecki, and Ryszard Horodecki. General teleportation channel, singlet fraction and quasi-distillation. Physical Review A, 60:1888, 1999. quant-ph\/9807091.","DOI":"10.1103\/PhysRevA.60.1888"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Aram W. Harrow and Andreas Winter. How many copies are needed for state discrimination? IEEE Transactions on Information Theory, 58(1):1\u20132, 2012. quant-ph\/0606131.","DOI":"10.1109\/TIT.2011.2169544"},{"key":"21","unstructured":"Richard Jozsa. Unpublished note, 2017."},{"key":"22","unstructured":"Richard Jozsa and Sergii Strelchuk. Efficient classical verification of quantum computations. arxiv:1705.02817, 8 May 2017."},{"key":"23","doi-asserted-by":"publisher","unstructured":"Richard Kueng, David M. Long, Andrew C. Doherty, and Steven T. Flammia. Comparing experiments to the fault-tolerance threshold. Physical Review Letters, 117:170502, 2014. arxiv:1510.05653.","DOI":"10.1103\/PhysRevLett.117.170502"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T. Sornborge, and Patrick J. Coles. Quantum-assisted quantum compiling. Quantum, 3:140, 2019. arxiv:1807.00800.","DOI":"10.22331\/q-2019-05-13-140"},{"key":"25","doi-asserted-by":"crossref","unstructured":"Julia Kempe, Oded Regev, Falk Unger, and Ronald de Wolf. Upper bounds on the noise threshold for fault-tolerant quantum computing. Quantum Information and Computation, 10(5\u20136):361\u2013376, 2010. Earlier version in ICALP'08. arxiv:0802.1464.","DOI":"10.26421\/QIC10.5-6-1"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Robert Koenig and John A. Smolin. How to efficiently select an arbitrary Clifford group element. Journal of Mathematical Physics, 55:122202, 2014. arxiv:1406.2170.","DOI":"10.1063\/1.4903507"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Richard A. Low. Learning and testing algorithms for the Clifford group. Physical Review A, 80:052314, 2009. arxiv:0907.2833.","DOI":"10.1103\/PhysRevA.80.052314"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259\u2013267, 2018. arxiv:1804.01082.","DOI":"10.1109\/FOCS.2018.00033"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Characterizing quantum gates via randomized benchmarking. Physical Review A, 85:042311, 2012. arxiv:1109.6887.","DOI":"10.1103\/PhysRevA.85.042311"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory of Computing, 2016. ToC Library, Graduate Survey. arxiv:1310.2035.","DOI":"10.4086\/toc.gs.2016.007"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen. A simple formula for the average gate fidelity of a quantum dynamical operation. Physical Letters A, 303(4):249\u2013252, 2002. quant-ph\/0205035.","DOI":"10.1016\/S0375-9601(02)01272-0"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Timothy Proctor, Kenneth Rudinger, Kevin Young, Mohan Sarovar, and Robin Blume-Kohout. What randomized benchmarking actually measures. Physical Review Letters, 119:130502, 2017. arxiv:1702.01853.","DOI":"10.1103\/PhysRevLett.119.130502"},{"key":"33","unstructured":"Joel J. Wallman. Error rates in quantum circuits, 2015. arxiv:1511.00727."},{"key":"34","doi-asserted-by":"publisher","unstructured":"John Watrous. Quantum computational complexity. In Encyclopedia of Complexity and Systems Science. Springer, 2009. arxiv:0804.3401.","DOI":"10.1007\/978-0-387-30440-3_428"},{"key":"35","doi-asserted-by":"publisher","unstructured":"John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.","DOI":"10.1017\/9781316848142"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Joel J. Wallman and Joseph Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94:052325, 2016. arxiv:1512.01098.","DOI":"10.1103\/PhysRevA.94.052325"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-20-436\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,4,20]],"date-time":"2021-04-20T14:44:25Z","timestamp":1618929865000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-04-20-436\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,20]]},"references-count":37,"URL":"https:\/\/doi.org\/10.22331\/q-2021-04-20-436","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,20]]},"article-number":"436"}}