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

Noah Linden1 and Ronald de Wolf2

1School of Mathematics, University of Bristol
2QuSoft, CWI and University of Amsterdam, the Netherlands

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


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}$.

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

► 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.

[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.

[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.

[4] Frank Arute, ..., and John Martinis. Quantum supremacy using a programmable superconducting processor. Nature, 574:505–510, 2019. 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[17] Steven T. Flammia and Yi-Kai Liu. Direct fidelity estimation from few Pauli measurements. Physical Review Letters, 106:230501, 2011. 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.

[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.

[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.

[22] Richard Jozsa. Unpublished note, 2017.

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

[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.

[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.

[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.

[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.

[28] Richard A. Low. Learning and testing algorithms for the Clifford group. Physical Review A, 80:052314, 2009. arxiv:0907.2833.

[29] Urmila Mahadev. Classical verification of quantum computations. In Proceedings of 59th IEEE FOCS, pages 259–267, 2018. 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.

[31] Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory of Computing, 2016. ToC Library, Graduate Survey. 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.

[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.

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

[35] John Watrous. Quantum computational complexity. In Encyclopedia of Complexity and Systems Science. Springer, 2009. arxiv:0804.3401.

[36] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018.

[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.

Cited by

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

[2] Noah Linden and Ronald de Wolf, "Average-Case Verification of the Quantum Fourier Transform Enables Worst-Case Phase Estimation", arXiv:2109.10215.

The above citations are from Crossref's cited-by service (last updated successfully 2022-05-18 10:05:30) and SAO/NASA ADS (last updated successfully 2022-05-18 10:05:31). The list may be incomplete as not all publishers provide suitable and complete citation data.