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

arXiv:2608.03777

Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs

Kiyoji Huang Fujiwara, Yujia Shi, Thomas G. Wong

quant-phSubmitted Aug 4, 2026• Announced Aug 5, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
37 pages, 22 figures

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 quantum search on truncated simplex lattices

Yunkai Wang, Shengjun Wu, Wei Wang

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.

Physical Review A•Jun 24, 2020•13 citations

Faster quantum walk search on a weighted graph

Thomas G. Wong

A randomly walking quantum particle evolving by Schr\"odinger's equation searches for a unique marked vertex on the ``simplex of complete graphs'' in time $\mathrm{\ensuremath{\Theta}}({N}^{3/4})$. We give a weighted version of this graph that preserves vertex transitivity, and we show that the time to search on it can be reduced to nearly $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$. To prove this, we introduce two extensions to degenerate perturbation theory: an adjustment that distinguishes the weights of the edges and a method to determine how precisely the jumping rate of the quantum walk must be chosen.

arXiv:1507.07590•Physical Review A•Sep 21, 2015•22 citations

Deterministic discrete-time quantum walk search on complete bipartite graphs

Fangjie Peng, Meng Li, Xiaoming Sun

Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024

Physical Review Research•Jul 9, 2024•5 citations

Fixed-point Quantum Walk Search.

Lvzhou Li, Yongzhen Xu, Zhang Delong

n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter $\epsilon$. More specifically, for an $N$-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps $h$ satisfies $h \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}$, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given $\epsilon\in (0,1]$. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.

•Nov 17, 2021•0 citations

Engineering the success of quantum walk search using weighted graphs

Thomas G. Wong, Pascal Philipp

Continuous-time quantum walks are natural tools for spatial search, where one searches for a marked vertex in a graph. Sometimes the structure of the graph causes the walker to get trapped, such that the probability of finding the marked vertex is limited. We give an example with two linked cliques, proving that the captive probability can be liberated by increasing the weights of the links. This allows the search to succeed with probability 1 without increasing the energy scaling of the algorithm. Further increasing the weights, however, slows the runtime, so the optimal search requires weights that are neither too weak nor too strong.

arXiv:1605.04862•Physical Review A•Aug 4, 2016•12 citations
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.
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.
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 $\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.
A randomly walking quantum particle evolving by Schr\"odinger's equation searches for a unique marked vertex on the ``simplex of complete graphs'' in time $\mathrm{\ensuremath{\Theta}}({N}^{3/4})$. We give a weighted version of this graph that preserves vertex transitivity, and we show that the time to search on it can be reduced to nearly $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$. To prove this, we introduce two extensions to degenerate perturbation theory: an adjustment that distinguishes the weights of the edges and a method to determine how precisely the jumping rate of the quantum walk must be chosen.
Searching via quantum walk is a topic that has been extensively studied. Most previous results provide approximate solutions, while in this paper we prove an algorithm that can find a marked vertex certainly. We adopt the coined discrete-time quantum walk (DTQW) model with adjusted operators and prove that, on complete bipartite graphs, when parameters are set properly, coined DTQW can deterministically find a marked vertex, i.e., the success probability is exactly 1. Before this paper there have been results of an alternating continuous-time quantum walk method that achieve deterministic spatial search, but this paper provides a deterministic quantum spatial search result via DTQW, while maintaining a quadratic speedup compared to classical algorithms. We also provide the quantum circuit implementation. Published by the American Physical Society 2024
n this paper, we consider the problem of searching a marked vertex in a graph based on quantum walks. A very large body of research exists on this issue, from both theoretical and experimental studies, yet the existing quantum walk-based search algorithms require knowing exactly how many marked vertices there are before starting the search process. In addition, even if the precise knowledge of the number of marked vertices is known, the success probability of these algorithms could shrink dramatically when the number of search steps is greater than the right one. For avoiding these defects, in this paper we present a new quantum walk-based search algorithm which need not know any prior information about the marked vertices, but still keeps a quadratic speedup over classical ones and ensures that the error is bounded by a tunable parameter ϵ\epsilonϵ. More specifically, for an NNN-vertex complete bipartite graph with marked vertices but without knowing the number of marked vertices, if the number of search steps hhh satisfies h≥ln⁡(2ϵ)Nh \geq \ln(\frac{2}{\sqrt{\epsilon}})\sqrt{N}h≥ln(ϵ​2​)N​, then the algorithm will output a marked vertex with probability at least $ 1-\epsilon$ for any given ϵ∈(0,1]\epsilon\in (0,1]ϵ∈(0,1]. This feature leads to quantum search algorithms with stronger robustness and a wider scope of application.
Continuous-time quantum walks are natural tools for spatial search, where one searches for a marked vertex in a graph. Sometimes the structure of the graph causes the walker to get trapped, such that the probability of finding the marked vertex is limited. We give an example with two linked cliques, proving that the captive probability can be liberated by increasing the weights of the links. This allows the search to succeed with probability 1 without increasing the energy scaling of the algorithm. Further increasing the weights, however, slows the runtime, so the optimal search requires weights that are neither too weak nor too strong.