Quantum interactive proofs and the complexity of separability testing

DOI10.4086/TOC.2015.V011A003MaRDI QIDQ2941643zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Gus Gutoski, Patrick Hayden, Kevin Milner, Mark M. Wilde

Publication date 21 August 2015

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

quantum entanglementBQPquantum complexity theoryquantum interactive proofsQMAQIPQSZKquantum statistical zero knowledgeseparability testing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum coherence, entanglement, quantum correlations (81P40)

Abstract: We identify a formal connection between physical problems related to the detection of separable (unentangled) quantum states and complexity classes in theoretical computer science. In particular, we show that to nearly every quantum interactive proof complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural separability testing problem that is complete for that class. Of particular interest is the fact that the problem of determining whether an isometry can be made to produce a separable state is either QMA-complete or QMA(2)-complete, depending upon whether the distance between quantum states is measured by the one-way LOCC norm or the trace norm. We obtain strong hardness results by proving that for each n-qubit maximally entangled state there exists a fixed one-way LOCC measurement that distinguishes it from any separable state with error probability that decays exponentially in n.

Recommendations

• Computational complexity of the quantum separability problem
• Strong NP-hardness of the quantum separability problem
• A quasipolynomial-time algorithm for the quantum separability problem
• Faithful squashed entanglement
• Quantum proofs

Cites work

• Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
• On QMA protocols with two short quantum proofs
• Quantum entanglement
• Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model
• Skepticism of quantum computing
• Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
• Universal Quantum Simulators

Cited in

(18)

• Computational complexity of the quantum separability problem
• Constant-space quantum interactive proofs against multiple provers
• Pointer Quantum PCPs and Multi-Prover Games
• Quantum computation vs. firewalls
• scientific article; zbMATH DE number 5899305 (Why is no real title available?)
• scientific article; zbMATH DE number 6292749 (Why is no real title available?)
• Distinguishing short quantum computations
• Quantum hedging in two-round prover-verifier interactions
• On the power of quantum, one round, two prover interactive proof systems
• scientific article; zbMATH DE number 7378343 (Why is no real title available?)
• Strong NP-hardness of the quantum separability problem
• Quantum state testing beyond the polarizing regime and quantum triangular discrimination
• Pseudorandom isometries
• Dvoretzky's theorem and the complexity of entanglement detection
• Epsilon-net method for optimizations over separable states
• Testing non-isometry is QMA-complete
• Lower bounds for testing complete positivity and quantum separability
• Stabilizer testing and magic entropy via quantum Fourier analysis

This page was built for publication: Quantum interactive proofs and the complexity of separability testing

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