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:2405.07009 · Physical Review A

Quantum search in many-body interacting systems with long-range interactions

Fan Xing, Yan Wei, Zeyang Liao

Published May 23, 2024• 7 citations
arXivHTMLPDF

Abstract

Continuous-time quantum walks provide an alternative method for quantum search problems. Most earlier studies confirmed that quadratic speedup exists in some synthetic Hamiltonians, but whether there is quadratic speedup in real physical systems remains elusive. Here, we investigate three physical systems with long-range atom-atom interaction which are possibly good candidates for realizing the quantum search, including one-dimensional atom arrays either trapped in an optical lattice or coupled to a waveguide near the band edge or dispersively coupled to a good cavity. We find that all three systems can provide a near-optimal quantum search if there is no dissipation. However, if the dissipation is considered, only the latter two systems (i.e., waveguide-QED and cavity-QED systems) can still have high success probabilities because they can significantly enhance the atom-atom interaction even if they are far apart and the spectra gap can be much larger, which can reduce the search time and the effects of dissipation significantly. Our studies here can provide helpful instructions for realizing quantum search in real physical systems in the noisy intermediate-scale quantum era.

DOI
10.1103/physreva.109.052435

Related papers

Optimal Quantum Spatial Search with One-Dimensional Long-Range Interactions

Dylan Lewis, Asmae Benhemou, Natasha Feinstein +2 more

Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(sqrt[n]) time for n entries. However, the capability of models found in nature is largely unexplored-e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(sqrt[n]) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/r^{α} with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.

arXiv:2010.04299•Physical Review Letters•Jun 17, 2021•16 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•9 citations

Atomic-waveguide quantum electrodynamics

Stuart J. Masson, Ana Asenjo-García

Atom arrays are a new type of quantum light-matter interface.Here we propose to employ one-dimensional ordered arrays as atomic waveguides.These arrays support optical guided modes that do not decay into free space.We show that these modes can be harnessed to mediate tunable, long-range interactions between additional "impurity qubits" coupled to the chain, without need for photonic structures.The efficient coupling between qubits and atomic waveguides enables the realization of tunable qubit-qubit interactions, which can be short or long range, dissipative or coherent, as well as chiral.Moreover, owing to the two-level nature of atoms, these waveguides are intrinsically quantum.In contrast to classical waveguides, where photons do not interact with each other, atomic waveguides display strong nonlinearities, which create a tunable dissipative channel for qubit-qubit interactions, and opens the door to the exploration of many-body physics between guided photons.This physics is universal as it only relies on photon interference and can also be observed with other types of quantum emitters, such as those in molecular or solid-state systems.

arXiv:1912.06234•Physical Review Research•Nov 10, 2020•101 citations

Long-distance entanglement in many-body atomic and optical systems

S. M. Giampaolo, Fabrizio Illuminati

We discuss the phenomenon of long-distance entanglement (LDE) in the ground state of quantum spin models, its use in high-fidelity and robust quantum communication, and its realization in many-body systems of ultracold atoms in optical lattices and in arrays of coupled optical cavities. We investigate XX quantum spin models on one-dimensional lattices with open ends and different patterns of site-dependent interaction couplings, singling out two general settings: patterns that allow for perfect LDE in the ground state of the system, namely such that the end-to-end entanglement remains finite in the thermodynamic limit, and patterns of quasi-long-distance entanglement (QLDE) in the ground state of the system, namely such that the end-to-end entanglement vanishes with a very slow power-law decay as the length of the spin chain is increased. We discuss physical realizations of these models in ensembles of ultracold bosonic atoms loaded in optical lattices. We show how, using either suitably engineered super-lattice structures or exploiting the presence of edge impurities in lattices with single periodicity, it is possible to realize models endowed with nonvanishing LDE or QLDE. We then study how to realize models that optimize the robustness of QLDE at finite temperature and in the presence of imperfections using suitably engineered arrays of coupled optical cavities. For both cases the numerical estimates of the end-to-end entanglement in the actual physical systems are thoroughly compared with the analytical results obtained for the spin model systems. We finally introduce LDE-based schemes of long-distance quantum teleportation in linear arrays of coupled cavities, and show that they allow for high-fidelity and high success rates even at moderately high temperatures.

arXiv:0910.0016•New Journal of Physics•Feb 26, 2010•59 citations

Constant-time quantum search with a many-body quantum system

Benjamin DalFavero, Alexander Meill, David Meyer +2 more

The optimal runtime of a quantum computer searching a database is typically cited as the square root of the number of items in the database, which is famously achieved by Grover's algorithm. With parallel oracles, however, it is possible to search faster than this. We consider a many-body quantum system that naturally effects parallel queries, and we show that its parameters can be tuned to search a database in constant time, assuming a sufficient number of interacting particles. In particular, we consider Bose-Einstein condensates with pairwise and three-body interactions in the mean-field limit, which effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic nonlinearities. We solve the unstructured search problem formulated as a continuous-time quantum walk searching the complete graph in constant time. Depending on the number of marked vertices, however, the success probability can peak sharply, necessitating high precision time measurement to observe the system at this peak. Overcoming this, we prove that the relative coefficients of the cubic and quintic terms can be tuned to eliminate the need for high time-measurement precision by widening the peak in success probability or having it plateau. Finally, we derive a lower bound on the number of atoms needed for the many-body system to evolve by the effective nonlinearity.

arXiv:2408.05376•Physical Review A•Nov 7, 2024•2 citations

Quantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise

James G. Morley, Nicholas Chancellor, Sougato Bose +1 more

Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.

arXiv:1709.00371•Physical Review A•Feb 28, 2019•49 citations
Continuous-time quantum walks provide an alternative method for quantum search problems. Most earlier studies confirmed that quadratic speedup exists in some synthetic Hamiltonians, but whether there is quadratic speedup in real physical systems remains elusive. Here, we investigate three physical systems with long-range atom-atom interaction which are possibly good candidates for realizing the quantum search, including one-dimensional atom arrays either trapped in an optical lattice or coupled to a waveguide near the band edge or dispersively coupled to a good cavity. We find that all three systems can provide a near-optimal quantum search if there is no dissipation. However, if the dissipation is considered, only the latter two systems (i.e., waveguide-QED and cavity-QED systems) can still have high success probabilities because they can significantly enhance the atom-atom interaction even if they are far apart and the spectra gap can be much larger, which can reduce the search time and the effects of dissipation significantly. Our studies here can provide helpful instructions for realizing quantum search in real physical systems in the noisy intermediate-scale quantum era.
Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(sqrt[n]) time for n entries. However, the capability of models found in nature is largely unexplored-e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(sqrt[n]) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/r^{α} with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.
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.
Atom arrays are a new type of quantum light-matter interface.Here we propose to employ one-dimensional ordered arrays as atomic waveguides.These arrays support optical guided modes that do not decay into free space.We show that these modes can be harnessed to mediate tunable, long-range interactions between additional "impurity qubits" coupled to the chain, without need for photonic structures.The efficient coupling between qubits and atomic waveguides enables the realization of tunable qubit-qubit interactions, which can be short or long range, dissipative or coherent, as well as chiral.Moreover, owing to the two-level nature of atoms, these waveguides are intrinsically quantum.In contrast to classical waveguides, where photons do not interact with each other, atomic waveguides display strong nonlinearities, which create a tunable dissipative channel for qubit-qubit interactions, and opens the door to the exploration of many-body physics between guided photons.This physics is universal as it only relies on photon interference and can also be observed with other types of quantum emitters, such as those in molecular or solid-state systems.
We discuss the phenomenon of long-distance entanglement (LDE) in the ground state of quantum spin models, its use in high-fidelity and robust quantum communication, and its realization in many-body systems of ultracold atoms in optical lattices and in arrays of coupled optical cavities. We investigate XX quantum spin models on one-dimensional lattices with open ends and different patterns of site-dependent interaction couplings, singling out two general settings: patterns that allow for perfect LDE in the ground state of the system, namely such that the end-to-end entanglement remains finite in the thermodynamic limit, and patterns of quasi-long-distance entanglement (QLDE) in the ground state of the system, namely such that the end-to-end entanglement vanishes with a very slow power-law decay as the length of the spin chain is increased. We discuss physical realizations of these models in ensembles of ultracold bosonic atoms loaded in optical lattices. We show how, using either suitably engineered super-lattice structures or exploiting the presence of edge impurities in lattices with single periodicity, it is possible to realize models endowed with nonvanishing LDE or QLDE. We then study how to realize models that optimize the robustness of QLDE at finite temperature and in the presence of imperfections using suitably engineered arrays of coupled optical cavities. For both cases the numerical estimates of the end-to-end entanglement in the actual physical systems are thoroughly compared with the analytical results obtained for the spin model systems. We finally introduce LDE-based schemes of long-distance quantum teleportation in linear arrays of coupled cavities, and show that they allow for high-fidelity and high success rates even at moderately high temperatures.
The optimal runtime of a quantum computer searching a database is typically cited as the square root of the number of items in the database, which is famously achieved by Grover's algorithm. With parallel oracles, however, it is possible to search faster than this. We consider a many-body quantum system that naturally effects parallel queries, and we show that its parameters can be tuned to search a database in constant time, assuming a sufficient number of interacting particles. In particular, we consider Bose-Einstein condensates with pairwise and three-body interactions in the mean-field limit, which effectively evolve by a nonlinear Schr\"odinger equation with cubic and quintic nonlinearities. We solve the unstructured search problem formulated as a continuous-time quantum walk searching the complete graph in constant time. Depending on the number of marked vertices, however, the success probability can peak sharply, necessitating high precision time measurement to observe the system at this peak. Overcoming this, we prove that the relative coefficients of the cubic and quintic terms can be tuned to eliminate the need for high time-measurement precision by widening the peak in success probability or having it plateau. Finally, we derive a lower bound on the number of atoms needed for the many-body system to evolve by the effective nonlinearity.
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.