Two-particle quantum walks applied to the graph isomorphism problem

Details Two-particle quantum walks applied to the graph isomorphism problem Two-particle quantum walks applied to the graph isomorphism problem

2010-02-16

arxiv.org/abs/1002.3003v1

Phys. Rev. A 81, 052313 (2010)

Physics

Quantum Physics

12 pages, 3 figures, 3 tables

Scientific paper

10.1103/PhysRevA.81.052313

We show that the quantum dynamics of interacting and noninteracting quantum particles are fundamentally different in the context of solving a particular computational problem. Specifically, we consider the graph isomorphism problem, in which one wishes to determine whether two graphs are isomorphic (related to each other by a relabeling of the graph vertices), and focus on a class of graphs with particularly high symmetry called strongly regular graphs (SRG's). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of non-isomorphic SRG's and show that interacting particles can distinguish non-isomorphic graphs that noninteracting particles cannot. We obtain the following specific results: (1) We prove that quantum walks of two noninteracting particles, Fermions or Bosons, cannot distinguish certain pairs of non-isomorphic SRG's. (2) We demonstrate numerically that two interacting Bosons are more powerful than single particles and two noninteracting particles, in that quantum walks of interacting bosons distinguish all non-isomorphic pairs of SRGs that we examined. By utilizing high-throughput computing to perform over 500 million direct comparisons between evolution operators, we checked all tabulated pairs of non-isomorphic SRGs, including graphs with up to 64 vertices. (3) By performing a short-time expansion of the evolution operator, we derive distinguishing operators that provide analytic insight into the power of the interacting two-particle quantum walk.

Affiliated with

Also associated with

No associations

Rating

Two-particle quantum walks applied to the graph isomorphism problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two-particle quantum walks applied to the graph isomorphism problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-particle quantum walks applied to the graph isomorphism problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-51070