Quantum Walk Search on Johnson Graphs Thomas G Wong Faculty of Computing, University of Latvia, Rain¸a bulv. 19, R¯ıga, LV-1586, Latvia E-mail: [email protected] Abstract. The Johnson graph J(n,k) is defined by n symbols, where vertices are 6 k-elementsubsetsofthesymbols,andverticesareadjacentiftheydifferinexactlyone 1 0 symbol. In particular, J(n,1) is the complete graph Kn, and J(n,2) is the strongly 2 regular triangular graph T , both of which are known to support fast spatial search n r by continuous-time quantum walk. In this paper, we prove that J(n,3), which is the p n-tetrahedralgraph,alsosupportsfastsearch. Intheprocess,weshowthatachangeof A basisisneededfordegenerateperturbationtheorytoaccuratelydescribethedynamics. 2 This method can also be applied to general Johnson graphs J(n,k) with fixed k. 1 ] h PACS numbers: 03.67.Ac, 05.40.Fb, 02.10.Ox p - t n 1. Introduction a u q The Johnson graph J(n,k) is defined by n symbols, where vertices are k-element subsets [ of the symbols, and vertices are adjacent if they differ in exactly one symbol (Section 8 2 v of [1]). Consider two examples with n = 4 symbols {a,b,c,d}. First, if k = 1, then the 2 vertices of J(4,1) are 1-element subsets of the symbols, so the vertices are simply a, b, c, 1 2 and d. Since they all differ from each other by one symbol, all the vertices are adjacent 4 0 to each other, and the resulting graph is the complete graph K shown in figure 1a. In 4 . 1 general, J(n,1) is the complete graph K . For the second example, if k = 2, then the n 0 vertices of J(4,2) are 2-element subsets of {a,b,c,d}, so the vertices are ab, ac, ad, bc, 6 1 bd, and cd. Vertices are adjacent if they differ in exactly one element; for example, ab : v and ac are adjacent, while ab and cd are not. The resulting graph is shown in figure 1b, i X and it is the triangular graph T . In general, J(n,2) with n ≥ 4 is the triangular graph 4 r a Tn [2]. Johnson graphs have made recent headlines in the computer science and quantum computing communities [3, 4] due to Babai’s quasipolynomial algorithm for graph isomorphism [5], in which the algorithm is polynomial in all cases except for Johnson graphs. That is, Johnson graphs are the only structures preventing the graph isomorphishm problem from being polynomial rather than quasipolynomial. Despite this recent notoriety, Johnson graphs are familiar structures on which to perform quantum walks, with Ambainis’s element distinctness algorithm [6] famously walking on them in discrete-time. More recently, a continuous-time quantum walk Quantum Walk Search on Johnson Graphs 2 ab a bc bd b d cd c ac ad (a) (b) Figure 1. (a) The Johnson graph J(4,1), which is the complete graph K . (b) The 4 Johnson graph J(4,2), which is the triangular graph T . 4 algorithm for element distinctness was developed by Childs [7], which walks on a modified Johnson graph with additional vertices and edges acting as the oracle. In this paper, we investigate spatial search by continuous-time quantum walk [8] on Johnson graphs for a unique marked vertex. The system |ψ(t)(cid:105) begins in an equal superposition |s(cid:105) over the vertices: N 1 (cid:88) |ψ(0)(cid:105) = |s(cid:105) = √ |v(cid:105), (1) N v=1 where (cid:18) (cid:19) n n! N = = (2) k (n−k)!k! is the number of vertices of J(n,k) since we choose k symbols out of n for each vertex. From this starting state, the system evolves by Schro¨dinger’s equation d i |ψ(t)(cid:105) = H|ψ(t)(cid:105) dt with Hamiltonian H = −γA−|w(cid:105)(cid:104)w|. (3) Here, γ is a real and positive parameter corresponding to the jumping rate (amplitude per time) of the quantum walk, A is the adjacency matrix of the graph (A = 1 if ij two vertices are adjacent and 0 otherwise), and |w(cid:105) is the marked vertex to search for (so |w(cid:105)(cid:104)w| acts as a Hamiltonian oracle [9]). Note that Johnson graphs are regular, so using the adjacency matrix to effect the quantum walk is equivalent to using the Laplacian [10]. Also, Johnson graphs are vertex-transitive, so regardless of which vertex is marked, the algorithm behaves the same way. Finally, since the search Hamiltonian (3) is time-independent, the solution to Schr¨odinger’s equation is |ψ(t)(cid:105) = e−iHt|ψ(0)(cid:105). (4) Quantum Walk Search on Johnson Graphs 3 abc def abd cef abe cdf abf cde acd bef ace bdf acf bde bcd aef bce adf bcf ade Figure 2. The Johnson graph J(6,3), which is the 6-tetrahedral graph. The runtime of the continuous-time quantum walk search algorithm is known for some specific cases of Johnson graphs. As introduced above, J(n,1) corresponds to the complete graph K , and the search algorithm is simply the continuous-time quantum n √ walk formulation of Grover’s algorithm, which runs in O( N) time [11, 12, 8, 13] (where the number of vertices (2) is N = n in this case). Similarly, the triangular graphs J(n,2) with n ≥ 4 are strongly regular graphs, which are also known to support fast √ quantum search in O( N) time for large N [14] (where the number of vertices (2) is N = n(n−1)/2 in this case). Thus search on Johnson graphs with k = 1 and k = 2 is fast, achieving the full quadratic Grover speedup. In the next section, we explicitly prove that search on the √ next case, k = 3, is also fast, searching in O( N) time, with N = n(n − 1)(n − 2)/6 the number of vertices (2). In particular, J(n,3) is the n-tetrahedral graph for n ≥ 6 [15]. For example, J(6,3) is shown in figure 2, and it seems to be the first illustration of a tetrahedral graph in the literature. To construct it, we take the n = 6 symbols to be {a,b,c,d,e,f}, and the vertices are (k = 3)-element subsets of the symbols. The vertices are adjacent if they differ by one symbol (or, equivalently, when they share two symbols). Also, although it is hard to tell from the figure, tetrahedral graphs are vertex- transitive, as are all Johnson graphs, so the algorithm will behave identically regardless of which vertex is marked. The proof that search on J(n,3) is fast involves reducing the evolution to a 4D subspace, which is found by taking equal superpositions of identically-evolving vertices Quantum Walk Search on Johnson Graphs 4 as orthonormal basis states. Often, analyzing the energy eigensystem in this basis using degenerate perturbation theory [14] is sufficient to find the evolution of the algorithm [16, 17, 18, 19, 10]. In this case, however, the calculation is not precise enough to derive accurate dynamics. We show that a change of basis, followed by approximations as in [17], does allow degenerate perturbation theory to derive accurate dynamics. We end by outlining how this method can be applied to search on Johnson graphs J(n,k) with other values of k, such as k = 4,5,6, etc. Each value of k seems to require repeating the calculations, which is tedious and unending (since there is an infinite number of possible values of k). So we leave these calculations, and the case of general k, for further research. 2. Search on Tetrahedral Graphs J(n,3) 2.1. 4D Subspace We begin our analysis of search on tetrahedral graphs J(n,3) by continuous-time quantum walk by noting that Johnson graphs are distance-transitive [1], meaning vertices the same distance from a given vertex are all structurally identical [20]. Thus if we mark a vertex, as indicated in figure 3 by a double circle and colored red, then the vertices adjacent (one away) from the marked vertices evolve identically. These are colored blue. Similarly, vertices two away from the marked vertex evolve identically, and they are colored yellow. Finally, vertices three away from the marked vertex, colored magenta, evolve identically (in this diagram with n = 6, there is just one such vertex). Let us respectively call these types d , d , d , and d , where the subscript indicates the 0 1 2 3 distance from the marked vertex. Note that tetrahedral graphs J(n,3) have diameter 3, meaning vertices are at most distance 3 from each other. As a simple proof, consider two non-adjacent vertices abc and xyz of an arbitrary tetrahedral graph, with x,y,z (cid:54)∈ {a,b,c}. Then one can connect them through three edges, such as abc ∼ abz ∼ ayz ∼ xyz. Thus d , d , d , and d are 0 1 2 3 the only types of vertices. That is, there is no d , for example. So the system evolves 4 in a 4D subspace. This is also the source of the constraint that n ≥ 6; if n < 6, then the graph has smaller diameter. How many vertices of each type are there? Let us denote this as |d | and determine i it for each type: • d : Clearly, there is only one d vertex, namely the marked vertex. That is, 0 0 |d | = 1. 0 • d : Without loss of generality, say the marked vertex has symbols abc. Then the 1 vertices adjacent to it have the form xbc, axc, and abx, where x (cid:54)∈ {a,b,c}. Since each of these three forms leaves n−3 possibilities for x, |d | = 3(n−3). 1 Note this is also the degree of the graph, since it is regular. Quantum Walk Search on Johnson Graphs 5 abc def abd cef abe cdf abf cde acd bef ace bdf acf bde bcd aef bce adf bcf ade Figure 3. The Johnson graph J(6,3), which is the 6-tetrahedral graph. Without loss of generality, a vertex is marked, as indicated by the double circle. Identically evolving vertices are identically colored. • d : Type d vertices are two away from the marked vertex abc, so they have the 2 2 form axy, xby, and xyc with x,y (cid:54)∈ {a,b,c} and x (cid:54)= y. For each of the three forms, there are n−3 options for x and n−4 options for y. Thus 3(n−3)(n−4) |d | = , 2 2 where we divide by 2 because the order of x and y does not matter. • d : Finally, type d vertices are three away from the marked vertex abc, so they 3 3 have the form xyz with x,y,z (cid:54)∈ {a,b,c} and x (cid:54)= y (cid:54)= z (cid:54)= x. Thus there are n−3 options for x, n−4 options for y, and n−5 options for z. Thus (n−3)(n−4)(n−5) |d | = , 3 6 where we divide by 6 = 3! because the order of x,y,z does not matter. As a check, it is straightforward to show that |d | + |d | + |d | + |d | equals the total 0 1 2 3 number of vertices N = n(n−1)(n−2)/6, which comes from (2) with k = 3. Now we take equal superpositions of each type of vertex, which together serve as an orthonormal basis of the 4D subspace: |d (cid:105) = |w(cid:105) 0 1 (cid:88) 1 (cid:88) |d (cid:105) = |v(cid:105) = |v(cid:105) 1 (cid:112) (cid:112) |d | 3(n−3) 1 d(v,w)=1 d(v,w)=1 Quantum Walk Search on Johnson Graphs 6 (cid:115) 1 (cid:88) 2 (cid:88) |d (cid:105) = |v(cid:105) = |v(cid:105) 2 (cid:112) |d | 3(n−3)(n−4) 2 d(v,w)=2 d(v,w)=2 (cid:115) 1 (cid:88) 6 (cid:88) |d (cid:105) = |v(cid:105) = |v(cid:105). 3 (cid:112) |d | (n−3)(n−4)(n−5) 3 d(v,w)=3 d(v,w)=3 In this {|d (cid:105),|d (cid:105),|d (cid:105),|d (cid:105)} basis, the initial equal superposition state (1) is 0 1 2 3 (cid:18) (cid:114) 1 (cid:112) 3(n−3)(n−4) |s(cid:105) = √ |d (cid:105)+ 3(n−3)|d (cid:105)+ |d (cid:105) 0 1 2 N 2 (cid:114) (cid:19) (n−3)(n−4)(n−5) + |d (cid:105) 3 6   1 (cid:112)  3(n−3)  = √1  (cid:113)3(n−3)(n−4) . (5) N   (cid:113) 2  (n−3)(n−4)(n−5) 6 From this initial state, the system evolves by Schr¨odinger’s equation with Hamiltonian given in (3). To find the Hamiltonian in the 4D subspace, let us first find the adjacency matrix. To find the adjacency matrix in the {|d (cid:105),|d (cid:105),|d (cid:105),|d (cid:105)} basis, recall that 0 1 2 3 tetrahedral graphs (and general Johnson graphs) are distance-transitive. Then the relation between each type of vertex can be summarized by its intersection array [15]:   ∗ 1 4 9  0 n−2 2(n−4) 3(n−6).   3(n−3) 2(n−4) n−5 ∗ To explain this intersection array, let us start with the left column, which indicates that a d vertex is adjacent to no other d vertices (obviously, since there is only one 0 0 marked vertex) and adjacent to 3(n−3) vertices of type b. Now for the second column, a type d vertex is adjacent to one d vertex, n−2 other d vertices, and 2(n−4) type 1 0 1 d vertices. For the third column, a d vertex is adjacent to four d vertices, 2(n−4) 2 2 1 other d -vertices, and n−5 type d vertices. Finally, for the last column, a d vertex is 2 3 3 adjacent to nine d vertices and 3(n − 6) other d vertices. Note that each column of 2 3 the intersection array sums up to 3(n−3), the degree of the graph, as expected. Using this intersection array and the number of each type of vertex, we get the adjacency matrix in the {|d (cid:105),|d (cid:105),|d (cid:105),|d (cid:105)} basis: 0 1 2 3  (cid:112)  0 3(n−3) 0 0 (cid:112) (cid:112)  3(n−3) n−2 2 2(n−4) 0  A =  0 2(cid:112)2(n−4) 2(n−4) 3√n−5.  √  0 0 3 n−5 3(n−6) √ For example, the last entry of the third row is 3 n−5 because a d vertex is adjacent 2 (cid:112) to n−5 type d vertices, but we multiply it by |d |/|d | to adjust the normalization 3 3 2 Quantum Walk Search on Johnson Graphs 7 1 1 0.8 0.8 2 2 2 2 |〈s|ψ 〉| |〈s|ψ 〉| |〈d |ψ 〉| |〈d |ψ 〉| 1 0 0 0 0 1 bility 0.6 bility 0.6 a a b b Pro 0.4 Pro 0.4 0.2 0.2 0 0 0.003 0.0032 0.0034 0.0036 0.0038 0.004 0.003 0.0032 0.0034 0.0036 0.0038 0.004 γ γ (a) (b) Figure 4. Probability overlaps of (a) the initial equal superposition state |s(cid:105) and (b) the marked vertex |d (cid:105) with the eigenvectors |ψ (cid:105) of the search Hamiltonian H on 0 i J(100,3). factor between the basis states |d (cid:105) and |d (cid:105). That is, if we denote the elements of A as 2 3 A with i,j = 0,1,2,3, then ij (cid:115) |d | j A = (number of d vertices adjacent to a d vertex) . ij j i |d | i To get the search Hamiltonian (3), we simply multiply the adjacency matrix by −γ and include the oracle −|w(cid:105)(cid:104)w| = −|d (cid:105)(cid:104)d |: 0 0  (cid:112)  1 3(n−3) 0 0 γ (cid:112) (cid:112)  3(n−3) n−2 2 2(n−4) 0  H = −γ √ . (6)  (cid:112)  0 2 2(n−4) 2(n−4) 3 n−5  √  0 0 3 n−5 3(n−6) 2.2. Numerical Simulations To get a sense for how the algorithm depends on the jumping rate γ, we plot in figure 4a the probability overlaps of the initial state |s(cid:105) with the eigenvectors of H for various values of γ [8]. From this figure, we see that if γ is small (towards the left side of the plot), then |s(cid:105) is approximately equal to the first excited state |ψ (cid:105) of H. Then we 1 roughly start in an eigenstate of H, so the system only evolves by acquiring a global, unobservable phase (4). Similarly, if γ is large (towards the right side of the plot), then |s(cid:105) is approximately equal to the ground state |ψ (cid:105) of H. So again, the system roughly 0 remains in a uniform distribution over the vertices. When γ takes its critical value γ , however, where the support of |s(cid:105) experiences a c phase transition [8] and is equally supported by both |ψ (cid:105) and |ψ (cid:105), then the evolution is 0 1 nontrivial. In figure 4a, we identify that γ ≈ 0.003455. At this critical value, figure 4a c and figure 4b together indicate that the ground state and first excited state are each Quantum Walk Search on Johnson Graphs 8 1 0.8 y bilit a 0.6 b o Pr ss 0.4 e c c u S 0.2 0 0 500 1000 1500 2000 2500 Time Figure 5. For search on J(100,3), the success probability as a function of time with γ =0.003455. half in |s(cid:105) and half in |d (cid:105). That is, |ψ (cid:105) ∝ |s(cid:105)±|d (cid:105). This implies [8] that the system 0 0,1 0 evolves from |s(cid:105) to the marked vertex |d (cid:105) in time π/∆E, where ∆E is the energy gap 0 between the ground and first excited states. To demonstrate that this evolution occurs, we numerically simulate the evolution of the system |ψ(t)(cid:105) according to (4) with γ = 0.003455 and plot in figure 5 the success probability |(cid:104)d |ψ(t)(cid:105)|2 as the system evolves with time. We see that the system evolves 0 √ √ to the marked vertex |d (cid:105) with probability 1 at time roughly π N/2 = π 161700/2 ≈ 0 631.65, where we used N = n(n−1)(n−2)/6, with n = 100, for the number of vertices (2). This implies that the energy gap is √ 2 2 6 ∆E = √ ≈ , N n3/2 since N ≈ n3/6 for large N. Furthermore, using this energy gap, we can find how precisely the critical jumping rate must be determined. Say we are (cid:15) away from the true critical value, i.e., γ = γ +(cid:15). Then from the argument in Section VI of [19], a calculation using degenerate c perturbation theory [14] would contain a leading-order term in (cid:15) that scales as Θ(n(cid:15)). For this term to be negligible, it must scale smaller than the energy gap: n(cid:15) = o(∆E). Solving for (cid:15), (cid:18) (cid:19) 1 (cid:15) = o . n5/2 Thus we must determine γ up to o(1/n5/2). c With this sense for how the algorithm evolves, let us analytically find the critical jumping rate γ and prove that, at this value of γ, the algorithm finds the c √ √ marked vertex |d (cid:105) with probability 1 at time π N/2 = O( N), thus achieving 0 the full Grover speedup. We do this by finding the eigensystem of the search Hamiltonian (6). Unfortunately, analytically finding this eigensystem is messy, so as in [14, 16, 21, 17, 18, 19, 10], we attempt to approximate it using degenerate perturbation Quantum Walk Search on Johnson Graphs 9 theory. As we will see, in this case, a change of basis is required for the calculation to succeed. 2.3. Failure of Perturbation Theory The idea of perturbation theory is to first find the eigensystem of a simpler matrix, then see how higher-order corrections (i.e., the perturbation) change the eigensystem. To do this, we break the search Hamiltonian (6) into leading and higher-order terms: H = H(0) +H(1) +H(2) +..., where   1 0 0 0 γ 0 n 0 0  H(0) = −γ ,   0 0 2n 0   0 0 0 3n √   0 3n 0 0 √ √  3n 0 2 2n 0  H(1) = −γ √ √ ,  0 2 2n 0 3 n  √  0 0 3 n 0 and so forth. It is now easy to find the eigensystem of the leading-order Hamiltonian H(0); its eigenvectors are |d (cid:105), |d (cid:105), |d (cid:105), and |d (cid:105) with respective eigenvalues −1, 0 1 2 3 −γn, −2γn, and −3γn. If these eigenvalues are not degenerate, perturbation theory [14] implies that adding higher-order corrections will not significantly change the eigenvectors. Then |d (cid:105) remains an approximate eigenvector of the system. Since the 3 initial state |s(cid:105) ≈ |d (cid:105) for large N (5), this implies that the system roughly starts in an 3 eigenvector of H, so it fails to evolve apart from a global, unobservable phase (4). Whentheleading-ordereigenvectorsaredegenerate,however,thentheperturbation can cause a dramatic change [14]. Say γ = 1/3n so that |d (cid:105) and |d (cid:105) are degenerate 0 3 eigenvectors of H(0), with both of them having eigenvalue −1. Then the perturbation causes two linear combinations of |d (cid:105) and |d (cid:105) to be eigenvectors of the perturbed 0 3 system. This choice of γ = 1/3n yields an estimate for the critical γ. Often, such a calculation is precise enough [16, 17, 18, 19, 10], but in this case, it is not. If n = 100, then this estimate for γ yields 1/300 ≈ 0.0033, which from figure 4a is not close enough c to the actual value of 0.003455. In the last section, we showed that γ must be known c up to terms o(1/n5/2); while we have the leading-order term 1/3n, we need a correction that scales as Θ(1/n2). That is, the next correction beyond that would scale as Θ(1/n3), which we can ignore. The perturbative calculation is also not accurate enough for another reason, which we illustrate by expressing the calculation diagrammatically [21]. Figure 6a expresses the full search Hamiltonian H, and figure 6b expresses its leading-order terms H(0). When γ = 1/3n, |d (cid:105) and |d (cid:105) are degenerate in figure 6b since they have self-loops 0 3 of the same weight. With the perturbation H(1), we get figure 6c, which restores the Quantum Walk Search on Johnson Graphs 10 1 γ n−2 2(n−4) 3(n−6) (cid:112) (cid:112) √ 3(n−3) 2 2(n−4) 3 n−5 d d d d 0 1 2 3 (a) 1 γ n 2n 3n d d d d 0 1 2 3 (b) 1 γ n 2n 3n √ √ √ 3n 2 2n 3 n d d d d 0 1 2 3 (c) Figure6. Apartfromafactorof−γ,(a)theHamiltonianforsearchonthetetrahedral graph J(n,3). (b) The terms scaling as n. (c) The terms up scaling greater than or √ equal to n. missing edges. But since there is no edge connecting |d (cid:105) and |d (cid:105), these states do not 0 3 mix; the perturbed eigenstates roughly remain |d (cid:105) and |d (cid:105), not a combination of the 0 3 two, and so probability does not flow between the vertices. One might try to improve the precision of the perturbative calculation by letting H(0) contain higher-order terms, like for the “simplex of complete graphs” in [16, 17, 19]. √ In our case, however, including both terms that scale as Θ(n) and Θ( n) in H(0) yields a matrix, equivalent to figure 6c, whose eigensystem is still too messy to determine. 2.4. Change of Basis and Success of Perturbation Theory We can circumvent this failure of degenerate perturbation theory by changing the basis. Rather than using superpositions of identically evolving vertices {|d (cid:105),|d (cid:105),|d (cid:105),|d (cid:105)} as 0 1 2 3 basis states, we use |d (cid:105) 0 1 (cid:88) |r(cid:105) = √ |v(cid:105) N −1 v(cid:54)=w (cid:114) (cid:32) (cid:114) (cid:114) (cid:33) 18 n−4 (n−4)(n−5) = |d (cid:105)+ |d (cid:105)+ |d (cid:105) n2 +2 1 2 2 18 3 (cid:114) (cid:32) (cid:114) (cid:33) 9 n−5 |r(cid:48)(cid:105) = − |d (cid:105)+|d (cid:105) 2 3 n+4 9 √ √ √ (cid:18) (cid:19) 9 2 (n+4) n−4 n−5 |r(cid:48)(cid:48)(cid:105) = √ |d (cid:105)−|d (cid:105)− |d (cid:105) . (cid:112) 1 2 3 (n2 +2)(n+4) 9 2 3