Quantum de Finetti Theorems under Local Measurements with Applications

• A symmetric distribution on k subsystems has an l-subsystem marginal within l(l −1)/k in variational distance of a convex combination of i.i.d. distributions.Quantum de Finetti theorems give an analogous approximation of reduced quantum states by mixtures of i.i.d. quantum states.Source: §1 · p. 2
• Quantum de Finetti structure also makes the l-subsystem state close to separable, giving a quantitative statement of entanglement monogamy.In a symmetric state, subsystems are equally correlated, so each can be only slightly entangled with a few others.Source: §1 · p. 2
• The trace-norm theorem of Christandl, König, Mitchison, and Renner gives error 2d^2l/k, while examples attain error Ω(dl/k) [34].Here d is the subsystem dimension, and the bound can be too large for applications.Source: §1 · p. 2
• Renner’s exponential de Finetti theorem [86] achieves error exponentially small in k − l, but only places the state near a convex combination of almost-i.i.d. states; Ref. [26] treats l = 2.Source: §1 · p. 2
• Non-signaling de Finetti theorems also exist, but error scaling linearly with the number of possible measurements has limited their applicability [35].Source: §1 · p. 3
• Entanglement also matters in proof systems, including MIP∗ with shared entanglement and QMA(k) with unentangled proofs.The paper focuses on these settings, where the assumption of unentangled proofs can appear to give a proof system extra power.Source: §1 · p. 3

2.1 Quantum de Finetti Theorems for Local Measurements

• The new de Finetti bounds compare states through their local-measurement statistics and improve dimension dependence, with extensions to non-signaling distributions and, in some cases, explicit rounding.For multipartite symmetric states and distributions, the bounds depend logarithmically on dimension; the paper states that the k = Ω(l^2) dependence is optimal in a computational-complexity sense. The explicit rounded separable state depends on the chosen measurement.Source: §2 · p. 3, §2.1 · pp. 6–8

2 Results

• Any similar 3-SAT protocol using O(n^(1/2−ε)) proof qubits would imply an exp(n^(1−2ε) polylog(n))-time algorithm, supporting the optimality of Chen and Drucker’s protocol [31].The optimality claim assumes there are no subexponential-time algorithms for SAT.Source: §2 · p. 4

2.2 Non-Local Games: Algorithms and Hardness Results

• Free-game winning probability can be approximated to additive error ε by linear programming in time exp(O(log |Q| + log^2 |A|/ε^2)), matching the runtime of Aaronson, Impagliazzo, and Moshkovitz [3].The result applies to free games, where players’ questions are chosen independently.Source: §2 · p. 4
• 3-SAT on n variables reduces to constant-error approximation of the entangled winning probability for O(√n)-player one-round games with O(√n) total communication bits.An appropriate strengthening of a de Finetti theorem would also imply NP-hardness for four-player one-round games; the paper presents this as a new approach to a problem recently resolved in [91].Source: §2 · p. 4

2 Results

• Certain degree-d polynomials on the n-dimensional hypersphere can be approximated to error ε in quasipolynomial time using O(log(n)d^3ε^-2) Sum-of-Squares rounds.Unless subexponential-time algorithms for SAT exist, Ω(d^2) rounds are necessary even for constant-error approximation.Source: §2 · p. 5
• Multipartite separability can be decided in quasipolynomial time in the local subsystem dimensions, with distance measured in the one-way LOCC norm or a multipartite Frobenius norm.This extends prior findings from bipartite to general multipartite states and improves the cited bound [22].Source: §2 · p. 5
• Aaronson’s tomography result for an unknown n-qubit state [1] extends beyond i.i.d. copies: randomly selected subsystems suffice, with poly(n) selected and only O(n) measured.The remaining selected subsystems are discarded; the scheme estimates statistics for most observables to good accuracy.Source: §2 · p. 5

2.2 Non-Local Games: Algorithms and Hardness Results

• 3-SAT on n variables reduces to constant-additive-error estimation of ωe for O(√n)-player games with answer alphabets exp(O(√n)), while the total communication is O(√n) bits.Only two players are asked questions in these games.Source: §2.2 · pp. 11–12
• A free game’s maximum winning probability can be estimated by linear programming, and the paper gives a linear-programming relaxation for free games.The resulting algorithm matches the performance of Aaronson, Impagliazzo, and Moshkovitz [3].Source: §2.2 · pp. 11–12
• Adding players and consistency tests makes the game correspond to an m-extendible state or non-signaling distribution, whose error depends on answer outcomes rather than state dimension or measurement count.For non-signaling m-extendible distributions, the violation of a free-game Bell inequality is at most 1/m, regardless of the number of measurement settings, each with M possible outcomes.Source: §2.2 · p. 12
• A conjectured strengthening of Theorem 1 would imply NP-hardness of constant-error entangled-value estimation for four-player one-round games, but its no-signaling version would imply P = NP.The paper leaves open whether a k-extendible no-signaling distribution can be distinguished from local-hidden-variable distributions using correlated measurements.Source: §2.2 · pp. 12–13

2.3 Optimality of Chen and Drucker’s Multiple-Proof Protocol for 3-SAT

• Under the exponential time hypothesis, no BellSymQMA protocol with O(log(n)) proofs of n^(1/2−ε) qubits achieves constant completeness–soundness gap for 3-SAT unless it is solvable in exp(n^(1−2ε) polylog(n)) time.This makes the square-root improvement in Chen–Drucker’s proof size essentially optimal for BellSymQMA; whether an analogous result holds for BellQMA remains open.Source: §2.3 · p. 14
• BellQMA with polynomially many provers is contained in QMA, so in the stated regime its advantage is limited to polynomially reducing proof size.The result also extends to verification where all but one party measure and send classical messages to the remaining party, who may choose a measurement adaptively.Source: §2.3 · p. 15

2.4 Polynomial Optimization and Sum-of-Squares Proofs

• The sum-of-squares hierarchy approximates polynomial optimization over the sphere through moment constraints, with its polynomial-space moments connected to symmetric tensor subspaces and k-extendibility.The hierarchy’s computational cost grows exponentially with its level, motivating bounds on its convergence rate.Source: §2.4 · p. 16
• O(log(n)l^4/ε^2) sum-of-squares levels approximate the specified multiquadratic polynomial within additive error ε in time exp(O(l^4 log^2(n)/ε^2)).The corollary concerns polynomials defined by a one-way LOCC operator M.Source: §2.4 · pp. 16–17
• For unique games, de Finetti algorithms may need the PPT condition in addition to k-extendability; prior evidence of an asymptotic PPT improvement was limited to [76].The cited example [27] concerns the unique games problem, motivating the suggested need to exploit PPT constraints in algorithms proposed in [10].Source: §2.4 · p. 17

2.5 Testing Multipartite Separability

• The Sum-of-Squares hierarchy solves weak membership for multipartite separability in the one-way LOCC norm.The supplied result passage states a running-time bound, but its expression is incomplete in the supplied text.Source: §2.5 · p. 18
• The Sum-of-Squares hierarchy also solves weak membership for multipartite separability in the multipartite Forbenius norm.The supplied result passage states a running-time bound, but its expression is incomplete in the supplied text.Source: §2.5 · p. 18

2.6 Pretty-Good Tomography in Permutation-Symmetric States

• Theorem 2 yields pretty-good tomography from permutation-symmetric states, relaxing the need for i.i.d. copies while preserving approximate predictions for local measurements.With high probability, compatible hypothesis states can predict future measurement statistics; for nonzero ν, the guarantee applies to local-measurement statistics up to error ν even if the post-measured state is far from a convex combination of i.i.d. states.Source: §2.6 · pp. 20–21
• The tomography relaxation uses a global state with polynomially many subsystems and measures only O(log |H|) of them, leaving the resource requirement polynomial in the unknown state's qubit count.The passages describe this as the cost of relaxing the i.i.d.-copy assumption.Source: §2.6 · p. 21
• The tomography approach does not establish that the hypothesis state can be found efficiently.The passage identifies efficient construction of ρv for particular classes of states as an open question, as noted in [1].Source: §2.6 · p. 21

Theorem 1

• A classical computer can compute a separable σ ∈ Sep(A:B) in time polynomial in |A| and |B|^k under the conditions of Theorem 1, part 2.The result uses a fixed measurement rather than maximizing over measurements.Source: §3 · pp. 22, 24
• The proof of Theorem 1 repeatedly applies the mutual-information chain rule, with the maximized conditional mutual information bounded above by ln |Ã|.The argument sequentially applies the chain rule across the extended systems.Source: §3 · pp. 21, 22, 24

Comparison with prior bounds

• The one-way LOCC bound, like Ref. [23], requires k ≳ log |A| for constant error, whereas prior trace-norm bounds generally required k ≥ poly(|B|) [86] [34] [76] [45].The passage notes that conversion from one-way LOCC to trace norm costs a dimension factor [74].Source: §3 · p. 25

Proposition 12

• For a state with a symmetric extension on B, Proposition 12 guarantees a separable σ ∈ Sep(A:B).The extension has equal AB marginals and its B systems lie in the symmetric subspace; the supplied statement does not specify the approximation error.Source: §3 · p. 25

Quantum states

• For the quantum-state case, the theorem assumes a permutation-invariant state and asserts a measure on single-system quantum states for every 0 ≤ l ≤ k.The proof invokes a multipartite mutual-information bound and then Pinsker’s inequality.Source: §4 · pp. 27–28

Non-signaling distributions

• For non-signaling distributions, the theorem assumes permutation symmetry and a product input distribution, and asserts a measure on single-system conditional distributions for 0 < l < k.The proof bounds the relevant conditional multipartite mutual information by (l −1)^2 ln |X| before applying Pinsker’s inequality.Source: §4 · pp. 27, 29

Proof strategy

• The proof repeatedly uses symmetry and mutual-information monotonicity to relate the multipartite information terms across subsystems.The quantum argument also uses the chain decomposition of multipartite conditional mutual information.Source: §4 · pp. 26–29

Symmetrization

• Symmetrizing questions and answers on a subset of players allows the strategy to be assumed symmetric for classical, entangled, or non-signaling play.The stated lemma gives this conclusion for non-signaling strategies under symmetric question distributions and predicates.Source: §5 · pp. 29–30

Hardness

• 3-SAT on n variables reduces to constant-error approximation of the classical value of two-player one-round free games with 2^O(√n)-sized output alphabets [3].The proof identifies this as the Aaronson–Impagliazzo–Moshkovitz hardness result.Source: §5 · p. 30

Free-game reduction

• A two-player one-round free game can be transformed into a one-round non-local game with m+1 players and matching question and answer alphabet sizes across the replicated players.The supplied corollary excerpt does not include the resulting winning-probability comparison.Source: §5 · p. 30

Free-game algorithm

• The non-signaling value ω_ns is computable by linear programming, which the proof uses in its free-game result.The corollary also states that a free game has a linear-programming relaxation, but the displayed size expression is incomplete in the supplied passage.Source: §5 · pp. 30–31

Hardness

• Unless 3-SAT with n variables and O(n) clauses can be solved in exp(n^(1−2ε) polylog(n)) time, no BellSymQMA protocol with the stated parameters and constant completeness–soundness gap exists.The claim applies for every ε > 0 and c − s = Ω(1).Source: §6 · p. 32

Simulation

• To simulate a BellSymQMA protocol, the verifier symmetrizes blocks of a larger proof, keeps the first m blocks, and runs the original protocol on them.The stated proof size is 10n^2m^2/ε^2 qubits, and soundness is analyzed using Theorem 2, part 1.Source: §6 · p. 33
• For the BellQMA simulation, the verifier symmetrizes larger blocks, retains m blocks, and uses their diagonal n-qubit sub-blocks as the proof.The construction uses 10n^2m^4/ε^2 proof qubits and analyzes soundness with Theorem 2, part 1.Source: §6 · p. 33

Corollary 8

• The SOS hierarchy solves weak membership for separability in the one-way LOCC norm by testing whether a symmetric extension exists.If the state is more than ε-far from separable in that norm, such an extension does not exist, distinguishing it from the separable case.Source: §7 · pp. 33–34
• For the ∥∗∥2(l) norm, the SOS hierarchy also solves weak membership for separability.The passage states a runtime, but its expression is not included in the supplied text.Source: §7 · p. 33
• The weak membership task is to decide whether a given multipartite state is separable or ε-far from separable in the one-way LOCC norm.Source: §7 · p. 33
• The proof approximates the separable set with a k-extendible relaxation, searching by semidefinite programming for a permutation-invariant extension whose specified marginal is the input state.A separable input has such an extension for every k ≥ l; the proof chooses k = l + 4l^2ε^-2 Σ_j log |Aj|.Source: §7 · pp. 33–34

Corollary 7

• The SOS hierarchy achieves bounds at least as tight as the extension-based relaxation, using level O(l^4 ln(n)/ε^2) and an SDP of total dimension nkl.The proof takes k = O(l^3 ln(n)/ε^2).Source: §7 · p. 34

Open problem 1

• Conjecture 5 proposes an improved Theorem 1 that would imply O(log(k))-extendable states cannot be distinguished from separable states by Bell measurements with k outcomes per party.Source: §8 · p. 35

Open problem 2

• Improving Theorem 1 to cover separable measurements, rather than only 1-LOCC measurements, could yield quasipolynomial-time classical algorithms for separability testing and tensor optimization.The proposed strengthening would also imply the stated containment for QMAn(m, c, s).Source: §8 · p. 35

Open problem 3

• The antisymmetric state is d-extendable yet far from separable, obstructing stronger de Finetti bounds; the authors note that this example is not PPT.Highly extendable PPT states far from separable are not known, and the authors call for improved bounds or better counterexamples.Source: §8 · p. 35

Open problem 4

• The authors ask whether post-selection can replace dimension dependence with measurement-outcome dependence, noting difficulty choosing a test state when local dimension is infinite.They also ask whether the techniques can improve exponential de Finetti, which they say has no classical analogue because the proofs use classical or classical-quantum entropic properties.Source: §8 · p. 35