Zero-knowledge proof systems for qma
- Publisher:
- Society for Industrial & Applied Mathematics (SIAM)
- Publication Type:
- Journal Article
- Citation:
- SIAM Journal on Computing, 2020, 49, (2), pp. 245-283
- Issue Date:
- 2020-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| 18m1193530.pdf | Submitted version | 557.38 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
© 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: