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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.