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:2111.07881 · Harvard Data Science Review

Quantum Computation, Data Science, Bell Games

Richard David Gill

Published Jan 27, 2022• 0 citations
arXivHTMLPDF

Abstract

I draw attention to statistical and probabilistic and computer science aspects of the very, very close by topic of quantum internet.
DOI
10.1162/99608f92.ea411412

Related papers

Comment on "When Quantum Computation Meets Data Science: Making Data Science Quantum".

Richard David Gill

I draw attention to statistical, probabilistic, computer science aspects of the highly related topics of the Bell game and of a possible future Quantum Internet.

•Nov 11, 2021•0 citations

Data Science on a Future Quantum Internet

Nana Liu

Harvard Data Science Review•Jan 27, 2022•0 citations

Quantum Information, Games and Computation

Vladimir G. Ivancevic, Tijana T. Ivancevic

Springer eBooks•Jan 1, 2010•0 citations

Quantum Computing in a Statistical Context

Yazhen Wang, Hongzhi Liu

Quantum computing is widely considered a frontier of interdisciplinary research and involves fields ranging from computer science to physics and from chemistry to engineering. On the one hand, the stochastic essence of quantum physics results in the random nature of quantum computing; thus, there is an important role for statistics to play in the development of quantum computing. On the other hand, quantum computing has great potential to revolutionize computational statistics and data science. This article provides an overview of the statistical aspect of quantum computing. We review the basic concepts of quantum computing and introduce quantum research topics such as quantum annealing and quantum machine learning, which require statistics to be understood.

Annual Review of Statistics and Its Application•Mar 7, 2022•15 citations

Quantum Games and Quantum Computers

Vladimir G. Ivancevic, Tijana T. Ivancevic

WORLD SCIENTIFIC eBooks•Oct 1, 2008•0 citations

The complexity-theoretic Bell inequality

Zhengfeng Ji

Forty years later, a group of computer scientists, Richard Cleve, Peter Høyer, Ben Toner and John Watrous [1], provided a computer science perspective on Bell inequalities in the framework of multi-player one-round games. In a multi-player one-round game, a referee samples and asks questions to multiple non-communicating players and checks the validity of the answers according to some rule. The classical value of the game is the maximum success probability with which the players can pass the referee's check. Multi-player one-round games form a well-studied topic in theoretical computer science and have connections to constraint satisfaction problems, interactive proof systems, probabilistically checkable proof (PCP) and the celebrated PCP theorem. Cleve et al. reformulated Bell inequalities as multi-player one-round games such that the players can achieve a higher success probability, called the quantum value, when they measure a shared entangled state to obtain the answers. They also pointed out that shared entanglement may cause the so-called soundness problem in quantum interactive proof systems, an intriguing phenomenon that leads to a series of investigations on the limitation and power of entanglement in multi-player games. It is well known that it is NP-hard to approximate the classical value of a game to inverse polynomial precision where NP stands for nondeterministic polynomial time. Just how hard is it to approximate the quantum value of a game? We do not know the answer after a decade of research efforts, mainly because the players measure on an arbitrarily high dimensional quantum system. Because of the soundness problem pointed out by Cleve et al., we did not even know how to establish that the quantum value is NP-hard until Kempe et al. finally proved it in 2007 [2]. Very recently, the author established that the quantum value of a game is NEXP-hard to approximate [3,4] where NEXP stands for nondeterministic exponential time. This can be seen as a complexity-theoretic Bell inequality. The standard Bell inequality tells us that the classical and quantum values can be different for a fixed game; our result instead establishes that the computational complexities for approximating the classical and quantum values are different, since NP ≠ NEXP. The complexity of Bell inequalities or the quantum values of multi-player one-round games has deep connections to quantum physics and theoretical computer science as we have already discussed. It is also related to the Connes embedding conjecture in mathematics. Using a group theory approach, Slofstra proved that the problem of determining whether a game has quantum value 1 or not is undecidable [5]. Is the quantum value approximation problem also undecidable or can we establish any complexity upper bound? Only time will tell.

National Science Review•Jul 23, 2018•0 citations
Quantum computing is widely considered a frontier of interdisciplinary research and involves fields ranging from computer science to physics and from chemistry to engineering. On the one hand, the stochastic essence of quantum physics results in the random nature of quantum computing; thus, there is an important role for statistics to play in the development of quantum computing. On the other hand, quantum computing has great potential to revolutionize computational statistics and data science. This article provides an overview of the statistical aspect of quantum computing. We review the basic concepts of quantum computing and introduce quantum research topics such as quantum annealing and quantum machine learning, which require statistics to be understood.
Forty years later, a group of computer scientists, Richard Cleve, Peter Høyer, Ben Toner and John Watrous [1], provided a computer science perspective on Bell inequalities in the framework of multi-player one-round games. In a multi-player one-round game, a referee samples and asks questions to multiple non-communicating players and checks the validity of the answers according to some rule. The classical value of the game is the maximum success probability with which the players can pass the referee's check. Multi-player one-round games form a well-studied topic in theoretical computer science and have connections to constraint satisfaction problems, interactive proof systems, probabilistically checkable proof (PCP) and the celebrated PCP theorem. Cleve et al. reformulated Bell inequalities as multi-player one-round games such that the players can achieve a higher success probability, called the quantum value, when they measure a shared entangled state to obtain the answers. They also pointed out that shared entanglement may cause the so-called soundness problem in quantum interactive proof systems, an intriguing phenomenon that leads to a series of investigations on the limitation and power of entanglement in multi-player games. It is well known that it is NP-hard to approximate the classical value of a game to inverse polynomial precision where NP stands for nondeterministic polynomial time. Just how hard is it to approximate the quantum value of a game? We do not know the answer after a decade of research efforts, mainly because the players measure on an arbitrarily high dimensional quantum system. Because of the soundness problem pointed out by Cleve et al., we did not even know how to establish that the quantum value is NP-hard until Kempe et al. finally proved it in 2007 [2]. Very recently, the author established that the quantum value of a game is NEXP-hard to approximate [3,4] where NEXP stands for nondeterministic exponential time. This can be seen as a complexity-theoretic Bell inequality. The standard Bell inequality tells us that the classical and quantum values can be different for a fixed game; our result instead establishes that the computational complexities for approximating the classical and quantum values are different, since NP ≠ NEXP. The complexity of Bell inequalities or the quantum values of multi-player one-round games has deep connections to quantum physics and theoretical computer science as we have already discussed. It is also related to the Connes embedding conjecture in mathematics. Using a group theory approach, Slofstra proved that the problem of determining whether a game has quantum value 1 or not is undecidable [5]. Is the quantum value approximation problem also undecidable or can we establish any complexity upper bound? Only time will tell.