We prove that there are tripartite quantum states (constructed from random unitaries) that can lead to arbitrarily large violations of Bell inequalities for dichotomic observables. As a consequence these states …
We prove that there are tripartite quantum states (constructed from random unitaries) that can lead to arbitrarily large violations of Bell inequalities for dichotomic observables. As a consequence these states can withstand an arbitrary amount of white noise before they admit a description within a local hidden variable model. This is in sharp contrast with the bipartite case, where all violations are bounded by Grothendieck's constant. We will discuss the possibility of determining the Hilbert space dimension from the obtained violation and comment on implications for communication complexity theory. Moreover, we show that the violation obtained from generalized GHZ states is always bounded so that, in contrast to many other contexts, GHZ states do in this case not lead to extremal quantum correlations. The results are based on tools from the theories of operator spaces and tensor norms which we exploit to prove the existence of bounded but not completely bounded trilinear forms from commutative C*-algebras.
We show that Tsirelson's problem concerning the set of quantum correlations and Connes' embedding problem on finite approximations in von Neumann algebras (known to be equivalent to Kirchberg's QWEP conjecture) …
We show that Tsirelson's problem concerning the set of quantum correlations and Connes' embedding problem on finite approximations in von Neumann algebras (known to be equivalent to Kirchberg's QWEP conjecture) are essentially equivalent. Specifically, Tsirelson's problem asks whether the set of bipartite quantum correlations generated between tensor product separated systems is the same as the set of correlations between commuting C*-algebras. Connes' embedding problem asks whether any separable II$_1$ factor is a subfactor of the ultrapower of the hyperfinite II$_1$ factor. We show that an affirmative answer to Connes' question implies a positive answer to Tsirelson's. Conversely, a positve answer to a matrix valued version of Tsirelson's problem implies a positive one to Connes' problem.
In this Letter we show that quantum nonlocality can be superactivated. That is, one can obtain violations of Bell inequalities by tensorizing a local state with itself. In the second …
In this Letter we show that quantum nonlocality can be superactivated. That is, one can obtain violations of Bell inequalities by tensorizing a local state with itself. In the second part of this work we study how large these violations can be. In particular, we show the existence of quantum states with very low Bell violation but such that five copies of them give very large violations. In fact, this gap can be made arbitrarily large by increasing the dimension of the states.
In this Letter we show that the field of operator space theory provides a general and powerful mathematical framework for arbitrary Bell inequalities, in particular, regarding the scaling of their …
In this Letter we show that the field of operator space theory provides a general and powerful mathematical framework for arbitrary Bell inequalities, in particular, regarding the scaling of their violation within quantum mechanics. We illustrate the power of this connection by showing that bipartite quantum states with local, Hilbert space dimension $n$ can violate a Bell inequality by a factor of order $\sqrt{n}/({log}^{2}n)$ when observables with $n$ possible outcomes are used. Applications to resistance to noise, Hilbert space dimension estimates, and communication complexity are given.
Entanglement theory is formulated as a quantum resource theory in which the free operations are local operations and classical communication (LOCC). This defines a partial order among bipartite pure states …
Entanglement theory is formulated as a quantum resource theory in which the free operations are local operations and classical communication (LOCC). This defines a partial order among bipartite pure states that makes it possible to identify a maximally entangled state, which turns out to be the most relevant state in applications. However, the situation changes drastically in the multipartite regime. Not only do there exist inequivalent forms of entanglement forbidding the existence of a unique maximally entangled state, but recent results have shown that LOCC induces a trivial ordering: almost all pure entangled multipartite states are incomparable (i.e., LOCC transformations among them are almost never possible). In order to cope with this problem we consider alternative resource theories in which we relax the class of LOCC to operations that do not create entanglement. We consider two possible theories depending on whether resources correspond to multipartite entangled or genuinely multipartite entangled (GME) states and we show that they are both nontrivial: no inequivalent forms of entanglement exist in them and they induce a meaningful partial order (i.e., every pure state is transformable to more weakly entangled pure states). Moreover, we prove that the resource theory of GME that we formulate here has a unique maximally entangled state, the generalized GHZ state, which can be transformed to any other state by the allowed free operations.
Quantum entanglement and nonlocality are inextricably linked. However, while entanglement is necessary for nonlocality, it is not always sufficient in the standard Bell scenario. We derive sufficient conditions for entanglement …
Quantum entanglement and nonlocality are inextricably linked. However, while entanglement is necessary for nonlocality, it is not always sufficient in the standard Bell scenario. We derive sufficient conditions for entanglement to give rise to genuine multipartite nonlocality in networks. We find that any network where the parties are connected by bipartite pure entangled states is genuine multipartite nonlocal, independently of the amount of entanglement in the shared states and of the topology of the network. As an application of this result, we also show that all pure genuine multipartite entangled states are genuine multipartite nonlocal in the sense that measurements can be found on finitely many copies of any genuine multipartite entangled state to yield a genuine multipartite nonlocal behavior. Our results pave the way toward feasible manners of generating genuine multipartite nonlocality using any connected network.
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the …
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the applications of quantum mechanics to information theory, cryptography, and algorithms. Using the framework of nonlocal games, we relate measures of the nonlocality of quantum mechanics to certain norms in the Banach and operator space categories. We survey recent results that exploit this connection to derive large violations of Bell inequalities, study the complexity of the classical and quantum values of games and their relation to Grothendieck inequalities, and quantify the nonlocality of different classes of entangled states.
Genuine multipartite entanglement (GME) is considered a powerful form of entanglement since it corresponds to those states that are not biseparable, i.e. a mixture of partially separable states across different …
Genuine multipartite entanglement (GME) is considered a powerful form of entanglement since it corresponds to those states that are not biseparable, i.e. a mixture of partially separable states across different bipartitions of the parties. In this work we study this phenomenon in the multiple-copy regime, where many perfect copies of a given state can be produced and controlled. In this scenario the above definition leads to subtle intricacies as biseparable states can be GME-activatable, i.e. several copies of a biseparable state can display GME. We show that the set of GME-activatable states admits a simple characterization: a state is GME-activatable if and only if it is not partially separable across one bipartition of the parties. This leads to the second question of whether there is a general upper bound in the number of copies that needs to be considered in order to observe the activation of GME, which we answer in the negative. In particular, by providing an explicit construction, we prove that for any number of parties and any number <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo>&#x2208;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">N</mml:mi></mml:mrow></mml:math> there exist GME-activatable multipartite states of fixed (i.e. independent of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>) local dimensions such that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> copies of them remain biseparable.
We prove that given any two general probabilistic theories (GPTs) the following are equivalent: (i) each theory is nonclassical, meaning that neither of their state spaces is a simplex; (ii) …
We prove that given any two general probabilistic theories (GPTs) the following are equivalent: (i) each theory is nonclassical, meaning that neither of their state spaces is a simplex; (ii) each theory satisfies a strong notion of incompatibility equivalent to the existence of "superpositions"; and (iii) the two theories are entangleable, in the sense that their composite exhibits either entangled states or entangled measurements. Intuitively, in the post-quantum GPT setting, a superposition is a set of two binary ensembles of states that are unambiguously distinguishable if the ensemble is revealed before the measurement has occurred, but not if it is revealed after. This notion is important because we show that, just like in quantum theory, superposition in the form of strong incompatibility is sufficient to realize the Bennett-Brassard 1984 protocol for secret key distribution.
Journal Article ORTHOGONALLY ADDITIVE POLYNOMIALS ON C*-ALGEBRAS Get access C. Palazuelos, C. Palazuelos Departamento de Análisis Matemático, Facultad de Matemáticas, Universidad Complutense de Madrid, Madrid 28040, Spain Search for other …
Journal Article ORTHOGONALLY ADDITIVE POLYNOMIALS ON C*-ALGEBRAS Get access C. Palazuelos, C. Palazuelos Departamento de Análisis Matemático, Facultad de Matemáticas, Universidad Complutense de Madrid, Madrid 28040, Spain Search for other works by this author on: Oxford Academic Google Scholar A. M. Peralta, A. M. Peralta ‡ Departamento de Análisis Matemático, Facultad de Ciencias, Universidad de Granada, 18071 Granada, Spain ‡Corresponding author. E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar I. Villanueva I. Villanueva Departamento de Análisis Matemático, Facultad de Matemáticas, Universidad Complutense de Madrid, Madrid 28040, Spain Search for other works by this author on: Oxford Academic Google Scholar The Quarterly Journal of Mathematics, Volume 59, Issue 3, September 2008, Pages 363–374, https://doi.org/10.1093/qmath/ham042 Published: 30 October 2007 Article history Received: 02 March 2007 Revision received: 20 June 2007 Published: 30 October 2007
The no-programing theorem prohibits the existence of a universal programmable quantum processor. This statement has several implications in relation to quantum computation but also to other tasks of quantum information …
The no-programing theorem prohibits the existence of a universal programmable quantum processor. This statement has several implications in relation to quantum computation but also to other tasks of quantum information processing, making this construction a central notion in this context. Nonetheless, it is well known that, even when the strict model is not implementable, it is possible to conceive of it in an approximate sense. Unfortunately, the minimal resources necessary for this aim are still not completely understood. Here, we investigate quantitative statements of the theorem, improving exponentially previous bounds on the resources required by such a hypothetical machine. The proofs exploit a new connection between quantum channels and embeddings between Banach spaces which allows us to use classical tools from geometric Banach space theory in a clean and simple way.
In this seminar we will introduce the problem of finding optimal time hypercontractivity bounds for the Ornstein-Uhlenbeck semigroup acting on Clifford algebras. Moreover, we will show how one can extend …
In this seminar we will introduce the problem of finding optimal time hypercontractivity bounds for the Ornstein-Uhlenbeck semigroup acting on Clifford algebras. Moreover, we will show how one can extend this result to obtain optimal time hypercontractivity estimates for the free product extension of that semigroup. This generalization is based on a central limit theorem for free products of spin matrix algebras with mixed commutation/anticommutation relations. In particular, this result generalizes the work of Nelson, Gross, Carlen/Lieb and Biane.
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question …
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$2t$ polynomials. Based on this, we obtain a refined notion of approximate …
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$2t$ polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials. Revision note: A mistake was found in the proof of the second result on degree-4 polynomials far from 2-query quantum algorithms. An explanation of the issue, a corrected proof and stronger examples are presented in work of Escudero Gutiérrez and the second author.
We define and study XOR games in the framework of general probabilistic theories, which encompasses all physical models whose predictive power obeys minimal requirements. The bias of an XOR game …
We define and study XOR games in the framework of general probabilistic theories, which encompasses all physical models whose predictive power obeys minimal requirements. The bias of an XOR game under local or global strategies is shown to be given by a certain injective or projective tensor norm, respectively. The intrinsic (i.e.\ model-independent) advantage of global over local strategies is thus connected to a universal function $r(n,m)$ called 'projective-injective ratio'. This is defined as the minimal constant $\rho$ such that $\|\cdot\|_{X\otimes_\pi Y}\leq\rho\,\|\cdot\|_{X\otimes_\varepsilon Y}$ holds for all Banach spaces of dimensions $\dim X=n$ and $\dim Y=m$, where $X\otimes_\pi Y$ and $X \otimes_\varepsilon Y$ are the projective and injective tensor products. By requiring that $X=Y$, one obtains a symmetrised version of the above ratio, denoted by $r_s(n)$. We prove that $r(n,m)\geq 19/18$ for all $n,m\geq 2$, implying that injective and projective tensor products are never isometric. We then study the asymptotic behaviour of $r(n,m)$ and $r_s(n)$, showing that, up to log factors: $r_s(n)$ is of the order $\sqrt{n}$ (which is sharp); $r(n,n)$ is at least of the order $n^{1/6}$; and $r(n,m)$ grows at least as $\min\{n,m\}^{1/8}$. These results constitute our main contribution to the theory of tensor norms. In our proof, a crucial role is played by an '$\ell_1$/$\ell_2$/$\ell_{\infty}$ trichotomy theorem' based on ideas by Pisier, Rudelson, Szarek, and Tomczak-Jaegermann. The main operational consequence we draw is that there is a universal gap between local and global strategies in general XOR games, and that this grows as a power of the minimal local dimension. In the quantum case, we are able to determine this gap up to universal constants. As a corollary, we obtain an improved bound on the scaling of the maximal quantum data hiding efficiency against local measurements.
We characterize by means of a vector norm inequality the space of operators that factorize through a p-summing operator from an L-r-space to an L-s-space. As an application, we prove …
We characterize by means of a vector norm inequality the space of operators that factorize through a p-summing operator from an L-r-space to an L-s-space. As an application, we prove a domination result in the sense of Dodds-Fremlin for p-summing operators on Banach lattices with cotype 2, showing moreover that this cannot hold in general for spaces with higher cotype. We also present a new characterization of Banach lattices satisfying a lower 2-estimate in terms of the order properties of 2-summing operators.
The study of entanglement in multipartite quantum states plays a major role in quantum information theory and genuine multipartite entanglement signals one of its strongest forms for applications. However, its …
The study of entanglement in multipartite quantum states plays a major role in quantum information theory and genuine multipartite entanglement signals one of its strongest forms for applications. However, its characterization for general (mixed) states is a highly nontrivial problem. We introduce a particularly simple subclass of multipartite states, which we term pair-entangled network (PEN) states, as those that can be created by distributing exclusively bipartite entanglement in a connected network. We show that genuine multipartite entanglement in a PEN state depends on both the level of noise and the network topology and, in sharp contrast to the case of pure states, it is not guaranteed by the mere distribution of mixed bipartite entangled states. Our main result is a markedly drastic feature of this phenomenon: the amount of connectivity in the network determines whether genuine multipartite entanglement is robust to noise for any system size or whether it is completely washed out under the slightest form of noise for a sufficiently large number of parties. This latter case implies fundamental limitations for the application of certain networks in realistic scenarios, where the presence of some form of noise is unavoidable. To illustrate the applicability of PEN states to study the complex phenomenology behind multipartite entanglement, we also use them to prove superactivation of genuine multipartite nonlocality for any number of parties.
We show how a vector-valued version of Schechtman’s empirical method can be used to reduce the number of questions in a nonlocal game G while preserving the quotient β∗(G)/β(G) of …
We show how a vector-valued version of Schechtman’s empirical method can be used to reduce the number of questions in a nonlocal game G while preserving the quotient β∗(G)/β(G) of the quantum over the classical bias. We apply our method to the Khot-Vishnoi game, with exponentially many questions per player, to produce a family of games indexed in n with polynomially many (N ≈ n8) questions and n answers per player so that the ratio of the quantum over the classical bias is Ω(n/log2 n).
Journal Article CB-Norm Estimates for Maps Between Noncommutative Lp-Spaces and Quantum Channel Theory Get access Marius Junge, Marius Junge 1Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green …
Journal Article CB-Norm Estimates for Maps Between Noncommutative Lp-Spaces and Quantum Channel Theory Get access Marius Junge, Marius Junge 1Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green St., Urbana, IL 61891, USA Correspondence to be sent to: e-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Carlos Palazuelos Carlos Palazuelos 2Instituto de Ciencias Matemáticas, ICMAT, Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid, Plaza de Ciencias s/n. 28040, Madrid, Spain Search for other works by this author on: Oxford Academic Google Scholar International Mathematics Research Notices, Volume 2016, Issue 3, 2016, Pages 875–925, https://doi.org/10.1093/imrn/rnv161 Published: 04 June 2015 Article history Received: 18 September 2014 Revision received: 28 April 2015 Accepted: 11 May 2015 Published: 04 June 2015
We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, …
We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, that any two orthogonal quantum states of a $n_A\times n_B$ bipartite quantum system can be discriminated via local measurements with an error probability no larger than $\frac12 \left(1 - \frac{1}{c \min\{n_A, n_B\}} \right)$, where $1\leq c\leq 2\sqrt2$ is a universal constant, and our bound scales provably optimally with the local dimensions $n_A,n_B$. Mathematically, this is achieved by showing that the distinguishability norm $\|\cdot\|_{LO}$ associated with local measurements satisfies that $\|\cdot\|_1\leq 2\sqrt2 \min\{n_A,n_B\} \|\cdot\|_{LO}$, where $\|\cdot\|_1$ is the trace norm.
In this paper we introduce a simple and natural bipartite Bell scenario, by considering the correlations between two parties defined by general measurements in one party and dichotomic ones in …
In this paper we introduce a simple and natural bipartite Bell scenario, by considering the correlations between two parties defined by general measurements in one party and dichotomic ones in the other. We show that unbounded Bell violations can be obtained in this context. Since such violations cannot occur when both parties use dichotomic measurements, our setting can be considered as the simplest one where this phenomenon can be observed. Our example is essentially optimal in terms of the outputs and the Hilbert space dimension.
In this paper, we provide a combinatorial/numerical method to establish new hypercontractivity estimates in group von Neumann algebras. We will illustrate our method with free groups, triangular groups and finite …
In this paper, we provide a combinatorial/numerical method to establish new hypercontractivity estimates in group von Neumann algebras. We will illustrate our method with free groups, triangular groups and finite cyclic groups, for which we shall obtain optimal time hypercontractive $L_2 \to L_q$ inequalities with respect to the Markov process given by the word length and with $q$ an even integer. Interpolation and differentiation also yield general $L_p \to L_q$ hypercontrativity for $1 < p \le q < \infty$ via logarithmic Sobolev inequalities. Our method admits further applications to other discrete groups without small loops as far as the numerical part ---which varies from one group to another--- is implemented and tested in a computer. We also develop another combinatorial method which does not rely on computational estimates and provides (non-optimal) $L_p \to L_q$ hypercontractive inequalities for a larger class of groups/lengths, including any finitely generated group equipped with a conditionally negative word length, like infinite Coxeter groups. Our second method also yields hypercontractivity bounds for groups admitting a finite dimensional proper cocycle. Hypercontractivity fails for conditionally negative lengths in groups satisfying Kazhdan property (T).
In this work we study rank-one quantum games. In particular, we focus on the study of the computability of the entangled value $\omega^*$. We show that the value $\omega^*$ can …
In this work we study rank-one quantum games. In particular, we focus on the study of the computability of the entangled value $\omega^*$. We show that the value $\omega^*$ can be efficiently approximated up to a multiplicative factor of 4. We also study the behavior of $\omega^*$ under the parallel repetition of rank-one quantum games, showing that it does not verify a perfect parallel repetition theorem. To obtain these results, we first connect rank-one games with the mathematical theory of operator spaces. We also reprove with these new tools essentially known results about the entangled value of rank-one games with one-way communication $\omega_{qow}$. In particular, we show that $\omega_{qow}$ can be computed efficiently and it satisfies a perfect parallel repetition theorem.
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We …
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We adopt the formalism of general probabilistic theories (GPTs), encompassing all physical models whose predictive power obeys minimal requirements. Examples include classical theories, which do not exhibit superposition and whose state space has the shape of a simplex, quantum mechanics, as well as more exotic models such as Popescu-Rohrlich boxes. We call two GPTs entangleable if their composite admits either entangled states or entangled measurements, and conjecture that any two non-classical theories are in fact entangleable. We present substantial evidence towards this conjecture by proving it (1) for the simplest case of 3-dimensional theories; (2) when the local state spaces are discrete, which covers foundationally relevant cases; (3) when one of the local theories is quantum mechanics. Furthermore, (4) we envision the existence of a quantitative relation between local non-classicality and global entangleability, explicitly describing it in the geometrically natural case where the local state spaces are centrally symmetric.
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, …
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, we use these estimates to study the classical capacity with restricted assisted entanglement of the quantum erasure channel and the quantum depolarizing channel. In particular, we exactly compute the capacity of the first one and we show that certain nonmultiplicative results hold for the second one.
In this paper we show how \emph{the metric theory of tensor products} developed by Grothendieck perfectly fits in the study of channel capacities, a central topic in \emph{Shannon's information theory}. …
In this paper we show how \emph{the metric theory of tensor products} developed by Grothendieck perfectly fits in the study of channel capacities, a central topic in \emph{Shannon's information theory}. Furthermore, in the last years Shannon's theory has been generalized to the quantum setting to let the \emph{quantum information theory} step in. In this paper we consider the classical capacity of quantum channels with restricted assisted entanglement. In particular these capacities include the classical capacity and the unlimited entanglement-assisted classical capacity of a quantum channel. To deal with the quantum case we will use the noncommutative version of $p$-summing maps. More precisely, we prove that the (product state) classical capacity of a quantum channel with restricted assisted entanglement can be expressed as the derivative of a completely $p$-summing norm.
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We …
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We adopt the formalism of general probabilistic theories (GPTs), encompassing all physical models whose predictive power obeys minimal requirements. Examples include classical theories, which do not exhibit superposition and whose state space has the shape of a simplex, quantum mechanics, as well as more exotic models such as Popescu-Rohrlich boxes. We call two GPTs entangleable if their composite admits either entangled states or entangled measurements, and conjecture that any two non-classical theories are in fact entangleable. We present substantial evidence towards this conjecture by proving it (1) for the simplest case of 3-dimensional theories; (2) when the local state spaces are discrete, which covers foundationally relevant cases; (3) when one of the local theories is quantum mechanics. Furthermore, (4) we envision the existence of a quantitative relation between local non-classicality and global entangleability, explicitly describing it in the geometrically natural case where the local state spaces are centrally symmetric.
We obtain hypercontractivity estimates for a large class of semigroups defined on finite-dimensional matrix algebras 𝕄n. These semigroups arise from Poisson-like length functions ψ on ℤn × ℤn and provide …
We obtain hypercontractivity estimates for a large class of semigroups defined on finite-dimensional matrix algebras 𝕄n. These semigroups arise from Poisson-like length functions ψ on ℤn × ℤn and provide new hypercontractive families of quantum channels when ψ is conditionally negative. We also study the optimality of our estimates.
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, …
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, we use these estimates to study the classical capacity with restricted assisted entanglement of the quantum erasure channel and the quantum depolarizing channel. In particular, we exactly compute the capacity of the first one and we show that certain nonmultiplicative results hold for the second one.
In this paper, we obtain optimal time hypercontractivity bounds for the free product extension of the Ornstein-Uhlenbeck semigroup acting on the Clifford algebra. Our approach is based on a central …
In this paper, we obtain optimal time hypercontractivity bounds for the free product extension of the Ornstein-Uhlenbeck semigroup acting on the Clifford algebra. Our approach is based on a central limit theorem for free products of spin matrix algebras with mixed commutation/anticommutation relations. With another use of Speicher's central limit theorem, we may also obtain the same bounds for free products of q-deformed von Neumann algebras interpolating between the fermonic and bosonic frameworks. This generalizes the work of Nelson, Gross, Carlen/Lieb and Biane. Our main application yields hypercontractivity bounds for the free Poisson semigroup acting on the group algebra of the free group Fn, uniformly in the number of generators.
We study the projective tensor norm as a measure of the largest Bell violation of a quantum state. In order to do this, we consider a truncated version of a …
We study the projective tensor norm as a measure of the largest Bell violation of a quantum state. In order to do this, we consider a truncated version of a well-known SDP relaxation for the quantum value of a two-prover one-round game, one which has extra restrictions on the dimension of the SDP solutions. Our main result provides a quite accurate upper bound for the distance between the classical value of a Bell inequality and the corresponding value of the relaxation. Along the way, we give a simple proof that the best complementation constant of $\ell_2^n$ in $\ell_1(\ell_\infty)$ is of order $\sqrt{\ln n}$. As a direct consequence, we show that we cannot remove a logarithmic factor when we are computing the largest Bell violation attainable by the maximally entangled state.
The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this …
The discrepancy method is widely used to find lower bounds for communication complexity of XOR games. It is well known that these bounds can be far from optimal. In this context Disjointness is usually mentioned as a case where the method fails to give good bounds, because the increment of the value of the game is linear (rather than exponential) in the number of communicated bits. We show in this paper the existence of XOR games where the discrepancy method yields bounds as poor as one desires. Indeed, we show the existence of such games with any previously prescribed value. To prove this result we apply the theory of p-summing operators, a central topic in Banach space theory. We show in the paper other applications of this theory to the study of the communication complexity of XOR games.
In recent papers, the Right and the Strong$^*$ topologies have been introduced and studied on general Banach spaces. We characterize different types of continuity for multilinear operators (joint, uniform, etc.) …
In recent papers, the Right and the Strong$^*$ topologies have been introduced and studied on general Banach spaces. We characterize different types of continuity for multilinear operators (joint, uniform, etc.) with respect to the above topologies. We al
The violations of Bell inequalities by measurements on quantum states give rise to the phenomenon of quantum non-locality and express the advantage of using quantum resources over classical ones for …
The violations of Bell inequalities by measurements on quantum states give rise to the phenomenon of quantum non-locality and express the advantage of using quantum resources over classical ones for certain information-theoretic tasks. The relative degree of quantum violations has been well studied in the bipartite scenario and in the multipartite scenario with respect to fully local behaviours. However, the multipartite setting entails a more complex classification in which different notions on non-locality can be established. In particular, genuine multipartite non-local distributions apprehend truly multipartite effects, given that these behaviours cannot be reproduced by bilocal models that allow correlations among strict subsets of the parties beyond a local common cause. We show here that, while in the so-called correlation scenario the relative violation of bilocal Bell inequalities by quantum resources is bounded, i.e. it does not grow arbitrarily with the number of inputs, it turns out to be unbounded in the general case. We identify Bell functionals that take the form of non-local games for which the ratio of the quantum and bilocal values grows unboundedly as a function of the number of inputs and outputs.
Quantum networks are under current active investigation for the implementation of quantum communication tasks. With this motivation in mind, we study the entanglement properties of the multipartite states underlying these …
Quantum networks are under current active investigation for the implementation of quantum communication tasks. With this motivation in mind, we study the entanglement properties of the multipartite states underlying these networks. We show that, in sharp contrast to the case of pure states, genuine multipartite entanglement is severely affected by the presence of noise depending on the network topology: the amount of connectivity determines whether genuine multipartite entanglement is robust for any system size or whether it is completely washed out under the slightest form of noise for a sufficiently large number of parties. The impossibility to obtain genuine multipartite entanglement in some networks implies some fundamental limitations for their applications. In addition, the family of states considered in this work proves very useful to find new examples of states with interesting properties. We show this by constructing states of any number of parties that display superactivation of genuine multipartite nonlocality.
In this paper, we obtain optimal time hypercontractivity bounds for the free product extension of the Ornstein-Uhlenbeck semigroup acting on the Clifford algebra. Our approach is based on a central …
In this paper, we obtain optimal time hypercontractivity bounds for the free product extension of the Ornstein-Uhlenbeck semigroup acting on the Clifford algebra. Our approach is based on a central limit theorem for free products of spin matrix algebras with mixed commutation/anticommutation relations. With another use of Speicher's central limit theorem, we may also obtain the same bounds for free products of q-deformed von Neumann algebras interpolating between the fermonic and bosonic frameworks. This generalizes the work of Nelson, Gross, Carlen/Lieb and Biane. Our main application yields hypercontractivity bounds for the free Poisson semigroup acting on the group algebra of the free group Fn, uniformly in the number of generators.
In this work we show that, given a linear map from a general operator space into the dual of a C⁎-algebra, its completely bounded norm is upper bounded by a …
In this work we show that, given a linear map from a general operator space into the dual of a C⁎-algebra, its completely bounded norm is upper bounded by a universal constant times its (1,cb)-summing norm. This problem is motivated by the study of quantum XOR games in the field of quantum information theory. In particular, our results imply that for such games entangled strategies cannot be arbitrarily better than those strategies using one-way classical communication.
Quantum networks are promising venues for quantum information processing. This motivates the study of the entanglement properties of the particular multipartite quantum states that underpin these structures. In particular, it …
Quantum networks are promising venues for quantum information processing. This motivates the study of the entanglement properties of the particular multipartite quantum states that underpin these structures. In particular, it has been recently shown that when the links are noisy two drastically different behaviors can occur regarding the global entanglement properties of the network. While in certain configurations the network displays genuine multipartite entanglement (GME) for any system size provided the noise level is below a certain threshold, in others GME is washed out if the system size is big enough for any fixed non-zero level of noise. However, this difference has only been established considering the two extreme cases of maximally and minimally connected networks (i.e. complete graphs versus trees, respectively). In this article we investigate this question much more in depth and relate this behavior to the growth of several graph theoretic parameters that measure the connectivity of the graph sequence that codifies the structure of the network as the number of parties increases. The strongest conditions are obtained when considering the degree growth. Our main results are that a sufficiently fast degree growth (i.e. $\Omega(N)$, where $N$ is the size of the network) is sufficient for asymptotic robustness of GME, while if it is sufficiently slow (i.e. $o(\log N)$) then the network becomes asymptotically biseparable. We also present several explicit constructions related to the optimality of these results.
Abstract We show that, given , there exist ‐player quantum XOR games for which the entangled bias can be arbitrarily larger than the bias of the game when the players …
Abstract We show that, given , there exist ‐player quantum XOR games for which the entangled bias can be arbitrarily larger than the bias of the game when the players are restricted to separable strategies. In particular, quantum entanglement can be a much more powerful resource than local operations and classical communication to play these games. This result shows a strong contrast to the bipartite case, where it was recently proved that, as a consequence of a noncommutative version of Grothendieck theorem, the entangled bias is always upper bounded by a universal constant times the one‐way classical communication bias. In this sense, our main result can be understood as a counterexample to an extension of such a noncommutative Grothendieck theorem to multilinear forms.
We show the failure of a matricial version of Grothendieck's theorem for operator spaces, thereby resolving a long-standing open question in the field. Moreover, by showing that such a counterexample …
We show the failure of a matricial version of Grothendieck's theorem for operator spaces, thereby resolving a long-standing open question in the field. Moreover, by showing that such a counterexample can occur in the simplest context of commutative $C^*$-algebras, we address some other open questions in operator algebras. Our constructions, completely explicit and fairly simple, are inspired by some techniques in quantum information theory.
We consider the problem of learning low-degree quantum objects up to $\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and …
We consider the problem of learning low-degree quantum objects up to $\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and unitaries can be learned using $O(1/\varepsilon^d)$ queries (independent of $n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithms can be classically learned from $O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (which implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$ polynomials $p:\{-1,1\}^n\to [-1,1]$ can be learned through $O(1/\varepsilon^d)$ queries to a quantum unitary $U_p$ that block-encodes $p$. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.
In this paper we show that, given $k\geq 3$, there exist $k$-player quantum XOR games for which the entangled bias can be arbitrarily larger than the bias of the game …
In this paper we show that, given $k\geq 3$, there exist $k$-player quantum XOR games for which the entangled bias can be arbitrarily larger than the bias of the game when the players are restricted to separable strategies. In particular, quantum entanglement can be a much more powerful resource than local operations and classical communication to play these games. This result shows a strong contrast to the bipartite case, where it was recently proved that the entangled bias is always upper bounded by a universal constant times the one-way classical communication bias.
In this work we show that, given a linear map from a general operator space into the dual of a C⁎-algebra, its completely bounded norm is upper bounded by a …
In this work we show that, given a linear map from a general operator space into the dual of a C⁎-algebra, its completely bounded norm is upper bounded by a universal constant times its (1,cb)-summing norm. This problem is motivated by the study of quantum XOR games in the field of quantum information theory. In particular, our results imply that for such games entangled strategies cannot be arbitrarily better than those strategies using one-way classical communication.
We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, …
We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, that any two orthogonal quantum states of a $n_A\times n_B$ bipartite quantum system can be discriminated via local measurements with an error probability no larger than $\frac12 \left(1 - \frac{1}{c \min\{n_A, n_B\}} \right)$, where $1\leq c\leq 2\sqrt2$ is a universal constant, and our bound scales provably optimally with the local dimensions $n_A,n_B$. Mathematically, this is achieved by showing that the distinguishability norm $\|\cdot\|_{LO}$ associated with local measurements satisfies that $\|\cdot\|_1\leq 2\sqrt2 \min\{n_A,n_B\} \|\cdot\|_{LO}$, where $\|\cdot\|_1$ is the trace norm.
Genuine multipartite entanglement (GME) is considered a powerful form of entanglement since it corresponds to those states that are not biseparable, i.e. a mixture of partially separable states across different …
Genuine multipartite entanglement (GME) is considered a powerful form of entanglement since it corresponds to those states that are not biseparable, i.e. a mixture of partially separable states across different bipartitions of the parties. In this work we study this phenomenon in the multiple-copy regime, where many perfect copies of a given state can be produced and controlled. In this scenario the above definition leads to subtle intricacies as biseparable states can be GME-activatable, i.e. several copies of a biseparable state can display GME. We show that the set of GME-activatable states admits a simple characterization: a state is GME-activatable if and only if it is not partially separable across one bipartition of the parties. This leads to the second question of whether there is a general upper bound in the number of copies that needs to be considered in order to observe the activation of GME, which we answer in the negative. In particular, by providing an explicit construction, we prove that for any number of parties and any number <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo>&#x2208;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi mathvariant="double-struck">N</mml:mi></mml:mrow></mml:math> there exist GME-activatable multipartite states of fixed (i.e. independent of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>) local dimensions such that <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> copies of them remain biseparable.
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question …
Abstract In this work we initiate the study of position based quantum cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games. The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol. Known upper bounds for that quantity are exponential in the size of the quantum systems manipulated in the honest implementation of the protocol. However, known lower bounds are only linear. In order to deepen the understanding of this question, here we propose a position verification (PV) protocol and find lower bounds on the resources needed to break it. The main idea behind the proof of these bounds is the understanding of cheating strategies as vector valued assignments on the Boolean hypercube. Then, the bounds follow from the understanding of some geometric properties of particular Banach spaces, their type constants. Under some regularity assumptions on the former assignment, these bounds lead to exponential lower bounds on the quantum resources employed, clarifying the question in this restricted case. Known attacks indeed satisfy the assumption we make, although we do not know how universal this feature is. Furthermore, we show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol. Unfortunately, we were not able to estimate the relevant type constant. Despite that, we conjecture an upper bound for this quantity and show some evidence supporting it. A positive solution of the conjecture would lead to stronger security guarantees for the proposed PV protocol providing a better understanding of the question asked above.
The study of entanglement in multipartite quantum states plays a major role in quantum information theory and genuine multipartite entanglement signals one of its strongest forms for applications. However, its …
The study of entanglement in multipartite quantum states plays a major role in quantum information theory and genuine multipartite entanglement signals one of its strongest forms for applications. However, its characterization for general (mixed) states is a highly nontrivial problem. We introduce a particularly simple subclass of multipartite states, which we term pair-entangled network (PEN) states, as those that can be created by distributing exclusively bipartite entanglement in a connected network. We show that genuine multipartite entanglement in a PEN state depends on both the level of noise and the network topology and, in sharp contrast to the case of pure states, it is not guaranteed by the mere distribution of mixed bipartite entangled states. Our main result is a markedly drastic feature of this phenomenon: the amount of connectivity in the network determines whether genuine multipartite entanglement is robust to noise for any system size or whether it is completely washed out under the slightest form of noise for a sufficiently large number of parties. This latter case implies fundamental limitations for the application of certain networks in realistic scenarios, where the presence of some form of noise is unavoidable. To illustrate the applicability of PEN states to study the complex phenomenology behind multipartite entanglement, we also use them to prove superactivation of genuine multipartite nonlocality for any number of parties.
We prove that given any two general probabilistic theories (GPTs) the following are equivalent: (i) each theory is nonclassical, meaning that neither of their state spaces is a simplex; (ii) …
We prove that given any two general probabilistic theories (GPTs) the following are equivalent: (i) each theory is nonclassical, meaning that neither of their state spaces is a simplex; (ii) each theory satisfies a strong notion of incompatibility equivalent to the existence of "superpositions"; and (iii) the two theories are entangleable, in the sense that their composite exhibits either entangled states or entangled measurements. Intuitively, in the post-quantum GPT setting, a superposition is a set of two binary ensembles of states that are unambiguously distinguishable if the ensemble is revealed before the measurement has occurred, but not if it is revealed after. This notion is important because we show that, just like in quantum theory, superposition in the form of strong incompatibility is sufficient to realize the Bennett-Brassard 1984 protocol for secret key distribution.
Quantum networks are under current active investigation for the implementation of quantum communication tasks. With this motivation in mind, we study the entanglement properties of the multipartite states underlying these …
Quantum networks are under current active investigation for the implementation of quantum communication tasks. With this motivation in mind, we study the entanglement properties of the multipartite states underlying these networks. We show that, in sharp contrast to the case of pure states, genuine multipartite entanglement is severely affected by the presence of noise depending on the network topology: the amount of connectivity determines whether genuine multipartite entanglement is robust for any system size or whether it is completely washed out under the slightest form of noise for a sufficiently large number of parties. The impossibility to obtain genuine multipartite entanglement in some networks implies some fundamental limitations for their applications. In addition, the family of states considered in this work proves very useful to find new examples of states with interesting properties. We show this by constructing states of any number of parties that display superactivation of genuine multipartite nonlocality.
Quantum entanglement and nonlocality are inextricably linked. However, while entanglement is necessary for nonlocality, it is not always sufficient in the standard Bell scenario. We derive sufficient conditions for entanglement …
Quantum entanglement and nonlocality are inextricably linked. However, while entanglement is necessary for nonlocality, it is not always sufficient in the standard Bell scenario. We derive sufficient conditions for entanglement to give rise to genuine multipartite nonlocality in networks. We find that any network where the parties are connected by bipartite pure entangled states is genuine multipartite nonlocal, independently of the amount of entanglement in the shared states and of the topology of the network. As an application of this result, we also show that all pure genuine multipartite entangled states are genuine multipartite nonlocal in the sense that measurements can be found on finitely many copies of any genuine multipartite entangled state to yield a genuine multipartite nonlocal behavior. Our results pave the way toward feasible manners of generating genuine multipartite nonlocality using any connected network.
In this work we show that, given a linear map from a general operator space into the dual of a C$^*$-algebra, its completely bounded norm is upper bounded by a …
In this work we show that, given a linear map from a general operator space into the dual of a C$^*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(1,cb)$-summing norm. This problem is motivated by the study of quantum XOR games in the field of quantum information theory. In particular, our results imply that for such games entangled strategies cannot be arbitrarily better than those strategies using one-way classical communication.
We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, …
We prove a tight and close-to-optimal lower bound on the effectiveness of local quantum measurements (without classical communication) at discriminating any two bipartite quantum states. Our result implies, for example, that any two orthogonal quantum states of a $n_A\times n_B$ bipartite quantum system can be discriminated via local measurements with an error probability no larger than $\frac12 \left(1 - \frac{1}{c \min\{n_A, n_B\}} \right)$, where $1\leq c\leq 2\sqrt2$ is a universal constant, and our bound scales provably optimally with the local dimensions $n_A,n_B$. Mathematically, this is achieved by showing that the distinguishability norm $\|\cdot\|_{LO}$ associated with local measurements satisfies that $\|\cdot\|_1\leq 2\sqrt2 \min\{n_A,n_B\} \|\cdot\|_{LO}$, where $\|\cdot\|_1$ is the trace norm.
The violations of Bell inequalities by measurements on quantum states give rise to the phenomenon of quantum non-locality and express the advantage of using quantum resources over classical ones for …
The violations of Bell inequalities by measurements on quantum states give rise to the phenomenon of quantum non-locality and express the advantage of using quantum resources over classical ones for certain information-theoretic tasks. The relative degree of quantum violations has been well studied in the bipartite scenario and in the multipartite scenario with respect to fully local behaviours. However, the multipartite setting entails a more complex classification in which different notions on non-locality can be established. In particular, genuine multipartite non-local distributions apprehend truly multipartite effects, given that these behaviours cannot be reproduced by bilocal models that allow correlations among strict subsets of the parties beyond a local common cause. We show here that, while in the so-called correlation scenario the relative violation of bilocal Bell inequalities by quantum resources is bounded, i.e. it does not grow arbitrarily with the number of inputs, it turns out to be unbounded in the general case. We identify Bell functionals that take the form of non-local games for which the ratio of the quantum and bilocal values grows unboundedly as a function of the number of inputs and outputs.
We define and study XOR games in the framework of general probabilistic theories, which encompasses all physical models whose predictive power obeys minimal requirements. The bias of an XOR game …
We define and study XOR games in the framework of general probabilistic theories, which encompasses all physical models whose predictive power obeys minimal requirements. The bias of an XOR game under local or global strategies is shown to be given by a certain injective or projective tensor norm, respectively. The intrinsic (i.e.\ model-independent) advantage of global over local strategies is thus connected to a universal function $r(n,m)$ called 'projective-injective ratio'. This is defined as the minimal constant $\rho$ such that $\|\cdot\|_{X\otimes_\pi Y}\leq\rho\,\|\cdot\|_{X\otimes_\varepsilon Y}$ holds for all Banach spaces of dimensions $\dim X=n$ and $\dim Y=m$, where $X\otimes_\pi Y$ and $X \otimes_\varepsilon Y$ are the projective and injective tensor products. By requiring that $X=Y$, one obtains a symmetrised version of the above ratio, denoted by $r_s(n)$. We prove that $r(n,m)\geq 19/18$ for all $n,m\geq 2$, implying that injective and projective tensor products are never isometric. We then study the asymptotic behaviour of $r(n,m)$ and $r_s(n)$, showing that, up to log factors: $r_s(n)$ is of the order $\sqrt{n}$ (which is sharp); $r(n,n)$ is at least of the order $n^{1/6}$; and $r(n,m)$ grows at least as $\min\{n,m\}^{1/8}$. These results constitute our main contribution to the theory of tensor norms. In our proof, a crucial role is played by an '$\ell_1$/$\ell_2$/$\ell_{\infty}$ trichotomy theorem' based on ideas by Pisier, Rudelson, Szarek, and Tomczak-Jaegermann. The main operational consequence we draw is that there is a universal gap between local and global strategies in general XOR games, and that this grows as a power of the minimal local dimension. In the quantum case, we are able to determine this gap up to universal constants. As a corollary, we obtain an improved bound on the scaling of the maximal quantum data hiding efficiency against local measurements.
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We …
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We adopt the formalism of general probabilistic theories (GPTs), encompassing all physical models whose predictive power obeys minimal requirements. Examples include classical theories, which do not exhibit superposition and whose state space has the shape of a simplex, quantum mechanics, as well as more exotic models such as Popescu-Rohrlich boxes. We call two GPTs entangleable if their composite admits either entangled states or entangled measurements, and conjecture that any two non-classical theories are in fact entangleable. We present substantial evidence towards this conjecture by proving it (1) for the simplest case of 3-dimensional theories; (2) when the local state spaces are discrete, which covers foundationally relevant cases; (3) when one of the local theories is quantum mechanics. Furthermore, (4) we envision the existence of a quantitative relation between local non-classicality and global entangleability, explicitly describing it in the geometrically natural case where the local state spaces are centrally symmetric.
In this paper we characterize the set of bipartite non-signalling probability distributions in terms of tensor norms. Using this characterization we give optimal upper and lower bounds on Bell inequality …
In this paper we characterize the set of bipartite non-signalling probability distributions in terms of tensor norms. Using this characterization we give optimal upper and lower bounds on Bell inequality violations when non-signalling distributions are considered. Interestingly, our upper bounds show that non-signalling Bell inequality violations cannot be significantly larger than quantum Bell inequality violations.
Entanglement theory is formulated as a quantum resource theory in which the free operations are local operations and classical communication (LOCC). This defines a partial order among bipartite pure states …
Entanglement theory is formulated as a quantum resource theory in which the free operations are local operations and classical communication (LOCC). This defines a partial order among bipartite pure states that makes it possible to identify a maximally entangled state, which turns out to be the most relevant state in applications. However, the situation changes drastically in the multipartite regime. Not only do there exist inequivalent forms of entanglement forbidding the existence of a unique maximally entangled state, but recent results have shown that LOCC induces a trivial ordering: almost all pure entangled multipartite states are incomparable (i.e., LOCC transformations among them are almost never possible). In order to cope with this problem we consider alternative resource theories in which we relax the class of LOCC to operations that do not create entanglement. We consider two possible theories depending on whether resources correspond to multipartite entangled or genuinely multipartite entangled (GME) states and we show that they are both nontrivial: no inequivalent forms of entanglement exist in them and they induce a meaningful partial order (i.e., every pure state is transformable to more weakly entangled pure states). Moreover, we prove that the resource theory of GME that we formulate here has a unique maximally entangled state, the generalized GHZ state, which can be transformed to any other state by the allowed free operations.
The no-programing theorem prohibits the existence of a universal programmable quantum processor. This statement has several implications in relation to quantum computation but also to other tasks of quantum information …
The no-programing theorem prohibits the existence of a universal programmable quantum processor. This statement has several implications in relation to quantum computation but also to other tasks of quantum information processing, making this construction a central notion in this context. Nonetheless, it is well known that, even when the strict model is not implementable, it is possible to conceive of it in an approximate sense. Unfortunately, the minimal resources necessary for this aim are still not completely understood. Here, we investigate quantitative statements of the theorem, improving exponentially previous bounds on the resources required by such a hypothetical machine. The proofs exploit a new connection between quantum channels and embeddings between Banach spaces which allows us to use classical tools from geometric Banach space theory in a clean and simple way.
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$2t$ polynomials. Based on this, we obtain a refined notion of approximate …
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space of degree-$2t$ polynomials. Based on this, we obtain a refined notion of approximate polynomial degree that equals the quantum query complexity, answering a question of Aaronson et al. (CCC'16). Our proof is based on a fundamental result of Christensen and Sinclair (J. Funct. Anal., 1987) that generalizes the well-known Stinespring representation for quantum channels to multilinear forms. Using our characterization, we show that many polynomials of degree four are far from those coming from two-query quantum algorithms. We also give a simple and short proof of one of the results of Aaronson et al. showing an equivalence between one-query quantum algorithms and bounded quadratic polynomials. Revision note: A mistake was found in the proof of the second result on degree-4 polynomials far from 2-query quantum algorithms. An explanation of the issue, a corrected proof and stronger examples are presented in work of Escudero Gutiérrez and the second author.
In this paper we characterize the set of bipartite non-signalling probability distributions in terms of tensor norms. Using this characterization we give optimal upper and lower bounds on Bell inequality …
In this paper we characterize the set of bipartite non-signalling probability distributions in terms of tensor norms. Using this characterization we give optimal upper and lower bounds on Bell inequality violations when non-signalling distributions are considered. Interestingly, our upper bounds show that non-signalling Bell inequality violations cannot be significantly larger than quantum Bell inequality violations.
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We …
Inspired by its fundamental importance in quantum mechanics, we define and study the notion of entanglement for abstract physical theories, investigating its profound connection with the concept of superposition. We adopt the formalism of general probabilistic theories (GPTs), encompassing all physical models whose predictive power obeys minimal requirements. Examples include classical theories, which do not exhibit superposition and whose state space has the shape of a simplex, quantum mechanics, as well as more exotic models such as Popescu-Rohrlich boxes. We call two GPTs entangleable if their composite admits either entangled states or entangled measurements, and conjecture that any two non-classical theories are in fact entangleable. We present substantial evidence towards this conjecture by proving it (1) for the simplest case of 3-dimensional theories; (2) when the local state spaces are discrete, which covers foundationally relevant cases; (3) when one of the local theories is quantum mechanics. Furthermore, (4) we envision the existence of a quantitative relation between local non-classicality and global entangleability, explicitly describing it in the geometrically natural case where the local state spaces are centrally symmetric.
The no-programming theorem prohibits the existence of a Universal Programmable Quantum Processor. This statement has several implications in relation to quantum computation, but also to other tasks of quantum information …
The no-programming theorem prohibits the existence of a Universal Programmable Quantum Processor. This statement has several implications in relation to quantum computation, but also to other tasks of quantum information processing, making this construction a central notion in this context. Nonetheless, it is well known that even when the strict model is not implementable, it is possible to conceive of it in an approximate sense. Unfortunately, the minimal resources necessary for this aim are still not completely understood. Here, we investigate quantitative statements of the theorem, improving exponentially previous bounds on the resources required by such a hypothetical machine. The proofs exploit a new connection between quantum channels and embeddings between Banach spaces which allows us to use classical tools from geometric Banach space theory in a clean and simple way.
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are …
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are allowed to use a limited amount of one-way classical communication $\omega_{o.w.-c}(G)$ (resp. one-way quantum communication $\omega_{o.w.-c}^*(G)$), where $c$ denotes the number of bits (resp. qubits). The key quantity here is the quotient $\omega_{o.w.-c}^*(G)/\omega_{o.w.-c}(G)$.
We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient $\omega_{o.w.-c}^*(G)/\omega_{o.w.-2c}(G)$ is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016).
We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information $c$. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are …
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are allowed to use a limited amount of one-way classical communication $\omega_{o.w.-c}(G)$ (resp. one-way quantum communication $\omega_{o.w.-c}^*(G)$), where $c$ denotes the number of bits (resp. qubits). The key quantity here is the quotient $\omega_{o.w.-c}^*(G)/\omega_{o.w.-c}(G)$. We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient $\omega_{o.w.-c}^*(G)/\omega_{o.w.-2c}(G)$ is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information $c$. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.
We show how a vector-valued version of Schechtman’s empirical method can be used to reduce the number of questions in a nonlocal game G while preserving the quotient β∗(G)/β(G) of …
We show how a vector-valued version of Schechtman’s empirical method can be used to reduce the number of questions in a nonlocal game G while preserving the quotient β∗(G)/β(G) of the quantum over the classical bias. We apply our method to the Khot-Vishnoi game, with exponentially many questions per player, to produce a family of games indexed in n with polynomially many (N ≈ n8) questions and n answers per player so that the ratio of the quantum over the classical bias is Ω(n/log2 n).
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the …
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the applications of quantum mechanics to information theory, cryptography, and algorithms. Using the framework of nonlocal games, we relate measures of the nonlocality of quantum mechanics to certain norms in the Banach and operator space categories. We survey recent results that exploit this connection to derive large violations of Bell inequalities, study the complexity of the classical and quantum values of games and their relation to Grothendieck inequalities, and quantify the nonlocality of different classes of entangled states.
In this paper we introduce a simple and natural bipartite Bell scenario, by considering the correlations between two parties defined by general measurements in one party and dichotomic ones in …
In this paper we introduce a simple and natural bipartite Bell scenario, by considering the correlations between two parties defined by general measurements in one party and dichotomic ones in the other. We show that unbounded Bell violations can be obtained in this context. Since such violations cannot occur when both parties use dichotomic measurements, our setting can be considered as the simplest one where this phenomenon can be observed. Our example is essentially optimal in terms of the outputs and the Hilbert space dimension.
Journal Article CB-Norm Estimates for Maps Between Noncommutative Lp-Spaces and Quantum Channel Theory Get access Marius Junge, Marius Junge 1Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green …
Journal Article CB-Norm Estimates for Maps Between Noncommutative Lp-Spaces and Quantum Channel Theory Get access Marius Junge, Marius Junge 1Department of Mathematics, University of Illinois at Urbana-Champaign, 1409 W. Green St., Urbana, IL 61891, USA Correspondence to be sent to: e-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Carlos Palazuelos Carlos Palazuelos 2Instituto de Ciencias Matemáticas, ICMAT, Facultad de Ciencias Matemáticas, Universidad Complutense de Madrid, Plaza de Ciencias s/n. 28040, Madrid, Spain Search for other works by this author on: Oxford Academic Google Scholar International Mathematics Research Notices, Volume 2016, Issue 3, 2016, Pages 875–925, https://doi.org/10.1093/imrn/rnv161 Published: 04 June 2015 Article history Received: 18 September 2014 Revision received: 28 April 2015 Accepted: 11 May 2015 Published: 04 June 2015
We obtain hypercontractivity estimates for a large class of semigroups defined on finite-dimensional matrix algebras 𝕄n. These semigroups arise from Poisson-like length functions ψ on ℤn × ℤn and provide …
We obtain hypercontractivity estimates for a large class of semigroups defined on finite-dimensional matrix algebras 𝕄n. These semigroups arise from Poisson-like length functions ψ on ℤn × ℤn and provide new hypercontractive families of quantum channels when ψ is conditionally negative. We also study the optimality of our estimates.
In this seminar we will introduce the problem of finding optimal time hypercontractivity bounds for the Ornstein-Uhlenbeck semigroup acting on Clifford algebras. Moreover, we will show how one can extend …
In this seminar we will introduce the problem of finding optimal time hypercontractivity bounds for the Ornstein-Uhlenbeck semigroup acting on Clifford algebras. Moreover, we will show how one can extend this result to obtain optimal time hypercontractivity estimates for the free product extension of that semigroup. This generalization is based on a central limit theorem for free products of spin matrix algebras with mixed commutation/anticommutation relations. In particular, this result generalizes the work of Nelson, Gross, Carlen/Lieb and Biane.
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, …
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, we use these estimates to study the classical capacity with restricted assisted entanglement of the quantum erasure channel and the quantum depolarizing channel. In particular, we exactly compute the capacity of the first one and we show that certain nonmultiplicative results hold for the second one.
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, …
In the first part of this work we show how certain techniques from quantum information theory can be used in order to obtain very sharp embeddings between noncommutative $L_p$-spaces. Then, we use these estimates to study the classical capacity with restricted assisted entanglement of the quantum erasure channel and the quantum depolarizing channel. In particular, we exactly compute the capacity of the first one and we show that certain nonmultiplicative results hold for the second one.
In this paper we show how \emph{the metric theory of tensor products} developed by Grothendieck perfectly fits in the study of channel capacities, a central topic in \emph{Shannon's information theory}. …
In this paper we show how \emph{the metric theory of tensor products} developed by Grothendieck perfectly fits in the study of channel capacities, a central topic in \emph{Shannon's information theory}. Furthermore, in the last years Shannon's theory has been generalized to the quantum setting to let the \emph{quantum information theory} step in. In this paper we consider the classical capacity of quantum channels with restricted assisted entanglement. In particular these capacities include the classical capacity and the unlimited entanglement-assisted classical capacity of a quantum channel. To deal with the quantum case we will use the noncommutative version of $p$-summing maps. More precisely, we prove that the (product state) classical capacity of a quantum channel with restricted assisted entanglement can be expressed as the derivative of a completely $p$-summing norm.
In this paper, we provide a combinatorial/numerical method to establish new hypercontractivity estimates in group von Neumann algebras. We will illustrate our method with free groups, triangular groups and finite …
In this paper, we provide a combinatorial/numerical method to establish new hypercontractivity estimates in group von Neumann algebras. We will illustrate our method with free groups, triangular groups and finite cyclic groups, for which we shall obtain optimal time hypercontractive $L_2 \to L_q$ inequalities with respect to the Markov process given by the word length and with $q$ an even integer. Interpolation and differentiation also yield general $L_p \to L_q$ hypercontrativity for $1 < p \le q < \infty$ via logarithmic Sobolev inequalities. Our method admits further applications to other discrete groups without small loops as far as the numerical part ---which varies from one group to another--- is implemented and tested in a computer. We also develop another combinatorial method which does not rely on computational estimates and provides (non-optimal) $L_p \to L_q$ hypercontractive inequalities for a larger class of groups/lengths, including any finitely generated group equipped with a conditionally negative word length, like infinite Coxeter groups. Our second method also yields hypercontractivity bounds for groups admitting a finite dimensional proper cocycle. Hypercontractivity fails for conditionally negative lengths in groups satisfying Kazhdan property (T).
In this paper, we provide a combinatorial/numerical method to establish new hypercontractivity estimates in group von Neumann algebras. We will illustrate our method with free groups, triangular groups and finite …
In this paper, we provide a combinatorial/numerical method to establish new hypercontractivity estimates in group von Neumann algebras. We will illustrate our method with free groups, triangular groups and finite cyclic groups, for which we shall obtain optimal time hypercontractive $L_2 \to L_q$ inequalities with respect to the Markov process given by the word length and with $q$ an even integer. Interpolation and differentiation also yield general $L_p \to L_q$ hypercontrativity for $1 < p \le q < \infty$ via logarithmic Sobolev inequalities. Our method admits further applications to other discrete groups without small loops as far as the numerical part ---which varies from one group to another--- is implemented and tested in a computer. We also develop another combinatorial method which does not rely on computational estimates and provides (non-optimal) $L_p \to L_q$ hypercontractive inequalities for a larger class of groups/lengths, including any finitely generated group equipped with a conditionally negative word length, like infinite Coxeter groups. Our second method also yields hypercontractivity bounds for groups admitting a finite dimensional proper cocycle. Hypercontractivity fails for conditionally negative lengths in groups satisfying Kazhdan property (T).
We prove that there are tripartite quantum states (constructed from random unitaries) that can lead to arbitrarily large violations of Bell inequalities for dichotomic observables. As a consequence these states …
We prove that there are tripartite quantum states (constructed from random unitaries) that can lead to arbitrarily large violations of Bell inequalities for dichotomic observables. As a consequence these states can withstand an arbitrary amount of white noise before they admit a description within a local hidden variable model. This is in sharp contrast with the bipartite case, where all violations are bounded by Grothendieck's constant. We will discuss the possibility of determining the Hilbert space dimension from the obtained violation and comment on implications for communication complexity theory. Moreover, we show that the violation obtained from generalized GHZ states is always bounded so that, in contrast to many other contexts, GHZ states do in this case not lead to extremal quantum correlations. The results are based on tools from the theories of operator spaces and tensor norms which we exploit to prove the existence of bounded but not completely bounded trilinear forms from commutative C*-algebras.
In this Letter we show that the field of operator space theory provides a general and powerful mathematical framework for arbitrary Bell inequalities, in particular, regarding the scaling of their …
In this Letter we show that the field of operator space theory provides a general and powerful mathematical framework for arbitrary Bell inequalities, in particular, regarding the scaling of their violation within quantum mechanics. We illustrate the power of this connection by showing that bipartite quantum states with local, Hilbert space dimension $n$ can violate a Bell inequality by a factor of order $\sqrt{n}/({log}^{2}n)$ when observables with $n$ possible outcomes are used. Applications to resistance to noise, Hilbert space dimension estimates, and communication complexity are given.
We present the optimal collective attack on a quantum key distribution protocol in the "device-independent" security scenario, where no assumptions are made about the way the quantum key distribution devices …
We present the optimal collective attack on a quantum key distribution protocol in the "device-independent" security scenario, where no assumptions are made about the way the quantum key distribution devices work or on what quantum system they operate. Our main result is a tight bound on the Holevo information between one of the authorized parties and the eavesdropper, as a function of the amount of violation of a Bell-type inequality.
In this paper, we disprove the following conjecture due to Goemans (1997) and Linial (2002): "Every negative type metric embeds into with constant distortion." We show that for every /spl …
In this paper, we disprove the following conjecture due to Goemans (1997) and Linial (2002): "Every negative type metric embeds into with constant distortion." We show that for every /spl delta/ > 0, and for large enough n, there is an n-point negative type metric which requires distortion at-least (log log n) /sup 1/6-/spl delta// to embed into l/sub 1/. Surprisingly, our construction is inspired by the Unique Games Conjecture (UGC) of Khot (2002), establishing a previously unsuspected connection between PCPs and the theory of metric embeddings. We first prove that the UGC implies super-constant hardness results for (non-uniform) sparsest cut and minimum uncut problems. It is already known that the UGC also implies an optimal hardness result for maximum cut (2004). Though these hardness results depend on the UGC, the integrality gap instances rely "only" on the PCP reductions for the respective problems. Towards this, we first construct an integrality gap instance for a natural SDP relaxation of unique games. Then, we "simulate" the PCP reduction and "translate"the integrality gap instance of unique games to integrality gap instances for the respective cut problems! This enables us to prove a (log log n) /sup 1/6-/spl delta// integrality gap for (nonuniform) sparsest cut and minimum uncut, and an optimal integrality gap for maximum cut. All our SDP solutions satisfy the so-called "triangle inequality" constraints. This also shows, for the first time, that the triangle inequality constraints do not add any power to the Goemans-Williamson's SDP relaxation of maximum cut. The integrality gap for sparsest cut immediately implies a lower bound for embedding negative type metrics into l/sub i/. It also disproves the non-uniform version of Arora, Rao and Vazirani's Conjecture (2004), asserting that the integrality gap of the sparsest cut SDP, with the triangle inequality constraints, is bounded from above by a constant.
The first step in any quantum key distribution (QKD) protocol consists of sequences of measurements that produce correlated classical data. We show that these correlation data must violate some Bell …
The first step in any quantum key distribution (QKD) protocol consists of sequences of measurements that produce correlated classical data. We show that these correlation data must violate some Bell inequality in order to contain distillable secrecy, if not they could be produced by quantum measurements performed on a separable state of larger dimension. We introduce a new QKD protocol and prove its security against any individual attack by an adversary only limited by the no-signaling condition.
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the …
This review article is concerned with a recently uncovered connection between operator spaces, a noncommutative extension of Banach spaces, and quantum nonlocality, a striking phenomenon which underlies many of the applications of quantum mechanics to information theory, cryptography, and algorithms. Using the framework of nonlocal games, we relate measures of the nonlocality of quantum mechanics to certain norms in the Banach and operator space categories. We survey recent results that exploit this connection to derive large violations of Bell inequalities, study the complexity of the classical and quantum values of games and their relation to Grothendieck inequalities, and quantify the nonlocality of different classes of entangled states.
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and interference. In this review …
Quantum information processing is the emerging field that defines and realizes computing devices that make use of quantum mechanical principles, like the superposition principle, entanglement, and interference. In this review we study the information counterpart of computing. The abstract form of the distributed computing setting is called communication complexity. It studies the amount of information, in terms of bits or in our case qubits, that two spatially separated computing devices need to exchange in order to perform some computational task. Surprisingly, quantum mechanics can be used to obtain dramatic advantages for such tasks. We review the area of quantum communication complexity, and show how it connects the foundational physics questions regarding non-locality with those of communication complexity studied in theoretical computer science. The first examples exhibiting the advantage of the use of qubits in distributed information-processing tasks were based on non-locality tests. However, by now the field has produced strong and interesting quantum protocols and algorithms of its own that demonstrate that entanglement, although it cannot be used to replace communication, can be used to reduce the communication exponentially. In turn, these new advances yield a new outlook on the foundations of physics, and could even yield new proposals for experiments that test the foundations of physics.
Bell's 1964 theorem, which states that the predictions of quantum theory cannot be accounted for by any local theory, represents one of the most profound developments in the foundations of …
Bell's 1964 theorem, which states that the predictions of quantum theory cannot be accounted for by any local theory, represents one of the most profound developments in the foundations of physics. In the last two decades, Bell's theorem has been a central theme of research from a variety of perspectives, mainly motivated by quantum information science, where the nonlocality of quantum theory underpins many of the advantages afforded by a quantum processing of information. The focus of this review is to a large extent oriented by these later developments. We review the main concepts and tools which have been developed to describe and study the nonlocality of quantum theory, and which have raised this topic to the status of a full sub-field of quantum information science.
Let $E$ be an operator space in the sense of the theory recently developed by Blecher-Paulsen and Effros-Ruan. We introduce a notion of $E$-valued non commutative $L_p$-space for $1 \leq …
Let $E$ be an operator space in the sense of the theory recently developed by Blecher-Paulsen and Effros-Ruan. We introduce a notion of $E$-valued non commutative $L_p$-space for $1 \leq p < \infty$ and we prove that the resulting operator space satisfies the natural properties to be expected with respect to e.g. duality and interpolation. This notion leads to the definition of a ``completely p-summing" map which is the operator space analogue of the $p$-absolutely summing maps in the sense of Pietsch-Kwapie\'n. These notions extend the particular case $p=1$ which was previously studied by Effros-Ruan.
We discuss general Bell inequalities for bipartite and multipartite systems, emphasizing the connection with convex geometry on the mathematical side, and the communication aspects on the physical side. Known results …
We discuss general Bell inequalities for bipartite and multipartite systems, emphasizing the connection with convex geometry on the mathematical side, and the communication aspects on the physical side. Known results on families of generalized Bell inequalities are summarized. We investigate maximal violations of Bell inequalities as well as states not violating (certain) Bell inequalities. Finally, we discuss the relation between Bell inequality violations and entanglement properties currently discussed in quantum information theory.
Probably the most famous of Grothendieck's contributions to Banach space theory is the result that he himself described as "the fundamental theorem in the metric theory of tensor products". That …
Probably the most famous of Grothendieck's contributions to Banach space theory is the result that he himself described as "the fundamental theorem in the metric theory of tensor products". That is now commonly referred to as "Grothendieck's theorem" ("GT" for short), or sometimes as "Grothendieck's inequality". This had a major impact first in Banach space theory (roughly after 1968), then, later on, in $C^*$-algebra theory (roughly after 1978). More recently, in this millennium, a new version of GT has been successfully developed in the framework of "operator spaces" or non-commutative Banach spaces. In addition, GT independently surfaced in several quite unrelated fields: in connection with Bell's inequality in quantum mechanics, in graph theory where the Grothendieck constant of a graph has been introduced and in computer science where the Grothendieck inequality is invoked to replace certain NP hard problems by others that can be treated by "semidefinite programming" and hence solved in polynomial time. This expository paper (where many proofs are included), presents a review of all these topics, starting from the original GT. We concentrate on the more recent developments and merely outline those of the first Banach space period since detailed accounts of that are already available, for instance the author's 1986 CBMS notes.
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” We give two new two-player games with Bell inequality …
Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called “Bell inequality violations.” We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work. The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a strategy using a maximally entangled state with local dimension $n$ (e.g., $\log n$ EPR-pairs), while we show that the winning probability of any classical strategy differs from $\frac{1}{2}$ by at most $O((\log n)/\sqrt{n})$. The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here $n$-dimensional entanglement allows the game to be won with probability $1/(\log n)^2$, while the best winning probability without entanglement is $1/n$. This near-linear ratio is almost optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players. An earlier version of this paper appeared in the Proceedings of the 26th IEEE Conference on Computational Complexity, pages 157--166, 2011.
We provide alternative proofs of two recent Grothendieck theorems for jointly completely bounded bilinear forms, originally due to Pisier and Shlyakhtenko [PS02] and Haagerup and Musat [HM08].Our proofs are elementary …
We provide alternative proofs of two recent Grothendieck theorems for jointly completely bounded bilinear forms, originally due to Pisier and Shlyakhtenko [PS02] and Haagerup and Musat [HM08].Our proofs are elementary and are inspired by the so-called embezzlement states in quantum information theory.Moreover, our proofs lead to quantitative estimates.
In this Letter we show that quantum nonlocality can be superactivated. That is, one can obtain violations of Bell inequalities by tensorizing a local state with itself. In the second …
In this Letter we show that quantum nonlocality can be superactivated. That is, one can obtain violations of Bell inequalities by tensorizing a local state with itself. In the second part of this work we study how large these violations can be. In particular, we show the existence of quantum states with very low Bell violation but such that five copies of them give very large violations. In fact, this gap can be made arbitrarily large by increasing the dimension of the states.
Let $\Phi$ be a super-operator, i.e., a linear mapping of the form $\Phi:\mathrm{L}(\mathcal{F})\rightarrow\mathrm{L}(\mathcal{G})$ for finite dimensional Hilbert spaces $\mathcal{F}$ and $\mathcal{G}$. This paper considers basic properties of the super-operator norms …
Let $\Phi$ be a super-operator, i.e., a linear mapping of the form $\Phi:\mathrm{L}(\mathcal{F})\rightarrow\mathrm{L}(\mathcal{G})$ for finite dimensional Hilbert spaces $\mathcal{F}$ and $\mathcal{G}$. This paper considers basic properties of the super-operator norms defined by $\|\Phi\|_{q\rightarrow p}= \sup\{\|\Phi(X)\|_p/\|X\|_q\,:\,X\not=0\}$, induced by Schatten norms for $1\leq p,q\leq\infty$. These super-operator norms arise in various contexts in the study of quantum information. In this paper it is proved that if $\Phi$ is completely positive, the value of the supremum in the definition of $\|\Phi\|_{q\rightarrow p}$ is achieved by a positive semidefinite operator $X$, answering a question recently posed by King and Ruskai~\cite{KingR04}. However, for any choice of $p\in [1,\infty]$, there exists a super-operator $\Phi$ that is the {\em difference} of two completely positive, trace-preserving super-operators such that all Hermitian $X$ fail to achieve the supremum in the definition of $\|\Phi\|_{1\rightarrow p}$. Also considered are the properties of the above norms for super-operators tensored with the identity super-operator. In particular, it is proved that for all $p\geq 2$, $q\leq 2$, and arbitrary $\Phi$, the norm $\|\Phi \|_{q\rightarrow p}$ is stable under tensoring $\Phi$ with the identity super-operator, meaning that $\|\Phi \|_{q\rightarrow p} = \|\Phi \otimes I\|_{q\rightarrow p}$. For $1\leq p < 2$, the norm $\|\Phi\|_{1\rightarrow p}$ may fail to be stable with respect to tensoring $\Phi$ with the identity super-operator as just described, but $\|\Phi\otimes I\|_{1\rightarrow p}$ is stable in this sense for $I$ the identity super-operator on $\mathrm{L}(\mathcal{H})$ for $\op{dim}(\mathcal{H}) = \op{dim}(\mathcal{F})$. This generalizes and simplifies a proof due to Kitaev \cite{Kitaev97} that established this fact for the case $p=1$.
We prove a generalized version of the no-broadcasting theorem, applicable to essentially any nonclassical finite-dimensional probabilistic model satisfying a no-signaling criterion, including ones with ``superquantum'' correlations. A strengthened version of …
We prove a generalized version of the no-broadcasting theorem, applicable to essentially any nonclassical finite-dimensional probabilistic model satisfying a no-signaling criterion, including ones with ``superquantum'' correlations. A strengthened version of the quantum no-broadcasting theorem follows, and its proof is significantly simpler than existing proofs of the no-broadcasting theorem.
We develop a novel approach to Bell inequalities based on a constraint that the correlations exhibited by local variable theories must satisfy. This is used to construct a family of …
We develop a novel approach to Bell inequalities based on a constraint that the correlations exhibited by local variable theories must satisfy. This is used to construct a family of Bell inequalities for bipartite quantum systems of arbitrarily high dimensionality which are strongly resistant to noise. In particular, our work gives an analytic description of previous numerical results and generalizes them to arbitrarily high dimensionality.
We consider schemes for secret key distribution which use as a resource correlations that violate Bell inequalities. We provide the first security proof for such schemes, according to the strongest …
We consider schemes for secret key distribution which use as a resource correlations that violate Bell inequalities. We provide the first security proof for such schemes, according to the strongest notion of security, the so-called universally composable security. Our security proof does not rely on the validity of quantum mechanics, it solely relies on the impossibility of arbitrarily fast signaling between separate physical systems. This allows for secret communication in situations where the participants distrust their quantum devices.
We consider the problem of transmitting classical and quantum information reliably over an entanglement-assisted quantum channel. Our main result is a capacity theorem that gives a three-dimensional achievable rate region. …
We consider the problem of transmitting classical and quantum information reliably over an entanglement-assisted quantum channel. Our main result is a capacity theorem that gives a three-dimensional achievable rate region. Points in the region are rate triples, consisting of the classical communication rate, the quantum communication rate, and the entanglement consumption rate of a particular coding scheme. The crucial protocol in achieving the boundary points of the capacity region is a protocol that we name the classically-enhanced father protocol. The classically-enhanced father protocol is more general than other protocols in the family tree of quantum Shannon theoretic protocols, in the sense that several previously known quantum protocols are now child protocols of it. The classically-enhanced father protocol also shows an improvement over a time-sharing strategy for the case of a qubit dephasing channel--this result justifies the need for simultaneous coding of classical and quantum information over an entanglement-assisted quantum channel. Our capacity theorem is of a multi-letter nature (requiring a limit over many uses of the channel), but it reduces to a single-letter characterization for at least three channels: the completely depolarizing channel, the quantum erasure channel, and the qubit dephasing channel.
Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, …
Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> , while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.
We introduce a new class of multilinear p-summing operators, which we call multiplep-summing. Using them, we can prove several multilinear generalizations of Grothendieck's 'fundamental theorem of the metric theory of …
We introduce a new class of multilinear p-summing operators, which we call multiplep-summing. Using them, we can prove several multilinear generalizations of Grothendieck's 'fundamental theorem of the metric theory of tensor products'. As an application we prove a vector-valued Littlewood's inequality.
Given a set of correlations originating from measurements on a quantum state of unknown Hilbert space dimension, what is the minimal dimension $d$ necessary to describe such correlations? We introduce …
Given a set of correlations originating from measurements on a quantum state of unknown Hilbert space dimension, what is the minimal dimension $d$ necessary to describe such correlations? We introduce the concept of dimension witness to put lower bounds on $d$. This work represents a first step in a broader research program aiming to characterize Hilbert space dimension in various contexts related to fundamental questions and quantum information applications.
Two non-commutative versions of the classical L^q(L^p) norm on the algebra of (mn)x(mn) matrices are compared. The first norm was defined recently by Carlen and Lieb, as a byproduct of …
Two non-commutative versions of the classical L^q(L^p) norm on the algebra of (mn)x(mn) matrices are compared. The first norm was defined recently by Carlen and Lieb, as a byproduct of their analysis of certain convex functions on matrix spaces. The second norm was defined by Pisier and others using results from the theory of operator spaces. It is shown that the second norm is upper bounded by a constant multiple of the first for all 1 <= p <= 2, q >= 1. In one case (2 = p < q) it is also shown that there is no such lower bound, and hence that the norms are inequivalent. It is conjectured that the norms are inequivalent in all cases.
We study the nonlocal properties of states resulting from the mixture of an arbitrary entangled state rho of two d-dimensional systems and completely depolarized noise, with respective weights p and …
We study the nonlocal properties of states resulting from the mixture of an arbitrary entangled state rho of two d-dimensional systems and completely depolarized noise, with respective weights p and 1-p. We first construct a local model for the case in which rho is maximally entangled and p at or below a certain bound. We then extend the model to arbitrary rho. Our results provide bounds on the resistance to noise of the nonlocal correlations of entangled states. For projective measurements, the critical value of the noise parameter p for which the state becomes local is at least asymptotically log(d) larger than the critical value for separability.
We imagine an experiment on an unknown quantum mechanical system in which the system is prepared in various ways and a range of measurements are performed. For each measurement $M$ …
We imagine an experiment on an unknown quantum mechanical system in which the system is prepared in various ways and a range of measurements are performed. For each measurement $M$ and preparation $\ensuremath{\rho}$ the experimenter can determine, given enough time, the probability of a given outcome $a$: $p(a\ensuremath{\mid}M,\ensuremath{\rho})$. How large does the Hilbert space of the quantum system have to be in order to allow us to find density matrices and measurement operators that will reproduce the given probability distribution? In this paper, we prove a simple lower bound for the dimension of the Hilbert space. The main insight is to relate this problem to the construction of quantum random access codes, for which interesting bounds on the Hilbert space dimension already exist. We discuss several applications of our result to hidden-variable or ontological models, to Bell inequalities, and to properties of the smooth min-entropy.