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

Lecture notes in computer science

Spatial Search for Two Marked Vertices on Hypercube by Continuous-Time Quantum Walk

Xi Li, Hanwu Chen, Zhihao Liu, Wenjie Liu, Mengke Xu

Published Jan 1, 2018• 0 citations
Publisher
DOI
10.1007/978-3-030-00018-9_50

Related papers

Spatial search by continuous-time quantum walk with multiple marked vertices

Thomas G. Wong

arXiv:1501.07071•Quantum Information Processing•Jan 25, 2016•38 citations

Continuous-time quantum walks on strongly regular graphs with loops and its application to spatial search for multiple marked vertices

Xi Li, Hanwu Chen, Yue Ruan +2 more

Quantum Information Processing•May 13, 2019•4 citations

Lackadaisical Quantum Walk in the Hypercube to Search for Multiple Marked Vertices

Luciano S. de Souza, Jonathan H. A. de Carvalho, Tiago A. E. Ferreira

arXiv:2108.09399•Lecture notes in computer science•Jan 1, 2021•4 citations

Spatial search by continuous-time quantum walks on crystal lattices

Andrew M. Childs, Yimin Ge

We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt{N})$ for $d>2$ and $O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.

arXiv:1403.2676•Physical Review A•May 30, 2014•46 citations

Efficient Circuit Implementations of Continuous-Time Quantum Walks for Quantum Search

Renato Portugal, Jalil Khatibi Moqadam

Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.

arXiv:2212.08889•Entropy•Apr 23, 2025•1 citation

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384•ACM Transactions on Quantum Computing•Nov 27, 2024•5 citations
We consider the problem of searching a general ddd-dimensional lattice of NNN vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of O(N)O(\sqrt{N})O(N​) for d>2d>2d>2 and O(NlogN)O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)O(N​logN) in d=2d=2d=2. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.
Quantum walks are a powerful framework for simulating complex quantum systems and designing quantum algorithms, particularly for spatial search on graphs, where the goal is to find a marked vertex efficiently. In this work, we present efficient quantum circuits that implement the evolution operator of continuous-time quantum-walk-based search algorithms for three graph families: complete graphs, complete bipartite graphs, and hypercubes. For complete and complete bipartite graphs, our circuits exactly implement the evolution operator. For hypercubes, we propose an approximate implementation that closely matches the exact evolution operator as the number of vertices increases. Our Qiskit simulations demonstrate that even for low-dimensional hypercubes, the algorithm effectively identifies the marked vertex. Furthermore, the approximate implementation developed for hypercubes can be extended to a broad class of graphs, enabling efficient quantum search in scenarios where exact implementations are impractical.
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N)O(\sqrt {N})O(N​) with an asymptotic probability of 1+ o (1), where N is the number of vertices.