1
$\begingroup$

The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should start with constructing the state $|f\rangle$.

$$ |f\rangle = \frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle |f\left(g\right)\rangle $$

I am trying to figure out the efficient way to construct $\frac{1}{\sqrt{|G|}} \sum_{g \in G} |g\rangle$. For a $3$-node graph isomorphsim problem, $|G| = 720$. It means, if we map each permutation of $G$ to an unique basis state, we need $720$ basis states. It entails that $|g\rangle$ has to be at least a $10$ qubit register.

My questions are:

  1. Is there a more efficient way to construct the state with lesser number of qubits?
  2. If we need at least 10 qubits, which $720$ of the $2^{10}$ states should I choose?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.