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

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

Yang Liu, GUI LU LONG

Published Mar 1, 2009• 7 citations
Publisher

Abstract

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.
DOI
10.1142/s0219749909005201

Related papers

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

Yang Liu, Long, Gui Lu

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.

arXiv:0710.3301•Oct 17, 2007•4 citations

Efficient Quantum State Synthesis with One Query

Gregory Rosenthal

We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state |ψ〉 there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of |ψ〉. Previous algorithms for this problem either used a linear number of queries and polynomial time, or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime. As corollaries we do the following:

arXiv:2306.01723•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•15 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•1 citation

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

A quantum algorithm that deletes marked states from an arbitrary database

Yang Liu, Xiaoping Ouyang

Chinese Science Bulletin•Jul 1, 2013•19 citations

Sophisticated Quantum Search Without Entanglement

David Meyer

Grover's quantum search algorithm has recently been implemented without entanglement, by replacing multiple particles with a single particle having exponentially many states. We recall that all physical resources must be accounted for to quantify algorithm complexity, and that this scheme typically incurs exponential costs in some other resource(s). In particular, we demonstrate that a recent experimental realization requires exponentially increasing precision. There is, however, a quantum algorithm which searches a "sophisticated" database (not unlike a Web search engine) with a single query, but which we show does not require entanglement even for multiparticle implementations.

arXiv:quant-ph/0007070•Physical Review Letters•Aug 28, 2000•239 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.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
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.
Grover's quantum search algorithm has recently been implemented without entanglement, by replacing multiple particles with a single particle having exponentially many states. We recall that all physical resources must be accounted for to quantify algorithm complexity, and that this scheme typically incurs exponential costs in some other resource(s). In particular, we demonstrate that a recent experimental realization requires exponentially increasing precision. There is, however, a quantum algorithm which searches a "sophisticated" database (not unlike a Web search engine) with a single query, but which we show does not require entanglement even for multiparticle implementations.