Compression of qantum multi-prover interactive proofs

Ji, Z

Compression of qantum multi-prover interactive proofs

Ji, Z

Permalink

Publication Type:: Conference Proceeding
Citation:: Proceedings of the Annual ACM Symposium on Theory of Computing, 2017, Part F128415 pp. 289 - 302
Issue Date:: 2017-06-19

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Accepted ManuscriptAdobe PDF (554.18 kB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Ji, Z https://orcid.org/0000-0002-7659-3178	en_US
dc.date.issued	2017-06-19	en_US
dc.identifier.citation	Proceedings of the Annual ACM Symposium on Theory of Computing, 2017, Part F128415 pp. 289 - 302	en_US
dc.identifier.isbn	9781450345286	en_US
dc.identifier.issn	0737-8017	en_US
dc.identifier.uri	http://hdl.handle.net/10453/126441
dc.description.abstract	© 2017 ACM. We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, it follows that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP∗, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the feasibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.	en_US
dc.relation.ispartof	Proceedings of the Annual ACM Symposium on Theory of Computing	en_US
dc.relation.isbasedon	10.1145/3055399.3055441	en_US
dc.title	Compression of qantum multi-prover interactive proofs	en_US
dc.type	Conference Proceeding
utslib.citation.volume	Part F128415	en_US
utslib.for	0802 Computation Theory and Mathematics	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	Part F128415	en_US

Abstract:

© 2017 ACM. We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, it follows that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP∗, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the feasibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.

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

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