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

Quantum Information Processing

Analysis of Boolean functions related to two-party nonlocal games for biased inputs

Jyotirmoy Basak, Anurag Ghosh

Published Sep 30, 2026• 0 citations
Publisher
DOI
10.1007/s11128-026-05346-3

Related papers

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

Jyotirmoy Basak, Subhamoy Maitra, Prabal Paul +1 more

arXiv:2306.14815•Cryptography and Communications•Jun 9, 2023•1 citation

Linear conic formulations for two-party correlations and values of nonlocal games

Jamie Sikora, Antonios Varvitsiotis

arXiv:1506.07297•Mathematical Programming•Jul 29, 2016•31 citations

Fine-grained uncertainty relation and biased nonlocal games in bipartite and tripartite systems

Ansuman Dey, Tanumoy Pramanik, A. S. Majumdar

The fine-grained uncertainty relation can be used to discriminate among classical, quantum, and superquantum correlations based on their strength of nonlocality, as has been shown for bipartite and tripartite systems with unbiased measurement settings. Here we consider the situations when two and three parties choose settings with bias for playing certain nonlocal games. We show analytically that while the fine-grained uncertainty principle is still able to distinguish classical, quantum, and superquantum correlations for biased settings corresponding to certain ranges of the biasing parameters, the above-mentioned discrimination is not manifested for all biasing.

arXiv:1210.4300•Physical Review A•Jan 18, 2013•21 citations

On symmetric nonlocal games

Andris Ambainis, Dmitry Kravchenko, Nikolay Nahimov +2 more

Theoretical Computer Science•Mar 25, 2013•2 citations

A nonlocal game whose dimension exponent is uncomputable

Seth Douglas, Nidhal Mghirbi

Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If $D(\varepsilon)$ is the least local dimension needed to win with probability at least $1-\varepsilon$, then $\lim_{n\to\infty}\log_2 D(2^{-n})/n=(3+\theta_K)/4$, where $\theta_K=\sum_{e\in K}4^{-(e+1)}$ and $K$ is the halting set. This exponent has the Turing degree of $K$. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.

•Oct 27, 2026•10 citations

An introduction to quantum: computing, communication complexity protocols, nonlocality and graph parameters

Lucas Silva Arenstein

What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.

•Dec 12, 2022•0 citations
The fine-grained uncertainty relation can be used to discriminate among classical, quantum, and superquantum correlations based on their strength of nonlocality, as has been shown for bipartite and tripartite systems with unbiased measurement settings. Here we consider the situations when two and three parties choose settings with bias for playing certain nonlocal games. We show analytically that while the fine-grained uncertainty principle is still able to distinguish classical, quantum, and superquantum correlations for biased settings corresponding to certain ranges of the biasing parameters, the above-mentioned discrimination is not manifested for all biasing.
Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If D(ε)D(\varepsilon)D(ε) is the least local dimension needed to win with probability at least 1−ε1-\varepsilon1−ε, then lim⁡n→∞log⁡2D(2−n)/n=(3+θK)/4\lim_{n\to\infty}\log_2 D(2^{-n})/n=(3+\theta_K)/4limn→∞​log2​D(2−n)/n=(3+θK​)/4, where θK=∑e∈K4−(e+1)\theta_K=\sum_{e\in K}4^{-(e+1)}θK​=∑e∈K​4−(e+1) and KKK is the halting set. This exponent has the Turing degree of KKK. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.