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

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.