A Caltech Library Service

A quantum linearity test for robustly verifying entanglement

Natarajan, Anand and Vidick, Thomas (2017) A quantum linearity test for robustly verifying entanglement. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017. ACM , New York, NY, pp. 1003-1015. ISBN 978-1-4503-4528-6.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We introduce a simple two-player test which certifies that the players apply tensor products of Pauli σ_X and σ_Z observables on the tensor product of n EPR pairs. The test has constant robustness: any strategy achieving success probability within an additive of the optimal must be poly(ε)-close, in the appropriate distance measure, to the honest n-qubit strategy. The test involves 2n-bit questions and 2-bit answers. The key technical ingredient is a quantum version of the classical linearity test of Blum, Luby, and Rubinfeld. As applications of our result we give (i) the first robust self-test for n EPR pairs; (ii) a quantum multiprover interactive proof system for the local Hamiltonian problem with a constant number of provers and classical questions and answers, and a constant completeness-soundness gap independent of system size; (iii) a robust protocol for verifiable delegated quantum computation with a constant number of quantum polynomial-time provers sharing entanglement.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
Alternate Title:Robust self-testing of many-qubit states
Additional Information:© 2017 ACM. AN was supported by NSF Grant CCF-1629809 and ARO Contract Number W911NF-12-0486. TV was supported by NSF CAREER Grant CCF-1553477 and AFOSR YIP award number FA9550-16-1-0495. Parts of this work was completed while the first author was visiting the Institute for Quantum Information and Matter (IQIM) at the California Institute of Technology, and while both authors were visiting the Perimeter Institute in Waterloo, ON. Both authors acknowledge funding provided by the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-12-0486
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Gordon and Betty Moore FoundationGBMF-12500028
Subject Keywords:Theory of computation → Quantum complexity theory; Interactive proof systems; Complexity classes; Quantum Interactive Proofs, Self-Testing, Nonlocal Games, Quantum PCP Conjecture
Record Number:CaltechAUTHORS:20170710-154654821
Persistent URL:
Official Citation:Anand Natarajan and Thomas Vidick. 2017. A quantum linearity test for robustly verifying entanglement. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017). ACM, New York, NY, USA, 1003-1015. DOI:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78915
Deposited On:10 Jul 2017 23:29
Last Modified:15 Nov 2021 17:44

Repository Staff Only: item control page