Genuinely quantum solutions of the game Sudoku and their cardinality
Jerzy Paczos, Marcin Wierzbiński, Grzegorz Rajchel-Mieldzioć, Adam Burchardt, Karol Życzkowski
Abstract
We expand the quantum variant of the popular game Sudoku by introducing the notion of cardinality of a quantum Sudoku (SudoQ), equal to the number of distinct vectors appearing in the pattern. Our considerations are focused on the genuinely quantum solutions---the solutions of size ${N}^{2}$ that have cardinality greater than ${N}^{2}$, and therefore cannot be reduced to classical counterparts by a unitary transformation. We find the complete parametrization of the genuinely quantum solutions of a $4\ifmmode\times\else\texttimes\fi{}4$ SudoQ game and establish that in this case the admissible cardinalities are 4, 6, 8, and 16. In particular, a solution with the maximal cardinality equal to 16 is presented. Furthermore, the parametrization enabled us to prove a recent conjecture of Nechita and Pillet [I. Nechita and J. Pillet, Quantum Inf. Comput. 21, 781 (2021)] for this special dimension. In general, we proved that for any $N$ it is possible to find an ${N}^{2}\ifmmode\times\else\texttimes\fi{}{N}^{2}$ SudoQ solution of cardinality ${N}^{4}$, which for a prime $N$ is related to a set of $N$ mutually unbiased bases of size ${N}^{2}$. Such a construction of ${N}^{4}$ different vectors of size $N$ yields a set of ${N}^{3}$ orthogonal measurements.