On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems

Andrew M. Childs, Pawel Wocjan

We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using…