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 |φ) whose maximum overlap with a product state is 1- ε, the test passes with probability 1-Θ(ε), regardless of n or the local dimensions of the individual systems. The test uses two copies of |φ). 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 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 Õ(√n) qubits. Among other consequences, this result implies complexity-theoretic obstructions to finding a polynomial-time algorithm to determine separability of mixed quantum states, even up to constant error, and also to proving "weak" variants of the additivity conjecture for quantum channels. 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.
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 |φ) whose maximum overlap with a product state is 1- ε, the test passes with probability 1-Θ(ε), regardless of n or the local dimensions of the individual systems. The test uses two copies of |φ). 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 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 Õ(√n) qubits. Among other consequences, this result implies complexity-theoretic obstructions to finding a polynomial-time algorithm to determine separability of mixed quantum states, even up to constant error, and also to proving "weak" variants of the additivity conjecture for quantum channels. 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.
Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property testing, unentangled quantum proof systems, and tensor optimization. Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined. In this work, we determine this curve exactly. Let ω be the maximum squared overlap of the input with a product state, and let PTn(ω) be the largest possible acceptance probability of the product test over all n-partite pure states with product overlap ω, allowing arbitrary finite local dimensions. We prove that, for every $n\ge 2 $ and every $ω\in(0,1] $, PTn(ω)=21(1+mω2+(1−mω)2), where $m=\lfloor1/ω\rfloor $. The formula recovers the previously known tight section of the curve for $ω\ge 1/2 $, resolves all low-overlap regimes $ω<1/2 $, and implies $\mathrm{PT}_n(ω)\to 1/2 $ as ω→0 answering an open problem in [Soleimanifar and Wright, SODA 2022]. As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from QMA(k) to QMA(2). Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.
We give a test that can distinguish efficiently between product states of n quantum systems and states that are far from product. If applied to a state | ψ 〉 whose maximum overlap with a product state is 1 − ε , the test passes with probability 1 − Θ ( ε ), regardless of n or the local dimensions of the individual systems. The test uses two copies of | ψ 〉. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing 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 Õ (√ 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 generalization of classical linearity testing.
We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce the QMA(2)-complete Separable Sparse Hamiltonian problem to a variant of the Separable Local Hamiltonian problem with an exponentially small promise gap, and then to decide this instance using epsilon-net methods. Our results imply an exponential time algorithm for the Pure State N-Representability problem in quantum chemistry, which is in QMA(2), but is not known to be in QMA. We also discuss the implications of our results on the Best Separable State problem.
Interference and entanglement are among the most fundamental properties of quantum mechanics. In this work, we investigate the power of interference in the role of detecting entanglement in the context of quantum Merlin-Arthur verification. In particular, we show that unentanglement gives no additional power to stoquastic Merlin-Arthur proof systems, whose restriction to a classical gate set results in entrywise non-negative acceptance operators and non-negative optimal witnesses, therein removing destructive interference from the verification process. Our results show that for any polynomial number of unentangled witnesses k=k(n), StoqMA(k)=StoqMA. The analytic core of this result is a new non-negative de Finetti theorem for separately bosonic states. If a mixed state ρ is supported on the tensor product of symmetric subspaces of H1⊗R⊗H2⊗R⊗⋯⊗Hk⊗R then there exists a separable state τ on H1⊗⋯⊗Hk such that Tr(M(ρH1⊗⋯⊗Hk−τ))≤2R−1klog2dim(H1⊗⋯⊗Hk), simultaneously for all non-negative effects M. For any such operator M, one can define the separately symmetric lift SSR(M) whose largest eigenvalue approximates the maximum acceptance probability of M over product states within the same error bound. Such a lift can be approximated by a stoquastic verifier, giving that product-state constraint of StoqMA(k) verifiers can be absorbed into a polynomially larger one-witness StoqMA verification, while preserving an inverse polynomial completeness-soundness gap.
This paper studies quantum Arthur–Merlin games, which are Arthur–Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur–Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin’s message. Previous constructions for reducing error required a polynomial increase in the length of Merlin’s message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA⊆PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur–Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur–Merlin games.
This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games in which Arthur and Merlin can perform quantum computations and Merlin can send Arthur quantum information. As in the classical case, messages from Arthur to Merlin are restricted to be strings of uniformly generated random bits. It is proved that for one-message quantum Arthur-Merlin games, which correspond to the complexity class QMA, completeness and soundness errors can be reduced exponentially without increasing the length of Merlin's message. Previous constructions for reducing error required a polynomial increase in the length of Merlin's message. Applications of this fact include a proof that logarithmic length quantum certificates yield no increase in power over BQP and a simple proof that QMA is contained in PP. Other facts that are proved include the equivalence of three (or more) message quantum Arthur-Merlin games with ordinary quantum interactive proof systems and some basic properties concerning two-message quantum Arthur-Merlin games.