Quantum Soundness of Testing Tensor Codes

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

Quantum Soundness of Testing Tensor Codes

Ji, Z

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

Permalink

Publication Type:: Journal Article
Citation:: Discrete Analysis, 2022, 2022
Issue Date:: 2022-01-01

Closed Access

	Filename	Description	Size
	Quantum Soundness of Testing Tensor Codes.pdf	Published version	761.79 kB	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	2023-03-20T23:56:08Z
dc.date.available	2023-03-20T23:56:08Z
dc.date.issued	2022-01-01
dc.identifier.citation	Discrete Analysis, 2022, 2022
dc.identifier.issn	2397-3129
dc.identifier.uri	http://hdl.handle.net/10453/167829
dc.description.abstract	A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP = RE theorem. Our proof generalizes to the infinite-dimensional commuting-operator model of quantum provers.
dc.language	en
dc.relation.ispartof	Discrete Analysis
dc.relation.isbasedon	10.19086/da.55554
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Quantum Soundness of Testing Tensor Codes
dc.type	Journal Article
utslib.citation.volume	2022
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	2023-03-20T23:56:07Z
pubs.publication-status	Published
pubs.volume	2022

Abstract:

A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP = RE theorem. Our proof generalizes to the infinite-dimensional commuting-operator model of quantum provers.

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

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