PaperlayerView exact revision on arXiv

Source-linked AI summary

Testing product states, quantum Merlin-Arthur games and tensor optimisation

Aram W. Harrow, Ashley Montanaro

arXiv:1001.0017v6quant-ph

TL;DR

Testing quantum states for product structure is difficult because interference and measurements can create entanglement. The paper introduces a two-copy product test, proves it via depolarising-channel output-purity stability, and extends it to product-unitary testing.

  • Problem

    Testing quantum-state properties is difficult because interference prevents direct probability-distribution methods and measurements can induce entanglement.

  • Method

    The paper develops a two-copy test for product states and proves its correctness through a stability theorem for depolarising-channel output purity.

  • Results

    The test passes with probability 1−c(ψ)ϵ, where 11/512 ≤ c(ψ) ≤ 2, when the closest product-state overlap is 1−ϵ.

  • Takeaways & Limitations

    The test also yields an efficient test for tensor-product unitaries, generalising classical linearity testing.

  • Takeaways & Limitations

    The analysis rules out only algorithms restricted to recognizing a nearly convex set approximating Sep to constant accuracy, and leaves analogous stability questions open.

Abstract

from arXiv · show

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.

1 Introduction

The paper develops an efficient two-copy test for product states, proves its soundness through depolarising-channel stability, and applies it to multi-Merlin verification, tensor optimisation, and product-unitary testing.

  • 1.1 Our results: The product test accepts product states with certainty and rejects states whose closest product-state overlap is 1−ϵ with probability Θ(ϵ), independent of system count and local dimensions.It uses two copies and performs swap tests on corresponding subsystems.
  • 1.1 Our results: The test’s correctness follows from a stability theorem: states nearly attaining maximal depolarising-channel output purity must be close to product states.This strengthens the previously known multiplicativity result for channel output purity.
  • 1.2 Applications and interpretations of the product test: The product test enables efficient soundness amplification and establishes QMA(k)=QMA(2) for every k≥2.The result also holds when the QMA(2) verifier’s yes-measurement operator is separable.
  • 1.2 Applications and interpretations of the product test: A QMA(2) protocol verifies 3-SAT with constant soundness using two unentangled proofs of O(√n poly log(n)) qubits, while related problems yield hardness-of-approximation results.These include separability, minimum output entropy, mean-field ground-state energy, and tensor optimisation problems.
  • 1.2 Applications and interpretations of the product test: The framework connects QMA(2) with injective tensor norms and other tensor problems, and supports extensions from trilinear to k-linear optimisation.The paper also identifies potential algorithmic consequences for approximating QMA(2) acceptance probabilities.
  • 1.2 Applications and interpretations of the product test: The same test gives an efficient procedure for distinguishing tensor-product unitaries from operators far from tensor products in Hilbert–Schmidt norm.This generalises classical linearity testing for Boolean functions.

2 Overview of the proof of correctness

The proof bounds the product-test acceptance probability using subsystem purity and a decomposition by Hamming weight, yielding a dimension-independent linear dependence on the distance from product states.

  • For small ϵ, the proof writes |ψ⟩ as a product component plus an orthogonal remainder and bounds reductions using Hamming-weight components.
  • The closest-product-state condition excludes remainder amplitude on Hamming-weight-0 and Hamming-weight-1 basis states, enabling the small-ϵ bound.
  • For large ϵ, the proof groups systems into fewer parties and applies a product test across a suitable partition to obtain a constant upper bound.
  • Ptest(|ψ⟩⟨ψ|) = 1 −c(ψ)ϵ with 11/512 ≤c(ψ) ≤2, establishing the claimed Θ(ϵ) failure probability.
  • The argument generalizes to depolarising channels: approximate maximizers of output purity must themselves be approximately product, with the product test as a special case.

3 QMA(2) vs. QMA(k)

The product test lets two Merlins simulate protocols with many unentangled proofs, while separable-measurement variants support efficient soundness amplification and tensor-power optimisation results.

  • QMA(2) versus QMA(k): QMA(k) protocols can be placed in QMA(2) by having two Merlins send copies of all k proofs and testing that each combined state is product.
  • Soundness amplification: On NO instances, the product test rejects entangled proofs, while continuity limits the advantage of proofs that are nearly product, preserving controlled soundness.
  • Soundness amplification: Separable accept measurements prevent conditioning from inducing entanglement in unmeasured proofs, removing the entanglement-swapping obstacle to parallel repetition.
  • Soundness amplification: Theorem 9 gives efficient amplification to QMASEP(2) with perfect or exponentially close-to-perfect completeness and exponentially small soundness under inverse-polynomial gap assumptions.
  • hSep and tensor optimisation: QMA(2) is characterised through deciding whether the separable-state support function hSep(M) exceeds a completeness threshold or falls below a soundness threshold.
  • hSep and tensor optimisation: For separable M, hSep(d^k,d^k)(M⊗k) = hSep(M)^k, and a constructed M′ transforms promised thresholds efficiently with explicit bounds on k.

4 Complexity-theoretic implications

The paper derives complexity-theoretic consequences from QMA(2) hardness, relating separability, tensor, channel, entropy, and optimization problems. Under standard 3-SAT hardness assumptions, many of these problems cannot be solved or approximated efficiently.

  • QMA(2) hardness: Two-prover protocols verify 3-SAT with perfect completeness, arbitrary soundness, and proofs of ℓ(n)√n polylog(n) qubits.The resulting soundness is 2^-ℓ(n).
  • Equivalent problems: Tasks including separability optimization, tensor norms, channel norms, and minimum output entropies inherit hardness from QMAlog(2).The paper presents these as equivalent or related formulations of the reference problem hSep.
  • Tensor optimization: The results establish constant-factor hardness for central tensor problems and extend trilinear-form optimization methods to k-linear forms with little loss of accuracy.The paper also lists higher-partite injective tensor norms and geometric entanglement among the affected problems.
  • Hardness consequences: Under the stated 3-SAT assumption, Tasks 1–13 and 20–21 cannot be solved in poly(d) time for any constants 0 < s < c < 1.The excluded algorithmic regime would imply 3-SAT ∈ DTIME(exp(√n polylog(n))).
  • Limitations and open problems: For separability, the paper proves hardness only for algorithms recognizing nearly convex approximations, while conjecturing stronger constant-accuracy hardness for weak membership.A convex approximation within constant Hausdorff distance with polynomial-time weak membership would imply a subexponential-time algorithm for 3-SAT.
  • Norm approximation: Approximating the 2 → 4 norm is NP-hard to 1/poly(d) accuracy and NPlog2-hard within a constant multiplicative error.This follows from the reductions connecting norm approximation to separability-related problems.

5 Optimality of the product test

The product test is optimal among two-copy, perfectly complete product-state tests, and no nontrivial test exists with only one copy. Its two-copy construction is a projection onto the relevant symmetric product subspace.

  • The product test has perfect completeness and passes with probability at most 1−Θ(ϵ) when the nearest product-state overlap is at most 1−ϵ.This gives constant soundness independent of the number of systems and local dimensions.
  • For k copies, the relevant space is the tensor product of the local symmetric subspaces, whose projector can be implemented efficiently.The construction uses Symk C^d for each local system and projects onto their tensor product.
  • Among product-state tests with perfect completeness, projecting onto the product-state span rejects as often as possible.Any test accepting every k-copy product state must accept at least as often as this projector on every input.
  • With one copy, the symmetric space is the entire system, so no nontrivial product-state test is possible.
  • With two copies, the local symmetric-space projection is the swap-test eigenspace, making the product test reject non-product states as often as possible.The same argument extends to an optimal k-copy product-state test, although its strength increases with k.

6 Stability of the depolarising channel

The product-test analysis is framed as a stability result for maximum output purity under repeated depolarising channels. This broader formulation supplies the proof strategy for the product-state test.

  • The generalised analysis averages purities after selecting subsets according to a binomial distribution over the n systems.
  • This averaged purity equals the output purity of n uses of the depolarising channel, with the product-test passing probability as a special case.
  • The paper presents the product-test correctness theorem as a special case of a more general stability result.
  • The stability statement is parameterised by the maximum overlap 1−ϵ with a product state.
  • The proof follows the earlier outline, with technical details deferred to Appendix A.

7 Testing for product unitaries

The paper converts unitary-product testing into product-state testing through the Choi–Jamiołkowski correspondence. The resulting test is efficient, perfectly complete, and detects distance from product unitaries in normalised Hilbert–Schmidt overlap.

  • Testing tensor-product unitaries generalises classical linearity testing for Boolean functions represented by diagonal unitaries.
  • The unitary test always accepts product unitaries and rejects operators far from product, measured by normalised Hilbert–Schmidt overlap.
  • The Choi correspondence preserves the normalised Hilbert–Schmidt inner product as the inner product between the associated states.
  • The test prepares two Choi states for U and applies the product test across the n d^2-dimensional subsystems.Each Choi state is produced by applying U to one half of n maximally entangled pairs.
  • For ϵ=0 the test passes with probability 1, while generally Ptest(U)=1−Θ(ϵ).For 0.106 ≲ ϵ ≤ 1, the supplied bound gives Ptest(U) ≤ 501/512.
  • The analysis does not directly transfer from the closest product state to the closest product unitary.

8 Open problems

The paper closes with open problems on strengthening the depolarising-channel stability theorem, improving product-test bounds, testing repeated identical states, and clarifying QMA versus QMA(2).

  • It remains open whether analogous stability results hold for all output Rényi entropies or all channels with additivity.
  • The product-test constants might be improved, especially the ϵ^3/2 term and the pessimistic large-ϵ regime.
  • The minimum product-test passing probability and the largest possible distance from product states remain unknown for large ϵ.
  • A further problem is to test whether a state equals |ϕ⟩^⊗n with acceptance decreasing exponentially in positions that differ from |ϕ⟩, without dimension dependence.
  • The relationship between QMA and QMA(2) remains unresolved despite equalities involving separable and LOCC variants.
  • An oracle separation between QMA and QMA(2) is also posed as an open question.

A The depolarising channel

The paper characterizes depolarizing-channel output purity and uses this stability result to connect near-maximal purity with closeness to product states.

  • The resulting bounds combine terms from the depolarizing-channel expansion to establish the stability theorem.
  • The proof expands the input state in a tensor-product Hermitian operator basis and analyzes weighted contributions indexed by subsets.
  • Only product states saturate the depolarizing-channel output-purity bound.
  • Near-maximal output purity implies that the input state is close to a product state.
  • Choosing a closest product state as |0⟩^⊗n forces all Hamming-weight-one components of the residual state to vanish.

B Proof of Theorem 1: correctness of the product test

The product test uses two copies and has acceptance probability that decreases linearly with distance from the nearest product state, including states far from product.

  • The test is implemented through swap tests on corresponding subsystems and can assume equal local dimensions by padding.
  • 1 − ϵ + d1 2(d1 −1)ϵ2 ≤ Ptest(|ψ⟩⟨ψ|) ≤ 1 − ϵ + ϵ2 bounds the two-copy test's acceptance probability.
  • For small distance ϵ, the proof combines the general passing-probability formula with the depolarizing-channel stability result.
  • The bounds are close to optimal, but the theorem does not extend to separability testing for mixed states.
  • The theorem's constants were not fully optimized, although combining the two regimes proves correctness of the product test.
  • For ϵ ≥ 11/32, the test passes with probability at most 501/512 < 0.979.

C Classes of measurement operators

The paper organizes measurement operators by increasingly general locality and separability constraints, with PPT and SEP variants distinguished by whether the complement is constrained.

  • LOCC1: LOCC1 measures the first system and conditionally chooses a measurement on the second system.
  • LOCC: LOCC measurements use alternating local measurements whose choices depend on previous outcomes.
  • SEP: SEP consists of separable measurement operators, while SEP-BOTH additionally requires I − M to be separable.
  • PPT: PPT requires positivity under partial transpose, whereas PPT-BOTH requires both M and I − M to satisfy that condition.
  • The operator classes satisfy strict inclusions from BELL through LOCC, SEP-BOTH, PPT-BOTH, SEP, PPT, and ALL.

D Nonexistence of an LOCC product test

No efficient LOCC product test exists in the studied two-copy bipartite setting: even the larger PPT-BOTH class has only O(1/d) distinguishing bias.

  • The impossibility result already holds for n = 2 and rules out PPT-BOTH measurements, which include the targeted LOCC setting.
  • A product test is a two-outcome measurement on two copies, with M accepting the product hypothesis.
  • The paper evaluates completeness on uniformly random product states and soundness on random bipartite states, which are overwhelmingly near maximally entangled.
  • O(1/d) is the maximum bias of any two-copy PPT-BOTH product test for d × d-dimensional bipartite states.
  • The proof compares invariant second-moment operators for product-state and uniform bipartite-state distributions under PPT constraints.
  • The resulting objective is x + y + O(1/d), yielding the stated asymptotic bias bound.

E Proof of correctness of the protocol to put QMA(k) in QMA(2)

The proof converts a multi-Merlin protocol into a two-Merlin protocol while preserving separability and enabling efficient soundness amplification. The argument combines product-state structure with repetition, yielding exponentially small soundness under the stated parameter conditions.

  • The protocol’s completeness is immediate because honest Merlins provide product proofs that pass the product test with certainty.
  • A k-prover soundness-s protocol can therefore be simulated by two provers, with polynomial-size messages when k ≤poly(n).
  • The protocol design must account for the fact that separable measurements do not generally compose under A^1/2BA^1/2, although alternative separable measurements are available.
  • For NO instances, separability across Merlins prevents entanglement from arising between provers during sequential applications of the separable measurement.
  • Repeating a separable protocol preserves the product structure needed to bound the probability that all repeated measurements accept by s^ℓ.
  • Under polynomial inverse gaps, the construction achieves exponentially small soundness while retaining perfect or exponentially near-perfect completeness.

F Proof of correctness of the product unitary test

The product unitary test is analyzed by relating overlap with product operators to overlap with product unitaries. This transfers the product-state test’s bounds to unitary operators, giving acceptance probability 1 for exact tensor products and 1−Θ(ϵ) otherwise.

  • The proof relates a unitary’s maximum overlap with normalized product operators to its maximum overlap with product unitaries.
  • When the operator overlap defect is at most 1/2, polar decomposition produces product unitaries with squared overlap at least (1−2ϵ)^2.
  • The unitary test accepts exact tensor-product unitaries with probability 1 and otherwise has acceptance probability 1−Θ(ϵ).
  • The overlap comparison yields 4ϵ ≤ϵ′ ≤ϵ, allowing the operator-based product-test bound to control the unitary test.
  • The product test can be interpreted through average purity across subsystem bipartitions, connecting low average entanglement to closeness to a product state.
  • The result parallels an inverse theorem for the second Gowers uniformity norm, where maximum structured overlap is approximated by average squared overlaps.
Loading 1001.0017v6…