Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Optimal quantum search on truncated simplex lattices

Yunkai Wang, Shengjun Wu, Wei Wang

Published Jun 24, 2020• 13 citations
Publisher

Abstract

First-order truncated simplex lattices have been used as interesting data structures to explore the properties of quantum search such as the effect of connectivity on search speed [D. A. Meyer and T. G. Wong, Phys. Rev. Lett. 114, 110503 (2015)]. In this paper, we further discuss quantum search algorithms for truncated simplex lattices. We first propose a multistage quantum algorithm for an $r\mathrm{th}$-order truncated simplex lattice with $N$ vertices based on the numerical calculation up to the fifth-order lattice, which requires an $(r+1)$-stage search process and consumes a run time $\mathrm{\ensuremath{\Theta}}({N}^{(2r+1)/(2r+2)})$ in general. Furthermore, with edge weights suitably adjusted (which increases the connectivity according to certain definitions), we merge the multistage search process into a single stage and achieve a fast quantum search algorithm with an optimal run time $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$ for first-order truncated simplex lattices, which we conjecture is generally true for any-order lattice. Under small noise of the lattice structure, both our multistage and our single-stage search algorithms are quite robust.

DOI
10.1103/physreva.101.062333

Related papers

Spatial search by continuous-time quantum walk on truncated simplex lattices

Xuanmin Zhu, Yuanchun Deng, Dezheng Zhang +3 more

Abstract Quantum search via continuous-time quantum walk on truncated simplex lattices is an important example of the quantum search on the structured database. In this letter, when the search target is a set of the marked vertices, the run time of the quantum search and the critical jumping rates are derived. Quantum search with the partial information of the location of the marked vertex is also discussed. Furthermore, with the edge weights suitably adjusted, the three-stage search process can be optimized into a two-stage quantum search algorithm on the second-order truncated simplex lattice.

Laser Physics Letters•Feb 2, 2023•1 citation

Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs

Kiyoji Huang Fujiwara, Yujia Shi, Thomas G. Wong

The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of $M+1$ identical complete graphs, each with $M$ vertices, such that each clique contains an edge or bridge to every other clique. It contains $N = M(M+1)$ vertices, and previous asymptotic results using a continuous-time quantum walk to search this graph for a single marked vertex have either numerically demonstrated an optimal runtime of $O(\sqrt{N})$, or analytically proved a deterministic success probability of 1, but not both, even when the bridges are weighted. In this paper, we give the first analytical proof of optimal quantum search on this graph, proving that it occurs when the weight of the bridges equals $M$. In addition, we numerically show that the optimal runtime is achieved more broadly whenever the weight is at least $\sqrt{M}$. Furthermore, the algorithm is also deterministic when the weight scales between $\sqrt{M}$ and $M$, and this is the first example of quantum search on the simplex of complete graphs that is both asymptotically optimal and deterministic. In addition, for weights where the algorithm is nondeterministic, we give a way to find the marked vertex by inspecting neighboring vertices. Finally, while it is known that connectivity is not a reliable indicator of fast quantum search when comparing different graph families, we show that it is also unreliable within the graph family of weighted simplex of complete graphs.

quant-pharXiv:2608.03777•Aug 5, 2026•0 citations

Depth optimization of quantum search algorithms beyond Grover's algorithm

Kun Zhang, V. E. Korepin

Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.

arXiv:1908.04171•Physical Review A•Mar 26, 2020•55 citations

Optimality of spatial search via continuous-time quantum walks

Shantanav Chakraborty, Leonardo Novo, Jérémie Roland

One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of $n$ nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in $O(\sqrt{n})$ time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.

arXiv:2004.12686•Physical Review A•Sep 14, 2020•37 citations

Spatial Search by Nonlinear Quantum Walk

David A. Meyer, Thomas G. Wong

Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size $Θ(N)$, for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.

quant-pharXiv:2606.01403•Jun 2, 2026•0 citations

Quantum search of many vertices on the joined complete graph

Tingting Ji, Naiqiao Pan, Tian Chen +1 more

The quantum search on the graph is a very important topic. In this work, we develop a theoretic method on searching of single vertex on the graph [Phys. Rev. Lett. 114 110503 (2015)], and systematically study the search of many vertices on one low-connectivity graph, the joined complete graph. Our results reveal that, with the optimal jumping rate obtained from the theoretical method, we can find such target vertices at the time O ( N ) , where N is the number of total vertices. Therefore, the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.

Chinese Physics B•Feb 7, 2022•3 citations
First-order truncated simplex lattices have been used as interesting data structures to explore the properties of quantum search such as the effect of connectivity on search speed [D. A. Meyer and T. G. Wong, Phys. Rev. Lett. 114, 110503 (2015)]. In this paper, we further discuss quantum search algorithms for truncated simplex lattices. We first propose a multistage quantum algorithm for an rthr\mathrm{th}rth-order truncated simplex lattice with NNN vertices based on the numerical calculation up to the fifth-order lattice, which requires an (r+1)(r+1)(r+1)-stage search process and consumes a run time \ensuremathΘ(N(2r+1)/(2r+2))\mathrm{\ensuremath{\Theta}}({N}^{(2r+1)/(2r+2)})\ensuremathΘ(N(2r+1)/(2r+2)) in general. Furthermore, with edge weights suitably adjusted (which increases the connectivity according to certain definitions), we merge the multistage search process into a single stage and achieve a fast quantum search algorithm with an optimal run time \ensuremathΘ(N)\mathrm{\ensuremath{\Theta}}(\sqrt{N})\ensuremathΘ(N​) for first-order truncated simplex lattices, which we conjecture is generally true for any-order lattice. Under small noise of the lattice structure, both our multistage and our single-stage search algorithms are quite robust.
Abstract Quantum search via continuous-time quantum walk on truncated simplex lattices is an important example of the quantum search on the structured database. In this letter, when the search target is a set of the marked vertices, the run time of the quantum search and the critical jumping rates are derived. Quantum search with the partial information of the location of the marked vertex is also discussed. Furthermore, with the edge weights suitably adjusted, the three-stage search process can be optimized into a two-stage quantum search algorithm on the second-order truncated simplex lattice.
The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of M+1M+1M+1 identical complete graphs, each with MMM vertices, such that each clique contains an edge or bridge to every other clique. It contains N=M(M+1)N = M(M+1)N=M(M+1) vertices, and previous asymptotic results using a continuous-time quantum walk to search this graph for a single marked vertex have either numerically demonstrated an optimal runtime of O(N)O(\sqrt{N})O(N​), or analytically proved a deterministic success probability of 1, but not both, even when the bridges are weighted. In this paper, we give the first analytical proof of optimal quantum search on this graph, proving that it occurs when the weight of the bridges equals MMM. In addition, we numerically show that the optimal runtime is achieved more broadly whenever the weight is at least M\sqrt{M}M​. Furthermore, the algorithm is also deterministic when the weight scales between M\sqrt{M}M​ and MMM, and this is the first example of quantum search on the simplex of complete graphs that is both asymptotically optimal and deterministic. In addition, for weights where the algorithm is nondeterministic, we give a way to find the marked vertex by inspecting neighboring vertices. Finally, while it is known that connectivity is not a reliable indicator of fast quantum search when comparing different graph families, we show that it is also unreliable within the graph family of weighted simplex of complete graphs.
Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.
One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)], finds a marked node on a graph of nnn nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n)O(\sqrt{n})O(n​) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than ${n}^{\ensuremath{-}1/2}$. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results.
Many-body quantum systems with effective nonlinearities have been shown to speed up quantum search on the complete graph, \textit{i.e.}, the combinatorial version of Grover's algorithm, at the expense of the number of particles needed for the effective nonlinearity to hold. Physically, however, data may not be arranged in an all-to-all network, and the task of searching incomplete graphs is the spatial search problem. We explore spatial search using a continuous-time nonlinear quantum walk on a variety of graphs. First, we consider incomplete graphs that are ``sufficiently complete'' so as to asymptotically search like the complete graph under a continuous-time (linear) quantum walk, which includes strongly regular graphs such as Paley graphs, regular graphs such as hypercubes, and irregular graphs such as complete bipartite graphs. For these sufficiently complete graphs, we analytically prove nonlinear speedups for Paley graphs and for complete bipartite graphs whose two partite sets both have size Θ(N)Θ(N)Θ(N), for suitable cubic and cubic-quintic nonlinearities, and we give numerical evidence for stronger nonlinearities and for hypercubes. Second, we explore arbitrary-dimensional cubic lattices, and we numerically show that certain nonlinearities speed up search on sufficiently high dimensional lattices. Thus, nonlinear quantum search can remain viable even when the underlying graph is incomplete.
The quantum search on the graph is a very important topic. In this work, we develop a theoretic method on searching of single vertex on the graph [Phys. Rev. Lett. 114 110503 (2015)], and systematically study the search of many vertices on one low-connectivity graph, the joined complete graph. Our results reveal that, with the optimal jumping rate obtained from the theoretical method, we can find such target vertices at the time O ( N ) , where N is the number of total vertices. Therefore, the search of many vertices on the joined complete graph possessing quantum advantage has been achieved.