Two-particle quantum walks applied to the graph isomorphism problem

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

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

     

Profile ID: LFWR-SCP-O-51070

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.