Questions tagged [graph-isomorphism]

Two graphs 𝐺 and 𝐻 are isomorphic if they have a function 𝑓 which provides an exact pairing of vertices in the two graphs such that for any adjacent vertices 𝑢,𝑣 ∈ {set of vertices of 𝐺}, 𝑓(𝑢) and 𝑓(𝑣) are also adjacent in 𝐻.

Filter by
Sorted by
Tagged with
0 votes
0 answers
29 views

How does the hardness of the HSP change when the hiding function is altered?

When talking about many (presumably) NP-intermediate problems, such as factoring and graph isomorphism, the HSP is brought up. The HSP, as a problem, is often paired with a group, $G$, and an oracle, $...
Andrew Baker's user avatar
2 votes
1 answer
76 views

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

It is thought that Graph Isomorphism, at least the HSP with the symmetric group, is unsolvable on quantum computers. This is a case of the non-abelian HSP. But if a solution to this problem were to ...
Andrew Baker's user avatar
2 votes
0 answers
43 views

Does a solution to SAT solve the HSP for $S_N$, $D_{2N}$, or even the general case?

I often hear about the graph isomorphism problem reducing to the HSP with the symmetric group and a mapping $f \colon \pi \in S_N \mapsto \pi(G)$ with $G$ being some graph (the union of the graphs we’...
Andrew Baker's user avatar
6 votes
1 answer
192 views

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

The graph isomorphism problem can be reduced to a case of the hidden subgroup problem, with the group $S_N$ and the function $f \colon \pi \mapsto \pi(G)$ where $G$ is some graph, and $\pi \in S_N$. ...
Andrew Baker's user avatar
1 vote
1 answer
68 views

Implementing a HSP for Graph Isomorphism in the Quantum Circuit Model

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,...
Andrew Baker's user avatar
8 votes
1 answer
1k views

What is known about quantum algorithms for graph isomorphism?

Shor's algorithm (for factoring integers) and Grover's algorithm (for searches) are the two most well-known quantum algorithms. I was wondering if there was a similar result in QC that dealt with the ...
paulinho's user avatar
  • 221
6 votes
1 answer
211 views

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

I'm having some trouble understanding quantum interactive proof systems (QIP systems) and the related circuit constructions. Interactive proof systems model these type of situations: Interactive ...
Sanchayan Dutta's user avatar