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

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Conference Proceeding
Citation:: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2022, 2022-February, pp. 586-597
Issue Date:: 2022-01-01

Closed Access

	Filename	Description	Size
	Quantum_soundness_of_testing_tensor_codes.pdf	Published version	234.89 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	2022-02-07
dc.date.accessioned	2023-03-20T23:51:04Z
dc.date.available	2023-03-20T23:51:04Z
dc.date.issued	2022-01-01
dc.identifier.citation	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2022, 2022-February, pp. 586-597
dc.identifier.isbn	9781665420556
dc.identifier.issn	0272-5428
dc.identifier.uri	http://hdl.handle.net/10453/167827
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 also generalizes to the infinite-dimensional commuting-operator model of quantum provers.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation	http://purl.org/au-research/grants/arc/DP200100950
dc.relation.ispartof	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
dc.relation.ispartof	2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
dc.relation.isbasedon	10.1109/FOCS52979.2021.00064
dc.rights	info:eu-repo/semantics/closedAccess
dc.title	Quantum soundness of testing tensor codes
dc.type	Conference Proceeding
utslib.citation.volume	2022-February
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:51:03Z
pubs.finish-date	2022-02-10
pubs.publication-status	Published
pubs.start-date	2022-02-07
pubs.volume	2022-February

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 also 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/167827