MIP∗= RE

Ji, Z; Natarajan, A; Vidick, T; Wright, J; Yuen, H

MIP∗= RE

Ji, Z

Natarajan, A Vidick, T Wright, J Yuen, H

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: Communications of the ACM, 2021, 64, (11), pp. 131-138
Issue Date:: 2021-11-01

Closed Access

	Filename	Description	Size
	3485628.pdf	Published version	1.41 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ji, Z https://orcid.org/0000-0002-7659-3178
dc.contributor.author	Natarajan, A
dc.contributor.author	Vidick, T
dc.contributor.author	Wright, J
dc.contributor.author	Yuen, H
dc.date.accessioned	2022-01-24T05:38:34Z
dc.date.available	2022-01-24T05:38:34Z
dc.date.issued	2021-11-01
dc.identifier.citation	Communications of the ACM, 2021, 64, (11), pp. 131-138
dc.identifier.issn	0001-0782
dc.identifier.issn	1557-7317
dc.identifier.uri	http://hdl.handle.net/10453/153510
dc.description.abstract	Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation.ispartof	Communications of the ACM
dc.relation.isbasedon	10.1145/3485628
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.title	MIP∗= RE
dc.type	Journal Article
utslib.citation.volume	64
utslib.for	08 Information and Computing Sciences
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	closed_access	*
dc.date.updated	2022-01-24T05:38:32Z
pubs.issue	11
pubs.publication-status	Published
pubs.volume	64
utslib.citation.issue	11

Abstract:

Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in Communications is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers. The complexity class NP characterizes the collection of computational problems that have efficiently verifiable solutions. With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of randomness (the class MA), interaction (the class IP), and the possibility to interact with multiple proofs, or provers (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols. In this work, we study a fourth modification to the notion of efficient verification that originates in the study of quantum entanglement. We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).

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

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