Quantum vs. classical proofs

Presenting Author: Shelby Kimmel, Middlebury College

QMA is the quantum generalization of the complexity class NP. QMA contains important and physically relevant problems, such as whether a local Hamiltonian admits a low energy ground state. In QMA, the goal is to verify a proof using a quantum verifier, where the proof is given as a quantum state. It is an open question whether the complexity class loses power if the proof is restricted to be a classical bit-string rather than a quantum state. I will describe work with Bill Fefferman in which we find a class of permutation-oracle-based problems where a quantum proof can be used for verification, but any classical proof is insufficient. This builds off of work by Aaronson and Kuperberg, who first described such a separation using oracles derived from Haar random states.

(Session 12 : Saturday from 1:30pm-2:15pm)


SQuInT Chief Organizer
Akimasa Miyake, Assistant Professor

SQuInT Co-Organizer
Mark M. Wilde, Assistant Professor LSU

SQuInT Administrator
Gloria Cordova
505 277-1850

SQuInT Founder
Ivan Deutsch, Regents' Professor

Tweet About SQuInT 2018!