Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3055399.3055468 | STOC |
Keywords | Field | DocType |
Quantum Interactive Proofs,Self-Testing,Nonlocal Games,Quantum PCP Conjecture | Tensor product,Quantum,Discrete mathematics,Combinatorics,Observable,Quantum entanglement,Interactive proof system,Quantum mechanics,Quantum computer,Robustness (computer science),Mathematics,Pauli exclusion principle | Conference |
ISSN | Citations | PageRank |
Proc. of STOC '17, pp. 1003-1015 (2017) | 2 | 0.38 |
References | Authors | |
3 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Anand Natarajan | 1 | 16 | 5.09 |
| Thomas Vidick | 2 | 377 | 31.69 |