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:0811.4247

Constant-Time Quantum Algorithm For The Unstructured Search Problem

Ahmed Younes

Published Nov 26, 2008• 1 citation
arXivHTMLPDF

Abstract

Given an item and a list of values of size $N$. It is required to decide if such item exists in the list. Classical computer can search for the item in O(N). The best known quantum algorithm can do the job in $O(\sqrt{N})$. In this paper, a quantum algorithm will be proposed that can search an unstructured list in O(1) to get the YES/NO answer with certainty.

DOI
10.48550/arxiv.0811.4247

Related papers

On New Quantum Search Algorithms and Complexity of NP-Complete Problems

Dhananjay P. Mehendale

We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!

•Jul 1, 2016•0 citations

Quantum Mechanical Square Root Speedup in a Structured Search Problem

Edward Farhi, Sam Gutmann

An unstructured search for one item out of N can be performed quantum mechanically in time of order square root of N whereas classically this requires of order N steps. This raises the question of whether square root speedup persists in problems with more structure. In this note we focus on one example of a structured problem and find a quantum algorithm which takes time of order the square root of the classical time.

arXiv:quant-ph/9711035•Nov 18, 1997•12 citations

Quantum algorithms for the ordered search problem via semidefinite programming

Andrew M. Childs, Andrew J. Landahl, Pablo A. Parrilo

One of the most basic computational problems is the task of finding a desired item in an ordered list of $N$ items. While the best classical algorithm for this problem uses ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{605}\phantom{\rule{0.2em}{0ex}}N\ensuremath{\approx}0.433\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries, which improves upon the previously best known exact algorithm.

arXiv:quant-ph/0608161•Physical Review A•Mar 26, 2007•46 citations

An Improved Quantum Search Algorithm

Amrita Mitra

If we have to search an unsorted database or solve an unstructured search problem, we can use a quantum search algorithm. As of now, a quantum search algorithm like Grover's algorithm takes Ω(\sqrt N) time, where N is the size of the search space. This paper proposes an improved quantum search algorithm that yields the correct result in constant time with a high probability.

Journal of Quantum Information Science•Jan 1, 2025•0 citations

An Improved Quantum Algorithm for Searching an Ordered List

Brian Jacokes

The best known quantum algorithm for searching an ordered list of N items is recursive and requires 3 log52 N ≈ 0.526 log2 N queries. We find an improved base case for this recursion, yielding an algorithm that requires only 4 log434 N ≈ 0.457 log2 N queries. This algorithm is more than twice as fast as the best possible classical algorithm, which requires log2 N queries.

•Jan 1, 2007•7 citations

Grover's Search Algorithm for Database Validation

Dr CH Pavan Satish, K. Bhargavi, G.Vanaja +2 more

In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.

International Journal of Engineering Research and Science & Technology•Mar 22, 2026•0 citations
Given an item and a list of values of size NNN. It is required to decide if such item exists in the list. Classical computer can search for the item in O(N). The best known quantum algorithm can do the job in O(N)O(\sqrt{N})O(N​). In this paper, a quantum algorithm will be proposed that can search an unstructured list in O(1) to get the YES/NO answer with certainty.
We develop three new quantum algorithms for searching the desired target state in the unstructured database of size N. The first algorithm requires Log N iterative steps. It constructs two quantum bags of equal size in terms of two quantum states, out of which exactly one quantum state will have nonzero overlap with the target state. This determination of overlap is done by taking the inner product, in Log N time [2], of the implicitly known target state with any one of these two quantum states. The second algorithm requires just one single step which uses a new suitable operator and the choice of this operator is problem dependent, i.e. it depends upon the number of qubits required to be used to represent an element in the index set. The third algorithm again requires only a single step and this algorithm makes use of a fixed (same) operator. It is known that algorithm for unstructured database search can be easily adaptable for solving NP-Complete problems. However, the computational complexity of NP-Complete problems after the adaptations of both the classical as well as quantum [1] search algorithms remains of the exponential order as the exponent for quantum [1] algorithm changes only to one-half times the exponent for classical algorithm. But for our quantum algorithms the exponent falls substantially so that our new quantum algorithms for unstructured search are capable if reducing the computational complexity of NP-Complete problems to polynomial order!
One of the most basic computational problems is the task of finding a desired item in an ordered list of NNN items. While the best classical algorithm for this problem uses log2N{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}Nlog2​N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{605}\phantom{\rule{0.2em}{0ex}}N\ensuremath{\approx}0.433\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries, which improves upon the previously best known exact algorithm.
In my project I would have considered how the old search algorithms that are used when working with large unstructured data set end up taking linear time (O(N)) that in effect is the time that scales with the size of the data. These old ways get gradually sluggish, as everything gets bigger. Then I read about quantum computing, and especially Search Algorithm that was developed by Grover which is capable of quadratic speed-up with a complexity of O(sqrt(N)) of unstructured data. I created a hybrid system which fuses classical and quantum search applied on Flask as the web front end and Qiskit as the quantum one. This will enable me to compare the simple linear algorithm of searching through the list item-by-item with the quantum algorithm of Grover which uses superposition, a marking oracle to identify the desired item, and multiple amplitude amplification diffusion operators. The web page also accepts a student ID, and actually searches both simultaneously and allows me to tweak a depolarizing noise model so as to more closely mimic real quantum hardware. I measured such variables as the number of calls to the oracle, the number of qubits that I require, the quantum run time, and the number of measurements that I receive out of the quantum measurement. As the results indicate, the algorithm developed by Grover reduces the number of operations significantly compared to the classical one, and it must be emphasized that the algorithm remains quite effective even in the case of simulated noise. On the whole, it demonstrates that the classical and quantum components may be an efficient method to deal with the large search in the database.