Nonadaptive fault-tolerant verification of quantum supremacy with noise
arXiv:1703.09568 · doi:10.22331/q-2019-07-12-164
Abstract
Quantum samplers are believed capable of sampling efficiently from distributions that are classically hard to sample from. We consider a sampler inspired by the classical Ising model. It is nonadaptive and therefore experimentally amenable. Under a plausible conjecture, classical sampling upto additive errors from this model is known to be hard. We present a trap-based verification scheme for quantum supremacy that only requires the verifier to prepare single-qubit states. The verification is done on the same model as the original sampler, a square lattice, with only a constant overhead. We next revamp our verification scheme in two distinct ways using fault tolerance that preserves the nonadaptivity. The first has a lower overhead based on error correction with the same threshold as universal quantum computation. The second has a higher overhead but an improved threshold (1.97\%) based on error detection. We show that classically sampling upto additive errors is likely hard in both these schemes. Our results are applicable to other sampling problems such as the Instantaneous Quantum Polynomial-time (IQP) computation model. They should also assist near-term attempts at experimentally demonstrating quantum supremacy and guide long-term ones.
33 pages, 11 figures, 3 theorems, 2 conjectures
References in corpus (18)
- Multi-party entanglement in graph states
- Quantum Computational Supremacy
- Efficient quantum state tomography
- Topological fault-tolerance in cluster state quantum computation
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Verification of quantum computation: An overview of existing approaches
- Optimal verification of entangled states with local measurements
- Architectures for quantum simulation showing a quantum speedup
- Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
- Interactive Proofs For Quantum Computations
- Hardness of classically sampling one clean qubit model with constant total variation distance error
- Towards Quantum Supremacy with Lossy Scattershot Boson Sampling
- Efficient quantum pseudorandomness with simple graph states
- Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification
- Reducing resources for verification of quantum computations
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation
- Information Theoretically Secure Hypothesis Test for Temporally Unstructured Quantum Computation (Extended Abstract)
- On optimising quantum communication in verifiable quantum computing
Cited by in corpus (8)
- Computational advantage of quantum random sampling
- Securing Quantum Computations in the NISQ Era
- Accrediting outputs of noisy intermediate-scale quantum computing devices
- Efficient verification of Boson Sampling
- Fault-tolerant quantum speedup from constant depth quantum circuits
- Efficiently verifiable quantum advantage on near-term analog quantum simulators
- Passive verification protocol for thermal graph states
- Accreditation Against Limited Adversarial Noise