Classical veriﬁcation of quantum proofs

Ji, Z

Classical veriﬁcation of quantum proofs

Ji, Z

Permalink

Publication Type:: Journal Article
Citation:: Theory of Computing, 2019, 15
Issue Date:: 2019-09-01

Recently Added

	Filename	Description	Size
	699110.pdf	Published Version	267.71 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ji, Z https://orcid.org/0000-0002-7659-3178	en_US
dc.date.issued	2019-09-01	en_US
dc.identifier.citation	Theory of Computing, 2019, 15	en_US
dc.identifier.uri	http://hdl.handle.net/10453/138205
dc.description.abstract	© 2019 Zhengfeng Ji. We present a classical interactive protocol that checks the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the nonlocal value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our result makes a connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of nonlocal games and Bell inequalities on the other.	en_US
dc.relation.ispartof	Theory of Computing	en_US
dc.relation.isbasedon	10.4086/toc.2019.v015a005	en_US
dc.title	Classical veriﬁcation of quantum proofs	en_US
dc.type	Journal Article
utslib.citation.volume	15	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
utslib.for	1702 Cognitive Sciences	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	recently_added
pubs.publication-status	Published	en_US
pubs.volume	15	en_US

Abstract:

© 2019 Zhengfeng Ji. We present a classical interactive protocol that checks the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the nonlocal value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our result makes a connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of nonlocal games and Bell inequalities on the other.

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

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