Verification of quantum computation: An overview of existing approaches

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.

Published in Theory of Computing systems. 65 pages, 17 figures

References in corpus (21)

• Device-independent security of quantum cryptography against collective attacks
• Experimental quantum computing without entanglement
• Exponential algorithmic speedup by quantum walk
• Topological fault-tolerance in cluster state quantum computation
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Experimental Scattershot Boson Sampling
• Robust Self Testing of the Singlet
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
• Experimental Blind Quantum Computing for a Classical Client
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Interactive Proofs For Quantum Computations
• Measurement-Based Quantum Computation
• Quantum Fully Homomorphic Encryption With Verification
• Practical and efficient experimental characterization of multiqubit stabilizer states
• Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
• The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation
• New Limits on Fault-Tolerant Quantum Computation
• On optimising quantum communication in verifiable quantum computing
• Separation of finite and infinite-dimensional quantum correlations, with infinite question or answer sets
• Verified Delegated Quantum Computing with One Pure Qubit

Cited by in corpus (78)

• Self-testing of quantum systems: a review
• Quantum simulation and computing with Rydberg-interacting qubits
• Quantum certification and benchmarking
• Theory of quantum system certification: a tutorial
• Quantum Algorithmic Measurement
• Flexible entanglement-distribution network with an AlGaAs chip for secure communications
• Biology and medicine in the landscape of quantum advantages
• Theoretical and Experimental Perspectives of Quantum Verification
• Anonymity for practical quantum networks
• Benchmarking quantum computers
• Nonstabilizerness determining the hardness of direct fidelity estimation
• A Deductive Verification Framework for Circuit-building Quantum Programs
• Quantum quench dynamics in Dicke superradiance models
• Sublattice Coding Algorithm and Distributed Memory Parallelization for Large-Scale Exact Diagonalizations of Quantum Many-Body Systems
• Verifiable blind quantum computing with trapped ions and single photons
• Application-Motivated, Holistic Benchmarking of a Full Quantum Computing Stack
• Securing Quantum Computations in the NISQ Era
• Learning efficient decoders for quasi-chaotic quantum scramblers
• Accrediting outputs of noisy intermediate-scale quantum computing devices
• Efficient verification of Boson Sampling
• Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
• Cryptographic approach to Quantum Metrology
• Warm-Starting and Quantum Computing: A Systematic Mapping Study
• Robust and efficient verification of graph states in blind measurement-based quantum computation
• Quantum verification and estimation with few copies
• Reducing resources for verification of quantum computations
• An elegant proof of self-testing for multipartite Bell inequalities
• Efficient verification of continuous-variable quantum states and devices without assuming identical and independent operations
• QEnclave -- A practical solution for secure quantum cloud computing
• Quantum cryptography beyond key distribution: theory and experiment
• As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation
• Mitigating errors by quantum verification and post-selection
• Security Limitations of Classical-Client Delegated Quantum Computing
• Experimental verifiable multi-client blind quantum computing on a Qline architecture
• Client-friendly continuous-variable blind and verifiable quantum computing
• Quantum Metrology with Delegated Tasks
• Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors
• Benchmarks of Nonclassicality for Qubit Arrays
• Authenticated teleportation and verification in a noisy network
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• High-accuracy Hamiltonian learning via delocalized quantum state evolutions
• Collective Operations Can Exponentially Enhance Quantum State Verification
• Hardware requirements for trapped-ion based verifiable blind quantum computing with a measurement-only client
• Benchmarking Quantum Computers: Towards a Standard Performance Evaluation Approach
• A Specification Format and a Verification Method of Fault-Tolerant Quantum Circuits
• Cross-Platform Verification in Quantum Networks
• Optimal parent Hamiltonians for time-dependent states
• A Uniform Representation of Classical and Quantum Source Code for Static Code Analysis
• Benchmarking bosonic modes for quantum information with randomized displacements
• tqix: A toolbox for Quantum in X: Quantum measurement, quantum tomography, quantum metrology, and others
• Accreditation of Analogue Quantum Simulators
• Learning Properties of Quantum States Without the I.I.D. Assumption
• Trie-based ranking of quantum many-body states
• Selective Quantum State Tomography
• A survey of universal quantum von Neumann architecture
• Methods for Classically Simulating Noisy Networked Quantum Architectures
• Trusted center verification model and classical channel remote state preparation
• Multi-agent blind quantum computation without universal cluster states
• Analogue Quantum Simulation: A Philosophical Prospectus
• Experimental Implementation of an Efficient Test of Quantumness
• Benchmarks for quantum computers from Shor's algorithm
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Blindly Factorizing 21 Quantumly
• Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
• Quantum Software Ecosystem Design
• Certifying Temporal Correlations
• Practical parallel self-testing of Bell states via magic rectangles
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Building trust for continuous variable quantum states
• Quantum Proofs of Proximity
• Sampling and the complexity of nature
• Determining non-Hermitian parent Hamiltonian from a single eigenstate
• Inserting Planar-Measured Qubits into MBQC Patterns while Preserving Flow
• Beating the Optimal Verification of Entangled States via Collective Strategies
• Partial Blind Quantum Computation: A Framework for Selective Circuit Protection
• Bounded-Error Quantum Simulation via Hamiltonian and Lindbladian Learning
• Accreditation Against Limited Adversarial Noise
• Efficient verification and fidelity estimation of discrete bipartite squeezed states