PaperlayerView exact revision on arXiv

Source-linked AI summary

The quantum moment problem and bounds on entangled multi-prover games

Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, Stephanie Wehner

arXiv:0803.4373v1quant-phcs.CC

TL;DR

The paper asks how to characterize feasible quantum moments and compute values of multi-prover games with entangled provers. It uses a noncommutative Positivstellensatz to construct infeasibility certificates and derives an SDP hierarchy. The hierarchy converges to the field-theoretic value, implying recursiveness under a finite-dimensionality assumption.

  • Problem

    The paper studies whether prescribed probabilities and polynomial measurement constraints admit a quantum realization, and how to compute entangled multi-prover game values.

  • Method

    The paper uses noncommutative Positivstellensatz sum-of-squares certificates and a hierarchy of semidefinite programs based on bounded certificate degree.

  • Results

    The SDP hierarchy converges to the field-theoretic value of the game, and under finite-dimensional optimal strategies yields an algorithm for deciding MIP∗ membership.

  • Takeaways & Limitations

    The framework gives computable upper-bound hierarchies and certificates for quantum moment instances and multi-prover game values.

  • Takeaways & Limitations

    The field-theoretic value is not known to equal the usual entangled value, and the recursiveness conclusion assumes finite-dimensional optimal operators.

Abstract

from arXiv · show

We study the quantum moment problem: Given a conditional probability distribution together with some polynomial constraints, does there exist a quantum state rho and a collection of measurement operators such that (i) the probability of obtaining a particular outcome when a particular measurement is performed on rho is specified by the conditional probability distribution, and (ii) the measurement operators satisfy the constraints. For example, the constraints might specify that some measurement operators must commute. We show that if an instance of the quantum moment problem is unsatisfiable, then there exists a certificate of a particular form proving this. Our proof is based on a recent result in algebraic geometry, the noncommutative Positivstellensatz of Helton and McCullough [Trans. Amer. Math. Soc., 356(9):3721, 2004]. A special case of the quantum moment problem is to compute the value of one-round multi-prover games with entangled provers. Under the conjecture that the provers need only share states in finite-dimensional Hilbert spaces, we prove that a hierarchy of semidefinite programs similar to the one given by Navascues, Pironio and Acin [Phys. Rev. Lett., 98:010401, 2007] converges to the entangled value of the game. It follows that the class of languages recognized by a multi-prover interactive proof system where the provers share entanglement is recursive.

1 Introduction

The paper formulates quantum strategies through the quantum moment problem, develops Positivstellensatz certificates for unsatisfiability, and applies them to semidefinite hierarchies for entangled multi-prover games. The hierarchy converges to the field-theoretic value, yielding recursiveness results under a finite-dimensionality assumption.

  • Entangled games: Entanglement can increase multi-prover game values, as illustrated by CHSH, whose entangled value is approximately 85%, exceeding the classical 3/4.The verifier communicates classically, while the provers perform local measurements on a shared entangled state.
  • Quantum moment problem: The quantum moment problem asks whether a probability distribution and polynomial constraints can be realized by a quantum state and measurement operators.Constraints can require measurement operators to satisfy relations such as commutation or subsystem independence.
  • Certificates: A noncommutative Positivstellensatz supplies sum-of-squares certificates proving that unsatisfiable quantum moment instances have no feasible realization.The certificates apply to polynomial constraints on measurement operators, including systems of arbitrary dimension.
  • SDP hierarchy: The SDP hierarchy converges to the field-theoretic value for games whose players’ observables satisfy commutation constraints.This value permits possibly infinite-dimensional operators and is not known in general to equal the usual tensor-product entangled value.
  • Complexity consequences: Under the assumption that optimal strategies use finite-dimensional operators, hierarchy convergence provides an algorithm deciding MIP∗ membership, so MIP∗ and MIPf are recursive.The paper also gives algorithmically constructed certificates for the I3322 inequality and a multi-player game suggested by Yao and collaborators.

2 Preliminaries

The preliminaries define two-prover games, their entangled and field-theoretic values, and the MIP framework with completeness and soundness parameters.

  • Games: A two-prover game samples questions, receives answers, and accepts according to a predicate; its value is the maximum winning probability.The game uses a question distribution π and predicate V, with no communication after questions are sent.
  • Entangled strategies: The entangled value optimizes winning probability over shared states and local projective measurements for Alice and Bob.Alice and Bob measure their respective subsystems of a shared state and return the resulting outcomes.
  • Field-theoretic value: The field-theoretic value instead permits operators on a common Hilbert space whose measurements for different players commute.For two-prover games, the entangled value is bounded above by the field-theoretic value.
  • Multi-prover extension: For multiple players, game values are expressed using POVMs that are positive and sum to the identity for every question.The winning probability is the verifier’s predicate averaged against the resulting measurement moments.
  • Interactive proofs: An entangled MIP system uses one-round classical communication, shared entanglement, and completeness and soundness bounds for yes and no instances.The verifier sends one question to each prover and accepts according to the returned answers.

3 The quantum moment problem

The quantum moment problem asks whether prescribed probabilities can arise from a quantum state and measurements satisfying polynomial constraints. Its nonlocal-game specialization turns existence of such operators into an optimization problem for success probability.

  • Problem formulation: The quantum moment problem asks whether a probability distribution can be realized by quantum measurements and a state obeying specified polynomial equations and inequalities.The operators and state must jointly satisfy the constraints while reproducing the prescribed moments.
  • Nonlocal-game specialization: For nonlocal games, the problem asks whether a shared state and local measurements produce the specified conditional probabilities.The two-party setting uses separate Hilbert spaces for Alice and Bob and measurement operators indexed by settings and outcomes.
  • Constraints: Polynomial constraints enforce locality, valid measurements, positivity, and projectivity of the measurement operators.The construction includes commutation constraints between Alice’s and Bob’s operators, normalization constraints, and projector constraints.
  • Optimization: Semidefinite programming converts the existence question into optimization over a success probability ν.The resulting optimization targets weighted average outcome probabilities in the nonlocal game.

4 Tools

The paper develops two tools: commutation constraints that recover tensor-product structure in finite dimensions, and a Positivstellensatz that certifies infeasible quantum moment instances.

  • Tensor products and commutation: Commutativity of measurement operators associated with different parties is equivalent, in finite dimensions, to a tensor-product decomposition of the Hilbert space.Each party’s operators act on its own tensor factor under the equivalent representation.
  • Positivstellensatz: The Positivstellensatz provides certificates that a quantum moment problem or nonlocal-game constraint system is infeasible.The proof extends Helton and McCullough’s noncommutative Positivstellensatz to the complex setting used here.
  • Constraint cone: The convex cone C_P is generated from Hermitian constraint polynomials and records the measurement-operator restrictions.Weighted sums of squares use these constraint polynomials together with arbitrary polynomial multipliers.
  • Measurement constraints: The measurement constraints include inter-party commutation, valid measurement normalization, positivity, projectivity, and orthogonality of same-setting outcomes.These conditions are encoded as Hermitian noncommutative polynomials.
  • Certificate construction: The Positivstellensatz is formulated through weighted sums of squares whose vanishing follows when the measurement operators satisfy the constraints.The theorem is stated for a cone generated by the relevant Hermitian polynomials.

5 Finding upper bounds

The paper constructs SDP relaxations from weighted-sum-of-squares certificates and shows that increasing the degree yields progressively tighter upper bounds converging to the field-theoretic game value.

  • 5 Finding upper bounds: A weighted-sum-of-squares representation of qν certifies that no measurement strategy achieves winning probability ν or higher.The Positivstellensatz supplies the certificate, while semidefinite programming tests whether such representations exist.
  • 5 Finding upper bounds: The optimization minimizes ν subject to qν admitting a weighted-sum-of-squares form that incorporates the measurement constraints.The extra weighted terms vanish when the measurement operators satisfy the constraints.
  • 5.1 SDP hierarchy: Fixing a maximum polynomial degree produces computable SDP relaxations, although the required certificate degree is not known in advance.At level n, the representation has total degree at most 2n, so finite levels may remain above the exact value.
  • 5.1 SDP hierarchy: The SDP hierarchy converges to the field-theoretic value ωf(G) as the relaxation degree tends to infinity.The hierarchy provides upper bounds at finite levels, and its optimum approaches ωf(G) arbitrarily closely.
  • 5.2.2 The I3322 inequality: For the I3322 example, the second-order relaxation gives approximately 0.251 470 90, below 3/8 = 0.375.The relaxation is formed by extending the monomial vector with degree-two measurement-operator monomials.

A Tool 1: Tensor product structure from commutation relations

The finite-dimensional tensor-product structure is obtained from commutation relations between Alice’s and Bob’s measurement operators.

  • A Tool 1: Tensor product structure from commutation relations: The proof uses finite-dimensional C∗-algebras generated by the measurement operators and their conjugate transposes.These algebras provide the framework for deriving the subsystem decomposition from commutation.

A.1 Optimizing non-local games

The optimization argument reduces non-local games to simple operator algebras, decomposes the strategy into blocks, and retains a block achieving at least the original performance.

  • A.1 Optimizing non-local games: Finite-dimensional operator algebras can be decomposed into simple components, enabling the strategy to be reduced to simple algebras.The reduction uses the decomposition of finite-dimensional C∗-algebras and the tensor-factor form of simple algebras.
  • A.1 Optimizing non-local games: The argument begins with a finite-dimensional bipartite state and measurement operators acting on the two tensor factors.The operators and shared state satisfy the finite-dimensional setting required for the algebraic reduction.
  • A.1 Optimizing non-local games: Convexity implies that one pair of algebraic blocks achieves performance at least as large as the average over all blocks.Choosing a block with maximal conditional value allows the initial block-selection measurement to be skipped.
  • A.1 Optimizing non-local games: When both generated algebras are abelian, the resulting strategy is classical because the remaining state is one-dimensional.The same block-selection argument therefore recovers a classical strategy achieving the target value.

A.2 Tensor product structure

The section shows that commutation relations can yield a tensor-product decomposition, with each prover’s measurement operators acting on its own subsystem. The argument extends recursively to multiple provers but depends on the operator algebra and excludes some infinite-dimensional cases.

  • A.2 Tensor product structure: Commutation with all operators on one subsystem forces an operator to act as an operator on the other subsystem tensored with identity.The proof expands an operator into blocks and uses the fact that the center of B(H) consists only of scalar multiples of the identity.
  • A.2 Tensor product structure: For a simple algebra generated by Alice’s measurements, the Hilbert space decomposes as H = H_A ⊗ H_B and Bob’s operators act on the second factor.The simple-algebra case follows from the algebraic decomposition and the commutant characterization.
  • A.2 Tensor product structure: In finite dimensions, semisimple algebras can be decomposed into simple factors, preserving a bipartite structure even when the full algebra is not simple.The section invokes finite-dimensional C*-algebra decomposition into a sum of simple algebras.
  • A.2 Tensor product structure: Applying the commutant argument recursively partitions an N-prover Hilbert space as H = H_1 ⊗ . . . ⊗ H_N, with prover P_j acting only on H_j.The multi-prover extension uses Lemma A.6 repeatedly after grouping the first N−1 provers.
  • A.2 Tensor product structure: The argument does not generally extend to type-II or type-III algebras, although quantum mechanics is stated to yield tensor-product structure from commutation relations even in infinite dimensions.The stated limitation concerns the applicability of the algebraic argument beyond type-I settings.

B Tool 2: Positivstellensatz

This section develops a Positivstellensatz-based certificate for quantum moment infeasibility. It separates a violating polynomial from a constraint cone and uses a GNS-style construction to obtain operators and a state satisfying the constraints.

  • B Tool 2: Positivstellensatz: The Positivstellensatz gives a weighted-sums-of-squares certificate when the polynomial q_ν is positive, while its contrapositive constructs a feasible operator model when no such representation exists.The proof separates q_ν from the cone of constrained polynomials and then realizes the separating functional through operators on a Hilbert space.
  • B Tool 2: Positivstellensatz: A separating linear functional λ is obtained for any Hermitian polynomial outside the cone, satisfying λ(C_P) ≥ 0, λ(I) > 0, and λ(q) ≤ 0.Hahn–Banach separation supplies the functional used in the subsequent representation theorem.
  • B Tool 2: Positivstellensatz: The Helton–McCullough representation realizes such a functional with a Hilbert space, bounded operators, and a state whose expectations reproduce λ on Hermitian polynomials.The construction uses a positive semidefinite inner product, quotients out its degeneracy, completes the quotient, and defines an operator representation.
  • B Tool 2: Positivstellensatz: The constructed operators satisfy all polynomial constraints, including equality constraints encoded by placing both p and −p in the constraint set.The resulting state and measurements witness the required sign condition for q_ν.
  • B Tool 2: Positivstellensatz: The representation theorem does not ensure finite-dimensionality or a type-I operator algebra, so commutation constraints cannot automatically be converted into tensor-product form.This leaves open whether some games satisfy ω∗(G) < ω_f(G).

D.1 Implementing Lowest Level SDP Relaxations for I3322

The lowest-level I3322 relaxation is expressed as a semidefinite program by choosing sparse symmetric matrices F_k and constants b′_k that encode the polynomial constraints in a matrix inequality.

  • D.1 Implementing Lowest Level SDP Relaxations for I3322: The lowest-level I3322 SDP chooses F_k with only three specified nonzero entries and sets b′_k = 0 for k = 1, 2, . . . , 6.The matrices are symmetric, with [F_k]_{1,k+1} = [F_k]_{k+1,1} = 1/2 and [F_k]_{k+1,k+1} = −1.
  • D.1 Implementing Lowest Level SDP Relaxations for I3322: The resulting matrix inequality, together with positive semidefiniteness of Γ, enforces the required polynomial inequality for the I3322 relaxation.The construction identifies the polynomial expression with a quadratic form z†Γz.

D.2 Implementing Higher Level SDP Relaxations for I3322

Higher-level I3322 relaxations remain semidefinite programs by representing higher-degree polynomial terms as quadratic forms in a monomial vector and collecting their coefficients into positive semidefinite matrices.

  • D.2 Implementing Higher Level SDP Relaxations for I3322: At level two, each multiplier s_ij may be a degree-at-most-one polynomial expanded in the monomial vector μ containing I and Alice’s and Bob’s measurement operators.The coefficient matrices Λ_ij are positive semidefinite rank-one matrices before aggregation over j.
  • D.2 Implementing Higher Level SDP Relaxations for I3322: The positive-semidefinite requirement on Λ_i can be removed for I3322 because each constraint polynomial p_i is accompanied by −p_i.This uses the symmetry of the constraint set under sign reversal.
  • D.2 Implementing Higher Level SDP Relaxations for I3322: Independent entries of the coefficient matrices become optimization variables x_k, while the associated Hermitian F_k encode the corresponding polynomial identities.The construction maps entries of Λ_i to entries of Ω_i and then to quadratic forms in z.
  • D.2 Implementing Higher Level SDP Relaxations for I3322: Any higher-order relaxation in the hierarchy can be implemented as an SDP by finding a positive semidefinite Γ and suitable Hermitian matrices F_k.The polynomial constraints are rewritten as quadratic forms z†F_kz, with optimization variables multiplying the matrices.

D.3 Yao’s inequality

This section establishes an equality for operators satisfying specified pairwise commutation relations and shows that it remains valid without imposing the constraints A2_k = I. The equality can also be rewritten in the form of Eq. (8) using identities involving g_jk := B_jC_k.

  • The operators A_i, B_j, and C_k are assumed to satisfy pairwise commutation relations across the three operator families.
  • The construction distinguishes terms with mutually distinct indices from terms whose indices coincide.
  • The equality holds even when none of the constraints A2_k = I are satisfied.
  • The expression can be recast in the form of Eq. (8) using identities involving g_jk := B_jC_k and its adjoint.
Loading 0803.4373v1…