Fang Song: Zero-knowledge proof systems for QMA

Опубликовано 1 февраля 2017, 0:30

"Prior work has established that all problems in NP admit classical zero-knowledge proof
systems, and under reasonable hardness assumptions for quantum computations, these proof
systems can be made secure against quantum attacks. We prove a result representing a further
quantum generalization of this fact, which is that every problem in the complexity class QMA
has a quantum zero-knowledge proof system. More specifically, assuming the existence of an
unconditionally binding and quantum computationally concealing commitment scheme, we
prove that every problem in the complexity class QMA has a quantum interactive proof system
that is zero-knowledge with respect to efficient quantum computations.

Our QMA proof system is sound against arbitrary quantum provers, but only requires an
honest prover to perform polynomial-time quantum computations, provided that it holds a
quantum witness for a given instance of the QMA problem under consideration. The proof
system relies on a new variant of the QMA-complete local Hamiltonian problem in which the
local terms are described by Clifford operations and standard basis measurements. We believe
that the QMA-completeness of this problem may have other uses in quantum complexity."