ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.