arXiv:quant-ph/0006136

Finding Matches between Two Databases on a Quantum Computer

Mark Heiligman

Published Jun 30, 2000• 9 citations

Abstract

Given two unsorted lists each of length N that have a single common entry, a quantum computer can find that matching element with a work factor of $O(N^{3/4}\log N)$ (measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is $O(N^{1/2})$. The quantum algorithm that accomplishes this consists of an inner Grover search combined with a partial sort all sitting inside of an outer Grover search.

DOI: 10.48550/arxiv.quant-ph/0006136

Related papers

Strength and Weakness in Grover's Quantum Search Algorithm

Ahmed Younes

arXiv:0811.4481Nov 27, 200817 citations

Sorting N elements using quantum entanglement sets

Ammar Odeh, Khaled M. Elleithy, Marwah Mohammad Almasri +1 more

To search for an element in an unsorted database, it requires O(N) operations using classical computers, where it takes only O(√ N) operations in quantum systems. In this paper, we provide an in-depth look at the existing quantum searching algorithms and emphasize the quantum entanglement feature to propose a new technique for sorting N elements and thus improve the sorting process.

International Conference on Innovative Computing TechnologyAug 1, 20137 citations

A Modification of Grover’s Quantum Search Algorithm

I. Ashraf, T. Mahmood, Vasudevan Lakshminarayanan

Abstract-We propose a quantum search method based on Grover’s algorithm. This algorithm is described and we show that to search for a single marked element from an unsorted search space of N elements, the number of queries are required using this algorithm when compared to for the Grover algorithm.

Aug 31, 20161 citation

Optimal quantum searching to find a common element of two sets

Avatar Tulsi

arXiv:1210.4648Oct 17, 20121 citation

Implementation of Database Search with Quantum Computing: Grover's Algorithm vs Linear Search

Sachin Khurana, Manisha J. Nene

International Conference on Ambient Intelligence, Knowledge Informatics and Industrial Electronics (AIKIIE)Nov 2, 20238 citations

An efficient quantum search engine on unsorted database

Heping Hu, Yingyu Zhang, Zhengding Lu

arXiv:0904.3060Apr 20, 20090 citations

arXiv:quant-ph/0006136

Finding Matches between Two Databases on a Quantum Computer

Mark Heiligman

Published Jun 30, 2000• 9 citations

arXiv HTML PDF

Abstract

Given two unsorted lists each of length N that have a single common entry, a quantum computer can find that matching element with a work factor of

O(N^{3/4}\log N)

(measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is

O(N^{1/2})

. The quantum algorithm that accomplishes this consists of an inner Grover search combined with a partial sort all sitting inside of an outer Grover search.

DOI: 10.48550/arxiv.quant-ph/0006136

Related papers

Strength and Weakness in Grover's Quantum Search Algorithm

Ahmed Younes

Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with $N$ records in $O(\sqrt{N})$ assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for $M>3N/4$ , where $M$ is the number of matches in the list.Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with $N$ records in $O(\sqrt{N})$ assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for $M>3N/4$, where $M$ is the number of matches in the list.

arXiv:0811.4481Nov 27, 200817 citations

Sorting N elements using quantum entanglement sets

Ammar Odeh, Khaled M. Elleithy, Marwah Mohammad Almasri +1 more

International Conference on Innovative Computing TechnologyAug 1, 20137 citations

A Modification of Grover’s Quantum Search Algorithm

I. Ashraf, T. Mahmood, Vasudevan Lakshminarayanan

Aug 31, 20161 citation

Optimal quantum searching to find a common element of two sets

Avatar Tulsi

Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.

arXiv:1210.4648Oct 17, 20121 citation

Implementation of Database Search with Quantum Computing: Grover's Algorithm vs Linear Search

Sachin Khurana, Manisha J. Nene

The present study aims to examine the real-world implications of Grover's algorithm, specifically focusing on its quadratic speedup in contrast to classical linear search techniques employed for unsorted databases. The objective is to bridge the gap between theoretical potential and practical application in the field of quantum computing. This study conducts a comprehensive analysis of Grover's Algorithm and traditional linear search across databases of varying sizes, uniquely contributing by empirically validating Grover's Algorithm's superior performance and aligning it with theoretical expectations. Significantly, the study expands its analysis to encompass larger databases, further affirming the algorithm's utility in handling growing database sizes. This study significantly contributes to the progress of quantum computing through the practical implementation of theoretical principles as well as enhancing the scientific community's understanding of quantum search algorithms and their relative efficacy.The present study aims to examine the real-world implications of Grover's algorithm, specifically focusing on its quadratic speedup in contrast to classical linear search techniques employed for unsorted databases. The objective is to bridge the gap between theoretical potential and practical application in the field of quantum computing. This study conducts a comprehensive analysis of Grover's Algorithm and traditional linear search across databases of varying sizes, uniquely contributing by empirically validating Grover's Algorithm's superior performance and aligning it with theoretical expectations. Significantly, the study expands its analysis to encompass larger databases, further affirming the algorithm's utility in handling growing database sizes. This study significantly contributes to the progress of quantum computing through the practical implementation of theoretical principles as well as enhancing the scientific community's understanding of quantum search algorithms and their relative efficacy.

International Conference on Ambient Intelligence, Knowledge Informatics and Industrial Electronics (AIKIIE)Nov 2, 20238 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.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.3060Apr 20, 20090 citations

Given two unsorted lists each of length N that have a single common entry, a quantum computer can find that matching element with a work factor of

O(N^{3/4}\log N)

(measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is

O(N^{1/2})

. The quantum algorithm that accomplishes this consists of an inner Grover search combined with a partial sort all sitting inside of an outer Grover search.

Grover's quantum search algorithm is considered as one of the milestone in the field of quantum computing. The algorithm can search for a single match in a database with

N

records in

O(\sqrt{N})

assuming that the item must exist in the database with quadratic speedup over the best known classical algorithm. This review paper discusses the performance of Grover's algorithm in case of multiple matches where the problem is expected to be easier. Unfortunately, we will find that the algorithm will fail for

M>3N/4

, where

M

is the number of matches in the list.

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.