Satisfiability Phase Transtion for Random Quantum 3XOR Games
- URL: http://arxiv.org/abs/2209.04655v1
- Date: Sat, 10 Sep 2022 12:54:53 GMT
- Title: Satisfiability Phase Transtion for Random Quantum 3XOR Games
- Authors: Adam Bene Watts, J. William Helton, Zehong Zhao
- Abstract summary: We numerically study the behavior of randomly generated 3XOR games with large numbers of questions.
Our experiments strongly indicate that the probability of a randomly generated game being pseudotelpathic stays far from 1.
We also find strong evidence that randomly generated 3XOR games undergo both a quantum and classical "phase transition"
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent results showed it was possible to determine if a modest size 3XOR game
has a perfect quantum strategy. We build on these and give an explicit
polynomial time algorithm which constructs such a perfect strategy or refutes
its existence. This new tool lets us numerically study the behavior of randomly
generated 3XOR games with large numbers of questions.
A key issue is: how common are pseudotelephathy games (games with perfect
quantum strategies but no perfect classical strategies)? Our experiments
strongly indicate that the probability of a randomly generated game being
pseudotelpathic stays far from 1, indeed it is bounded below 0.15.
We also find strong evidence that randomly generated 3XOR games undergo both
a quantum and classical "phase transition", transitioning from almost certainly
perfect to almost certainly imperfect as the ratio of number of clauses ($m$)
to number of questions ($n$) increases. The locations of these two phase
transitions appear to coincide at $m/n \approx 2.74$.
Related papers
- Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
We investigate optimal decision making under imperfect recall, that is, when an agent forgets information it once held before.
In the framework of extensive-form games with imperfect recall, we analyze the computational complexities of finding equilibria in multiplayer settings.
arXiv Detail & Related papers (2024-06-23T00:27:28Z) - Repeated quantum game as a stochastic game: Effects of the shadow of the
future and entanglement [0.0]
We present a systematic investigation of the quantum games, constructed using a novel repeated game protocol.
We find that how two pure strategies fare against each other is crucially dependent on the discount factor.
In the quantum game setup, always-defect strategy can be beaten by the tit-for-tat strategy for high enough discount factor.
arXiv Detail & Related papers (2023-12-08T15:54:51Z) - Two new non-equivalent three-qubit CHSH games [0.0]
We generalize to three players the well-known CHSH quantum game.
In particular we provide two new three players quantum games where, in one case, the best quantum strategy is obtained when the players share a $GHZ$ state.
In the other one the players have a better advantage when they use a $W$ state as their quantum resource.
arXiv Detail & Related papers (2023-12-01T13:36:21Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - Photonic implementation of the quantum Morra game [69.65384453064829]
We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case.
We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game.
We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
arXiv Detail & Related papers (2023-11-14T19:41:50Z) - Experimental Demonstration of Quantum Pseudotelepathy [8.366359388178546]
We report a faithful experimental demonstration of quantum pseudotelepathy via playing the non-local version of Mermin-Peres magic square game.
We adopt the hyperentanglement scheme and prepare photon pairs entangled in both the polarization and the orbital angular momentum degrees of freedom.
Our results show that quantum players can simultaneously win all the queries over any classical strategy.
arXiv Detail & Related papers (2022-06-24T02:35:55Z) - No-Regret Learning in Time-Varying Zero-Sum Games [99.86860277006318]
Learning from repeated play in a fixed zero-sum game is a classic problem in game theory and online learning.
We develop a single parameter-free algorithm that simultaneously enjoys favorable guarantees under three performance measures.
Our algorithm is based on a two-layer structure with a meta-algorithm learning over a group of black-box base-learners satisfying a certain property.
arXiv Detail & Related papers (2022-01-30T06:10:04Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
arXiv Detail & Related papers (2021-12-09T21:06:52Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - 3XOR Games with Perfect Commuting Operator Strategies Have Perfect
Tensor Product Strategies and are Decidable in Polynomial Time [0.0]
We consider 3XOR games with perfect commuting operator strategies.
We show existence of a perfect commuting operator strategy for the game can be decided in time.
arXiv Detail & Related papers (2020-10-30T14:35:19Z) - Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
Subtraction games are sometimes referred to as one-heap Nim games.
In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games.
For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
arXiv Detail & Related papers (2020-06-12T06:36:07Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.