Testing product states, quantum Merlin-Arthur games and tensor optimization
From MaRDI portal
Abstract: We give a test that can distinguish efficiently between product states of n quantum systems and states which are far from product. If applied to a state psi whose maximum overlap with a product state is 1-epsilon, the test passes with probability 1-Theta(epsilon), regardless of n or the local dimensions of the individual systems. The test uses two copies of psi. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarising channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(k)=QMA(2) for k>=2. Building on a previous result of Aaronson et al, this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of O(sqrt(n) polylog(n)) qubits. We also show how QMA(2) with log-sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalisation of classical linearity testing.
Recommendations
Cited in
(30)- Limitations of semidefinite programs for separable states and entangled games
- Noisy tensor completion via the sum-of-squares hierarchy
- The sum-of-squares hierarchy on the sphere and applications in quantum information theory
- Quantum de Finetti theorems under local measurements with applications
- QMA with subset state witnesses
- The efficiency of quantum identity testing of multiple states
- Sequential measurements, disturbance and property testing
- Dvoretzky's theorem and the complexity of entanglement detection
- Epsilon-net method for optimizations over separable states
- A quantum linearity test for robustly verifying entanglement
- An improved semidefinite programming hierarchy for testing entanglement
- Flexible constrained de Finetti reductions and applications
- Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
- A Gap in the Subrank of Tensors
- scientific article; zbMATH DE number 7692356 (Why is no real title available?)
- Non-Boolean quantum amplitude amplification and quantum mean estimation
- Approximate orthogonality of permutation operators, with application to quantum information
- Quantum free games
- The power of unentangled quantum proofs with non-negative amplitudes
- Geometry of entanglement and separability in Hilbert subspaces of dimension up to three
- Unconditionally secure commitments with quantum auxiliary inputs
- The role of piracy in quantum proofs
- Dimension independent disentanglers from unentanglement and applications
- The entangled quantum polynomial hierarchy collapses
- Quantum Merlin-Arthur and proofs without relative phase
- Testing multipartite productness is easier than testing bipartite productness
- Sample efficient identity testing and independence testing of quantum states
- Distributed quantum proofs for replicated data
- Quantum polynomial hierarchies: Karp-Lipton, error reduction, and lower bounds
- Optimizing entanglement manipulation via algebraic-geometric decompositions and semi-definite programming hierarchies
This page was built for publication: Testing product states, quantum Merlin-Arthur games and tensor optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395703)
