Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit

Noah Linden; Ronald de Wolf

doi:10.22331/q-2021-04-20-436

Lightweight Detection of a Small Number of Large Errors in a Quantum Circuit

Noah Linden¹ and Ronald de Wolf²

¹School of Mathematics, University of Bristol
²QuSoft, CWI and University of Amsterdam, the Netherlands

Published:	2021-04-20, volume 5, page 436
Eprint:	arXiv:2009.08840v3
Doi:	https://doi.org/10.22331/q-2021-04-20-436
Citation:	Quantum 5, 436 (2021).

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

Abstract

Suppose we want to implement a unitary $U$, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary $\tilde{U}$, which we can only apply as a black-box. In general it is an exponentially-hard task to decide whether $\tilde{U}$ equals the intended $U$, 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$ and $\tilde{U}$ (both of which we can now apply as a black-box) are either equal, or differ significantly in only one $k$-qubit gate, where $k=O(1)$ (the $k$ qubits need not be contiguous). Second, we give an even more lightweight procedure under the assumption that $U$ and $\tilde{U}$ are $\textit{Clifford}$ circuits which are either equal, or different in arbitrary ways (the specification of $U$ is now classically given while $\tilde{U}$ can still only be applied as a black-box). Both procedures only need to run $\tilde{U}$ 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) $\tilde{U}$ if we have a small list of possible errors that could have happened to $U$; for example if we know that only $O(1)$ of the gates of $\tilde{U}$ are wrong, this list will be polynomially small and we can test each possible erroneous version of $U$ for equality with $\tilde{U}$.

Popular summary

Suppose we want to implement a unitary $U$, for instance a circuit for some quantum algorithm. Suppose our actual implementation is a unitary $\tilde{U}$, which we can only apply as a black-box (i.e. we only have access to the input and output). In general it is an exponentially-hard task to decide whether the output state from $\tilde{U}$ is close to that for the intended $U$ for all input states, or whether there are input states for which the output state from $\tilde{U}$ is significantly different from that from $U$. In this paper we consider two special cases where we can in fact provide relatively efficient and lightweight procedures for this discrimination task: (1) when $U$ and $\tilde{U}$ can use arbitrary gates but only differ in one gate on a constant number of (not necessarily neighbouring) qubits, and (2) when $U$ and $\tilde{U}$ are Clifford circuits.

► BibTeX data

@article{Linden2021lightweight,
  doi = {10.22331/q-2021-04-20-436},
  url = {https://doi.org/10.22331/q-2021-04-20-436},
  title = {Lightweight {D}etection of a {S}mall {N}umber of {L}arge {E}rrors in a {Q}uantum {C}ircuit},
  author = {Linden, Noah and de Wolf, Ronald},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {436},
  month = apr,
  year = {2021}
}

► References

[1] Dorit Aharonov and Michael Ben-Or. Fault tolerant quantum computation with constant error rate. SIAM Journal on Computing, 38(4):1207–1282, 2008. Earlier version in STOC'97. quant-ph/9611025.
https://doi.org/10.1137/S0097539799359385
arXiv:quant-ph/9611025

[2] 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–180, 2020. arxiv:1911.08101.
https://doi.org/10.1007/978-3-030-64381-2_6
arXiv:1911.08101

[3] Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of 30th ACM STOC, pages 10–20, 1998. quant-ph/9806029.
https://doi.org/10.1145/276698.276708
arXiv:quant-ph/9806029

[4] Frank Arute, ..., and John Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574:505–510, 2019. arxiv:1910.11333.
https://doi.org/10.1038/s41586-019-1666-5
arXiv:1910.11333

[5] Pablo Arrighi and Louis Salvail. Blind quantum computation. International Journal of Quantum Information, 4(05):883–898, 2006. quant-ph/0309152.
https://doi.org/10.1142/S0219749906002171
arXiv:quant-ph/0309152

[6] Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing, 26(5):1510–1523, 1997. quant-ph/9701001.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001

[7] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, September 26, 2001. quant-ph/0102001.
https://doi.org/10.1103/PhysRevLett.87.167902
arXiv:quant-ph/0102001

[8] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. Universal blind quantum computation. In Proceedings of 50th IEEE FOCS, pages 517–526, 2009. quant-ph/0807.4154.
https://doi.org/10.1109/FOCS.2009.36
arXiv:0807.4154

[9] Gilles Brassard, Peter Høyer, 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–74. 2002. quant-ph/0005055.
https://doi.org/10.1090/conm/305/05215
arXiv:quant-ph/0005055

[10] 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–772, 2021. arxiv:2011.07288.
https://doi.org/10.1145/3394885.3431590
arXiv:2011.07288

[11] 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.
https://doi.org/10.1103/PhysRevA.80.012304
arXiv:quant-ph/0606161

[12] Wim van Dam, Frédéric Magniez, Michele Mosca, and Miklos Santha. Self-testing of universal and fault-tolerant sets of quantum gates. SIAM Journal on Computing, 37(2):611–629, 2007. Earlier version in STOC'00. quant-ph/9904108.
https://doi.org/10.1137/S0097539702404377
arXiv:quant-ph/9904108

[13] 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.
https://doi.org/10.1103/PhysRevLett.107.210404
arXiv:1104.3835

[14] Joseph Emerson, Robert Alicki, and Karol Życzkowski. Scalable noise estimation with random unitary operators. Journal of Optics B: Quantum and Semiclassical Optics, 7(10):S347, 2005. quant-ph/0503243.
https://doi.org/10.1088/1464-4266/7/10/021
arXiv:quant-ph/0503243

[15] 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–390, 2020. arxiv:1910.06343.
https://doi.org/10.1038/s42254-020-0186-4
arXiv:1910.06343

[16] Andreas Elben, Benoı̂t 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.
https://doi.org/10.1103/PhysRevLett.124.010504
arXiv:1909.01282

[17] Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106:230501, 2011. arxiv:1104.4695.
https://doi.org/10.1103/PhysRevLett.106.230501
arXiv:1104.4695

[18] Rusins Freivalds. Probabilistic machines can use less running time. In Proceedings of 7th IFIP Congress, pages 839–842, 1977.

[19] David Gross. Hudson's theorem for finite-dimensional quantum systems. Journal of Mathematical Physics, 47:122107, 2006. quant-ph/0602001.
https://doi.org/10.1063/1.2393152
arXiv:quant-ph/0602001

[20] Paweł Horodecki, Michał Horodecki, and Ryszard Horodecki. General teleportation channel, singlet fraction and quasi-distillation. Physical Review A, 60:1888, 1999. quant-ph/9807091.
https://doi.org/10.1103/PhysRevA.60.1888
arXiv:quant-ph/9807091

[21] Aram W. Harrow and Andreas Winter. How many copies are needed for state discrimination? IEEE Transactions on Information Theory, 58(1):1–2, 2012. quant-ph/0606131.
https://doi.org/10.1109/TIT.2011.2169544
arXiv:quant-ph/0606131

[22] Richard Jozsa. Unpublished note, 2017.

[23] Richard Jozsa and Sergii Strelchuk. Efficient classical verification of quantum computations. arxiv:1705.02817, 8 May 2017.
arXiv:1705.02817

[24] 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.
https://doi.org/10.1103/PhysRevLett.117.170502
arXiv:1510.05653

[25] 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.
https://doi.org/10.22331/q-2019-05-13-140
arXiv:1807.00800

[26] 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–6):361–376, 2010. Earlier version in ICALP'08. arxiv:0802.1464.
arXiv:0802.1464

[27] 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.
https://doi.org/10.1063/1.4903507
arXiv:1406.2170

[28] Richard A. Low. Learning and testing algorithms for the Clifford group. Physical Review A, 80:052314, 2009. arxiv:0907.2833.
https://doi.org/10.1103/PhysRevA.80.052314
arXiv:0907.2833

[29] Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259–267, 2018. arxiv:1804.01082.
https://doi.org/10.1109/FOCS.2018.00033
arXiv:1804.01082

[30] Easwar Magesan, Jay M. Gambetta, and Joseph Emerson. Characterizing quantum gates via randomized benchmarking. Physical Review A, 85:042311, 2012. arxiv:1109.6887.
https://doi.org/10.1103/PhysRevA.85.042311
arXiv:1109.6887

[31] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory of Computing, 2016. ToC Library, Graduate Survey. arxiv:1310.2035.
https://doi.org/10.4086/toc.gs.2016.007
arXiv:1310.2035

[32] Michael A. Nielsen. A simple formula for the average gate fidelity of a quantum dynamical operation. Physical Letters A, 303(4):249–252, 2002. quant-ph/0205035.
https://doi.org/10.1016/S0375-9601(02)01272-0
arXiv:quant-ph/0205035

[33] 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.
https://doi.org/10.1103/PhysRevLett.119.130502
arXiv:1702.01853

[34] Joel J. Wallman. Error rates in quantum circuits, 2015. arxiv:1511.00727.
arXiv:1511.00727

[35] John Watrous. Quantum computational complexity. In Encyclopedia of Complexity and Systems Science. Springer, 2009. arxiv:0804.3401.
https://doi.org/10.1007/978-0-387-30440-3_428
arXiv:0804.3401

[36] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.
https://doi.org/10.1017/9781316848142

[37] Joel J. Wallman and Joseph Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94:052325, 2016. arxiv:1512.01098.
https://doi.org/10.1103/PhysRevA.94.052325
arXiv:1512.01098

Cited by

[1] Lukas Burgholzer, Robert Wille, and Richard Kueng, "Characteristics of reversible circuits for error detection", Array 14, 100165 (2022).

[2] Dimitrios Thanos, Tim Coopmans, and Alfons Laarman, Lecture Notes in Computer Science 14216, 199 (2023) ISBN:978-3-031-45331-1.

[3] Noah Linden and Ronald de Wolf, "Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation", Quantum 6, 872 (2022).

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

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.