RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Zero-knowledge proof systems for QMA

October 12, 2016 - 11:00am
Fang Song
Portland State University

Zero-knowledge (ZK) proof systems are fundamental in modern cryptography. 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. 

In this talk, I will present our recent work that further generalizes these results in a quantum setting. We show that every problem in QMA admits a zero-knowledge proof system under a mild intractable assumption. 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. I'll describe the main tools we develop to build the ZK proof systems: 1) a new variant of the QMA-complete local Hamiltonian problem in which the local terms are described by Clifford operations and standard basis measurements; and 2) a new quantum encoding scheme that provides authentication and transversal Clifford operations. 

Joint work with Anne Broadbent, Zhengfeng Ji, and John Watrous. Link here.

CSS 3100A

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to