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

IEEE Transactions on Computers

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

Sándor Imre

Published Apr 17, 2007• 31 citations
Publisher

Abstract

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

DOI
10.1109/tc.2007.1032

Related papers

EXTREME VALUE SEARCHING IN UNSORTED DATABASES BASED ON QUANTUM COMPUTING

Sándor Imre

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.

International Journal of Quantum Information•Dec 17, 2004•13 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•8 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

Quantum search algorithm in unstructured database

A. D. Kozhukhivskyi

Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.

Scientific Notes of the State University of Telecommunications•Jan 1, 2022•2 citations

Searching in an Unsorted Database

Sándor Imre, Ferenc Balázs

This chapter contains sections titled: The Basic Grover Algorithm Quantum Counting Quantum Existence Testing Finding Extreme Values in an Unsorted Database The Generalized Grover Algorithm Further Reading

Wiley eBooks•Nov 19, 2004•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
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
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.
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.
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.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.
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.