Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTradeoffs in the Quantum Search Algorithm
129
0
0.0
(
0
)
Authors
Lov K. Grover
Ask ChatGPT about the research
No Arabic abstract
Quantum search is a quantum mechanical technique for searching N possibilities in only sqrt(N) steps. This has been proved to be the best possible algorithm for the exhuastive search problem in the sense the number of queries it requires cannot be reduced. However, as this paper shows, the number of non-query operations, and thus the total number of operations, can be reduced. The number of non-query unitary operations can be reduced by a factor of log N/alpha*log(log N) while increasing the number of queries by a factor of only (1+(log N)^{-alpha}). Various choices of alpha yield different variants of the algorithm. For example, by choosing alpha to be O(log N/log(log N)), the number of non-query unitary operations can be reduced by 40% while increasing the number of queries by just two.
rate research
Read More
Grovers quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modelled easily because of the exact recursion formulas available for computing the quantum amplitude in Grovers algorithm. We study the algorithms intrinsic robustness when no quantum correction codes are used, and evaluate how much noise the algorithm can bear with, in terms of the size of the phone book and a desired probability of finding the correct result. The algorithm loses efficiency when noise is added, but does not slow down. We also study the maximal noise under which the iterated quantum algorithm is just as slow as the classical algorithm. In all cases, the width of the allowed noise scales with the size of the phone book as N^-2/3.
We investigate the role of quantum coherence depletion (QCD) in Grover search algorithm (GA) by using several typical measures of quantum coherence and quantum correlations. By using the relative entropy of coherence measure ($mathcal{C}_r$), we show that the success probability depends on the QCD. The same phenomenon is also found by using the $l_1$ norm of coherence measure ($mathcal{C}_{l_1}$). In the limit case, the cost performance is defined to characterize the behavior about QCD in enhancing the success probability of GA, which is only related to the number of searcher items and the scale of database, no matter using $mathcal{C}_r$ or $mathcal{C}_{l_1}$. In generalized Grover search algorithm (GGA), the QCD for a class of states increases with the required optimal measurement time. In comparison, the quantification of other quantum correlations in GA, such as pairwise entanglement, multipartite entanglement, pairwise discord and genuine multipartite discord, cannot be directly related to the success probability or the optimal measurement time. Additionally, we do not detect pairwise nonlocality or genuine tripartite nonlocality in GA since Clauser-Horne-Shimony-Holt inequality and Svetlichnys inequality are not violated.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grovers search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grovers search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grovers search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
We study the entanglement content of the states employed in the Grover algorithm after the first oracle call when a few searched items are concerned. We then construct a link between these initial states and hypergraphs, which provides an illustration of their entanglement properties.
We question whether the measurement based quantum computing algorithm is in fact Grovers algorithm or simply a similar oracular search method. The two algorithms share several qualitative features especially in the case of the trivial 4 element search, which is the largest size photonic search algorithm that has been experimentally implemented to date. This has led some to refer to both substantiations as Grovers algorithm. We compare multiple features of the two algorithms including the behavior of the oracle tags and the entanglement dynamics, both qualitatively and quantitatively. We find significant and fundamental differences in the operation of the two algorithms, particularly in cases involving searches on more than four elements.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
