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•7 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•1 citation

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

Mathlab Implementation of Quantum Computation in Searching an Unstructured Database

Iyabo Olukemi Awoyelu, P. Okoh

In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Clanek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.

•Jan 1, 2012•0 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.
In the classical model of a computer, the most fundamental building block, the bit, can only exist in one of two distinct states, a 0 or a 1. Computations are carried out by logic gates that act on these bits to produce other bits. Unless there is duplicate (parallel) hardware, only one problem instance (i.e. input data set) can be handled at a time. In this classical computing, increasing the number of bits increases the complexity of the problem and the time necessary to arrive at a solution. A quantum algorithm consists of a sequence of operations on a register, to transform it into a state which, when measured, yields the desired result with high probability. An n-bit quantum register can store an exponential amount of information. This paper aims at taking advantage of the superiority of quantum computing over classical computing to solve the problem of searching unstructured databases for a particular item or more than one item in good time. The general aim of this work is to establish the correctness and optimality of Grover’s quantum database search algorithm compared against classical database search methods in order to investigate the superiority or otherwise of quantum computing over classical computing. This is followed by a simulation of the algorithm using a classical computer, namely through functions that are present in MATLAB, referred to as “Quantum Computing Functions”. Povzetek: Clanek predstavlja implementacijo kvantnega iskanja v nestrukturiranih bazah.