Verification of Quantum Computation: An Overview of Existing Approaches
Open accessThe DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Abstract
Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification , has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Proposed Experiment to Test Local Hidden-Variable Theories
Clauser, J. F., Horne, M. A., Shimony, A., & Holt, R. A. (1969) · Physical Review Letters · doi:10.1103/physrevlett.23.880 · Cited by 7,573 · cited 1×
“not allowed to communicate during the game, however they are allowed to share classical or quantum correlations (in the form of entangled states). This denes a non-local game known as the CHSH game [72]. The optimal classical strategy for winning the game achieves a success probability of 75%, whereas, what Tsirelson…”
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806 · cited 1×
“pendence on the prover’s strategy and whether or not this strategy is the ideal one. 18 the nal measurement). To match Denition 2, one also considers: P incorrect= (ICj xihxjCy) j+ t ih+ t j (41) to be the projection onto the orthogonal complement of the correct output together with the trap state being projected onto…”
BackgroundRaussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904
Beitrag zur Theorie des Ferromagnetismus
Ising, E. (1925) · Zeitschrift für Physik · doi:10.1007/bf02980577 · Cited by 3,871 · cited 1×
“rived from VUBQC was introduced in [88] for a model known as the Ising spin sampler. This is based on the Ising model, which describes a lattice of interacting spins in the presence of a magnetic eld [89]. The Ising spin sampler is a translation invariant Ising model in which one measures the spins thus obtaining samp…”
MethodGottesman, D., & Chuang, I. L. (1999) · Nature · doi:10.1038/46503 · Cited by 1,860 · cited 1×
“This manner of performing gates is known as gate teleportation [55].”
BackgroundQuantum generalizations of Bell's inequality
Cirel'son, B. S. (1980) · Letters in Mathematical Physics · doi:10.1007/bf00417500 · Cited by 1,788
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284
Characterizing quantum supremacy in near-term devices
Boixo, S., Isakov, S. V., Smelyanskiy, V. N., Babbush, R., Ding, N., Jiang, Z., Bremner, M. J., Martinis, J. M., & Neven, H. (2018) · Nature Physics · doi:10.1038/s41567-018-0124-x · Cited by 1,175
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090 · cited 1×
“Since some of the protocols we review are expressed in the model of measurementbased quantum computation (MBQC), defined in [109, 110], we provide a brief description of this model.”
MethodThe computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Experimental Quantum Computing without Entanglement
Lanyon, B. P., Barbieri, M., Almeida, M. P., & White, A. G. (2008) · Physical Review Letters · doi:10.1103/physrevlett.101.200501 · Cited by 874 · cited 1×
“t(Enc s(j ih j jaccihaccj))) (8) We say that such a protocol is -veriable (with 0 1), if for any action P, of the prover, we have that16: Tr X s p(s)Ps incorrect P(Enc s(j ih j jaccihaccj)) ! (9) Essentially, this denition says that the probability for the output of the protocol to be incorrect and the verier acceptin…”
BackgroundExponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825 · cited 1×
“In fact, there are candidate problems known to be in both BQP and MA, for which computing the witness is believed to not be in BQP (a conjectured example is [18]).”
BackgroundSimple unified form for the major no-hidden-variables theorems
Mermin, N. D. (1990) · Physical Review Letters · doi:10.1103/physrevlett.65.3373 · Cited by 753
Tillmann, M., Dakić, B., Heilmann, R., Nolte, S., Szameit, A., & Walther, P. (2013) · Nature Photonics · doi:10.1038/nphoton.2013.102 · Cited by 709
The Complexity of the Local Hamiltonian Problem
Kempe, J., Kitaev, A., & Regev, O. (2006) · SIAM Journal on Computing · doi:10.1137/s0097539704445226 · Cited by 648
Universal Blind Quantum Computation
Broadbent, A., Fitzsimons, J., & Kashefi, E. (2009) · 2009 50th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.36 · Cited by 521
Self-citationFault-Tolerant Quantum Computation with Constant Error Rate
Aharonov, D., & Ben-Or, M. (2008) · SIAM Journal on Computing · doi:10.1137/s0097539799359385 · Cited by 513 · cited 1×
“it to a single round of quantum messages sent at the beginning of the protocol. To encode the input, this protocol uses a specic type of quantum error correcting code known as a polynomial CSS code [54]. We will not elaborate on the technical details of these codes as that is beyond the scope of this review. We only m…”
MethodDemonstration of Blind Quantum Computing
Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J. F., Zeilinger, A., & Walther, P. (2012) · Science · doi:10.1126/science.1214707 · Cited by 475
Self-citationA fault-tolerant one-way quantum computer
Raussendorf, R., Harrington, J., & Goyal, K. (2006) · Annals of Physics · doi:10.1016/j.aop.2006.01.012 · Cited by 397
Experimental validation of photonic boson sampling
Spagnolo, N., Vitelli, C., Bentivegna, M., Brod, D. J., Crespi, A., Flamini, F., Giacomini, S., Milani, G., Ramponi, R., Mataloni, P., et al. (2014) · Nature Photonics · doi:10.1038/nphoton.2014.135 · Cited by 312 · cited 1×
“ally, dene: Ps incorrect= (Ij s out ih s out j) jaccsihaccsj (6) as a projection onto the orthogonal complement of the correct output: j#TAB#s out ih s out j= Tr flag(P honest(Enc s(j ih j jaccihaccj))) (7) and on acceptance for the ag state: jaccsihaccsj= Tr input(P honest(Enc s(j ih j jaccihaccj))) (8) We say that s…”
BackgroundClassical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Bremner, M. J., Jozsa, R., & Shepherd, D. J. (2011) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2010.0301 · Cited by 308 · cited 16×
“Another test of IQP problems is provided by the Hangleiter et al approach, from Subsection 3.2 [31].”
BackgroundInfluentialExperimental scattershot boson sampling
Bentivegna, M., Spagnolo, N., Vitelli, C., Flamini, F., Viggianiello, N., Latmiral, L., Mataloni, P., Brod, D. J., Galvão, E. F., Crespi, A., et al. (2015) · Science Advances · doi:10.1126/sciadv.1400255 · Cited by 239
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
Aaronson, S., & Chen, L. (2016) · arXiv · doi:10.48550/arxiv.1612.05903 · Cited by 218
An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
Gottesman, D. (2009) · arXiv · doi:10.48550/arxiv.0904.2557 · Cited by 129
Cited by
Quantum simulation and computing with Rydberg-interacting qubits
Morgado, M., & Whitlock, S. (2021) · AVS Quantum Science · doi:10.1116/5.0036562 · Cited by 370
Self-testing of quantum systems: a review
Šupić, I., & Bowles, J. (2020) · Quantum · doi:10.22331/q-2020-09-30-337 · Cited by 365
Quantum certification and benchmarking
Eisert, J., Hangleiter, D., Walk, N., Roth, I., Markham, D., Parekh, R., Chabaud, U., & Kashefi, E. (2020) · Nature Reviews Physics · doi:10.1038/s42254-020-0186-4 · Cited by 342
Self-citationBiology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
Pednault, E., Gunnels, J. A., Nannicini, G., Horesh, L., Magerlein, T., Solomonik, E., Draeger, E. W., Holland, E. T., & Wisnieff, R. (2017) · arXiv · doi:10.48550/arxiv.1710.05867 · Cited by 48
Metadata
- Authors
- Gheorghiu, A., Kapourniotis, T., & Kashefi, E.
- Venue
- Theory of Computing Systems
- Published
- 2018-07-06
- Volume
- 63
- Issue
- 4
- Pages
- 715-808
- ISSN
- 0025-5661 (ISSN-L)
- 1432-4350
- 1433-0490
- OpenAlex
- W2758002822
- Cited by
- 166
- References
- 28
- FWCI
- 9.90
- Type
- journal article
- Language
- en
- Open access
- hybrid
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.