Query complexity for searching multiple marked states from an unsorted database

Bin Shang

REVIEW

Query complexity for searching multiple marked states from an unsorted database

Bin Shang

Quantum Physics · Submitted 10 Apr 2006 · 12 references

Pith's verdict: The central query-complexity formula is wrong on at least two independent grounds, and the qualitative result is already known; desk reject.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 4 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/0604059 (version 1)

Pith IDW7X635IS, Pith's permanent record of this paper and its review

CitationBin Shang. "Query complexity for searching multiple marked states from an unsorted database." arXiv:quant-ph/0604059 (2006). https://pith.science/paper/W7X635IS

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Quick note on quant-ph/0604059. The punchline: the central derivation does not hold. The paper claims a closed-form query count for finding all m marked states, but the schedule it analyzes has overall success probability about (1−δ)^(m−1), not 1−δ, because it budgets δ per step rather than across the whole run. So Eq. (2) is not a solution to the stated problem.

There is also an internal algebra slip: the Step i geometric series is written with ratio 1/m, but the solved value for r_i uses ratio (i−1)/m. Those are different numbers unless i=2. The off-by-one exponent in the failure term compounds the issue. Either way, the quantitative result is not established.

What is worth credit: the paper asks a sensible question — what does it cost to find all marked states, not just one — and it is explicit about the recall-oriented motivation. The examples show the proposed r grows with m and with 1/δ, which is the right qualitative direction. But that direction is already known: amplitude amplification gives O(sqrt(N/m)) per run and O(sqrt(N m)) overall for finding all m solutions, and refs [3,4] cover multiple-solution Grover. So the novelty is low.

The subroutine assumptions are also unproven. The "generalized Long's algorithm" is defined as repeating Long's algorithm until all marked states are found — that is the outer loop, not a multi-solution algorithm. There is no proof that a single run returns a marked state with certainty in O(sqrt(N/m)) queries, nor that the output is uniform over the marked states. The geometric argument relies on that uniformity. Without it, the probabilities (i−1)/m fail.

The duality-computer section is essentially a pointer to Long's and the author's own prior work. Even if the quoted m log(N/m) bound is correct, there is no derivation here, so it cannot be evaluated. Self-citation alone isn't a flaw, but here it carries the whole section.

Bottom line: this paper is not ready for peer review. The main formula is wrong on its own terms, the qualitative result is known, and the new section is unsubstantiated. I would desk reject. If the author revises, the fix list is clear: allocate failure probability across all m steps, correct the geometric series, and prove or cite a real multi-solution subroutine with the uniformity property. The only readers who might get something are those unfamiliar with amplitude amplification, but they'd be better served by the standard references.

Referee report

Significance

The problem addressed is natural, and the claimed scaling q ~ sqrt(N m) ln m ln(1/δ) would be a useful benchmark for this task. However, the derivation contains multiple load-bearing algebraic and probabilistic errors, the key subroutine is not actually specified or proved, and the duality-computer section is an unsupported outline that relies on the author's own prior work. The paper does not include machine-checked proofs, reproducible code, or parameter-free derivations beyond an elementary calculation that is itself incorrect. As a result, the quantitative claim in Eq. (2) is not established, and the qualitative conclusion that query complexity increases with the number of marked states, while plausible, is not rigorously supported by the presented analysis.

Major objections (4)

[Step i (displayed geometric series)] The geometric series displayed for Step i uses ratio 1/m in every term after the first, but the conclusion sets ((i−1)/m)^{r_i} = δ. These are algebraically inconsistent: for i > 2 the probability of resampling an already-found state is (i−1)/m, not 1/m. With the correct ratio, the equation should be sum_{j=0}^{r_i} ((i−1)/m)^j ((m−i+1)/m) = 1 − ((i−1)/m)^{r_i+1} = 1 − δ, giving r_i = ln(1/δ)/ln(m/(i−1)) − 1. The displayed series, the intermediate equation, and the final formula in Eq. (2) therefore do not follow from one another, and the off-by-one exponent also affects the quantitative result.
[Problem description and Result, Eq. (2)] The problem statement requires overall success probability at least 1−δ, but the construction targets success probability 1−δ independently in every step. Since Step 1 is treated as certain, the overall success probability of the prescribed schedule is at most (1−δ)^{m−1}, which is strictly less than 1−δ for every m ≥ 3 and 0 < δ < 1. For example, with m = 10 and δ = 0.01, the schedule succeeds with probability about 0.913, not 0.99. A correct construction must allocate failure probability δ/m to each step, which would replace every ln(1/δ) in Eq. (2) with ln(m/δ) and introduce an additional m-dependent term. Thus Eq. (2) does not solve the stated problem.
[Generalized Long's algorithm] The 'generalized Long's algorithm' is defined as 'repeat Long's algorithm until all marked states have been found,' which is a restatement of the outer loop rather than a subroutine specification. The subsequent calculation requires that a single run of the subroutine finds a marked state with certainty in O(sqrt(N/m)) queries and that the output is uniformly distributed over the m marked states. Neither property is proved or cited. Uniformity might follow by symmetry from a fully symmetric algorithm, but certainty and the O(sqrt(N/m)) cost for multiple solutions are nontrivial and are asserted without support. Since the probabilities (i−1)/m and (m−i+1)/m in Steps 2 through m depend on this uniformity assumption, the derived r_i values are unsupported.
[The search problem on a duality computer] This section asserts that on a duality computer one can find all m marked states with certainty within m log(N/m) queries using log N 'dubits', and that found states can be deleted in O(1) time and space. The only references given are Long's papers and the author's own prior manuscript, and 'dubit' is never defined. Because this section is presented as showing an advantage over the main algorithm, the lack of any derivation or independent verification is a load-bearing gap for that part of the paper.

Minor objections (4)

[Throughout] There are several typographical and wording issues: 'devote' should be 'denote', 'educe' should be 'deduce', and the phrase 'with no less than overall probability of success 1 − δ' is awkward.
[Figures] The figures are referenced by captions but the text does not clearly describe what is plotted beyond 'f(m)' and 'f(δ)'; the axes and units should be labeled more explicitly.
[References] Reference [6] gives 'quant-ph/010607', which is incomplete, and several references lack full bibliographic details (e.g., [4] and [11] report only preprint numbers).
[Header date] The manuscript is dated 'October 8, 2018' despite being an arXiv submission from 2006; this discrepancy should be explained or corrected.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

This paper derives the query complexity for finding all m marked states from an unsorted quantum database by repeatedly running a certainty version of Grover's algorithm, obtaining q = [1 + sum_{k=1}^{m-1} ln(delta^{-1})/ln(m/k)]…

The reading

This paper asks how many oracle queries a quantum search must make when the goal is to find *all* marked states in an unsorted database, not just one. The answer it proposes is to run Long's certainty version of Grover's algorithm repeatedly until every marked state has appeared, and it derives the total cost as q = [1 + \sum_{k=1}^{m-1} \ln(\$delta^{{-1}}$)/\ln(m/k)] O(\sqrt{N/m}) queries for overall success probability at least 1 - \delta. In rough terms this behaves like \sqrt{N m} \ln m \ln(1/\delta), so the price of recall is a factor that grows with the number of marked states. The paper also describes a duality-computer algorithm that deletes found states at O(1) cost and achieves m \log(N/m) queries, avoiding the repeated-search overhead.

What carries the argument

The engine is Long's algorithm, a variant of Grover's search that finds a single marked state with certainty. The paper generalizes it to multiple marked states by the simplest possible strategy: run the algorithm, record which marked state is returned, and repeat until all m have been seen. The analysis models each step as a geometric series: at step i, with i-1 states already found, a fresh run returns an old state with probability (i-1)/m and a new state with probability (m-i+1)/m, so the number of runs needed to see a new state with probability 1-\delta is r_i = \ln(\$delta^{{-1}}$)/\ln(m/(i-1)). The second part of the paper uses Long's duality-computer model, in which found states are erased in O(1) time using log N 'dubits', eliminating the repeated-run overhead and yielding m \log(N/m) queries.

Extended reading notes

Core claim

The central claim is equation (2): after dividing the search into m steps and letting r_i denote the number of runs of Long's algorithm needed to find the i-th new state with probability 1-\delta, the total number of oracle queries is q = [1 + \sum_{k=1}^{m-1} \ln(\$delta^{{-1}}$)/\ln(m/k)] O(\sqrt{N/m}). Each run costs O(\sqrt{N/m}) queries; the geometric series at step i has failure ratio (i-1)/m, and solving ((i-1)/m)^{r_i} = \delta gives r_i = \ln(\$delta^{{-1}}$)/\ln(m/(i-1)). Summing these run counts yields the displayed bound. On a duality computer, the paper claims the same problem is solved with certainty in m \log(N/m) queries, because already-found states can be deleted in constant time.

Load-bearing premise

The load-bearing premise is that each run of the generalized Long algorithm outputs a uniformly random marked state, so at step i the probability of drawing an already-found state is exactly (i-1)/m and the probability of a new state is (m-i+1)/m.

Editorial extensions

If this is right

If equation (2) is correct, collecting all m marked states costs O(\sqrt{N/m}) \cdot \ln(1/\delta) \cdot \sum_{k=1}^{m-1} 1/\ln(m/k) oracle queries, which grows roughly as \sqrt{N m} \ln m \ln(1/\delta).
For m = 1 the formula reduces to O(\sqrt{N}) queries with certainty, matching Long's original single-state result.
The bound makes the recall-vs-cost tradeoff explicit: doubling the number of marked states increases the total query count by more than a factor of two once the sum over k is included.
The duality-computer algorithm, if valid, achieves m \log(N/m) queries by deleting found states at constant cost, which improves on the repeated-search approach by removing the \ln m factor.
Comparing with classical exhaustive search that needs O(N) queries, the quantum bound still offers a quadratic speedup when m \ll N, but the speedup erodes as m approaches N.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The uniformity assumption is the fragile point: a multiple-solution generalization of Long's algorithm does not obviously return marked states with equal probability, and the paper does not prove it; if the distribution is peaked, the probabilities (i-1)/m and (m-i+1)/m in the geometric series would need to be replaced by state-dependent values, and equation (2) would become an upper or lower boun
The stepwise analysis implicitly assumes that finding an already-seen state carries no memory across runs; a more refined model might track the amplitude distribution, so the sum over k could be an overestimate (or underestimate) of the true coupon-collector cost.
The duality-computer result points to a general design principle: any architecture that can delete or mask solved target states at low cost removes the coupon-collector overhead; testing this on other quantum computing models could be a productive extension.
One could test the formula numerically for small N and m: simulate Long's algorithm with multiple marked states, measure the distribution of first returns, and compare the empirical r_i with \ln(1/\delta)/\ln(m/(i-1)).

Original abstract

An important and usual problem is to search all states we want from a database with a large number of states. In such, recall is vital. Grover's original quantum search algorithm has been generalized to the case of multiple solutions, but no one has calculated the query complexity in this case. We will use a generalized algorithm with higher precision to solve such a search problem that we should find all marked states and show that the practical query complexity increases with the number of marked states. In the end we will introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,165 input tokens.

What the abstract itself states, as probabilities: claims first 0.58 · states limitation 0.20 · human participants 0.02 · controlled comparison 0.21 · randomized assignment 0.01 · states quantitative result 0.11 · compares with prior results 0.81 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

An important and usual problem is to search all states we want from a database with a large number of states. In such, recall is vital. Grover's original quantum search algorithm has been generalized to the case of multiple solutions, but no one has calculated the query complexity in this case. We will use a generalized algorithm with higher precision to solve such a search problem that we should find all marked states and show that the practical query complexity increases with the number of marked states. In the end we will introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	An important and usual problem is to search all states we want from a database with a large number of states.	background 1.00	0.04	0.03	asserted 1.00
s1	In such, recall is vital.	background 1.00	0.04	0.02	asserted 0.97
s2	Grover's original quantum search algorithm has been generalized to the case of multiple solutions, but no one has calculated the query complexity in this case.	gap 0.99	0.05	0.06	asserted 1.00
s3	We will use a generalized algorithm with higher precision to solve such a search problem that we should find all marked states and show that the practical query complexity increases with the number of marked states.	contribution 0.84	0.89	0.71	asserted 1.00
s4	In the end we will introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.	contribution 0.93	0.88	0.16	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.53 · evidence from proof or derivation 0.95.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (12)

[1]

L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of 28th Annual ACM Sym- posium on Theory of Computing, 1996, pp. 212–219

View on Pith 1996
[2]

L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters, Vol. 79, no. 2, 14 July 1997, pp. 325–328

View on Pith 1997
[3]

Michel Boyer, Gilles Brassard, Peter Høyer and Alain Tapp,Tight bounds on quantum searching”, Fortschritte Der Physik, specialissue on quantum computing and quantum cryptography, 1998, Vol. 46,pp. 493–505

View on Pith 1998
[4]

G. Brassard, P. Ho.yer, M. Mosca, and A. Tapp, quant-ph/0005055

View on Pith Pith review arXiv
[5]

P. Høyer, Phys. Rev. A 62, 052304, 2001

View on Pith 2001
[6]

G. L. Long, Grover algorithm with zero theoretical fail- ure rate,Phys. Rev. A, Vol. 64, 022307, 2001. quant- ph/010607

View on Pith 2001
[7]

Beals, Robert, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf, Quantum lower bounds by polynomials, Proceedings of 39th Annual Symposium on Foundations of Computer Science,November 1998, pp. 352C361

View on Pith 1998
[8]

A. Ambainis. Quantum lower bounds by quantum arguments, J. Comput. Sys. Sci. 64:750–767, 2002. quant-ph/0002066

View on Pith Pith review arXiv 2002
[9]

P. Høyer, J. Neerbek, and Y. Shi. Quantum complexi- ties of ordered searching, sorting,and element distinct- ness. Algorithmica, 34(4):429–448, 2002

View on Pith 2002
[10]

C.Zalka, Grovers quantum searching algorithm is opti- mal, Phys. Rev. A60, 2746 1999, quant-ph/9711070

View on Pith Pith review arXiv 1999
[11]

G. L. Long. The general quantum interference princi- ple and the duality computer(2005), to appear in Com- mun.Theor.Phys. quant-ph/0512120

View on Pith Pith review arXiv 2005
[12]

B. Shang. A summary on two new algorithms for Grover’s unsorted database search problem. quant-ph/0603210

View on Pith Pith review arXiv

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of 28th Annual ACM Sym- posium on Theory of Computing, 1996, pp. 212–219

View on Pith 1996

[2] [2]

L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters, Vol. 79, no. 2, 14 July 1997, pp. 325–328

View on Pith 1997

[3] [3]

Michel Boyer, Gilles Brassard, Peter Høyer and Alain Tapp,Tight bounds on quantum searching”, Fortschritte Der Physik, specialissue on quantum computing and quantum cryptography, 1998, Vol. 46,pp. 493–505

View on Pith 1998

[4] [4]

G. Brassard, P. Ho.yer, M. Mosca, and A. Tapp, quant-ph/0005055

View on Pith Pith review arXiv

[5] [5]

P. Høyer, Phys. Rev. A 62, 052304, 2001

View on Pith 2001

[6] [6]

G. L. Long, Grover algorithm with zero theoretical fail- ure rate,Phys. Rev. A, Vol. 64, 022307, 2001. quant- ph/010607

View on Pith 2001

[7] [7]

Beals, Robert, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf, Quantum lower bounds by polynomials, Proceedings of 39th Annual Symposium on Foundations of Computer Science,November 1998, pp. 352C361

View on Pith 1998

[8] [8]

A. Ambainis. Quantum lower bounds by quantum arguments, J. Comput. Sys. Sci. 64:750–767, 2002. quant-ph/0002066

View on Pith Pith review arXiv 2002

[9] [9]

P. Høyer, J. Neerbek, and Y. Shi. Quantum complexi- ties of ordered searching, sorting,and element distinct- ness. Algorithmica, 34(4):429–448, 2002

View on Pith 2002

[10] [10]

C.Zalka, Grovers quantum searching algorithm is opti- mal, Phys. Rev. A60, 2746 1999, quant-ph/9711070

View on Pith Pith review arXiv 1999

[11] [11]

G. L. Long. The general quantum interference princi- ple and the duality computer(2005), to appear in Com- mun.Theor.Phys. quant-ph/0512120

View on Pith Pith review arXiv 2005

[12] [12]

B. Shang. A summary on two new algorithms for Grover’s unsorted database search problem. quant-ph/0603210

View on Pith Pith review arXiv