Nonadaptive fault-tolerant verification of quantum supremacy with noise

Theodoros Kapourniotis, Animesh Datta

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)164
Number of pages33
Publication statusPublished - 12 Jul 2019


Dive into the research topics of 'Nonadaptive fault-tolerant verification of quantum supremacy with noise'. Together they form a unique fingerprint.

Cite this