Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$.

We also denote the state $| G \rangle$ as the $n \choose 2$ qubit state that corresponds to the graph $G$.

Moreover, $S_n$ is the set of all permutations on $n$ elements, and $\pi(G)$ is the graph obtained by renaming all $v \in E$ to $\pi(v)$, and where $(i,j)$ is an edge in $G$ if and only if $(\pi(i),\pi(j))$ is an edge in $\pi(G)$.

I want to create the superposition state: $$ (n!) ^ {-\frac{1}{2}} \sum_{\pi \in S_n} | \pi, \pi (G) \rangle $$

We can assume that there is a $\lceil \log(n!) \rceil$ representation for a permutation, and that there is a classical circuit to calculate $\pi(i)$ and the representation of $\pi$.

My idea was to start from the state $|0 ^ {\log(n!)} \rangle |G\rangle$.

Then we apply Hadamard to the state to the first $\log(n!)$ qubits and we obtain $$(\frac{1}{2})^{\log(n!)/2}\sum_{\pi \in S_n} | \pi, G \rangle$$.

However, I don't know how to continue from here, and I'm not even sure what I've done until now is the correct way.

Help would be appreciated.


2 Answers 2


What you're missing is that if there is an efficient classical circuit to compute $\pi(G)$ from a binary representation of $\pi$, then it means that you are able to build the oracle: $$\mathcal{O}|\pi,y\rangle=|\pi,y\oplus\pi(G)\rangle$$ Indeed, since $G$ is fixed, the function $\pi\mapsto\pi(G)$ is well defined, and we can build an oracle out of it.

From there it's quite simple if you allow for "extra" permutations:

  • Create a uniform superposition on $\left\lceil\log_2(n!)\right\rceil$ qubits: $$\frac{1}{\sqrt{2^{\left\lceil\log_2(n!)\right\rceil}}}\left[\sum_{\pi\in\mathfrak{S}_n}|\pi, 0\rangle+\sum_{x\not\in\mathfrak{S}_n}|x,0\rangle\right].$$
  • Apply the oracle $\mathcal{O}$: $$\frac{1}{\sqrt{2^{\left\lceil\log_2(n!)\right\rceil}}}\left[\sum_{\pi\in\mathfrak{S}_n}|\pi, \pi(G)\rangle+\sum_{x\not\in\mathfrak{S}_n}|x,\text{junk}(x)\rangle\right].$$ (I've put $\text{junk}$ because it's not really defined what the $\pi\mapsto\pi(G)$ function does when called on an input not representing a permutation).

The problem however is that by doing so, you have some additional bistrings that don't represent a valid permutation. If you thus replace the first step by "create a uniform superposition over the $n!$ first basis states", you have the state you desire. The method to do so that has already been asked and answered on this site, for instance here.

Note that we have $\frac{n!}{2^{\left\lceil\log_2(n!)\right\rceil}}>\frac12$, which means that the first approach described in the aforementioned answer works with probability at least $\frac12$:

  • Create a uniform superposition on $\left\lceil\log_2(n!)\right\rceil$ qubits: $$\frac{1}{\sqrt{2^{\left\lceil\log_2(n!)\right\rceil}}}\left[\sum_{\pi\in\mathfrak{S}_n}|\pi, 0\rangle+\sum_{x\not\in\mathfrak{S}_n}|x,0\rangle\right].$$
  • Apply a "less-than-n!" oracle: $$\frac{1}{\sqrt{2^{\left\lceil\log_2(n!)\right\rceil}}}\left[\sum_{\pi\in\mathfrak{S}_n}|\pi, 1\rangle+\sum_{x\not\in\mathfrak{S}_n}|x,0\rangle\right].$$
  • Measure the second register. If you get the outcome $|1\rangle$, which happens with probability larger than $\frac12$, then the state you get is: $$\frac{1}{\sqrt{n!}}\sum_{\pi\in\mathfrak{S}_n}|\pi\rangle.$$ Otherwise, redo the procedure. Note that in the last state, we've discarded the second register which is not entangled with the first one anymore.
  • Add a second register in state $|0\rangle$ and apply the $\pi\mapsto\pi(G)$ oracle: $$\frac{1}{\sqrt{n!}}\sum_{\pi\in\mathfrak{S}_n}|\pi,\pi(G)\rangle.$$
  • $\begingroup$ Thanks for the insightful answer! I didn't think about the oracle here. $\endgroup$
    – Gabi G
    Feb 29 at 0:20

Surprisingly, the way to make a uniform superposition of all permutations is by using a sorting network. You make random shuffle states by sorting! Weird, right? This was figured out in "Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians", which solves this problem under the additional wrinkle that odd-parity permutations should have a negative amplitude.

Here's what you do.

  1. Initialize $n$ registers each into the state $|+\rangle^{\otimes m}$. Here $m$ is a value of size $O(\lg n/\epsilon)$ where $\epsilon$ is your error tolerance. The main source of error in this procedure is the probability of two registers containing the same value. You exponentially suppress that probability by making $m$ larger.

  2. Apply a sorting network to the registers. To maintain reversibility, each compare-and-swap operation doesn't just swap it will also output its comparison result as a qubit. These are the qubits that will represent the permutation.

  3. Discard the $n$ registers and keep the outputs of the comparison results. That's the uniformly superposed representation of $\pi$. You can apply $\pi$ by running the compare-and-swaps of the sorting network in reverse order, but with the swap conditioned on the output qubit from before instead of on the actual comparison of the values being swapped.

Conceptually what's happening here is that, if you generate a random /superposed list of integers, that list is the combination of which-integers-you-picked (the set) and what-order-they-are-in (the permutation). Your goal is to pull out the permutation part, to get a random/superposed permutation. Sorting separates the set from the permutation, so you can discard the set and keep the permutation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.