Publications

Results 6576–6600 of 9,998

Search results

Jump to search filters

Comparing Algorithms for Graph Isomorphism Using Discrete- and Continuous-Time Quantum Random Walks

Journal of Computational and Theoretical Nanoscience

Rudinger, Kenneth M.; Laros, James H.; Bach, Eric; Friesen, Mark; Joynt, Robert; Coppersmith, S.N.

Berry and Wang [Phys. Rev. A 83, 042317 (2011)] show numerically that a discrete-time quan- tum random walk of two noninteracting particles is able to distinguish some non-isomorphic strongly regular graphs from the same family. Here we analytically demonstrate how it is possible for these walks to distinguish such graphs, while continuous-time quantum walks of two noninteracting parti- cles cannot. We show analytically and numerically that even single-particle discrete-time quantum random walks can distinguish some strongly regular graphs, though not as many as two-particle noninteracting discrete-time walks. Additionally, we demonstrate how, given the same quantum random walk, subtle di erences in the graph certi cate construction algorithm can nontrivially im- pact the walk's distinguishing power. We also show that no continuous-time walk of a xed number of particles can distinguish all strongly regular graphs when used in conjunction with any of the graph certi cates we consider. We extend this constraint to discrete-time walks of xed numbers of noninteracting particles for one kind of graph certi cate; it remains an open question as to whether or not this constraint applies to the other graph certi cates we consider.

More Details
TYPE Journal Article YEAR 2013
DOIOSTI
Results 6576–6600 of 9,998
Results 6576–6600 of 9,998