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:2211.09194 · Physical Review A

Identifying the value of a random variable unambiguously: Quantum versus classical approaches

Saronath Halder, Alexander Streltsov, Manik Banik

Published May 6, 2024• 2 citations
arXivHTMLPDF

Abstract

Quantum resources may provide an advantage over their classical counterparts. Theoretically, in certain tasks, this advantage can be very high. In this work, we construct such a task based on a game, mediated by the Referee and played between Alice and Bob. The Referee sends Alice a value of a random variable. At the same time, the Referee also sends Bob some partial information regarding that value. Here partial information can be defined in the following way. Bob gets the information of a random set that must contain the value of the variable, which is sent to Alice by the Referee, along with other value(s). Alice is not allowed to know what information is sent to Bob by the Referee. Again, Bob does not know which value of the random variable is sent to Alice. Now, the game can be won if and only if Bob can unambiguously identify the value of the variable that is sent to Alice, with some nonzero probability, no matter what information Bob receives or which value is sent to Alice. However, to help Bob, Alice sends some limited amount of information to him, based on any strategy that is fixed by Alice and Bob before the game begins. We show that if Alice sends a limited amount of classical information, then the game cannot be won, while the quantum analog of the ``limited amount of classical information'' is sufficient for winning the game. Thus, it establishes a quantum advantage. We further analyze several variants of the game and provide certain bounds on the success probabilities. Moreover, we establish connections between the trine ensemble, mutually unbiased bases, and the encoding-decoding strategies of those variants. We also discuss the role of quantum coherence in the present context.

DOI
10.1103/physreva.109.052608

Related papers

Quantum advantage in a unified scenario and secure detection of resources

Saronath Halder, Alexander Streltsov

Quantum resources may provide an advantage over their classical counterparts in communication tasks. We refer to this as quantum advantage. Here, we consider a single communication task to study different approaches of observing quantum advantage. We call this setting a unified scenario. Our task is described as the following. There are three parties---the Manager, Alice, and Bob. The Manager sends a value of a random variable to Alice, and at the same time Bob receives some partial information regarding that value. Initially, neither Alice nor Bob knows the input of the other, which is received from the Manager. The goal of the task is achieved if and only if the value of the random variable, sent to Alice by the Manager, is identified by Bob with a success probability greater than half all the time. Here, nonzero error probability is allowed. However, to help Bob, Alice sends a limited amount of classical or quantum information to him (cbit or qubit). We show that the goal of the task can be achieved when Alice sends a qubit. On the other hand, a cbit communication is not sufficient for achieving the goal. Thus, it establishes quantum advantage. We further show that the optimal success probability in the overall process for a qubit communication can be higher than the optimal success probability for a cbit communication. In fact, this success probability is higher for qubit communication even if along with cbit communication Alice and Bob share randomness which allows mixing of classical strategies. Clearly, it not only establishes quantum advantage, it also demonstrates a more prominent nonclassical feature. Actually, we obtain higher success probability compared to other tasks. This also suggests the experiment-friendly nature of our task. For applications, we connect our task with semi-device-independence and show how our task can be useful to detect quantumness of a communication in a secure way. Moreover, within the same setting, we provide a way to detect universal coherence present in an ensemble. For a high-dimensional random variable, to achieve the goal, it may require a high-dimensional classical communication, while it can be achieved with only a qubit communication. This establishes a large separation between the quantum and the classical communication.

arXiv:2309.13208•Physical Review A•Feb 27, 2025•0 citations

Optimal Strategies for Winning Certain Coset-Guessing Quantum Games

Michael Schleppy, Emina Soljanin, Nicolas Swanson

In a recently introduced coset guessing game, Alice plays against Bob and Charlie, aiming to meet a joint winning condition. Bob and Charlie can only communicate before the game starts to devise a joint strategy. The game we consider begins with Alice preparing a 2m-qubit quantum state based on a random selection of three parameters. She sends the first m qubits to Bob and the rest to Charlie, and then reveals to them her choice for one of the parameters. Bob is supposed to guess one of the hidden parameters, Charlie the other, and they win if both guesses are correct. From previous work, we know that the probability of Bob’s and Charlie’s guesses being simultaneously correct goes to zero exponentially as m increases. We derive a tight upper bound on this probability and show how Bob and Charlie can achieve it. While developing an optimal strategy, we devised an encoding circuit using only and Hadamard gates, which builds CSS codes from EPR pairs using only local operations. We found that the role of quantum information that Alice communicates to Bob and Charlie is to make their responses correlated rather than improve their individual (marginal) correct guessing rates.

arXiv:2410.08160•IEEE Journal on Selected Areas in Information Theory•Jan 1, 2025•0 citations

Extended Nonlocal Games

Russo, Vincent

The notions of entanglement and nonlocality are among the most striking ingredients found in quantum information theory. One tool to better understand these notions is the model of nonlocal games; a mathematical framework that abstractly models a physical system. The simplest instance of a nonlocal game involves two players, Alice and Bob, who are not allowed to communicate with each other once the game has started and who play cooperatively against an adversary referred to as the referee. The focus of this thesis is a class of games called extended nonlocal games, of which nonlocal games are a subset. In an extended nonlocal game, the players initially share a tripartite state with the referee. In such games, the winning conditions for Alice and Bob may depend on outcomes of measurements made by the referee, on its part of the shared quantum state, in addition to Alice and Bob's answers to the questions sent by the referee. We build up the framework for extended nonlocal games and study their properties and how they relate to nonlocal games.

arXiv:1704.07375•Apr 24, 2017•3 citations

Limitation on the capacity of arbitrary bipartite pure entangled states for the unambiguous transmission of classical information

Lvjun Li

The capacity of quantum states to send information is a fundamental and intriguing issue in quantum communication theory. This study explores a scenario where Alice intends to transmit n bits of classical information to Bob by sending m qudits, using an arbitrary bipartite pure entangled state with E qudits as the shared resource. We employ the unambiguous discrimination strategy in decoding and establish an upper bound on the success probability, which extends the findings of a previous study (Li in Phys Rev A 85:052304, 2012).

Quantum Information Processing•Dec 27, 2024•0 citations

A game of quantum advantage: linking verification and simulation

Daniel Stilck França, Raúl García−Patrón

We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, the skeptical Alice, is then allowed to propose mock distributions supposed to reproduce Bob's device's statistics. He then needs to provide witness functions to prove that Alice's proposed mock distributions cannot properly approximate his device. Within this framework, we establish three results. First, for random quantum circuits, Bob being able to efficiently distinguish his distribution from Alice's implies efficient approximate simulation of the distribution. Secondly, finding a polynomial time function to distinguish the output of random circuits from the uniform distribution can also spoof the heavy output generation problem in polynomial time. This pinpoints that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Beyond this setting, by employing strong data processing inequalities, our framework allows us to analyse the effect of noise on classical simulability and verification of more general near-term quantum advantage proposals.

arXiv:2011.12173•Quantum•Jun 30, 2022•7 citations

Worst case analysis of non-local games

Andris Ambainis, Artūrs Bačkurs, Kaspars Balodis +3 more

Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input $x_i$ to the $i^{th}$ player who then responds by sending an answer $a_i$ to the referee. The players win if the answers $a_i$ satisfy a condition that may depend on the inputs $x_i$. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study of non-local games in a worst-case scenario when the referee's probability distribution is unknown and study several non-local games in this scenario.

arXiv:1112.2856•Dec 13, 2011•1 citation
Quantum resources may provide an advantage over their classical counterparts. Theoretically, in certain tasks, this advantage can be very high. In this work, we construct such a task based on a game, mediated by the Referee and played between Alice and Bob. The Referee sends Alice a value of a random variable. At the same time, the Referee also sends Bob some partial information regarding that value. Here partial information can be defined in the following way. Bob gets the information of a random set that must contain the value of the variable, which is sent to Alice by the Referee, along with other value(s). Alice is not allowed to know what information is sent to Bob by the Referee. Again, Bob does not know which value of the random variable is sent to Alice. Now, the game can be won if and only if Bob can unambiguously identify the value of the variable that is sent to Alice, with some nonzero probability, no matter what information Bob receives or which value is sent to Alice. However, to help Bob, Alice sends some limited amount of information to him, based on any strategy that is fixed by Alice and Bob before the game begins. We show that if Alice sends a limited amount of classical information, then the game cannot be won, while the quantum analog of the ``limited amount of classical information'' is sufficient for winning the game. Thus, it establishes a quantum advantage. We further analyze several variants of the game and provide certain bounds on the success probabilities. Moreover, we establish connections between the trine ensemble, mutually unbiased bases, and the encoding-decoding strategies of those variants. We also discuss the role of quantum coherence in the present context.
Quantum resources may provide an advantage over their classical counterparts in communication tasks. We refer to this as quantum advantage. Here, we consider a single communication task to study different approaches of observing quantum advantage. We call this setting a unified scenario. Our task is described as the following. There are three parties---the Manager, Alice, and Bob. The Manager sends a value of a random variable to Alice, and at the same time Bob receives some partial information regarding that value. Initially, neither Alice nor Bob knows the input of the other, which is received from the Manager. The goal of the task is achieved if and only if the value of the random variable, sent to Alice by the Manager, is identified by Bob with a success probability greater than half all the time. Here, nonzero error probability is allowed. However, to help Bob, Alice sends a limited amount of classical or quantum information to him (cbit or qubit). We show that the goal of the task can be achieved when Alice sends a qubit. On the other hand, a cbit communication is not sufficient for achieving the goal. Thus, it establishes quantum advantage. We further show that the optimal success probability in the overall process for a qubit communication can be higher than the optimal success probability for a cbit communication. In fact, this success probability is higher for qubit communication even if along with cbit communication Alice and Bob share randomness which allows mixing of classical strategies. Clearly, it not only establishes quantum advantage, it also demonstrates a more prominent nonclassical feature. Actually, we obtain higher success probability compared to other tasks. This also suggests the experiment-friendly nature of our task. For applications, we connect our task with semi-device-independence and show how our task can be useful to detect quantumness of a communication in a secure way. Moreover, within the same setting, we provide a way to detect universal coherence present in an ensemble. For a high-dimensional random variable, to achieve the goal, it may require a high-dimensional classical communication, while it can be achieved with only a qubit communication. This establishes a large separation between the quantum and the classical communication.
In a recently introduced coset guessing game, Alice plays against Bob and Charlie, aiming to meet a joint winning condition. Bob and Charlie can only communicate before the game starts to devise a joint strategy. The game we consider begins with Alice preparing a 2m-qubit quantum state based on a random selection of three parameters. She sends the first m qubits to Bob and the rest to Charlie, and then reveals to them her choice for one of the parameters. Bob is supposed to guess one of the hidden parameters, Charlie the other, and they win if both guesses are correct. From previous work, we know that the probability of Bob’s and Charlie’s guesses being simultaneously correct goes to zero exponentially as m increases. We derive a tight upper bound on this probability and show how Bob and Charlie can achieve it. While developing an optimal strategy, we devised an encoding circuit using only and Hadamard gates, which builds CSS codes from EPR pairs using only local operations. We found that the role of quantum information that Alice communicates to Bob and Charlie is to make their responses correlated rather than improve their individual (marginal) correct guessing rates.
The notions of entanglement and nonlocality are among the most striking ingredients found in quantum information theory. One tool to better understand these notions is the model of nonlocal games; a mathematical framework that abstractly models a physical system. The simplest instance of a nonlocal game involves two players, Alice and Bob, who are not allowed to communicate with each other once the game has started and who play cooperatively against an adversary referred to as the referee. The focus of this thesis is a class of games called extended nonlocal games, of which nonlocal games are a subset. In an extended nonlocal game, the players initially share a tripartite state with the referee. In such games, the winning conditions for Alice and Bob may depend on outcomes of measurements made by the referee, on its part of the shared quantum state, in addition to Alice and Bob's answers to the questions sent by the referee. We build up the framework for extended nonlocal games and study their properties and how they relate to nonlocal games.
The capacity of quantum states to send information is a fundamental and intriguing issue in quantum communication theory. This study explores a scenario where Alice intends to transmit n bits of classical information to Bob by sending m qudits, using an arbitrary bipartite pure entangled state with E qudits as the shared resource. We employ the unambiguous discrimination strategy in decoding and establish an upper bound on the success probability, which extends the findings of a previous study (Li in Phys Rev A 85:052304, 2012).
We present a formalism that captures the process of proving quantum superiority to skeptics as an interactive game between two agents, supervised by a referee. Bob, is sampling from a classical distribution on a quantum device that is supposed to demonstrate a quantum advantage. The other player, the skeptical Alice, is then allowed to propose mock distributions supposed to reproduce Bob's device's statistics. He then needs to provide witness functions to prove that Alice's proposed mock distributions cannot properly approximate his device. Within this framework, we establish three results. First, for random quantum circuits, Bob being able to efficiently distinguish his distribution from Alice's implies efficient approximate simulation of the distribution. Secondly, finding a polynomial time function to distinguish the output of random circuits from the uniform distribution can also spoof the heavy output generation problem in polynomial time. This pinpoints that exponential resources may be unavoidable for even the most basic verification tasks in the setting of random quantum circuits. Beyond this setting, by employing strong data processing inequalities, our framework allows us to analyse the effect of noise on classical simulability and verification of more general near-term quantum advantage proposals.
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input xix_ixi​ to the ithi^{th}ith player who then responds by sending an answer aia_iai​ to the referee. The players win if the answers aia_iai​ satisfy a condition that may depend on the inputs xix_ixi​. Typically, non-local games are studied in a framework where the referee picks the inputs from a known probability distribution. We initiate the study of non-local games in a worst-case scenario when the referee's probability distribution is unknown and study several non-local games in this scenario.