Constant-wide Demi-Quantum Nim hardness conjecture
Constant-wide Demi-Quantum Nim hardness conjecture
Let $Z=(B,\Sigma,\rho_L,\rho_R,b_0)$ be a combinatorial game instance, and let $\mathbb{B}=[b_1|\cdots|b_s]$ be a quantum board consisting of a superposition of distinct positions. The associated demi-quantum game $Z^{\mathrm{demi}\mathcal Q}[\mathbb{B}]$ starts from $\mathbb{B}$, permits only classical moves, and is called constant-wide when $s$ is constant. Playing optimally means determining the outcome under optimal play.
Constant-wide Demi-Quantum Nim conjecture. Constant-wide $\ruleset{Demi-Quantum Nim}$ is $\cclass{NP}$-hard to play optimally.
The paper establishes that poly-wide Demi-Quantum Nim is $\cclass{PSPACE}$-complete, while the constant-wide hardness claim remains open.
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.