Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2107.14010

A quantum complexity approach to the Kirchberg Embedding Problem

Isaac Goldbring, Bradd Hart

Published Jul 27, 2021• 0 citations
arXivHTMLPDF

Abstract

The Kirchberg Embedding Problem (KEP) asks if every C*-algebra embeds into an ultrapower of the Cuntz algebra $\cal O_2$. Motivated by the recent refutation of the Connes Embedding Problem using the quantum complexity result MIP*=RE, we establish two quantum complexity consequences of a positive solution to KEP. Both results involve almost-commuting strategies to nonlocal games.

DOI
10.48550/arxiv.2107.14010

Related papers

The Connes embedding problem: A guided tour

Isaac Goldbring

The Connes embedding problem (CEP) is a problem in the theory of tracial von Neumann algebras and asks whether or not every tracial von Neumann algebra embeds into an ultrapower of the hyperfinite II 1 _1 factor. The CEP has had interactions with a wide variety of areas of mathematics, including C ∗ \mathrm {C}^* -algebra theory, geometric group theory, free probability, and noncommutative real algebraic geometry, to name a few. After remaining open for over 40 years, a negative solution was recently obtained as a corollary of a landmark result in quantum complexity theory known as MIP ∗ = RE \operatorname {MIP}^*=\operatorname {RE} . In these notes, we introduce all of the background material necessary to understand the proof of the negative solution of the CEP from MIP ∗ = RE \operatorname {MIP}^*=\operatorname {RE} . In fact, we outline two such proofs, one following the “traditional” route that goes via Kirchberg’s QWEP problem in C ∗ \mathrm {C}^* -algebra theory and Tsirelson’s problem in quantum information theory and a second that uses basic ideas from logic.

arXiv:2109.12682•Bulletin of the American Mathematical Society•Jun 17, 2022•16 citations

MIP* = RE: A negative resolution to Connes’ embedding problem and Tsirelson’s problem

Thomas Vidick

Connes’ Embedding Problem is a deep question on approximability of certain tracial von Neumann algebras by finite-dimensional matrix algebras. We survey the connections between operator algebras, quantum information and theoretical computer science that enabled the recent resolution of this problem. The resolution goes through an equivalent formulation, known as Tsirelson’s problem, in terms of separating convex sets whose definition is motivated by the study of nonlocality in quantum mechanics. We construct an explicit separating hyperplane using the theory of two-player games from complexity theory.

EMS Press eBooks•Dec 15, 2023•1 citation

Connes implies Tsirelson: a simple proof

Alexander Frei

More precisely, we give a simple and very short proof of "the Connes embedding problem implies the synchronous Tsirelson conjecture" that relies on only two elementary ingredients: 1) the well-known description of synchronous correlations as traces on the algebra per player $C^*(\mathrm{player})=C^*(\mathrm{inputs}|\mathrm{outputs})$ and 2) an elementary lifting result by Kim, Paulsen and Schafhauser. Moreover, this bypasses every of the deep results by Kirchberg as well as any other implicit reformulation as the microstates conjecture and thelike. Meanwhile, we also give a different construction of Connes' algebra $\mathcal{R}^ω$ appearing in the Connes embedding problem, which is more suitable for the purposes of quantum information theory and much easier to comprehend for the reader without any prior knowledge in operator algebras. Most importantly, however, we present this proof for the following reason: Since the recent refutation of the synchronous Tsirelson conjecture by MIP*=RE, there exists a nonlocal game which violates the synchronous Tsirelson conjecture, and by the proof of MIP*=RE even a synchronous such game. The approach however is based on contradiction with the undecidability of the Halting problem, and so remains implicit. As such the quest now has started to give an explicit example of a synchronous game violating the synchronous Tsirelson conjecture together with a direct argument for the failure, and the current article serves as a direct translation to the corresponding operator algebra and its tracial state violating the Connes embedding problem.

arXiv:2209.07940•Sep 16, 2022•2 citations

Tsirelson's problem and asymptotically commuting unitary matrices

Narutaka Ozawa

In this paper, we consider quantum correlations of bipartite systems having a slight interaction, and reinterpret Tsirelson's problem (and hence Kirchberg's and Connes's conjectures) in terms of finite-dimensional asymptotically commuting positive operator valued measures. We also consider the systems of asymptotically commuting unitary matrices and formulate the Stronger Kirchberg Conjecture.

arXiv:1211.2712•Journal of Mathematical Physics•Mar 1, 2013•58 citations

Nonlocal games, compression theorems, and the arithmetical hierarchy

Hamoon Mousavi, Seyed Sajjad Nezhadi, Henry Yuen

We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 1/2 is complete for the class Σ1 (i.e., ). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE).

arXiv:2110.04651•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•28 citations

Computational Complexity of Quantum Satisfiability

Christian Herrmann, Martin Ziegler

Quantum logic generalizes, and in dimension one coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic formulas, and show both NP-complete in dimension two as well. For higher-dimensional spaces Rdand Cdwith d≥3 fixed, on the other hand, we show the problem to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and adds (a perhaps more natural and combinatorially flavoured) one to the still sparse list of NPR-complete problems, mostly pertaining to real algebraic geometry. Our proofs rely on (a careful examination of) works by John von Neumannas well as contributions by Hagge et. al (2005,2007,2009). We finally investigate the problem over Indefinite finite dimensions and relate it to NON-commutative semi algebraic geometry.

ACM/IEEE Symposium on Logic in Computer Science (LICS)•Jun 1, 2011•2 citations
The Kirchberg Embedding Problem (KEP) asks if every C*-algebra embeds into an ultrapower of the Cuntz algebra O2\cal O_2O2​. Motivated by the recent refutation of the Connes Embedding Problem using the quantum complexity result MIP*=RE, we establish two quantum complexity consequences of a positive solution to KEP. Both results involve almost-commuting strategies to nonlocal games.
The Connes embedding problem (CEP) is a problem in the theory of tracial von Neumann algebras and asks whether or not every tracial von Neumann algebra embeds into an ultrapower of the hyperfinite II 1 _1 factor. The CEP has had interactions with a wide variety of areas of mathematics, including C ∗ \mathrm {C}^* -algebra theory, geometric group theory, free probability, and noncommutative real algebraic geometry, to name a few. After remaining open for over 40 years, a negative solution was recently obtained as a corollary of a landmark result in quantum complexity theory known as MIP ∗ = RE \operatorname {MIP}^*=\operatorname {RE} . In these notes, we introduce all of the background material necessary to understand the proof of the negative solution of the CEP from MIP ∗ = RE \operatorname {MIP}^*=\operatorname {RE} . In fact, we outline two such proofs, one following the “traditional” route that goes via Kirchberg’s QWEP problem in C ∗ \mathrm {C}^* -algebra theory and Tsirelson’s problem in quantum information theory and a second that uses basic ideas from logic.
Connes’ Embedding Problem is a deep question on approximability of certain tracial von Neumann algebras by finite-dimensional matrix algebras. We survey the connections between operator algebras, quantum information and theoretical computer science that enabled the recent resolution of this problem. The resolution goes through an equivalent formulation, known as Tsirelson’s problem, in terms of separating convex sets whose definition is motivated by the study of nonlocality in quantum mechanics. We construct an explicit separating hyperplane using the theory of two-player games from complexity theory.
More precisely, we give a simple and very short proof of "the Connes embedding problem implies the synchronous Tsirelson conjecture" that relies on only two elementary ingredients: 1) the well-known description of synchronous correlations as traces on the algebra per player C∗(player)=C∗(inputs∣outputs)C^*(\mathrm{player})=C^*(\mathrm{inputs}|\mathrm{outputs})C∗(player)=C∗(inputs∣outputs) and 2) an elementary lifting result by Kim, Paulsen and Schafhauser. Moreover, this bypasses every of the deep results by Kirchberg as well as any other implicit reformulation as the microstates conjecture and thelike. Meanwhile, we also give a different construction of Connes' algebra Rω\mathcal{R}^ωRω appearing in the Connes embedding problem, which is more suitable for the purposes of quantum information theory and much easier to comprehend for the reader without any prior knowledge in operator algebras. Most importantly, however, we present this proof for the following reason: Since the recent refutation of the synchronous Tsirelson conjecture by MIP*=RE, there exists a nonlocal game which violates the synchronous Tsirelson conjecture, and by the proof of MIP*=RE even a synchronous such game. The approach however is based on contradiction with the undecidability of the Halting problem, and so remains implicit. As such the quest now has started to give an explicit example of a synchronous game violating the synchronous Tsirelson conjecture together with a direct argument for the failure, and the current article serves as a direct translation to the corresponding operator algebra and its tracial state violating the Connes embedding problem.
We investigate the connection between the complexity of nonlocal games and the arithmetical hierarchy, a classification of languages according to the complexity of arithmetical formulas defining them. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that deciding whether the (finite-dimensional) quantum value of a nonlocal game is 1 or at most 1/2 is complete for the class Σ1 (i.e., ). A result of Slofstra implies that deciding whether the commuting operator value of a nonlocal game is equal to 1 is complete for the class Π1 (i.e., coRE).
Quantum logic generalizes, and in dimension one coincides with, Boolean propositional logic. We introduce the weak and strong satisfiability problem for quantum logic formulas, and show both NP-complete in dimension two as well. For higher-dimensional spaces Rdand Cdwith d≥3 fixed, on the other hand, we show the problem to be complete for the nondeterministic Blum-Shub-Smale model of real computation. This provides a unified view on both Turing and real BSS complexity theory, and adds (a perhaps more natural and combinatorially flavoured) one to the still sparse list of NPR-complete problems, mostly pertaining to real algebraic geometry. Our proofs rely on (a careful examination of) works by John von Neumannas well as contributions by Hagge et. al (2005,2007,2009). We finally investigate the problem over Indefinite finite dimensions and relate it to NON-commutative semi algebraic geometry.