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

Deleting a marked item from an unsorted database with a single query

Yang Liu, Long, Gui Lu

Published Oct 17, 2007• 4 citations
arXivHTMLPDF

Abstract

In this Letter we present a quantum deletion algorithm that deletes a marked state from an unsorted database of $N$ items with only a single query. This algorithm achieves exponential speedup compared with classical algorithm where O(N) number of query is required. General property of this deleting algorithm is also studied.

DOI
10.48550/arxiv.0710.3301

Related papers

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 Query Complexity for Searching Multiple Marked States from an Unsorted Database

Shang Bin

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.

arXiv:quant-ph/0604059•Communications in Theoretical Physics•Aug 1, 2007•3 citations

DELETING A MARKED BASIS-STATE FROM AN EVEN SUPERPOSITION OF ALL BASIS-STATES WITH A SINGLE QUERY

Yang Liu, GUI LU LONG

We present a quantum deletion algorithm that deletes a marked basis-state from an even superposition of all N basis-states. This algorithm uses only a single query and achieves exponential speed-up compared with classical analog where Θ(N) queries are required.

International Journal of Quantum Information•Mar 1, 2009•7 citations

Quantum database search can do without sorting

Apoorva D. Patel

Sorting is a fundamental computational process that facilitates subsequent searching of a database. It can be thought of as factorization of the search process. The location of a desired item in a sorted database can be found by classical queries that inspect one letter of the label at a time. For an unsorted database, no such classical quick search algorithm is available. If the database permits quantum queries, however, then mere digitization is sufficient for efficient search. Sorting becomes redundant with the quantum superposition of states. A quantum algorithm is written down that locates the desired item in an unsorted database a factor of two faster than the best classical algorithm can in a sorted database. This algorithm has close resemblance to the assembly process in DNA replication.

arXiv:quant-ph/0012149•Physical Review A•Aug 15, 2001•18 citations

Fetching marked items from an unsorted database in NMR ensemble computing

Xiao Li, Gui‐Lu Long

The speedup of an unsorted database search has always been a challenging problem not only in classical computation but also in quantum computation. We propose a fetching algorithm for a Liouville space nuclear magnetic resonance (NMR) ensemble computing to fetch a marked item from an unsorted database directly. This algorithm achieves the absolute optimum in an unsorted database search problem: a single query. In fact, this algorithm also works well for fetching several unknown numbers of marked items. The computer simulation realization of the algorithm in a three-qubit homonuclear spin system is also presented. In addition, a compromised version of the algorithm, which reduces the demand on the structure of the molecules for the NMR experiment, is also devised.

arXiv:quant-ph/0112162•Physical Review A•Nov 22, 2002•25 citations

Quantum Computers Can Search Arbitrarily Large Databases by a Single Query

Lov K. Grover

This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least ${log}_{2}N$ queries, which it would achieve by using a binary search.

arXiv:quant-ph/9706005•Physical Review Letters•Dec 8, 1997•434 citations
In this Letter we present a quantum deletion algorithm that deletes a marked state from an unsorted database of NNN items with only a single query. This algorithm achieves exponential speedup compared with classical algorithm where O(N) number of query is required. General property of this deleting algorithm is also studied.
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.
An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.
Sorting is a fundamental computational process that facilitates subsequent searching of a database. It can be thought of as factorization of the search process. The location of a desired item in a sorted database can be found by classical queries that inspect one letter of the label at a time. For an unsorted database, no such classical quick search algorithm is available. If the database permits quantum queries, however, then mere digitization is sufficient for efficient search. Sorting becomes redundant with the quantum superposition of states. A quantum algorithm is written down that locates the desired item in an unsorted database a factor of two faster than the best classical algorithm can in a sorted database. This algorithm has close resemblance to the assembly process in DNA replication.
The speedup of an unsorted database search has always been a challenging problem not only in classical computation but also in quantum computation. We propose a fetching algorithm for a Liouville space nuclear magnetic resonance (NMR) ensemble computing to fetch a marked item from an unsorted database directly. This algorithm achieves the absolute optimum in an unsorted database search problem: a single query. In fact, this algorithm also works well for fetching several unknown numbers of marked items. The computer simulation realization of the algorithm in a three-qubit homonuclear spin system is also presented. In addition, a compromised version of the algorithm, which reduces the demand on the structure of the molecules for the NMR experiment, is also devised.
This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least log2N{log}_{2}Nlog2​N queries, which it would achieve by using a binary search.