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
7
votes
1answer
242 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 ...
6
votes
1answer
160 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 ...