Quantum Computing Stack Exchange
Quantum Computing Stack Exchange

Questions tagged [nonlocal-games]

46 questions
17
votes
1 answer

What exactly are Quantum XOR Games?

I have done some research & found a few different papers that discuss xor games (classic & quantum). I am curious if someone could give a concise introductory explanation as to what exactly xor games are & how they are or could be used/useful in…
user820789
  • 3,440
  • 13
  • 43
13
votes
3 answers

Are correlations stronger than those allowed by quantum mechanics possible?

We know how a quantum correlation setup can help us with a better probability of winning games like the CHSH. But what is the upper bound that physics can allow? Is it the quantum correlation setup? Or can we exceed them in general sense to get much…
Siddhant Singh
  • 1,795
  • 9
  • 22
9
votes
2 answers

Optimal strategy to a quantum state game

Consider the following game: I flip a fair coin, and depending on the outcome (either heads/tails), I'll give you one of the following states: $$|0\rangle \text{ or } \cos(x)|0\rangle + \sin(x)|1\rangle.$$ Here, $x$ is a known constant angle. But, I…
jjbid
  • 91
  • 4
9
votes
3 answers

Proof of optimality for CHSH game classical strategy

I'm aware that the optimality of the quantum strategy for the CHSH game is given by Tsirelson's bound, but presentations all skip over the (admittedly much less interesting) proof of the classical strategy's optimality. In the CHSH game, we have two…
ahelwer
  • 4,288
  • 2
  • 15
  • 36
7
votes
1 answer

In which paper was the CHSH game first presented?

The CHSH inequality was presented in the paper Proposed Experiment to Test Local Hidden-Variable Theories published in 1969 by J.F. Clauser, M.A. Horne, A. Shimony, and R.A. Holt. I'm interested in which paper first presented their proposed…
ahelwer
  • 4,288
  • 2
  • 15
  • 36
7
votes
1 answer

Worst Bell inequality violation with non-maximally entangled state?

I'm familiar with CHSH game and the strategy that allows Alice and Bob to succeed with a probability of $$\frac{1+\tfrac{1}{\sqrt 2}}{2}\approx 85\%$$ if they share a maximally entangled state such as $\lvert\Phi_+\rangle$ and use the measurements…
Franklin Pezzuti Dyer
  • 448
  • 2
  • 7
7
votes
1 answer

Has anyone analyzed multi-round nonlocal games?

The traditional definition of a nonlocal game is restricted to having two players and one round (e.g., here), but it is natural to consider a more general class of games that may have more than two players and more than one round of questions. While…
Evan Jenkins
  • 518
  • 3
  • 7
6
votes
1 answer

Is Connes' Embedding Problem akin to the word problem for finitely presented groups?

The complexity class $\mathrm{MIP^*}$ includes the set of languages that can be efficiently verified by a classical, polynomially-bounded verifier, engaging with two quantum provers that can share (potentially infinite) entanglement, but are…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
6
votes
1 answer

Why is $P(1,2)_{\text{same}} = \frac{1}{4}$ and not $\frac{1}{2}$ in Preskill's Bell experiment?

Context: Three coins on the table. Each is either heads or tails. You can uncover any one of the three coins, revealing whether it is heads or tails but then you choose two the other two coins disappear --- you'll never know whetehr those…
Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112
5
votes
1 answer

How can quantum computing win 97% of times in coin flipping experiment?

I'm new to this field of science. I'm curious about how quantum computing can win 97% of times in a coin flipping experiment? Refer this link: Ted Talk by Shohini Ghose To give an idea about how this coin experiment works: Quantum Computer…
Saddam Pojee
  • 153
  • 1
  • 5
5
votes
3 answers

Algorithm-based game project to introduce quantum computing

I am currently working on a quantum computing subject for my coding school, and I had some questions for you. My objective would be to introduce students to quantum computing with an algorithmic project. I had two games ideas for it, one of them…
F. Sabatié
  • 51
  • 3
5
votes
0 answers

Who first studied nonlocal games with probabilistic predicate?

For some background, a nonlocal game consists of questions $x,y\in X,Y$ and answers $a,b \in A,B$; the pair of questions $x,y$ is asked with probability $\mu(x,y)$, and a referee accepts the pair of answers $a,b$ for the pair of questions $x,y$ with…
Mateus Araújo
  • 3,112
  • 9
  • 20
4
votes
2 answers

How could a quantum computer perform nimber arithmetic?

I am interested in combinatorial game theory & was doing some research on quantum combinatorial games (arXiv). This lead me to wondering how a quantum computer might be able to perform nimber arithmetic (perhaps as a part of a game playing AI). I am…
user820789
  • 3,440
  • 13
  • 43
4
votes
1 answer

Using XOR games to benchmark quantum computers

In an answer to a previous question, What exactly are Quantum XOR Games?, ahelwer states: One application of xor games is self-testing: when running algorithms on an untrusted quantum computer, you can use xor games to verify that the computer…
user820789
  • 3,440
  • 13
  • 43
4
votes
0 answers

Can Alice and Bob convince the cops that they don't share any entanglement?

Suppose Alice and Bob are arrested for killing Eve, and are taken to two different interrogation rooms. The police quiz Alice and separately Bob, asking them a bunch of different questions along the way. If Alice and Bob can get their stories…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
1
2 3 4