A quantum linearity test for robustly verifying entanglement

DOI10.1145/3055399.3055468MaRDI QIDQ4978041zbMATH OpenOpenAlexWikidataFDO

Authors Anand Natarajan, Thomas Vidick

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.03574

zbMATH Keywords

nonlocal gamesquantum interactive proofsquantum PCP conjectureself-testing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum coherence, entanglement, quantum correlations (81P40) Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Abstract: We introduce a simple two-player test which certifies that the players apply tensor products of Pauli $sigm{a}_X$ and $sigm{a}_Z$ observables on the tensor product of $n$ EPR pairs. The test has constant robustness: any strategy achieving success probability within an additive $varepsilon$ of the optimal must be $mathrmpoly(varepsilon)$-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 delegated quantum computation.

Recommendations

• Verifier-on-a-leash: new schemes for verifiable delegated quantum computation, with quasilinear resources
• Self-testing in parallel
• Robust self-testing of the singlet
• Self-testing of Quantum Circuits
• Testing product states, quantum Merlin-Arthur games and tensor optimization

Cited in

(19)

• Entanglement in non-local games and the hyperlinear profile of groups
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Parallel self-testing of the GHZ state with a proof by diagrams
• scientific article; zbMATH DE number 7375938 (Why is no real title available?)
• A simple protocol for verifiable delegation of quantum computation in one round
• scientific article; zbMATH DE number 7250160 (Why is no real title available?)
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• Sumcheck-based delegation of quantum computing to rational server
• Stability of approximate group actions: uniform and probabilistic
• Arkhipov's theorem, graph minors, and linear system nonlocal games
• Rigidity of quantum steering and one-sided device-independent verifiable quantum computation
• \(\mathrm{MIP}^* = \mathrm{RE}\): a negative resolution to Connes' embedding problem and Tsirelson's problem
• Constant-sized robust self-tests for states and measurements of unbounded dimension
• Quantum delegation with an off-the-shelf device
• The computational advantage of MIP* vanishes in the presence of noise
• The computational advantage of MIP* vanishes in the presence of noise
• Spectral gap and stability for groups and non-local games
• Stabilizer testing and magic entropy via quantum Fourier analysis
• A verification scheme for universal quantum computers

This page was built for publication: A quantum linearity test for robustly verifying entanglement

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978041)