Abstract
In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the “simplex of \(K_M\) complete graphs” with all configurations of two marked vertices, two configurations of \(M+1\) marked vertices, and two configurations of \(2(M+1)\) marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration’s value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Schrödinger, E.: An undulatory theory of the mechanics of atoms and molecules. Phys. Rev. 28, 1049–1070 (1926)
Sakurai, J.J.: Modern Quantum Mechanics, Revised edn. Addison Wesley, Boston (1993)
Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915–928 (1998)
Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)
Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. Theory Comput. 4(8), 169–190 (2008)
Rudinger, K., Gamble, J.K., Wellons, M., Bach, E., Friesen, M., Joynt, R., Coppersmith, S.N.: Noninteracting multiparticle quantum random walks applied to the graph isomorphism problem for strongly regular graphs. Phys. Rev. A 86, 022334 (2012)
Childs, A.M.: Universal computation by quantum walk. Phys. Rev. Lett. 102, 180501 (2009)
Mochon, C.: Hamiltonian oracles. Phys. Rev. A 75, 042313 (2007)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. STOC ’96, pp. 212–219. ACM, New York (1996)
Farhi, E., Gutmann, S.: Analog analogue of a digital quantum computation. Phys. Rev. A 57(4), 2403–2406 (1998)
Wong, T.G.: Nonlinear quantum search. PhD dissertation (2014)
Wong, T.G.: Grover search with lackadaisical quantum walks. J. Phys. A: Math. Theor. 48, 435304 (2015). doi:10.1088/1751-8113/48/43/435304
Wong, T.G.: Quantum walk search through potential barriers. arXiv:1503.06605 [quant-ph] (2015)
Janmark, J., Meyer, D.A., Wong, T.G.: Global symmetry is unnecessary for fast quantum search. Phys. Rev. Lett. 112, 210502 (2014)
Meyer, D.A., Wong, T.G.: Connectivity is a poor indicator of fast quantum search. Phys. Rev. Lett. 114, 110503 (2015)
Novo, L., Chakraborty, S., Mohseni, M., Neven, H., Omar, Y.: Systematic dimensionality reduction for quantum walks: optimal spatial search and transport on non-regular graphs. Sci. Rep. 5, 13304 (2015)
Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A 92, 022338 (2015)
Kempe, J.: Quantum random walks: an introductory overview. Contemp. Phys. 44(4), 307–327 (2003)
Meyer, D.A.: From quantum cellular automata to quantum lattice gases. J. Stat. Phys. 85(5–6), 551–574 (1996)
Meyer, D.A.: On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A 223(5), 337–340 (1996)
Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pp. 1099–1108 (2005)
Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Phys. Rev. A 67, 052307 (2003)
Nahimovs, N., Rivosh, A.: Quantum walks on two-dimensional grids with multiple marked locations. In: Proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM ’16. Harrachov (2016). To appear arXiv:1507.03788
Ambainis, A., Rivosh, A.: Quantum walks with multiple or moving marked locations. In: V. Geffert, J. Karhumöki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková (eds.) Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2008, pp. 485–496 (2008)
Nahimovs, N., Rivosh, A.: Exceptional congurations of quantum walks with Grover’s coin. In: Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS ’15. Telc̆ (2015). To appear arXiv:1509.06862
Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’04, pp. 32–41 (2004)
Krovi, H., Magniez, F., Ozols, M., Roland, J.: Quantum walks can find a marked element on any graph. Algorithmica (2015). doi:10.1007/s00453-015-9979-8
Wong, T.G.: Faster quantum walk search on a weighted graph. Phys. Rev. A 92, 032320 (2015)
Wong, T.G.: Diagrammatic approach to quantum search. Quantum Inf. Process. 14(6), 1767–1775 (2015)
Acknowledgments
Thanks to Andris Ambainis for useful discussions. This work was supported by the European Union Seventh Framework Programme (FP7/2007–2013) under the QALGO (Grant Agreement No. 600700) project, and the ERC Advanced Grant MQC.
Author information
Authors and Affiliations
Corresponding author
Appendices
Appendix 1: Details for two marked vertices
In this appendix, we employ degenerate perturbation theory [2, 14, 29] to find the critical \(\gamma \)’s and runtimes for search with two marked vertices, of which there are five cases, as summarized in Table 1.
1.1 Two marked, case 1, generalized to constant marked vertices
Instead of having just 2 marked vertices in a single complete graph, we generalize the problem to k constant marked vertices. Even with this generalization, the system still evolves in an eight-dimensional subspace, as shown in Fig. 4a, spanned by
In this subspace, the search Hamiltonian (1) is
where \(M_k = M-k\) and \(M_{k1} = M - k - 1\).
Using the diagrammatic approach in [29] as a guide, this Hamiltonian can be visualized as a graph with eight vertices, as shown in Fig. 8a. For the first stage of the algorithm, the leading-order Hamiltonian \(H^{(0)}\) can be visualized as shown in Fig. 8b, where we have excluded edges that scale less than \(\sqrt{M}\). From this, the eight eigenvectors of \(H^{(0)}\) are easily seen: two are linear combinations of \({\left| a \right\rangle }\) and \({\left| b \right\rangle }\), three are linear combinations of \({\left| c \right\rangle }\), \({\left| d \right\rangle }\), and \({\left| h \right\rangle }\), and the final three are linear combinations of \({\left| e \right\rangle }\), \({\left| f \right\rangle }\), and \({\left| g \right\rangle }\). They correspond to the eigenvectors of
Since \({\left| s \right\rangle } \approx {\left| g \right\rangle }\), and we want probability to move toward the marked vertices \({\left| a \right\rangle }\), we want to choose \(\gamma \) so that a linear combination of \({\left| e \right\rangle }, {\left| f \right\rangle }\), and \({\left| g \right\rangle }\) is degenerate with a linear combination of \({\left| a \right\rangle }\) and \({\left| b \right\rangle }\). In particular, the eigenstates that we want to be degenerate are
with corresponding eigenvalue
and
with corresponding eigenvalue
Written this way, u and v are unnormalized, whereas \({\left| u \right\rangle }\) and \({\left| v \right\rangle }\) are their normalized versions. These eigenstates are degenerate when \(\gamma \) takes its critical value of
The perturbation \(H^{(1)}\), which restores terms of constant weight, causes certain linear combinations
of these states to be eigenstates of \(H^{(0)} + H^{(1)}\) [2, 14]. The coefficients \(\alpha _u\) and \(\alpha _v\) can be found by solving
where \(H_{uv} = \langle u | H^{(0)} + H^{(1)} | v \rangle \), etc. Solving this, the perturbed eigenvectors for large N with their corresponding eigenvalues are
Since \({\left| u \right\rangle } \approx {\left| g \right\rangle }\) and \({\left| v \right\rangle } \approx {\left| b \right\rangle }\) for large N, the system evolves from \({\left| s \right\rangle } \approx {\left| g \right\rangle }\) to \({\left| b \right\rangle }\) in time \(\pi /\Delta E\), which is
Diagrammatically, the perturbation \(H^{(1)}\) restores edges of constant weight in Fig. 8b, and probability flows between \({\left| g \right\rangle }\) and \({\left| b \right\rangle }\) since they are the most dominant terms.
Using the approach of Sect. VI of [28], if \(\gamma \) is within \(\epsilon \) of its critical value of \(\gamma _{c1} \approx (1+k)/M\), then the eigenvalues of \({\left| u \right\rangle }\) and \({\left| v \right\rangle }\) now include leading-order (in \(\epsilon \)) terms \(-\epsilon M\). In the perturbative calculation, this introduces terms scaling as \(\epsilon M\) due to \(H_{uu}\) and \(H_{vv}\), so for this to not influence the energy gap \(\varTheta (1/M^{3/2})\), we must have \(\epsilon M = o(1/M^{3/2})\), or \(\epsilon = o(1/M^{5/2})\). Thus for the first stage of the algorithm to asymptotically evolve from \({\left| s \right\rangle }\) to \({\left| b \right\rangle }\), we require \(\gamma = \gamma _{c1} + o(1/M^{5/2})\). Note if we relax this to evolve to \({\left| b \right\rangle }\) with constant probability, then \(\gamma = \gamma _{c1} + O(1/M^{5/2})\) suffices.
For the second stage of the algorithm, we take the leading-order Hamiltonian \(H^{(0)}\) to only include edges of weight \(\varTheta (M)\), and its diagram is shown in Fig. 8c. From this, the eight eigenvectors of \(H^{(0)}\) are simply the basis vectors \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), ..., \({\left| h \right\rangle }\) with corresponding eigenvalues \(-1\), \(-\gamma M\), ..., 0. When \(\gamma \) takes its critical value of
the eigenstates \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), \({\left| d \right\rangle }\), and \({\left| g \right\rangle }\) of \(H^{(0)}\) are degenerate with eigenvalue \(-1\). Then the perturbation \(H^{(1)}\), which restores terms \(\varTheta (\sqrt{M})\), causes certain linear combinations
of these states to be eigenstates of \(H^{(0)} + H^{(1)}\). The coefficients \(\alpha _a\), \(\alpha _b\), \(\alpha _d\), and \(\alpha _g\) can be found by solving
where \(H_{ab} = \langle a | H^{(0)} + H^{(1)} | b \rangle \), etc. Solving this, the perturbed eigenvectors with their corresponding eigenvalues are
So the system evolves from \({\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi / \Delta E\):
Diagrammatically, the perturbation \(H^{(1)}\) restores edges \(\varTheta (\sqrt{M})\) in Fig. 9c, and probability flows between \({\left| b \right\rangle }\) and \({\left| a \right\rangle }\).
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c2} = 1/M\)—a straightforward calculation shows that it must be within \(o(1/M^{3/2})\).
For \(k = 2\) marked vertices, the critical \(\gamma \)’s and runtimes are
all of which are in agreement with Table 1.
1.2 Two marked, case 2
As shown in Fig. 4b, the system evolves in a four-dimensional subspace spanned by
where the labels have been chosen this way to match the behavior of the vertices in the first case in Fig. 4a. In this subspace, the search Hamiltonian (1) is
This Hamiltonian can be visualized as shown in Fig. 9a. For the first stage of the algorithm, the leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than \(\sqrt{M}\), and it can be visualized as shown in Fig. 9b. The two eigenstates of \(H^{(0)}\) that we want to be degenerate are
with corresponding eigenvalue
and
with corresponding eigenvalue
These are degenerate when \(\gamma \) takes its critical value of
The perturbation \(H^{(1)}\), which restores terms of constant weight, causes certain linear combinations \(\alpha _u {\left| u \right\rangle } + \alpha _v {\left| v \right\rangle }\) to be eigenstates of \(H^{(0)} + H^{(1)}\). Doing the perturbative calculation to find the coefficients (as in the first case), the perturbed eigenstates for large N are
Since \({\left| u \right\rangle } \approx {\left| g \right\rangle }\) and \({\left| v \right\rangle } \approx {\left| b \right\rangle }\) for large N, the system evolves from \({\left| s \right\rangle } \approx {\left| g \right\rangle }\) to \({\left| b \right\rangle }\) in time \(\pi / \Delta E\):
Diagrammatically, the perturbation \(H^{(1)}\) restores edges of constant weight in Fig. 9b, and probability flows between \({\left| g \right\rangle }\) and \({\left| b \right\rangle }\) since they are the most dominant terms.
As in the first case in the precious section, we can use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c1} = 2/M\)—a straightforward calculation shows that it must be within \(o(1/M^{5/2})\).
For the second stage of the algorithm, we take the leading-order Hamiltonian \(H^{(0)}\) to only include edges of weight \(\varTheta (M)\), and its diagram is shown in Fig. 9c. When \(\gamma \) takes its critical value of
the eigenstates \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), and \({\left| g \right\rangle }\) of \(H^{(0)}\) are triply degenerate. Then the perturbation \(H^{(1)}\), which restores terms \(\varTheta (\sqrt{M})\), causes certain linear combinations \(\alpha _a {\left| a \right\rangle } + \alpha _b {\left| b \right\rangle } + \alpha _g {\left| g \right\rangle }\) of them to be eigenstates of \(H^{(0)} + H^{(1)}\). Doing the perturbative calculation to find the coefficients (as in the first case), the perturbed eigenstates for large N are
So the system evolves from \({\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi / \Delta E\):
Diagrammatically, the perturbation \(H^{(1)}\) restores edges \(\varTheta (\sqrt{M})\) in Fig. 9c, and probability flows between \({\left| b \right\rangle }\) and \({\left| a \right\rangle }\).
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c2} = 1/M\)—a straightforward calculation shows that it must be within \(o(1/M^{3/2})\).
These \(\gamma _c\)’s and runtimes are in agreement with Table 1.
1.3 Two marked, case 3
As shown in Fig. 4c, the system evolves in an eight-dimensional subspace spanned by
Note there are no h type vertices. Instead, there’s a new type, which we call i. In this subspace, the search Hamiltonian (1) is
where \(M_2 = M-2\) and \(M_3 = M-3\).
This Hamiltonian can be visualized as shown in Fig. 10a. For the first stage of the algorithm, the leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than \(\sqrt{M}\), and it can be visualized as shown in Fig. 10b. As with the last two cases, there are two eigenvectors that we want to be degenerate. The first is
with corresponding eigenvalue
The second eigenvector is messy, but can be approximated nicely. The leading-order Hamiltonian corresponding to \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), and \({\left| i \right\rangle }\) is
The eigenvalues \(\lambda \) of this satisfy the characteristic equation
When \(\gamma \) takes its critical value of
one of these eigenvalues, which we will call \(E_v\), and \(E_u\) both equal \(-2 - 270/M^3 + O(1/M^4)\), making them approximately degenerate. To find the corresponding eigenvector v, we use the first and third lines of the eigenvalue equation \(H_{a,b,i}^{(0)} v = E_v v\):
This yields
The perturbation \(H^{(1)}\), which restores terms of constant weight, causes certain linear combinations \(\alpha _u {\left| u \right\rangle } + \alpha _v {\left| v \right\rangle }\) to be eigenstates of \(H^{(0)} + H^{(1)}\). Doing the perturbative calculation to find the coefficients, the perturbed eigenstates for large N are
Since \({\left| u \right\rangle } \approx {\left| g \right\rangle }\) and \({\left| v \right\rangle } \approx {\left| b \right\rangle }\) for large N, the system evolves from \({\left| s \right\rangle } \approx {\left| g \right\rangle }\) to \({\left| b \right\rangle }\) in time \(\pi / \Delta E\):
Diagrammatically, the perturbation \(H^{(1)}\) restores edges of constant weight in Fig. 10b, and probability flows between \({\left| g \right\rangle }\) and \({\left| b \right\rangle }\) since they are the most dominant terms.
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c1} = 2/M\)—a straightforward calculation shows that it must be within \(o(1/M^{5/2})\).
The second stage of the algorithm is similar to the previous two cases, where we take the leading-order Hamiltonian \(H^{(0)}\) to only include edges of weight \(\varTheta (M)\). When \(\gamma \) takes its critical value of
then \({\left| a \right\rangle }\) and \({\left| b \right\rangle }\) are degenerate eigenvectors (among others) of \(H^{(0)}\). The perturbation \(H^{(1)}\) restores terms of order \(\varTheta (\sqrt{M})\), which causes probability to flow between \({\left| b \right\rangle }\) and \({\left| a \right\rangle }\). Doing the calculation, we find eigenstates of the perturbed system that are proportional to \({\left| b \right\rangle } \pm {\left| a \right\rangle }\) with eigenvalues \(-1 \mp 1 / \sqrt{M}\), so the system evolves from \({\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi / \Delta E\):
As before, a straightforward calculation using the method of [28] shows that \(\gamma \) must be chosen within \(o(1/M^{3/2})\) of its critical value \(\gamma _{c2} = 1/M\).
These \(\gamma _c\)’s and runtimes are in agreement with Table 1.
1.4 Two marked, case 4
As shown in Fig. 4d, the system evolves in an eleven-dimensional subspace spanned by
In this subspace, the search Hamiltonian (1) is
where \(M_3 = M-3\) and \(M_4 = M-4\).
This Hamiltonian can be visualized as shown in Fig. 11a. For the first stage of the algorithm, the leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than \(\sqrt{M}\), and it can be visualized as shown in Fig. 11b. As with the last two cases, there are two eigenvectors that we want to be degenerate. The first is
with corresponding eigenvalue
The second eigenvector is messy, but can be approximated nicely. The leading-order Hamiltonian corresponding to \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), \({\left| i \right\rangle }\), and \({\left| j \right\rangle }\) is
The eigenvalues \(\lambda \) of this satisfy the characteristic equation
When \(\gamma \) takes its critical value of
one of these eigenvalues, which we will call \(E_v\), and \(E_u\) both equal \(-2 - 640/M^3 - O(1/M^4)\), making them approximately degenerate. To find the corresponding eigenvector v, we use the eigenvalue equation \(H_{a,b,i,j}^{(0)} v = E_v v\):
This yields
The perturbation \(H^{(1)}\), which restores terms of constant weight, causes certain linear combinations \(\alpha _u {\left| u \right\rangle } + \alpha _v {\left| v \right\rangle }\) to be eigenstates of \(H^{(0)} + H^{(1)}\). Doing the perturbative calculation to find the coefficients, the perturbed eigenstates for large N are
Since \({\left| u \right\rangle } \approx {\left| g \right\rangle }\) and \({\left| v \right\rangle } \approx {\left| b \right\rangle }\) for large N, the system evolves from \({\left| s \right\rangle } \approx {\left| g \right\rangle }\) to \({\left| b \right\rangle }\) in time \(\pi / \Delta E\):
Diagrammatically, the perturbation \(H^{(1)}\) restores edges of constant weight in Fig. 11b, and probability flows between \({\left| g \right\rangle }\) and \({\left| b \right\rangle }\) since they are the most dominant terms.
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c1} = 2/M\)—a straightforward calculation shows that it must be within \(o(1/M^{5/2})\).
The second stage of the algorithm is similar to the previous three cases, where we take the leading-order Hamiltonian \(H^{(0)}\) to only include edges of weight \(\varTheta (M)\). When \(\gamma \) takes its critical value of
then \({\left| a \right\rangle }\) and \({\left| b \right\rangle }\) are degenerate eigenvectors (among others) of \(H^{(0)}\). The perturbation \(H^{(1)}\) restores terms of order \(\varTheta (\sqrt{M})\), which causes probability to flow between \({\left| b \right\rangle }\) and \({\left| a \right\rangle }\). Doing the calculation, we find eigenstates of the perturbed system that are proportional to \({\left| b \right\rangle } \pm {\left| a \right\rangle }\) with eigenvalues \(-1 \mp 1 / \sqrt{M}\), so the system evolves from \({\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi / \Delta E\):
As before, a straightforward calculation using the method of [28] shows that \(\gamma \) must be chosen within \(o(1/M^{3/2})\) of its critical value \(\gamma _{c2} = 1/M\).
These \(\gamma _c\)’s and runtimes are in agreement with Table 1.
1.5 Two marked, case 5
As shown in Fig. 4e, the system evolves in a thirteen-dimensional subspace spanned by
In this subspace, the search Hamiltonian (1) is
where \(M_2 = M-2\) and \(M_3 = M-3\).
This Hamiltonian can be visualized as shown in Fig. 12a. For the first stage of the algorithm, the leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than \(\sqrt{M}\), and it can be visualized as shown in Fig. 12b. The initial equal superposition state \({\left| s \right\rangle }\) is approximately \({\left| m \right\rangle }\) for large N, and we want it to evolve to the marked vertices \({\left| a \right\rangle }\) and \({\left| d \right\rangle }\). So we will need leading-order eigenstates that are approximately each of these to be triply degenerate. The first is
with corresponding eigenvalue
Note this is the same eigenvalue as \(E_u\) from Case 3. For the other two leading-order eigenstates, Fig. 12b reveals that \(H_{a,b,i}^{(0)}\) and \(H_{c,d,h}^{(0)}\) are identical with \(a \sim d\), \(b \sim h\), and \(i \sim c\), so their corresponding eigenstates are always degenerate. Furthermore, they are identical to \(H_{a,b,i}^{(0)}\) from Fig. 10b from Case 3. So the eigenvectors and eigenvalues carry over:
including the critical \(\gamma \)
at which the eigenvalues \(E_u\), \(E_v\), and \(E_w\) all equal \(-2 - 270/M^3 + O(1/M^4)\), making them approximately degenerate.
With the perturbation \(H^{(1)}\), which restores terms of constant weight, we have the same behavior and runtime
as Case 3, except the system evolves from \({\left| s \right\rangle } \approx {\left| m \right\rangle }\) to \({\left| b \right\rangle } + {\left| h \right\rangle }\). So the probability gets split between the two paths. Diagrammatically, the perturbation \(H^{(1)}\) restores edges of constant weight in Fig. 12b, and probability flows from \({\left| m \right\rangle }\) to \({\left| b \right\rangle }\) and \({\left| h \right\rangle }\) since they are the most dominant terms.
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c2} = 1/M\)—a straightforward calculation shows that it must be within \(o(1/M^{5/2})\).
The second stage of the algorithm is similar to the previous cases, where we take the leading-order Hamiltonian \(H^{(0)}\) to only include edges of weight \(\varTheta (M)\). When \(\gamma \) takes its critical value of
then \({\left| a \right\rangle }\) and \({\left| b \right\rangle }\) are degenerate eigenvectors, as are \({\left| d \right\rangle }\) and \({\left| h \right\rangle }\), of \(H^{(0)}\). The perturbation \(H^{(1)}\) restores terms of order \(\varTheta (\sqrt{M})\), which causes probability to flow from \({\left| b \right\rangle }\) to \({\left| a \right\rangle }\) and from \({\left| h \right\rangle }\) to \({\left| d \right\rangle }\). The runtime from Case 3 carries over:
As before, a straightforward calculation using the method of [28] shows that \(\gamma \) must be chosen within \(o(1/M^{3/2})\) of its critical value \(\gamma _{c2} = 1/M\).
These \(\gamma _c\)’s and runtimes are in agreement with Table 1.
Appendix 2: Details for larger examples
In this appendix, we employ degenerate perturbation theory [2, 14, 29] to find the critical \(\gamma \)’s and runtimes for search with a larger number of marked vertices, the results of which are summarized in Table 2.
1.1 One marked per complete
As shown in Fig. 6a, the system evolves in a three-dimensional subspace spanned by
In this subspace, the search Hamiltonian (1) is
This Hamiltonian can be visualized as shown in Fig. 13a. The leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than M, and it can be visualized as shown in Fig. 13b. Clearly, the eigenstates of this are \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), and \({\left| c \right\rangle }\) with corresponding eigenvalues \(-1\), \(-\gamma M\), and 0. Since \({\left| s \right\rangle } \approx {\left| b \right\rangle }\), we choose \(\gamma \) so that \({\left| b \right\rangle }\) and \({\left| a \right\rangle }\) are degenerate, i.e.,
The perturbation \(H^{(1)}\), which restores edges of weight \(\varTheta (\sqrt{M})\), causes certain linear combinations \(\alpha _a {\left| a \right\rangle } + \alpha _b {\left| b \right\rangle }\) to be eigenstates of \(H^{(0)} + H^{(1)}\). The coefficients can be found by solving
where \(H_{ab} = \langle a | H^{(0)} + H^{(1)} | b \rangle \), etc. With \(\gamma = \gamma _c\), this yields eigenstates and eigenvalues
So the system evolves from \({\left| s \right\rangle } \approx {\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi /\Delta E\):
Using the method Sect. VI of [28], if \(\gamma \) is within \(\epsilon \) of its critical value of \(\gamma _c = 1/M\), then the eigenvalue of \({\left| b \right\rangle }\) is now \(-\gamma M = -1 - \epsilon M\). In the perturbative calculation, this introduces a leading-order (in \(\epsilon \)) term \(\epsilon M\) due to \(H_{bb}\). For this to not influence the energy gap \(\varTheta (1/\sqrt{M})\), we require \(\epsilon M = o(1/\sqrt{M})\), or \(\epsilon = o(1/M^{3/2})\). Thus for the algorithm to asymptotically evolve from \({\left| b \right\rangle }\) to \({\left| a \right\rangle }\), we require \(\gamma = \gamma _c + o(1/M^{3/2})\).
This \(\gamma _c\) and runtime are in agreement with Table 2.
1.2 Fully marked complete, plus one
As shown in Fig. 6b, the system evolves in a seven-dimensional subspace spanned by
In this subspace, the search Hamiltonian (1) is
This Hamiltonian can be visualized as shown in Fig. 14a. The leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than \(\sqrt{M}\), and it can be visualized as shown in Fig. 14b. The two eigenstates of \(H^{(0)}\) that we want to be degenerate are
with corresponding eigenvalue
and
with corresponding eigenvalue
These are degenerate when \(\gamma \) takes its critical value of
The perturbation \(H^{(1)}\), which restores terms of constant weight, causes certain linear combinations \(\alpha _u {\left| u \right\rangle } + \alpha _v {\left| v \right\rangle }\) to be eigenstates of \(H^{(0)} + H^{(1)}\). Doing the perturbative calculation to find the coefficients, the perturbed eigenstates for large N are
Since \({\left| u \right\rangle } \approx {\left| g \right\rangle }\) and \({\left| v \right\rangle }\approx {\left| b \right\rangle }\) for large N, the system evolves from \({\left| s \right\rangle } \approx {\left| g \right\rangle }\) to \({\left| b \right\rangle }\), which is marked, in time \(\pi / \Delta E\):
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c} = 1 + 3/M\)—a straightforward calculation shows that it must be within \(o(1/M^{3/2})\).
This \(\gamma _c\) and runtime are in agreement with Table 2.
1.3 Two marked per complete graph, case 1
As shown in Fig. 7a, the system evolves in a two-dimensional subspace spanned by
In this subspace, the search Hamiltonian (1) is
We can find the eigenvectors and eigenvalues of this directly without perturbation theory. They are
with corresponding eigenvalue
and
with corresponding eigenvalue
When \(\gamma \) takes its critical value of
these become for large N
So the system evolves from \({\left| s \right\rangle } \approx {\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi / \Delta E\):
An explicit calculation as in [13] shows that \(\gamma \) must be chosen within \(o(1/M^{3/2})\) of its critical value \(\gamma _c = 1/M\) for this evolution to occur asymptotically.
This \(\gamma _c\) and runtime are in agreement with Table 2.
1.4 Two marked per complete graph, case 2
As shown in Fig. 7b, the system evolves in a three-dimensional subspace spanned by
In this subspace, the search Hamiltonian (1) is
This Hamiltonian can be visualized as shown in Fig. 15a. The leading-order Hamiltonian \(H^{(0)}\) excludes edges that scale less than M, and it can be visualized as shown in Fig. 15b. Clearly, the eigenstates of this are \({\left| a \right\rangle }\), \({\left| b \right\rangle }\), and \({\left| c \right\rangle }\) with corresponding eigenvalues \(-1\), \(-\gamma M\), and 0. Since \({\left| s \right\rangle } \approx {\left| b \right\rangle }\), we choose \(\gamma \) so that \({\left| b \right\rangle }\) and \({\left| a \right\rangle }\) are degenerate, i.e.,
The perturbation \(H^{(1)}\), which restores edges of weight \(\varTheta (\sqrt{M})\), causes certain linear combinations \(\alpha _a {\left| a \right\rangle } + \alpha _b {\left| b \right\rangle }\) to be eigenstates of \(H^{(0)} + H^{(1)}\). The coefficients can be found in the usual way, and they yield perturbed eigenstates
So the system evolves from \({\left| s \right\rangle } \approx {\left| b \right\rangle }\) to \({\left| a \right\rangle }\) in time \(\pi / \Delta E\):
We can again use the method of [28] to find how precisely \(\gamma \) must be chosen to its critical value \(\gamma _{c} = 1/M\)—a straightforward calculation shows that it must be within \(o(1/M^{3/2})\).
This \(\gamma _c\) and runtime are in agreement with Table 2.
Rights and permissions
About this article
Cite this article
Wong, T.G. Spatial search by continuous-time quantum walk with multiple marked vertices. Quantum Inf Process 15, 1411–1443 (2016). https://doi.org/10.1007/s11128-015-1239-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11128-015-1239-y