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:2106.03867 · Physical Review Applied

Quantum Spatial Search in Two-Dimensional Waveguide Arrays

Claudia Benedetti, Dario Tamascelli, Matteo G. A. Paris, Andrea Crespi

Published Nov 18, 2021• 22 citations
arXivHTMLPDF

Abstract

Continuous-time quantum walks (CTQWs) have shown the capability to perform efficiently the spatial search of a marked site on many kinds of graphs. However, most of such graphs are hard to realize in an experimental setting. Here we study CTQW spatial search on a planar triangular lattice by means of both numerical simulations and experiments. The experiments are performed using two-dimensional waveguide arrays fabricated by femtosecond laser pulses, illuminated by coherent light. We show that the retrieval of the marked site by the quantum walker is accomplished with higher probability than the classical counterpart, in a convenient time window placed early in the evolution.

DOI
10.1103/physrevapplied.16.054036

Related papers

Quantum spatial search in three-dimensional waveguide arrays

Claudia Benedetti, Dario Tamascelli, Matteo G. A. Paris +1 more

Continuous-time quantum walks (CTQW) have shown the capability to perform efficiently the spatial search of a marked site on many kinds of graphs. However, most of such graphs are hard to realize in an experimental setting. Here we study CTQW spatial search on a planar triangular lattice by means of both numerical simulations and experiments. The experiments are performed using three-dimensional waveguide arrays fabricated by femtosecond laser pulses, illuminated by coherent light. We show that the retrieval of the marked site by the quantum walker is accomplished with higher probability than the classical counterpart, in a convenient time window placed early in the evolution.

•Jun 7, 2021•0 citations

Spatial search on a two-dimensional lattice with long-range interactions

Tomo Osada, Kaoru Sanaka, William J. Munro +1 more

Quantum-walk-based algorithms that search a marked location among $N$ locations on a $d$-dimensional lattice succeeds in time $O(\sqrt{N})$ for $d>2$, while this is not found to be possible when $d=2$. In this paper, we consider a spatial search algorithm using continuous-time quantum walk on a two-dimensional square lattice with the existence of additional long-range edges. We examined such a search on a probabilistic graph model where an edge connecting non-nearest-neighbor lattice points $i$ and $j$ apart by a distance $|i\ensuremath{-}j|$ is added by probability ${p}_{ij}={|i\ensuremath{-}j|}^{\ensuremath{-}\ensuremath{\alpha}}\phantom{\rule{1em}{0ex}}(\ensuremath{\alpha}\ensuremath{\ge}0)$. Through numerical analysis, we found that the search succeeds in time $O(\sqrt{N})$ when $\ensuremath{\alpha}\ensuremath{\le}{\ensuremath{\alpha}}_{c}=2.4\ifmmode\pm\else\textpm\fi{}0.1$. For $\ensuremath{\alpha}>2$, the expectation value of the additional long-range edges on each node scales as a constant when $N\ensuremath{\rightarrow}\ensuremath{\infty}$, which means that search time of $O(\sqrt{N})$ is achieved on a graph with average degree scaling as a constant.

Physical Review A•Jun 11, 2018•10 citations

Spatial Search by Quantum Walk is Optimal for Almost all Graphs

Shantanav Chakraborty, Leonardo Novo, Andris Ambainis +1 more

The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdös-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum spatial search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.

arXiv:1508.01327•Physical Review Letters•Mar 11, 2016•163 citations

Experimental two-dimensional quantum walk on a photonic chip

Hao Long Tang, Xiao-Feng Lin, Zhen Feng +10 more

Quantum walks, in virtue of the coherent superposition and quantum interference, have exponential superiority over their classical counterpart in applications of quantum searching and quantum simulation. The quantum-enhanced power is highly related to the state space of quantum walks, which can be expanded by enlarging the photon number and/or the dimensions of the evolution network, but the former is considerably challenging due to probabilistic generation of single photons and multiplicative loss. We demonstrate a two-dimensional continuous-time quantum walk by using the external geometry of photonic waveguide arrays, rather than the inner degree of freedoms of photons. Using femtosecond laser direct writing, we construct a large-scale three-dimensional structure that forms a two-dimensional lattice with up to 49 × 49 nodes on a photonic chip. We demonstrate spatial two-dimensional quantum walks using heralded single photons and single photon-level imaging. We analyze the quantum transport properties via observing the ballistic evolution pattern and the variance profile, which agree well with simulation results. We further reveal the transient nature that is the unique feature for quantum walks of beyond one dimension. An architecture that allows a quantum walk to freely evolve in all directions and at a large scale, combining with defect and disorder control, may bring up powerful and versatile quantum walk machines for classically intractable problems.

arXiv:1704.08242•Science Advances•May 4, 2018•272 citations

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

Spatial search by continuous-time quantum walks on complex networks

Joonas Malmi

Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.

•Dec 8, 2020•0 citations
Continuous-time quantum walks (CTQWs) have shown the capability to perform efficiently the spatial search of a marked site on many kinds of graphs. However, most of such graphs are hard to realize in an experimental setting. Here we study CTQW spatial search on a planar triangular lattice by means of both numerical simulations and experiments. The experiments are performed using two-dimensional waveguide arrays fabricated by femtosecond laser pulses, illuminated by coherent light. We show that the retrieval of the marked site by the quantum walker is accomplished with higher probability than the classical counterpart, in a convenient time window placed early in the evolution.
Continuous-time quantum walks (CTQW) have shown the capability to perform efficiently the spatial search of a marked site on many kinds of graphs. However, most of such graphs are hard to realize in an experimental setting. Here we study CTQW spatial search on a planar triangular lattice by means of both numerical simulations and experiments. The experiments are performed using three-dimensional waveguide arrays fabricated by femtosecond laser pulses, illuminated by coherent light. We show that the retrieval of the marked site by the quantum walker is accomplished with higher probability than the classical counterpart, in a convenient time window placed early in the evolution.
Quantum-walk-based algorithms that search a marked location among NNN locations on a ddd-dimensional lattice succeeds in time O(N)O(\sqrt{N})O(N​) for d>2d>2d>2, while this is not found to be possible when d=2d=2d=2. In this paper, we consider a spatial search algorithm using continuous-time quantum walk on a two-dimensional square lattice with the existence of additional long-range edges. We examined such a search on a probabilistic graph model where an edge connecting non-nearest-neighbor lattice points iii and jjj apart by a distance $|i\ensuremath{-}j|$ is added by probability ${p}_{ij}={|i\ensuremath{-}j|}^{\ensuremath{-}\ensuremath{\alpha}}\phantom{\rule{1em}{0ex}}(\ensuremath{\alpha}\ensuremath{\ge}0)$. Through numerical analysis, we found that the search succeeds in time O(N)O(\sqrt{N})O(N​) when $\ensuremath{\alpha}\ensuremath{\le}{\ensuremath{\alpha}}_{c}=2.4\ifmmode\pm\else\textpm\fi{}0.1$. For $\ensuremath{\alpha}>2$, the expectation value of the additional long-range edges on each node scales as a constant when $N\ensuremath{\rightarrow}\ensuremath{\infty}$, which means that search time of O(N)O(\sqrt{N})O(N​) is achieved on a graph with average degree scaling as a constant.
The problem of finding a marked node in a graph can be solved by the spatial search algorithm based on continuous-time quantum walks (CTQW). However, this algorithm is known to run in optimal time only for a handful of graphs. In this work, we prove that for Erdös-Renyi random graphs, i.e., graphs of n vertices where each edge exists with probability p, search by CTQW is almost surely optimal as long as p≥log^{3/2}(n)/n. Consequently, we show that quantum spatial search is in fact optimal for almost all graphs, meaning that the fraction of graphs of n vertices for which this optimality holds tends to one in the asymptotic limit. We obtain this result by proving that search is optimal on graphs where the ratio between the second largest and the largest eigenvalue is bounded by a constant smaller than 1. Finally, we show that we can extend our results on search to establish high fidelity quantum communication between two arbitrary nodes of a random network of interacting qubits, namely, to perform quantum state transfer, as well as entanglement generation. Our work shows that quantum information tasks typically designed for structured systems retain performance in very disordered structures.
Quantum walks, in virtue of the coherent superposition and quantum interference, have exponential superiority over their classical counterpart in applications of quantum searching and quantum simulation. The quantum-enhanced power is highly related to the state space of quantum walks, which can be expanded by enlarging the photon number and/or the dimensions of the evolution network, but the former is considerably challenging due to probabilistic generation of single photons and multiplicative loss. We demonstrate a two-dimensional continuous-time quantum walk by using the external geometry of photonic waveguide arrays, rather than the inner degree of freedoms of photons. Using femtosecond laser direct writing, we construct a large-scale three-dimensional structure that forms a two-dimensional lattice with up to 49 × 49 nodes on a photonic chip. We demonstrate spatial two-dimensional quantum walks using heralded single photons and single photon-level imaging. We analyze the quantum transport properties via observing the ballistic evolution pattern and the variance profile, which agree well with simulation results. We further reveal the transient nature that is the unique feature for quantum walks of beyond one dimension. An architecture that allows a quantum walk to freely evolve in all directions and at a large scale, combining with defect and disorder control, may bring up powerful and versatile quantum walk machines for classically intractable problems.
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.
Spatial search by continuous-time quantum walks on complex networks is focused on using a quantum walk in continuous time in order to find a single or multiple marked vertices within the complex network. The specific formalism used here is to consider a coupling constant that shifts the state of the quantum walker from the initial state to the target state, which is the marked vertex. The thesis begins with establishing the mathematical framework of network theory, quantum walks and numerical methods that will be used in the remainder of the thesis. Then spatial search by continuous-time quantum walk is studied on regular and semi-regular graphs, where most analytical results can be found. This will get us acquainted with spatial search by quantum walk. The complex networks studied are Barabasi-Albert graphs and the Internet network on the level of autonomous systems. Different renormalized and pruned versions of the Internet network are studied. The parameters of the quantum walk that are focused on are the optimal values for the coupling constant, success probability, time and search time.