We prove a version of the quantum de Finetti theorem: permutation-invariant quantum states are well approximated as a probabilistic mixture of multifold product states. The approximation is measured by distinguishability under measurements that are implementable by fully-one-way local operations and classical communication (LOCC). Our result strengthens Brandão and Harrow's de Finetti theorem where a kind of partially-one-way LOCC measurements was used for measuring the approximation, with essentially the same error bound. As main applications, we show (i) a quasipolynomial-time algorithm which detects multipartite entanglement with an amount larger than an arbitrarily small constant (measured with a variant of the relative entropy of entanglement), and (ii) a proof that in quantum Merlin-Arthur proof systems, polynomially many provers are not more powerful than a single prover when the verifier is restricted to one-way LOCC operations.
We prove a version of the quantum de Finetti theorem: permutation-invariant quantum states are well approximated as a probabilistic mixture of multifold product states. The approximation is measured by distinguishability under measurements that are implementable by fully-one-way local operations and classical communication (LOCC). Our result strengthens Brandão and Harrow's de Finetti theorem where a kind of partially-one-way LOCC measurements was used for measuring the approximation, with essentially the same error bound. As main applications, we show (i) a quasipolynomial-time algorithm which detects multipartite entanglement with an amount larger than an arbitrarily small constant (measured with a variant of the relative entropy of entanglement), and (ii) a proof that in quantum Merlin-Arthur proof systems, polynomially many provers are not more powerful than a single prover when the verifier is restricted to one-way LOCC operations.
Standard finite quantum de Finetti theorems approximate the k-system marginals of permutation-invariant states of n-systems by mixtures of independent and identically distributed (iid) states, usually in trace distance. We prove both standard and Renner's exponential de Finetti theorems in the stronger form of operator inequalities, implying bounds in every Schatten norm and for every quantum Rényi divergence satisfying data processing. In the standard case, for fixed local dimension, our k/n error bound in max-relative entropy improves on the previously best known k2/n scaling, even in the classical setting. The operator-inequality approach is particularly suited to study channel de Finetti representations because operator order between Choi states is equivalent to completely positive (CP) order between the underlying channels. For permutation-covariant channels N(n):A⊗n→B⊗n, where dA=dimA, we prove that the k-system reduced channel is CP-dominated by a mixture of tensor-power channels with error O(k/n) and polynomial dependence on the local dimensions, addressing a question raised by Berta et al. [Math. Program. 194, 781-829 (2022)]. Under the no-signalling condition, we also prove an exponential channel de Finetti theorem where the approximating mixture consists of Choi-almost-iid channels, whose normalized Choi states are almost-iid in the sense of Mazzola-Sutter-Renner. In the case of r defects, the representation error is at most poly(n)(2dA4k3/(nr2))(r+1)/2 and decays exponentially in n for a suitable choice of parameters r and k.
Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/ε2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables n by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.
De Finetti theorems convert permutation symmetry into approximate mixtures of product states and thereby justify a wide range of reductions in classical and quantum statistics. In this work we study de Finetti hierarchies in which the feasible states are additionally constrained to be fixed points of quantum channels, a condition that subsumes invariance under arbitrary compact symmetry groups. Combining the mean-ergodic theorem with the structure theory of conditional expectations, we prove a tight bound on the entanglement-assisted classical capacity of the dual of a conditional expectation, block-wise distortion bounds for informationally complete measurements adapted to fixed point algebras, and an exact type-based refinement of the chain rule for permutation-invariant states. From these tools we derive several de Finetti theorems: a double-sided extension theorem with O(logn/n) convergence, an interpolation theorem whose dimension dependence is governed solely by the block structure of the fixed point algebras and which recovers the dimension-independent classical behavior for maximal tori, and a Bose-symmetric variant. Exploiting Schur-Weyl duality and Gelfand-Tsetlin bases, we further show that the rounding scheme producing certifiably good separable inner approximations for (constrained) separability problems can be implemented in time polynomial in 1/ε for fixed local dimensions, complementing the known efficient outer hierarchies. Applications to bilinear optimization under symmetries and to approximate quantum error correction are discussed.
De Finetti theorems show how sufficiently exchangeable states are well-approximated by convex combinations of independent identically distributed states. Recently, it was shown that in many quantum information applications, a more relaxed de Finetti reduction (i.e., only a matrix inequality between the symmetric state and one of the de Finetti forms) is enough and that it leads to more concise and elegant arguments. Here we show several uses and general flexible applicability of a constrained de Finetti reduction in quantum information theory, which was recently discovered by Duan, Severini, and Winter. In particular, we show that the technique can accommodate other symmetries commuting with the permutation action and permutation-invariant linear constraints. We then demonstrate that, in some cases, it is also fruitful with convex constraints, in particular separability in a bipartite setting. This is a constraint particularly interesting in the context of the complexity class QMA(2) of interactive quantum Merlin-Arthur games with unentangled provers, and our results relate to the soundness gap amplification of QMA(2) protocols by parallel repetition. It is also relevant for the regularization of certain entropic channel parameters. As an aside, we present an alternative way of attacking this problem, relying on an entanglement measure theory rather than the de Finetti approach. Finally, we explore an extension to infinite-dimensional systems, which usually pose inherent problems to de Finetti techniques in the quantum case.
In a seminal work [PRL85.4972], Walgate, Short, Hardy, and Vedral prove in finite dimensions that for every pair of pure multipartite orthogonal quantum states, there exists a one-way local operations and classical communication (LOCC) protocol that perfectly distinguishes the pair. We extend this result to infinite dimensions with a simpler proof. For states on CdA×dA⊗CdB×dB, we strengthen this existence result by constructing an O(dA2dB2)-time algorithm that specifies such a perfect one-way LOCC protocol. Finally, we establish the equivalence between Walgate et al.'s result and the fact that the one-shot environment-assisted classical capacity of every quantum channel is at least 1 bit per channel use, thereby clarifying the literature on these notions. At the core of all of these results is the fact that every operator with vanishing trace admits a basis where its diagonal entries are all zero.
We provide quantitative bounds on the characterization of multiparticle separable states by states that have locally symmetric extensions. The bounds are derived from two-particle bounds and relate to recent studies on quantum versions of de Finetti's theorem. We discuss algorithmic applications of our results, in particular a quasipolynomial-time algorithm to decide whether a multiparticle quantum state is separable or entangled (for constant number of particles and constant error in the norm induced by one-way local operations and classical communication, or in the Frobenius norm). Our results provide a theoretical justification for the use of the search for symmetric extensions as a test for multiparticle entanglement.