We study discrete-time quantum walks on the line and on general undirected graphs with two interacting or noninteracting particles. We introduce two simple interaction schemes and show that they both lead to a diverse range of probability distributions that depend on the correlations and relative phases between the initial coin states of the two particles. We investigate the characteristics of these quantum walks and the time evolution of the entanglement between the two particles from both separable and entangled initial states. We also test the capability of two-particle discrete-time quantum walks to distinguish nonisomorphic graphs. For strongly regular graphs, we show that noninteracting discrete-time quantum walks can distinguish some but not all nonisomorphic graphs with the same family parameters. By incorporating an interaction between the two particles, all nonisomorphic strongly regular graphs tested are successfully distinguished.
We study discrete-time quantum walks on the line and on general undirected graphs with two interacting or noninteracting particles. We introduce two simple interaction schemes and show that they both lead to a diverse range of probability distributions that depend on the correlations and relative phases between the initial coin states of the two particles. We investigate the characteristics of these quantum walks and the time evolution of the entanglement between the two particles from both separable and entangled initial states. We also test the capability of two-particle discrete-time quantum walks to distinguish nonisomorphic graphs. For strongly regular graphs, we show that noninteracting discrete-time quantum walks can distinguish some but not all nonisomorphic graphs with the same family parameters. By incorporating an interaction between the two particles, all nonisomorphic strongly regular graphs tested are successfully distinguished.
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 (SRGs). We study the Green's functions that characterize the dynamical evolution single-particle and two-particle quantum walks on pairs of nonisomorphic SRGs and show that interacting particles can distinguish nonisomorphic 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 nonisomorphic SRGs. (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 nonisomorphic 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 nonisomorphic 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.
Berry and Wang [Phys. Rev. A {\bf 83}, 042317 (2011)] show numerically that a discrete-time quantum 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 particles 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 differences in the graph certificate construction algorithm can nontrivially impact the walk's distinguishing power. We also show that no continuous-time walk of a fixed number of particles can distinguish all strongly regular graphs when used in conjunction with any of the graph certificates we consider. We extend this constraint to discrete-time walks of fixed numbers of noninteracting particles for one kind of graph certificate; it remains an open question as to whether or not this constraint applies to the other graph certificates we consider.
We investigate the quantum dynamics of particles on graphs (``quantum random walks''), with the aim of developing quantum algorithms for determining if two graphs are isomorphic (related to each other by a relabeling of vertices). We focus on quantum random walks of multiple noninteracting particles on strongly regular graphs (SRGs), a class of graphs with high symmetry that is known to have pairs of graphs that are hard to distinguish. Previous work has already demonstrated analytically that two-particle noninteracting quantum walks cannot distinguish nonisomorphic SRGs of the same family. Here, we demonstrate numerically that three-particle noninteracting quantum walks have significant, but not universal, distinguishing power for pairs of SRGs, proving a fundamental difference between the distinguishing power of two-particle and three-particle noninteracting walks. We show analytically why this distinguishing power is possible, whereas it is forbidden for two-particle noninteracting walks. Based on sampling of SRGs with up to 64 vertices, we find no difference in the distinguishing power of bosonic and fermionic walks. In addition, we find that the four-fermion noninteracting walk has greater distinguishing power than the three-particle walk on SRGs, showing that increasing the particle number increases the distinguishing power. However, we also show analytically that no noninteracting walk with a fixed number of particles can distinguish all SRGs, thus demonstrating a potential fundamental difference in the distinguishing power of interacting versus noninteracting walks.
Abstract This paper introduces a novel alternated two-particle discrete-time quantum walk model on arbitrary graphs, overcoming the limitation that conventional shared coin schemes are confined to regular graphs. By employing a fixed-dimension coin operator and encoding the graph structural information into the shift operator, the new model becomes applicable to arbitrary graphs. Further, by adding interaction between the two particles, an extension is presented, which can enhance the model’s dynamic properties and facilitate more intricate quantum interference phenomena. Based on the new model, a kind of quantum graph isomorphism algorithm framework is proposed. It just need O(N 0.5*∣E∣) steps of quantum walk and O(N 2) dimensions of Hilbert space, which offers a significant reduction in complexity compared to other quantum walk based algorithms. The graph isomorphism testing is performed in the framework using non-interacting and interacting quantum walks respectively. Experimental results illustrate that the algorithm based on interacting particles achieves a 100% success rate in discriminating all test graphs. While the algorithm with non-interacting particles performs a 100% distinction success rate on general non-regular graphs, albeit being ineffective on strongly regular graphs. Due to the effectiveness of the algorithm on arbitrary graphs, the algorithm has broad application prospects in the identification and comparison of chemical molecular structures, the analysis of social networks and so on.
We introduce the idea of a quantum walk with two particles and study it for the case of a discrete time walk on a line. We consider both separable and maximally entangled initial conditions, and show how the entanglement and the relative phase between the states describing the coin degree of freedom of each particle will influence the evolution of the quantum walk. In particular, these factors will have consequences for the distance between the particles and the probability of finding them at a given point, yielding results that cannot be obtained from a separable initial state, be it pure or mixed. Finally, we review briefly proposals for implementations.
Quantum random walks have been shown to be powerful quantum algorithms for certain tasks on graphs like database searching, quantum simulations etc. In this work we focus on its applications for the graph isomorphism problem. In particular we look at how we can compare multi-particle quantum walks and well known classical WL tests and how quantum walks can be used to distinguish hard graphs like CFI graphs which k-WL tests cannot distinguish. We provide theoretical proofs and empirical results to show that a k-QW with input superposition states distinguishes k-CFI graphs. In addition we also prove that a k-1 QW with localized input states distinguishes k-CFI graphs. We also prove some additional results about strongly regular graphs (SRGs).