# Effecient creation of a sudoku/permutatation state

I have $$n^2$$ qubits indexed $$|x_{i,j}\rangle\, i,j \in \{0,...,n-1\}$$ and want to create the state $$|\psi\rangle = \frac{1}{\sqrt{n!}}\sum _{x\in S} |x\rangle$$ where $$x\in S \iff \forall i\, \sum_{j}x_{i,j}=1,\, \forall j\, \sum_{i}x_{i,j}=1$$.

Can this be done effeciently?

Essenitally the qubits are in an $$n\times n$$ grid and each row and column must have exactly one qubit in $$|1\rangle$$, which corresponds to a permutation. My plan so far is to create a superposition in each row satisfy this property individually and then run a grovers search to make the columns also satisfy the property but this should still require exponential queries.

• A very involved but still polynomial approach might be to prepare a uniform superposition from $1$ to $n!$ in a first register with the number of qubits bounded by the log of Stirling’s formula, then use a bijection from each number in $[1,n!]$ to your permutation matrix in a second $n\times n$-qubit register, then uncompute the first register. The bijection could be a pain and may be based on, e.g., factoradic notation… Commented Jul 30 at 3:00
• Thanks @MarkSpinelli, is there any intuition to why such a bijection would be implementable efficiently? Commented Jul 30 at 8:22

Start by preparing the state equivalent to the identity matrix. i.e., the first qubit of the first row equals one, the second qubit of the second row equals one, ... $$|1000..0,\; 0100..0,\; 0010..0,\; ...,\; 0000..1\rangle$$

Now, we have a list of $$n$$ sorted, repetition-free, elements, each one of them is $$n$$ bits length, and we want to generate the uniform superposition of all possible permutations of these elements.

The paper Improved techniques for preparing eigenstates of fermionic Hamiltonians provides a polynomial time algorithm which does exactly that. (See figure 6 in the preprint for an illustrative example)

• Do you generate a bunch of $W$ states, one for each row? Commented Aug 1 at 11:28
• No. Why would I do that? Commented Aug 1 at 12:10
• I'm just curious how the superposition is created. I follow Fig. 6 of the preprint but I'm not yet seeing how you start off with $I$ as above and then use that to prepare a superposition over other permutations. Commented Aug 1 at 13:28
• Assume $4 \times 4$ matrices. When written in the notation described in my answer, the identity matrix will be $|1000,0100,0010,0001\rangle$. Which can be written as $|1,2,4,8\rangle$ (here, I'm assuming big-endian notation) Now, Apply Fisher-Yates shuffle to these number, you should get the 24 possible permutations which are the 24 possible $4 \times 4$ permutation matrices. Commented Aug 1 at 16:18
• i got it now; nice! Commented Aug 1 at 20:13

Expanding on a comment above, the following might work with a little bit of error and would be polynomial in $$n$$, but would probably be a brutal polynomial with a very deep circuit.

1. Initially prepare a first register of $$\ln (n!)=n\ln-n+O(\ln n)$$ qubits into a uniform superposition.
2. Use a (polynomial but deep) circuit to prepare a second register into the factoradic notation.
3. This is a bijection between the binary numbers from $$0$$ to roughly $$n!$$ and is achieved with basic algorithms for base conversion - e.g., the same efficient algorithm that lets us write a decimal number in binary would work here.
4. Uncompute the first register by running the above circuit backwards, using the second register to zero out the first.
5. Use an algorithm briefly outlined and discussed with regards to the Lehmer code in the above Wikipedia page to take the factoradic register and prepare a third register into your permutation matrix/Sudoku matrix.
6. This algorithm is also efficient, and you could uncompute the second register and zero it out.

The table in the Wikipedia article shows all the permutation matrices for $$n=4$$, along with their factoradic and decimal notations.

Because Stirling's approximation isn't perfect there will be errors and you would have probably a little higher amplitude on some permutations, but I'm pretty sure it "would work" mostly.