Zero-Knowledge Proof Systems for QMA

Broadbent, A; Ji, Z; Song, F; Watrous, J

Zero-Knowledge Proof Systems for QMA

Broadbent, A Ji, Z

Song, F Watrous, J

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2016, 2016-December pp. 31 - 40
Issue Date:: 2016-12-14

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted Manuscript versionAdobe PDF (331.33 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Broadbent, A	en_US
dc.contributor.author	Ji, Z https://orcid.org/0000-0002-7659-3178	en_US
dc.contributor.author	Song, F	en_US
dc.contributor.author	Watrous, J	en_US
dc.date.available	2020-05-25T19:01:26Z
dc.date.issued	2016-12-14	en_US
dc.identifier.citation	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2016, 2016-December pp. 31 - 40	en_US
dc.identifier.isbn	9781509039333	en_US
dc.identifier.issn	0272-5428	en_US
dc.identifier.uri	http://hdl.handle.net/10453/127886
dc.description.abstract	© 2016 IEEE. 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.	en_US
dc.relation.ispartof	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS	en_US
dc.relation.isbasedon	10.1109/FOCS.2016.13	en_US
dc.title	Zero-Knowledge Proof Systems for QMA	en_US
dc.type	Conference Proceeding
utslib.citation.volume	2016-December	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - QSI - Centre for Quantum Software and Information
utslib.copyright.status	open_access
pubs.publication-status	Published	en_US
pubs.volume	2016-December	en_US

Abstract:

© 2016 IEEE. 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/127886