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?


1 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.

  • $\begingroup$ Doesn’t your method require $N!$ qubits though? The $N$ I am referring to is the number of nodes of the graph. Shouldn’t this be disallowed, as $N!$ is not efficient? $\endgroup$ Apr 29, 2023 at 17:29
  • $\begingroup$ You’re right, my normalization factor was wrong. If there are N vertices there are up to N! different adjacency matrices. $\endgroup$ Apr 29, 2023 at 18:08
  • $\begingroup$ Oh, I get it now. We need $N!$ qubit states, and thus need $log(N!)$ qubits. Because $O(N!) = O(N log N)$, this is "efficient." (efficient meaning polynomial number of qubits). $\endgroup$ Apr 29, 2023 at 18:29
  • $\begingroup$ I just noticed this: in your second equation, shouldn't the state be $\frac{1}{\sqrt{N!}} \sum_{i = 1}^{N!} | \pi_i \rangle | \pi_i (G) \rangle$ ? Because $\pi_i$ is the input, not $G$. $\endgroup$ May 2, 2023 at 6:10
  • $\begingroup$ Yeah, I think you're right; sorry for my carelessness. $\pi_i(G)$ is meant to be another adjacency matrix having the $i$th permutation applied to $G$. We can't disentangle the permutation from the output of the permutation. I'll edit it again for clarity. $\endgroup$ May 2, 2023 at 12:31

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.