Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model

Question

The HSP (Hidden Subgroup Problem) links many NP-intermediate problems, such as factoring, graph isomorphism, and shortest vector.

The brief problem statement is presented like so:

Given some group, G, and a set, X, along with some function $f: G \mapsto X$, $f$ is said to hide a subgroup, $H$, if $f(a) = f(b) \iff aH = bH$. The task is to find the subgroup, $H$ (as a generating set), given $f$ as an oracle.

Factorization (period finding) can fit into this paradigm with the group $\mathbb{Z}_N$, where $N$ is some given constant.

On the other hand, Graph isomorphism has the group $S_N$; the symmetric group on $N$ elements. This group has $N!$ elements in it.

The oracle in graph isomorphism is $U_f | x \in S_N \rangle = | x(G) \in S_N \rangle$ where $G$ is the disjoint union of two graphs (the graphs we want to check the isomorphism of).

An oracle inputs $O(poly(N))$ qubits into it, meaning it has $2^{poly(N)}$ distinct states for $x$ it can hold. (I am using $poly(N)$ as some polynomial function). But $x$ can be anything in $S_N$, meaning it has $N!$ possible states.

We cannot represent an input to this oracle as a bitstring. So how is it done?

Answer 1

What do you mean that we cannot "represent an input to this oracle as a bitstring"?

For example we could have the basis states in our Hilbert space be the adjacency matrices over $N$ vertices, with $G$ being one of these states, while $\pi_i\in S_N$ being permutations of these vertices.

I claim it's easy to prepare the state:

$$\frac{1}{\sqrt {N!}}\sum_{i=1}^{N!}|i\rangle,\tag 1$$

for example where each $i$ is written as a number in the factoradic number system.

With $\pi_i\in S_N$, $G$ being an adjacency matrix on $N$ vertices of the test graph, and $\pi_i(G)$ being another adjacency matrix having the $i$th permutation applied to $G$, I then also claim that it's easy to prepare:

$$\frac{1}{\sqrt {N!}}\sum_{i=1}^{N!}|i\rangle|\pi_i(G)\rangle,\tag 2$$

by applying the $i$th permutation to the vertices on the test graph $G$. If $G$ is given as an adjacency matrix on $N$ vertices in, say, some canonical form, and $\pi_i$ is a permutation, then we can easily come up with classical code, and hence with a quantum circuit, to permute the $N$ vertices in the adjacency matrix to find another adjacency matrix.

The problem, though, is that we cannot then easily disentangle the first register from the second register to prepare:

$$\frac{1}{\sqrt {N!}}\sum_{i=1}^{N!}|\pi_i(G)\rangle,\tag 3$$

because we need to uncompute the garbage that's picked up along the way, while computing $\pi_i(G)$. For, if we had such a state, we could solve graph isomorphism in quantum polynomial time.

---

^{Note I'm using "easy" as synonymous with "polynomially", and not necessarily as meaning easy in the plain and ordinary interpretation of effortlessly or uncomplicated; it might indeed be actually be challenging to engineer the actual snippet of code to do the permutations, and to then convert the code into a quantum circuit.}