Reachable poly-wide Demi-Quantum Nim hardness conjecture
Reachable poly-wide Demi-Quantum Nim hardness conjecture
Let $Z^{\mathrm{demi}\mathcal Q}[\mathbb{B}]$ be a demi-quantum game whose initial quantum board $\mathbb{B}$ is a superposition of positions, and call it classically reachable when $\mathbb{B}$ is reachable from a classical position. A game is poly-wide when the number of realizations in its initial board is polynomial in the descriptive complexity of the underlying instance.
Reachable poly-wide Demi-Quantum Nim conjecture. Reachable poly-wide $\ruleset{\mathrm{demi\text{-}Quantum Nim}$ remains $\cclass{PSPACE}$-hard to play optimally.
The unrestricted poly-wide Demi-Quantum Nim problem is stated to be $\cclass{PSPACE}$-complete; the conjecture asks whether the hardness persists when the initial board is classically reachable.
Sources & referencesView supporting material
Primary source
Kyle Burke, Matthew Ferland and Shang-Hua Teng, “Quantum Combinatorial Games: Structures and Computational Complexity”, arXiv:2011.03704 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.