Quantum Avoid True complexity conjecture
Quantum Avoid True complexity conjecture
Let $\ruleset{Quantum Avoid True}$ be the quantum extension of the combinatorial game $\ruleset{Avoid True}$, and let a classical start mean that the initial position has no quantum superposition. Let $\ruleset{Quantum Nim}$ be the quantum extension of Nim, and let a poly-wide quantum start mean an initial quantum position whose number of realizations is polynomially bounded.
Quantum Avoid True conjecture. Determining the outcome class of $\ruleset{Quantum Avoid True}$ with a classical start is $\cclass{PSPACE}$-complete. Consequently, determining the outcome class of $\ruleset{Quantum Nim}$ with a poly-wide quantum start is $\cclass{PSPACE}$-hard.
The complexity of Quantum Nim is described as widely open, and this conjecture would establish a strong worst-case lower bound through Quantum Avoid True.
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.