Quantum Combinatorial Games: Structures and Computational Complexity
- URL: http://arxiv.org/abs/2011.03704v1
- Date: Sat, 7 Nov 2020 06:09:10 GMT
- Title: Quantum Combinatorial Games: Structures and Computational Complexity
- Authors: Kyle Burke, Matthew Ferland, Shang-Hua Teng
- Abstract summary: Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance.
We show that quantum moves not only enrich the game structure, but also impact their computational complexity.
- Score: 2.284455793077548
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, a standardized framework was proposed for introducing
quantum-inspired moves in mathematical games with perfect information and no
chance. The beauty of quantum games-succinct in representation, rich in
structures, explosive in complexity, dazzling for visualization, and
sophisticated for strategic reasoning-has drawn us to play concrete games full
of subtleties and to characterize abstract properties pertinent to complexity
consequence. Going beyond individual games, we explore the tractability of
quantum combinatorial games as whole, and address fundamental questions
including:
Quantum Leap in Complexity: Are there polynomial-time solvable games whose
quantum extensions are intractable?
Quantum Collapses in Complexity: Are there PSPACE-complete games whose
quantum extensions fall to the lower levels of the polynomial-time hierarchy?
Quantumness Matters: How do outcome classes and strategies change under
quantum moves? Under what conditions doesn't quantumness matter?
PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into
outer polynomial space
We show that quantum moves not only enrich the game structure, but also
impact their computational complexity. In settling some of these basic
questions, we characterize both the powers and limitations of quantum moves as
well as the superposition of game configurations that they create. Our
constructive proofs-both on the leap of complexity in concrete Quantum Nim and
Quantum Undirected Geography and on the continuous collapses, in the quantum
setting, of complexity in abstract PSPACE-complete games to each level of the
polynomial-time hierarchy-illustrate the striking computational landscape over
quantum games and highlight surprising turns with unexpected quantum impact.
Our studies also enable us to identify several elegant open questions
fundamental to quantum combinatorial game theory (QCGT).
Related papers
- A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover.
We establish a quantum soundness result for all compiled two-player nonlocal games.
arXiv Detail & Related papers (2024-08-13T08:11:56Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - The History of Quantum Games [0.0]
We collect over 260 quantum games ranging from commercial games, applied and serious games, and games that have been developed at quantum themed game jams and educational courses.
We provide an overview of the journey of quantum games across three dimensions.
arXiv Detail & Related papers (2023-09-04T11:10:58Z) - A vertical gate-defined double quantum dot in a strained germanium
double quantum well [48.7576911714538]
Gate-defined quantum dots in silicon-germanium heterostructures have become a compelling platform for quantum computation and simulation.
We demonstrate the operation of a gate-defined vertical double quantum dot in a strained germanium double quantum well.
We discuss challenges and opportunities and outline potential applications in quantum computing and quantum simulation.
arXiv Detail & Related papers (2023-05-23T13:42:36Z) - Quantum Extensive Form Games [0.0]
We propose a concept of quantum extensive-form games, which is a quantum extension of classical extensive-form games.
A quantum extensive-form game is also a generalization of quantum learning, including Quantum Generative Adrial Networks.
arXiv Detail & Related papers (2022-07-12T09:58:21Z) - No-signalling constrains quantum computation with indefinite causal
structure [45.279573215172285]
We develop a formalism for quantum computation with indefinite causal structures.
We characterize the computational structure of higher order quantum maps.
We prove that these rules, which have a computational and information-theoretic nature, are determined by the more physical notion of the signalling relations between the quantum systems.
arXiv Detail & Related papers (2022-02-21T13:43:50Z) - Endless Fun in high dimensions -- A Quantum Card Game [0.0]
We present a strategic card game in which the building blocks of a quantum computer can be experienced.
While playing, participants start with the lowest quantum state, play cards to "program" a quantum computer, and aim to achieve the highest possible quantum state.
By also including high-dimensional quantum states, i.e., systems that can take more than two possible values, the game can help the players to understand complex quantum state operations.
arXiv Detail & Related papers (2021-07-26T07:52:13Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - Quantum walk processes in quantum devices [55.41644538483948]
We study how to represent quantum walk on a graph as a quantum circuit.
Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
arXiv Detail & Related papers (2020-12-28T18:04:16Z) - Quantum Go Machine [15.33065067850941]
We experimentally demonstrate a quantum version of Go using correlated photon pairs entangled in polarization degree of freedom.
Some quantum resources, like coherence or entanglement, can also be encoded to represent the state of quantum stones.
Our results establish a paradigm of inventing new games with quantum-enabled difficulties.
arXiv Detail & Related papers (2020-07-23T18:00:01Z) - Quantum supremacy in driven quantum many-body systems [0.0]
We show that quantum supremacy can be obtained in generic periodically-driven quantum many-body systems.
Our proposal opens the way for a large class of quantum platforms to demonstrate and benchmark quantum supremacy.
arXiv Detail & Related papers (2020-02-27T07:20:15Z)
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.