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

International Journal of Quantum Information

EXTREME VALUE SEARCHING IN UNSORTED DATABASES BASED ON QUANTUM COMPUTING

Sándor Imre

Published Dec 17, 2004• 13 citations
Publisher

Abstract

Finding the extreme value of a database or a function plays an important role in computing and communication applications. Unfortunately, classical solutions suffer from computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing based solutions can guarantee success only in terms of the expected value of the database queries. In this paper we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive quantum existence testing which allows adapting the classical logarithmic search algorithm suitable for structured databases to unstructured ones while maintaining its efficiency.

DOI
10.1142/s0219749905000700

Related papers

Quantum Existence Testing and Its Application for Finding Extreme Values in Unsorted Databases

Sándor Imre

Many information processing and computing problems can be traced back to find the extreme value of a database or a function. Unfortunately, classical solutions suffer from high computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing-based solutions involve the repeated application of Grower's searching algorithm. In this paper, we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive a special case of quantum counting - we call it quantum existence testing - which allows adapting the classical logarithmic search algorithm so that it is suitable for structured databases to unstructured ones. The paper analyzes the required number of database queries, the corresponding computational complexity, and the probability of error and their relationship

IEEE Transactions on Computers•Apr 17, 2007•31 citations

An efficient quantum search engine on unsorted database

Heping Hu, Yingyu Zhang, Zhengding Lu

We consider the problem of finding one or more desired items out of an unsorted database. Patel has shown that if the database permits quantum queries, then mere digitization is sufficient for efficient search for one desired item. The algorithm, called factorized quantum search algorithm, presented by him can locate the desired item in an unsorted database using $O(log_{4}N)$ queries to factorized oracles. But the algorithm requires that all the property values must be distinct from each other. In this paper, we discuss how to make a database satisfy the requirements, and present a quantum search engine based on the algorithm. Our goal is achieved by introducing auxiliary files for the property values that are not distinct, and converting every complex query request into a sequence of calls to factorized quantum search algorithm. The query complexity of our algorithm is $O(P*Q*M*log_{4}N)$, where P is the number of the potential simple query requests in the complex query request, Q is the maximum number of calls to the factorized quantum search algorithm of the simple queries, M is the number of the auxiliary files for the property on which our algorithm are searching for desired items. This implies that to manage an unsorted database on an actual quantum computer is possible and efficient.

arXiv:0904.3060•Apr 20, 2009•0 citations

Efficient simulation of quantum-based searching

Tamás Varga, László Bacsárdi

The efficient search in unsorted database is extremely important for our everydays' applications. This type of search is useful in communication networks as well, since routing can be considered as a search in the database of the routing table. From the viewpoint of quantum computing, the not quantum-based solutions are named as classical. The search could be very time-consuming and computationally task if we need to solve it using classical algorithms, particularly for large data sets. This process can be accelerated and be more efficient by the application of quantum search algorithms. To investigate the quantum search, we have developed a Java-based system to simulate different quantum algorithms which are based on elementary quantum gates. In our model, we took into account the computation errors of the elementary quantum gates. We analyzed how these errors affect the efficiency of quantum search.

International Conference on Software, Telecommunications and Computer Networks (SoftCOM)•Sep 1, 2014•2 citations

Constrained Quantum Optimization Algorithm

Sara El Gaily, Sándor Imre

Classical computing still suffers from the high computational complexity of finding the extreme value of a constrained goal function or an unordered database with respect to a certain constraint. Quantum computing offers new possibilities and solutions due to its quantum nature to surmount this problem. In this paper, we extended a new version of quantum existence testing (QET) _we call it a constrained quantum relation testing (CQRT)_ we also investigate analytically its classical and quantum certainty. Furthermore, we show how the CQRT can be applied for extending the quantum extreme value searching algorithm (QEVSA) version to a constrained quantum optimization algorithm (CQOA). And we gave an extensive explanation of how the CQOA works and how it finds the extreme constrained optimum value solution with high complexity reduction, maximum exponential speed, and high certainty.

International Symposium INFOTEH-JAHORINA (INFOTEH)•Mar 17, 2021•7 citations

Quantum Optimization in Large Resource Management Systems

Sara El Gaily, Sándor Imre

Classical computing methods do not enable to withstand the cumbersome computational operations of complex applications and a bunch of untouched problems that still exist until today. The proposed quantum method tackles the computational complexity problem by exploiting the parallel processing techniques of quantum computing. This paper aims to take advantage of quantum computing power in resource distribution management for a large scale of resources. To achieve this, we use quantum extreme value searching algorithm as a minimum searching algorithm. Moreover, to prove the efficiency of the quantum strategy, we compare the quantum method and the randomized one.

IEEE International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)•Jul 1, 2019•10 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

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. Grover's 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 Grover's 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 Grover's 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.

arXiv:2103.14196•Mar 26, 2021•6 citations
Finding the extreme value of a database or a function plays an important role in computing and communication applications. Unfortunately, classical solutions suffer from computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing based solutions can guarantee success only in terms of the expected value of the database queries. In this paper we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive quantum existence testing which allows adapting the classical logarithmic search algorithm suitable for structured databases to unstructured ones while maintaining its efficiency.
Many information processing and computing problems can be traced back to find the extreme value of a database or a function. Unfortunately, classical solutions suffer from high computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing-based solutions involve the repeated application of Grower's searching algorithm. In this paper, we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive a special case of quantum counting - we call it quantum existence testing - which allows adapting the classical logarithmic search algorithm so that it is suitable for structured databases to unstructured ones. The paper analyzes the required number of database queries, the corresponding computational complexity, and the probability of error and their relationship
We consider the problem of finding one or more desired items out of an unsorted database. Patel has shown that if the database permits quantum queries, then mere digitization is sufficient for efficient search for one desired item. The algorithm, called factorized quantum search algorithm, presented by him can locate the desired item in an unsorted database using O(log4N)O(log_{4}N)O(log4​N) queries to factorized oracles. But the algorithm requires that all the property values must be distinct from each other. In this paper, we discuss how to make a database satisfy the requirements, and present a quantum search engine based on the algorithm. Our goal is achieved by introducing auxiliary files for the property values that are not distinct, and converting every complex query request into a sequence of calls to factorized quantum search algorithm. The query complexity of our algorithm is O(P∗Q∗M∗log4N)O(P*Q*M*log_{4}N)O(P∗Q∗M∗log4​N), where P is the number of the potential simple query requests in the complex query request, Q is the maximum number of calls to the factorized quantum search algorithm of the simple queries, M is the number of the auxiliary files for the property on which our algorithm are searching for desired items. This implies that to manage an unsorted database on an actual quantum computer is possible and efficient.
The efficient search in unsorted database is extremely important for our everydays' applications. This type of search is useful in communication networks as well, since routing can be considered as a search in the database of the routing table. From the viewpoint of quantum computing, the not quantum-based solutions are named as classical. The search could be very time-consuming and computationally task if we need to solve it using classical algorithms, particularly for large data sets. This process can be accelerated and be more efficient by the application of quantum search algorithms. To investigate the quantum search, we have developed a Java-based system to simulate different quantum algorithms which are based on elementary quantum gates. In our model, we took into account the computation errors of the elementary quantum gates. We analyzed how these errors affect the efficiency of quantum search.
Classical computing still suffers from the high computational complexity of finding the extreme value of a constrained goal function or an unordered database with respect to a certain constraint. Quantum computing offers new possibilities and solutions due to its quantum nature to surmount this problem. In this paper, we extended a new version of quantum existence testing (QET) _we call it a constrained quantum relation testing (CQRT)_ we also investigate analytically its classical and quantum certainty. Furthermore, we show how the CQRT can be applied for extending the quantum extreme value searching algorithm (QEVSA) version to a constrained quantum optimization algorithm (CQOA). And we gave an extensive explanation of how the CQOA works and how it finds the extreme constrained optimum value solution with high complexity reduction, maximum exponential speed, and high certainty.
Classical computing methods do not enable to withstand the cumbersome computational operations of complex applications and a bunch of untouched problems that still exist until today. The proposed quantum method tackles the computational complexity problem by exploiting the parallel processing techniques of quantum computing. This paper aims to take advantage of quantum computing power in resource distribution management for a large scale of resources. To achieve this, we use quantum extreme value searching algorithm as a minimum searching algorithm. Moreover, to prove the efficiency of the quantum strategy, we compare the quantum method and the randomized one.
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. Grover's 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 Grover's 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 Grover's 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.