We describe a new technique for obtaining Tsirelson bounds, which are upper bounds on the quantum value of a Bell inequality. Since quantum correlations do not allow signalling, we obtain a Tsirelson bound by maximizing over all no-signalling probability distributions. This maximization can be cast as a linear programme. In a setting where three parties, A, B and C, share an entangled quantum state of arbitrary dimension, we (i) bound the trade-off between AB's and AC's violation of the Clauser–Horne–Shimony–Holt inequality and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities, relevant for interactive proof systems and cryptography.We describe a new technique for obtaining Tsirelson bounds, which are upper bounds on the quantum value of a Bell inequality. Since quantum correlations do not allow signalling, we obtain a Tsirelson bound by maximizing over all no-signalling probability distributions. This maximization can be cast as a linear programme. In a setting where three parties, A, B and C, share an entangled quantum state of arbitrary dimension, we (i) bound the trade-off between AB's and AC's violation of the Clauser–Horne–Shimony–Holt inequality and (ii) demonstrate that forcing B and C to be classically correlated prevents A and B from violating certain Bell inequalities, relevant for interactive proof systems and cryptography.

arXiv:quant-ph/0601172Proceedings of the Royal Society A Mathematical Physical and Engineering SciencesAug 28, 2008206 citations

Lower bounds on non-local computation from controllable correlation

Richard Cleve, Alex May

Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\text{SWAP}}$ , and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.Understanding entanglement cost in non-local quantum computation (NLQC) is relevant to complexity, cryptography, gravity, and other areas. This entanglement cost is largely uncharacterized; previous lower bound techniques apply to narrowly defined cases, and proving lower bounds on most simple unitaries has remained open. Here, we give two new lower bound techniques that can be evaluated for any unitary, based on their controllable correlation and controllable entanglement. For Haar random two qubit unitaries, our techniques typically lead to non-trivial lower bounds. Further, we obtain lower bounds on most of the commonly studied two qubit quantum gates, including CNOT, DCNOT, $\sqrt{\text{SWAP}}$, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.

quant-pharXiv:2602.00255Feb 3, 20260 citations

Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

Sander Gribling, David de Laat, Monique Laurent

In this paper we study optimization problems related to bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. First we consider the problem of finding the minimal entanglement dimension of such correlations. We construct a hierarchy of semidefinite programming lower bounds and show convergence to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when access to shared randomness is free. Then we study optimization problems over synchronous quantum correlations arising from quantum graph parameters. We introduce semidefinite programming hierarchies and unify existing bounds on quantum chromatic and quantum stability numbers by placing them in the framework of tracial polynomial optimization.In this paper we study optimization problems related to bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. First we consider the problem of finding the minimal entanglement dimension of such correlations. We construct a hierarchy of semidefinite programming lower bounds and show convergence to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when access to shared randomness is free. Then we study optimization problems over synchronous quantum correlations arising from quantum graph parameters. We introduce semidefinite programming hierarchies and unify existing bounds on quantum chromatic and quantum stability numbers by placing them in the framework of tracial polynomial optimization.

arXiv:1708.09696Mathematical ProgrammingMay 21, 201822 citations

Quantum Correlations: Challenging the Tsirelson Bound

Alexei Grinbaum

Lecture notes in computer scienceJan 1, 20161 citation

Quantum Bounds for Temporal Correlations

Costantino Budroni

Springer thesesOct 21, 20151 citation

\sqrt{\text{SWAP}}

, and the XX interaction, none of which previously had known lower bounds. For the CNOT gate, one of our techniques gives a tight lower bound, fully resolving its entanglement cost. The resulting lower bounds have parallel repetition properties, and apply in the noisy setting.