A quantum linearity test for robustly verifying entanglement
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.
Cite this item
Natarajan, A., & Vidick, T. (2017). A quantum linearity test for robustly verifying entanglement. In P. McKenzie, V. King, & H. Hatami (Editors), STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. https://doi.org/10.1145/3055399.3055468
Click Copy to copy the citation, or select the text manually.
2-s2.0-85024366180
Center for Theoretical Physics
California Institute of Technology
2017-06-19
New York, NY, USA
978-1-4503-4528-6
Part F128415
1003
1015
REVIEWED
EPFL
| Event name | Event acronym | Event place | Event date |
Montreal, Canada | 2017-06-19 - 2017-06-23 | ||
| Funder | Funding(s) | Grant Number | Grant URL |
California Institute of Technology | |||
ARO | CCF-1553477,W911NF-12-0486 | ||
AFOSR | FA9550-16-1-0495 | ||
| Show more | |||