Skip to main content

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
1 vote
0 answers
25 views

Can Wang's effective resistance algorithms be used on Graph Isomorphism related problems?

Given a large, oracularly defined graph $\Gamma=(V,E)$, Guoming Wang has a paper describing a couple of quantum algorithms for the neat problem of determining the effective resistance between two ...
Mark Spinelli's user avatar
3 votes
1 answer
79 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
44 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
196 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
74 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
2k 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
  • 241
6 votes
1 answer
219 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