Zero-knowledge proof systems for qma

Society for Industrial & Applied Mathematics (SIAM)
Publication Type:
Journal Article
SIAM Journal on Computing, 2020, 49, (2), pp. 245-283
Issue Date:
Filename Description Size
18m1193530.pdfSubmitted version557.38 kB
Adobe PDF
Full metadata record
© 2020 Society for Industrial and Applied Mathematics. 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.
Please use this identifier to cite or link to this item: