Quantum proofs of proximity

Abstract

With the prevalence of massive datasets and small computing devices, offloading computation becomes increasingly important. One may model this problem as follows: a weak device (the “verifier”) holds an input string and communicates with an all-powerful computer (the “prover”) so as to verify the validity of this string. Since the verifier cannot perform the verification on its own, the prover provides a digest of the computational task, allowing the verifier to check that it was performed correctly. In an extreme setting, the verifier cannot even read all of its input, and must decide whether it is valid or far from any valid string; in this case, the digest is called a proof of proximity. We formalise quantum proofs of proximity, where prover and verifier are quantum computers, and begin to chart the complexity landscape of the quantum/classical as well as the interactive/non-interactive variants of these proof systems. This is joint work with Tom Gur and Subhayan Roy Moulik.