Skip to main content
Share Your Experience: Take the 2024 Developer Survey
6 votes

How would HSP with $S_N$ work when the automorphism subgroup is (almost) equal to the symmetric group?

TL;DR: We do not need to inspect all the elements of the hidden subgroup ${\mathcal H}=Aut(G)$. We only need to inspect the elements of the generating set that HSP subroutine has found. An efficient ...
Adam Zalcman's user avatar
  • 22.9k
4 votes

What is known about the 'structure' of the solution for Graph Isomorphism on quantum computers?

I wouldn't necessarily say that Graph Isomorphism (GI) is thought to be unsolvable on quantum computers. The consensus among many computer scientists (see e.g. Scott Aaronson) seems to be that GI ...
Stefan S's user avatar
3 votes

What is known about quantum algorithms for graph isomorphism?

Suppose we have two graphs, given by two different adjacency matrices $G_0$ and $G_1$. We wish to know whether the graphs are isomorphic. It's been a folklore result for a long time that if we can ...
Mark Spinelli's user avatar
1 vote

Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model

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$ ...
Mark Spinelli's user avatar
1 vote

How to construct a quantum circuit (QIP system) for the graph non-isomorphism problem?

As I understand $\mathsf{IP}$ and similarly $\mathsf{QIP}$, two parties, prover Peggy and verifier Vicky, engage in a number of rounds that are polynomial in $n$. Each round consists of Vicky ...
Mark Spinelli's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible