Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComplete Adiabatic Quantum Search in Unsorted Databases
149
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We propose a new adiabatic algorithm for the unsorted database search problem. This algorithm saves two thirds of qubits than Grovers algorithm in realizations. Meanwhile, we analyze the time complexity of the algorithm by both perturbative method and numerical simulation. The results show it provides a better speedup than the previous adiabatic search algorithm.
rate research
Read More
Adiabatic quantum algorithms are characterized by their run time and accuracy. The relation between the two is essential for quantifying adiabatic algorithmic performance, yet is often poorly understood. We study the dynamics of a continuous time, adiabatic quantum search algorithm, and find rigorous results relating the accuracy and the run time. Proceeding with estimates, we show that under fairly general circumstances the adiabatic algorithmic error exhibits a behavior with two discernible regimes: the error decreases exponentially for short times, then decreases polynomially for longer times. We show that the well known quadratic speedup over classical search is associated only with the exponential error regime. We illustrate the results through examples of evolution paths derived by minimization of the adiabatic error. We also discuss specific strategies for controlling the adiabatic error and run time.
In classical computing, analog approaches have sometimes appeared to be more powerful than they really are. This occurs when resources, particularly precision, are not appropriately taken into account. While the same should also hold for analog quantum computing, precision issues are often neglected from the analysis. In this work we present a classical analog algorithm for unstructured search that can be viewed as analogous to the quantum adiabatic unstructured search algorithm devised by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. We show that similarly to its quantum counterpart, the classical construction may also provide a quadratic speedup over standard digital unstructured search. We discuss the meaning and the possible implications of this result in the context of adiabatic quantum computing.
It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.
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 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 the optimal adiabatic schedule 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 speed up 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, quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.
We investigate the behavior of coherence in scattering quantum walk search on complete graph under the condition that the total number of vertices of the graph is greatly larger than the marked number of vertices we are searching, $N gg v$. We find that the consumption of coherence represents the increase of the success probability for the searching,also the consumption of coherence is related to the efficiency of the algorithm represented by oracle queries.If no coherence is consumed, the efficiency of the algorithm will be the same as the classical blind search, implying that coherence is responsible for the speed up in this quantum algorithm over its classical counterpart. In case the initial state is incoherent, still $N gg v$ is assumed,the probability of success for searching will not change with time, indicating that this quantum search algorithm loses its power.We then conclude that the coherence plays an essential role and is responsible for the speed up in this quantum algorithm.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
