Analysis of boolean functions related to binary input binary output two-party nonlocal games

Jyotirmoy Basak, Subhamoy Maitra, Prabal Paul, Animesh RoyCryptogr. Commun 2023 · DOI

TL;DR

This paper systematically analyzes all possible binary input, binary output two-party nonlocal games by framing them as Boolean functions. The authors identify which of these games offer a "quantum advantage" – a higher success probability in the quantum realm compared to classical strategies – and quantify this advantage, finding that while the CHSH game is the most efficient in terms of separation, other games also exhibit this quantum benefit.

What Problem Does This Paper Address?

Quantum computation offers significant advantages over classical computation, a fact that extends to the realm of nonlocal games. Nonlocal games are scenarios where multiple players, separated and unable to communicate, try to win a game based on shared inputs and their own outputs, judged by a referee. In particular, binary input, binary output two-party nonlocal games are a fundamental class. While the famous CHSH game is known to exhibit a quantum advantage, it's unclear if other games within this class also offer such benefits, and if so, how they compare. This paper aims to exhaustively explore all such games to identify those with quantum advantages and quantify their performance, with implications for device-independent quantum cryptography.

Methods

The core of the paper involves a comprehensive analysis of all possible Boolean functions that represent binary input, binary output two-party nonlocal games. The authors categorize these games based on "partitions" of their successful outcomes. They then derive the maximum classical success probability for each game by considering all possible classical strategies and the maximum quantum success probability by assuming shared entanglement (specifically, the Bell state) and optimal quantum strategies. The "separation" or quantum advantage is then calculated as the difference between these maximum probabilities.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Systematic Exploration: The paper moves beyond the CHSH game to systematically analyze all possible binary input, binary output two-party nonlocal games, framing them as 4-variable Boolean functions.
  • Partitioning for Analysis: Games are classified and analyzed based on "partitions" of their successful outcomes, providing a structured way to compare different game structures.
  • Quantum Advantage Beyond CHSH: While the CHSH game is a benchmark, the study reveals that other games also offer quantum advantages, though often with smaller separations.
  • CHSH's Efficiency: The CHSH game remains the most efficient in terms of the separation between quantum and classical success probabilities among the games analyzed.
  • Device Independence Implications: The search for games with higher quantum advantage is motivated by the need to reduce sample sizes in device-independent quantum cryptography, where success probability directly impacts efficiency.

Key Results

The paper identifies several partitions of games that offer quantum advantage. Specifically:

  • CHSH Game (2+2+2+2 partition): Achieves a maximum quantum success probability of approximately 0.853, with a classical maximum of 0.75, yielding a separation of about 0.103.
  • Games with 8 successful outcomes: Partitions 2+2+2+2 and 3+2+2+1 show quantum advantages with separations of 0.103 and 0.03, respectively.
  • Games with 9 successful outcomes: The partition 3+3+2+1 offers a quantum advantage with a separation of approximately 0.042.
  • Games with 10 successful outcomes: The partition 3+3+3+1 shows a quantum advantage with a separation of approximately 0.05.
  • Games with 7 successful outcomes: The partition 2+2+2+1 exhibits a quantum advantage with a separation of approximately 0.012.
  • Games with 6 successful outcomes: The partition 3+1+1+1 offers a quantum advantage with a separation of approximately 0.05.
  • Games with 5 successful outcomes: The partition 2+1+1+1 shows a quantum advantage with a separation of approximately 0.042.

Crucially, the paper demonstrates that for many other partitions, no quantum advantage is observed.

Limitations and Future Work

The authors acknowledge that their analysis focuses on two-party games and does not explore their performance as dimensionality distinguishers for quantum states, as done in some prior work. Future research could extend this analysis to three-party (or more) nonlocal games, which could be an interesting avenue for discovering new quantum advantages.

Summary updated

BibTeX
@article{basak2023analysis,
  author = {Jyotirmoy Basak and Subhamoy Maitra and Prabal Paul and Animesh Roy},
  title = {{Analysis of boolean functions related to binary input binary output two-party nonlocal games}},
  journal = {Cryptogr. Commun},
  year = {2023},
  doi = {10.1007/s12095-023-00648-0},
}
Figure