Quantum proofs of proximity
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 the extreme setting of property testing, 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 the digest is called a proof of proximity. We formalise the notion of quantum proofs of proximity, where prover and verifier are quantum computers, and show that a large class of properties admits quantum speedups. We also 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.