Loading...

Fang Song: Zero-knowledge proof systems for QMA

483 views

Loading...

Loading...

Transcript

The interactive transcript could not be loaded.

Loading...

Loading...

Rating is available when the video has been rented.
This feature is not available right now. Please try again later.
Published on Jan 31, 2017

"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."

Loading...

When autoplay is enabled, a suggested video will automatically play next.

Up next


to add this to Watch Later

Add to

Loading playlists...