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
Quantum 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
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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Verification of Quantum Computation: An Overview of Existing Approaches. https://app.cochat.ai/papers/10.1007/s00224-018-9872-3
- The paper
- Gheorghiu, A., Kapourniotis, T., & Kashefi, E. (2019). Verification of Quantum Computation: An Overview of Existing Approaches. Theory of Computing Systems. https://doi.org/10.1007/s00224-018-9872-3
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.