We prove that the family of embezzlement states defined by van Dam and Hayden [vanDamHayden2002] is universal for both quantum and classical entangled two-prover non-local games with an arbitrary number of rounds. More precisely, we show that for each $ε>0$ and each strategy for a k-round two-prover non-local game which uses a bipartite shared state on 2m qubits and makes the provers win with probability $ω$, there exists a strategy for the same game which uses an embezzlement state on $2m + 2m/ε$ qubits and makes the provers win with probability $ω-\sqrt{2ε}$. Since the value of a game can be defined as the limit of the value of a maximal 2m-qubit strategy as m goes to infinity, our result implies that the classes QMIP*_{c,s}[2,k] and MIP*_{c,s}[2,k] remain invariant if we allow the provers to share only embezzlement states, for any completeness value c in [0,1] and any soundness value s < c. Finally we notice that the circuits applied by each prover may be put into a very simple universal form.
We prove that the family of embezzlement states defined by van Dam and Hayden [vanDamHayden2002] is universal for both quantum and classical entangled two-prover non-local games with an arbitrary number of rounds. More precisely, we show that for each ε>0 and each strategy for a k-round two-prover non-local game which uses a bipartite shared state on 2m qubits and makes the provers win with probability ω, there exists a strategy for the same game which uses an embezzlement state on 2m+2m/ε qubits and makes the provers win with probability ω−2ε. Since the value of a game can be defined as the limit of the value of a maximal 2m-qubit strategy as m goes to infinity, our result implies that the classes QMIP_{c,s}[2,k] and MIP_{c,s}[2,k] remain invariant if we allow the provers to share only embezzlement states, for any completeness value c in [0,1] and any soundness value s < c. Finally we notice that the circuits applied by each prover may be put into a very simple universal form.
Quantum state embezzlement is the transformation $|\ensuremath{\mu}\ensuremath{\rangle}\ensuremath{\mapsto}|\ensuremath{\mu}\ensuremath{\rangle}|\ensuremath{\varphi}\ensuremath{\rangle}$ using only local operations, where $|\ensuremath{\varphi}\ensuremath{\rangle}$ and $|\ensuremath{\mu}\ensuremath{\rangle}$ are multipartite quantum states. Exact embezzlement is an impossible task since it implies the increase of entanglement without communication. Surprisingly, van Dam and Hayden [Phys. Rev. A 67, 060302 (2003)] find a universal embezzling family of states $|\ensuremath{\mu}\ensuremath{\rangle}$ that enables embezzlement in the bipartite setting with arbitrary precision as the dimension of $|\ensuremath{\mu}\ensuremath{\rangle}$ increases. Furthermore, the family is independent of the state $|\ensuremath{\varphi}\ensuremath{\rangle}$ to be embezzled. We study embezzlement in the bipartite setting. We present various requirements and consequences, and infinitely many universal embezzling families inequivalent to that proposed by van Dam and Hayden. We include numerical studies of up to 33-qubit large local systems.
This paper considers a special class of nonlocal games (G,ψ), where G is a two-player one-round game, and ψ is a bipartite state independent of G. In the game (G,ψ), the players are allowed to share arbitrarily many copies of ψ. The value of the game (G,ψ), denoted by ω∗(G,ψ), is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states ψ. For a noisy maximally entangled state ψ, a two-player one-round game G and an arbitrarily small precision ϵ>0, this paper proves an upper bound on the number of copies of ψ for the players to win the game with a probability ϵ close to ω∗(G,ψ). A noisy maximally entangled state is a two-qudit state with both marginals being completely mixed states and the maximal correlation being less than 1. In particular, it includes $(1-\epsilon)|\Psi_m\rangle\langle\Psi_m|+\epsilon\frac{\mathbbm{1}_m}{m}\otimes\frac{\mathbbm{1}_m}{m}$ for ϵ>0, where ∣Ψm⟩=m1∑i=0m−1∣m,m⟩ is an m-dimensional maximally entangled state. Hence, it is feasible to approximately compute ω∗(G,ψ) to an arbitrary precision. Recently, a breakthrough result by Ji et al. showed that it is undecidable to approximate the values of nonlocal games to a constant precision, when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that MIP∗=RE. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications. (A corrected version is attached.)
Embezzlement of entanglement refers to the task of extracting entanglement from an entanglement resource via local operations and without communication while perturbing the resource arbitrarily little. Recently, the existence of embezzling states of bipartite systems of type III von Neumann algebras was shown. However, both the multipartite case and the precise relation between embezzling states and the notion of embezzling families, as originally defined by van Dam and Hayden, was left open. Here, we show that finite-dimensional approximations of multipartite embezzling states form multipartite embezzling families. In contrast, not every embezzling family converges to an embezzling state. We identify an additional consistency condition that ensures that an embezzling family converges to an embezzling state. This criterion distinguishes the embezzling family of van Dam and Hayden from the one by Leung, Toner, and Watrous. The latter generalizes to the multipartite setting. By taking a limit, we obtain a multipartite system of commuting type III 1 factors on which every state is an embezzling state. We discuss our results in the context of quantum field theory and quantum many-body physics. As open problems, we ask whether vacua of relativistic quantum fields in more than two spacetime dimensions are multipartite embezzling states and whether multipartite embezzlement allows for an operator-algebraic characterization.
Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics.
The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT.
The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible.
We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size.
The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific unit of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically).
We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.
Van Dam and Hayden introduced a concept commonly referred to as embezzlement, where, for any entangled quantum state ϕ, there is an entangled catalyst state ψ, from which a high fidelity approximation of ϕ ⊗ ψ can be produced using only local operations. We investigate a version of this where the embezzlement is perfect (i.e., the fidelity is 1). We prove that perfect embezzlement is impossible in a tensor product framework, even with infinite-dimensional Hilbert spaces and infinite entanglement entropy. Then we prove that perfect embezzlement is possible in a commuting operator framework. We prove this using the theory of C*-algebras and we also provide an explicit construction. Next, we apply our results to analyze perfect versions of a nonlocal game introduced by Regev and Vidick. Finally, we analyze the structure of perfect embezzlement protocols in the commuting operator model, showing that they require infinite-dimensional Hilbert spaces.
Using local operations and classical communication (LOCC), entanglement can be manipulated but not created. However, entanglement can be embezzled . In this work, we completely characterize universal embezzling families and demonstrate how this singles out the original family introduced by van Dam and Hayden. To achieve this, we first give a full characterization of pure to mixed state LOCC-conversions. Then, we introduce a new conversion distance and derive a closed-form expression for it. These results might be of independent interest.