Verification of quantum computation: An overview of existing approaches
arXiv:1709.06984 · doi:10.1007/s00224-018-9872-3
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.
arXiv commentPublished in Theory of Computing systems. 65 pages, 17 figures
References in corpus (66)
- Quantum Teleportation is a Universal Computational Primitive
- Device-independent security of quantum cryptography against collective attacks
- Measurement-based quantum computation with cluster states
- Characterizing Quantum Supremacy in Near-Term Devices
- Measurement-based quantum computation
- No Signalling and Quantum Key Distribution
- On the Power of One Bit of Quantum Information
- Experimental quantum computing without entanglement
- Exponential algorithmic speedup by quantum walk
- Experimental Boson Sampling
- In defense of the epistemic view of quantum states: a toy theory
- Topological fault-tolerance in cluster state quantum computation
- Experimental Demonstration of Blind Quantum Computing
- Universal blind quantum computation
- A fault-tolerant one-way quantum computer
- Einstein, incompleteness, and the epistemic view of quantum states
- Efficient experimental validation of photonic boson sampling against the uniform distribution
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Unconditionally verifiable blind computation
- Authentication of Quantum Messages
- Experimental Scattershot Boson Sampling
- Robust Self Testing of the Singlet
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- Instantaneous Quantum Computation
- Quantum computing on encrypted data
- An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
- Experimental verification of quantum computations
- Determinism in the one-way model
- The BQP-hardness of approximating the Jones Polynomial
- Architectures for quantum simulation showing a quantum speedup
- Experimental Blind Quantum Computing for a Classical Client
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Quantum one-time programs
- Interactive Proofs For Quantum Computations
- Post hoc verification with a single prover
- Post hoc verification of quantum computation
- Optimal Blind Quantum Computation
- Efficient universal blind computation
- Interactive proofs for BQP via self-tested graph states
- Demonstration of measurement-only blind quantum computing
- Composable security of delegated quantum computation
- Rigidity of quantum steering and one-sided device-independent verifiable quantum computation
- Direct certification of a class of quantum simulations
- Verified measurement-based quantum computing with hypergraph states
- Robust self-testing of many-qubit states
- How to Verify a Quantum Computation
- Verifiable fault-tolerance in measurement-based quantum computation
- Device-Independent Verifiable Blind Quantum Computation
- Optimised resource construction for verifiable quantum computation
- Quantum proofs can be verified using only single qubit measurements
- Measurement-Based Quantum Computation
- Succinct quantum proofs for properties of finite groups
- Quantum Fully Homomorphic Encryption With Verification
- Graph States, Pivot Minor, and Universality of (X,Z)-measurements
- Garbled Quantum Computation
- Quantum Protocols within Spekkens' Toy Model
- Blind quantum computing with two almost identical states
- Practical and efficient experimental characterization of multiqubit stabilizer states
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
- The Quantum Cut-and-Choose Technique and Quantum Two-Party Computation
- On optimising quantum communication in verifiable quantum computing
- New Limits on Fault-Tolerant Quantum Computation
- 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 (79)
- 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
- As Accurate as Needed, as Efficient as Possible: Approximations in DD-based Quantum Circuit Simulation
- Quantum cryptography beyond key distribution: theory and experiment
- Mitigating errors by quantum verification and post-selection
- Nonadaptive fault-tolerant verification of quantum supremacy with noise
- Security Limitations of Classical-Client Delegated Quantum Computing
- Client-friendly continuous-variable blind and verifiable quantum computing
- Experimental verifiable multi-client blind quantum computing on a Qline architecture
- Sample-efficient verification of continuously-parameterized quantum gates for small quantum processors
- Benchmarks of Nonclassicality for Qubit Arrays
- Quantum Metrology with Delegated Tasks
- Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
- Authenticated teleportation and verification in a noisy network
- Collective Operations Can Exponentially Enhance Quantum State Verification
- High-accuracy Hamiltonian learning via delocalized quantum state evolutions
- Hardware requirements for trapped-ion based verifiable blind quantum computing with a measurement-only client
- A Specification Format and a Verification Method of Fault-Tolerant Quantum Circuits
- Cross-Platform Verification in Quantum Networks
- Benchmarking Quantum Computers: Towards a Standard Performance Evaluation Approach
- A Uniform Representation of Classical and Quantum Source Code for Static Code Analysis
- Optimal parent Hamiltonians for time-dependent states
- Benchmarking bosonic modes for quantum information with randomized displacements
- tqix: A toolbox for Quantum in X: Quantum measurement, quantum tomography, quantum metrology, and others
- A survey of universal quantum von Neumann architecture
- Selective Quantum State Tomography
- Trie-based ranking of quantum many-body states
- Accreditation of Analogue Quantum Simulators
- Learning Properties of Quantum States Without the I.I.D. Assumption
- Methods for Classically Simulating Noisy Networked Quantum Architectures
- Analogue Quantum Simulation: A Philosophical Prospectus
- Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
- Efficiently verifiable quantum advantage on near-term analog quantum simulators
- Experimental Implementation of an Efficient Test of Quantumness
- Blindly Factorizing 21 Quantumly
- Benchmarks for quantum computers from Shor's algorithm
- Trusted center verification model and classical channel remote state preparation
- Multi-agent blind quantum computation without universal cluster states
- Building trust for continuous variable quantum states
- Certifying Temporal Correlations
- Practical parallel self-testing of Bell states via magic rectangles
- Quantum Proofs of Proximity
- Continuous Variable Quantum Advantages and Applications in Quantum Optics
- Quantum Software Ecosystem Design
- Determining non-Hermitian parent Hamiltonian from a single eigenstate
- Sampling and the complexity of nature
- Beating the Optimal Verification of Entangled States via Collective Strategies
- Inserting Planar-Measured Qubits into MBQC Patterns while Preserving Flow
- Partial Blind Quantum Computation: A Framework for Selective Circuit Protection
- Bounded-Error Quantum Simulation via Hamiltonian and Lindbladian Learning
- Efficient verification and fidelity estimation of discrete bipartite squeezed states
- Accreditation Against Limited Adversarial Noise