One-quantum-move Nim solvability conjecture
One-quantum-move Nim solvability conjecture
Let $Z$ be any instance of Nim, let $\phi\in{A,B,C,C',D}$ be a quantum flavor, and let $Z^{\mathrm{symBudgeted}[1]\mathcal Q(\phi,2)}$ denote the symmetric budgeted quantum game in which both players together can make at most one quantum move and the superposition width is two. Likewise, let $Z^{\mathrm{asymBudgeted}[1,0]\mathcal Q(\phi,2)}$ and $Z^{\mathrm{asymBudgeted}[0,1]\mathcal Q(\phi,2)}$ allow at most one quantum move by player or player , respectively.
One-quantum-move Nim solvability conjecture. For every such $Z$ and $\phi$, $Z^{\mathrm{symBudgeted}[1]\mathcal Q(\phi,2)}$ is polynomial-time solvable. The same is conjectured for $Z^{\mathrm{asymBudgeted}[1,0]\mathcal Q(\phi,2)}$ and $Z^{\mathrm{asymBudgeted}[0,1]\mathcal Q(\phi,2)}$.
The symmetric claim is stated in the source as polynomial-time solvable, whereas the two asymmetric variants are explicitly conjectured. The claims concern the effect of a single bounded quantum move on Nim.
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.