Classical verification of quantum circuits containing few basis changes
arXiv:1612.04914 · doi:10.1103/PhysRevA.97.042319
Abstract
We consider the task of verifying the correctness of quantum computation for a restricted class of circuits which contain at most two basis changes. This contains circuits giving rise to the second level of the Fourier Hierarchy, the lowest level for which there is an established quantum advantage. We show that, when the circuit has an outcome with probability at least the inverse of some polynomial in the circuit size, the outcome can be checked in polynomial time with bounded error by a completely classical verifier. This verification procedure is based on random sampling of computational paths and is only possible given knowledge of the likely outcome.
arXiv comment5 pages, comments welcome!
References in corpus (19)
- Measurement-based quantum computation with cluster states
- Quantum annealing with more than one hundred qubits
- Experimental Demonstration of Blind Quantum Computing
- Can One Trust Quantum Simulators?
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Experimental signature of programmable quantum annealing
- Unconditionally verifiable blind computation
- Verifiable measurement-only blind quantum computing with stabilizer testing
- Blind quantum computation protocol in which Alice only makes measurements
- Experimental verification of quantum computations
- Robustness and device independence of verifiable blind quantum computing
- On the hardness of classically simulating the one clean qubit model
- Post hoc verification with a single prover
- Post hoc verification of quantum computation
- Interactive proofs for BQP via self-tested graph states
- Device-Independent Verifiable Blind Quantum Computation
- Sampling generalized cat states with linear optics is probably hard
- Flow Ambiguity: A Path Towards Classically Driven Blind Quantum Computation
- Quantum and Classical Tradeoffs
Cited by in corpus (7)
- Supervised learning with quantum enhanced feature spaces
- Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
- Sumcheck-based delegation of quantum computing to rational server
- On the role of coherence for quantum computational advantage
- A quantum homomorphic encryption scheme for polynomial-sized circuits
- Information-theoretically-sound non-interactive classical verification of quantum computing with trusted center
- Quantum Circuit Unoptimization