Constant-Time Quantum Search with a Many-Body Quantum System
- URL: http://arxiv.org/abs/2408.05376v1
- Date: Fri, 9 Aug 2024 22:57:59 GMT
- Title: Constant-Time Quantum Search with a Many-Body Quantum System
- Authors: Benjamin DalFavero, Alexander Meill, David A. Meyer, Thomas G. Wong, Jonathan P. Wrubel,
- Abstract summary: We consider a many-body quantum system that naturally effects parallel queries.
We show that its parameters can be tuned to search a database in constant time.
- Score: 39.58317527488534
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Quantum Dissipative Search via Lindbladians [0.0]
We analyze the convergence criteria and the convergence speed of a Markovian, purely dissipative quantum random walk on an unstructured search space.
We map the results onto an actual implementation to correctly estimate the potential and show that it is no more efficient than classical search.
arXiv Detail & Related papers (2024-07-16T14:39:18Z) - Realizing fracton order from long-range quantum entanglement in programmable Rydberg atom arrays [45.19832622389592]
Storing quantum information requires battling quantum decoherence, which results in a loss of information over time.
To achieve error-resistant quantum memory, one would like to store the information in a quantum superposition of degenerate states engineered in such a way that local sources of noise cannot change one state into another.
We show that this platform also allows to detect and correct certain types of errors en route to the goal of true error-resistant quantum memory.
arXiv Detail & Related papers (2024-07-08T12:46:08Z) - Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk.
The same technique can be applied to other 1-dimensional hierarchical graphs.
arXiv Detail & Related papers (2024-04-30T11:45:49Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - A streamlined quantum algorithm for topological data analysis with
exponentially fewer qubits [5.478764356647437]
We present an improved quantum algorithm for computing persistent Betti numbers.
We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
arXiv Detail & Related papers (2022-09-26T17:56:11Z) - Designing exceptional-point-based graphs yielding topologically
guaranteed quantum search [0.0]
We show how to construct walks with the property that all the eigenvalues of the non-Hermitian survival operator, coalesce to zero.
The resulting search is guaranteed to succeed in a bounded time for any initial condition.
arXiv Detail & Related papers (2022-02-08T04:30:24Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search.
We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
arXiv Detail & Related papers (2021-12-23T17:57:49Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems.
We propose an algorithm to implement imaginary time propagation on a quantum computer.
arXiv Detail & Related papers (2021-02-24T12:48:00Z) - Improved Upper Bounds for the Hitting Times of Quantum Walks [0.0]
Continuous-time quantum walks have proven to be an extremely useful framework for the design of quantum algorithms.
We provide improved upper bounds for the quantum hitting time that can be applied to several CTQW-based quantum algorithms.
arXiv Detail & Related papers (2020-05-08T14:25:24Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.