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 𝐻.

7 questions
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 ...
• 12.8k
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 ...
• 279
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’...
• 279
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$. ...
• 279
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,...
• 279
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 ...
• 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 ...
• 17.6k