An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games

摘要: We give a test that can distinguish efficiently between product states of n quantum systems and which are far from product. If applied to state psi whose maximum overlap with is 1-epsilon, the passes probability 1-Theta(epsilon), regardless or local dimensions individual systems. The uses two copies psi. prove correctness this as special case more general result regarding stability output purity depolarising channel. A key application Merlin-Arthur games multiple Merlins, where we obtain several structural results had been previously conjectured, including fact soundness amplification possible Merlins simulate many Merlins: QMA(k)=QMA(2) for k at least 2. Building on previous Aaronson et al, implies there an efficient algorithm verify 3-SAT constant soundness, given unentangled proofs O(sqrt(n) polylog(n)) qubits. Among other consequences, complexity-theoretic obstructions finding polynomial-time determine separability mixed states, even up error, also proving "weak" variants additivity conjecture channels. Finally, our be used construct determining whether unitary operator tensor product, generalisation classical linearity testing.