Noninteracting multiparticle quantum random walks applied to the graph isomorphism problem for strongly regular graphs

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.

Figure 1

Sketch of a generalized subgraph, or “widget,” used to calculate the values and degeneracy of a Green's function for a three-particle quantum walk on an SRG. Vertices on the right side correspond to the vertices the particles are on to begin with (the ket ${\left|pqr\right.〉}_B$ or ${\left|pqr\right.〉}_F$), and vertices on the left side correspond to the vertices the particles end up on (the bra ${}_B\left.〈ijk\right|$ or ${}_F\left.〈ijk\right|$), after application of the evolution operator $U$. A solid line between vertex $x$ and vertex $y$ indicates that $A_{xy}=1$. A dashed line between $x$ and $y$ means that the value of $A_{xy}$ does not affect the value of the Green's function. Thus, for bosons, the depicted widget corresponds to the Green's function ${}_B\left.〈ijk\right|{\mathbf{U}}_{3B}{\left|pqr\right.〉}_B$ when all six vertices are distinct and when $A_{xy}=1$ for all $x\in \{i,j,k\}$ and $y\in \{p,q,r\}$. Equations (10) and (12) show that the value of this Green's function, or widget, is ${}_B\left.〈ijk\right|{\mathbf{U}}_{3B}{\left|pqr\right.〉}_B=6{(\beta +\gamma )}^3$.

Figure 2

Empty widgets for two-particle and three-particle noninteracting walks. In both widgets, all vertices are distinct and no vertex in the initial state is adjacent to any vertex in the final state. The values of the widgets depend only on the family parameters for both (a) and (b), while the degeneracies of these values depend only on family parameters for two particles but not for three. The multiplicity of each widget's respective Green's function for a particular SRG is equal to the number of times that widget appears in the SRG. (a) The empty widget for two particles. The number of times this widget appears in an SRG is a function of the SRG family parameters, as is the case for all two-particle widgets [27]. (b) The empty widget for three particles. The number of times this widget appears in an SRG is $not$ a function solely of SRG family parameters. This is demonstrated by the graphs in Fig. 3. An analytic explanation for this phenomenon is given in the text following Eq. (A2).

Figure 3

The two nonisomorphic graphs of the SRG family (16,6,2,2). The widget in Fig. 2b appears in the graph shown in (a) 608 times, whereas the same widget appears in the graph shown in (b) 512 times. Thus we see that the same three-particle widget can have different multiplicities in graphs of the same family, so the three-particle noninteracting walk can distinguish at least some nonisomorphic graphs from the same SRG family.

Figure 4

Two copies of the Petersen graph, an SRG with parameters $(10,3,0,1)$. In each graph, three mutually nonadjacent vertices are highlighted as (red) diamonds. In (a), the three vertices share one common neighbor, shown as the (green) square. In (b), the three vertices share no common neighbors. This demonstrates that the number of neighbors common to a triple of vertices in a strongly regular graph is not strictly a function of the SRG family parameters, thus showing why widget multiplicity is not strictly governed by family parameters when $p\ge 3$.

Figure 5

The number of numerically distinguished elements in the evolution operator $\mathbf{U}\left(t\right)$, defined in Eq. (8) as a function of the bin size used in grouping the elements. This plot is for the noninteracting three-fermion walk on a graph in the SRG family (16,6,2,2). We see that the actual number of unique elements is about 150, which can be obtained by using a bin size in the range of ${10}^{-7}$ to ${10}^{-4}$.