pith. sign in

arxiv: 1907.03315 · v1 · pith:UFBPG4VSnew · submitted 2019-07-07 · 🪐 quant-ph

A Quantum Algorithm for Finding k-Minima

Kohei Miyamoto , Masakazu Iwamura , Koichi Kise This is my paper

Pith reviewed 2026-05-25 01:22 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum algorithmk-minimaamplitude amplificationquery complexitythreshold searchnearest neighbor searchclustering
0
0 comments X

The pith

A quantum algorithm finds the k smallest items among N with O(sqrt(k N)) queries by locating a threshold near the k-th smallest and applying generalized amplitude amplification.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proposes a quantum algorithm for finding the k minima in a dataset of size N. It achieves query complexity O(sqrt(k N)) by first searching for a threshold close to the k-th smallest value, then using a generalization of amplitude amplification to extract all k items without regard to order. This matches the complexity of prior work but is presented as simpler. The method is intended to apply directly to distance-based tasks such as k-nearest neighbor search, clustering, and classification. A brief proof is given for the query cost of the generalized amplitude amplification step.

Core claim

The algorithm searches for a good threshold near the k-th smallest datum and then applies a generalization of amplitude amplification to find all k marked items out of order, yielding overall query complexity O(sqrt(k N)). This is equivalent in cost to existing methods yet simpler in structure, and the generalization itself is shown to support the stated bound.

What carries the argument

Generalization of amplitude amplification that extracts all k marked items out of order.

If this is right

  • The algorithm adapts directly to k-nearest neighbor search.
  • It extends to clustering and classification problems.
  • It adds to the small set of quantum algorithms that return multiple answers.
  • The unordered extraction keeps the same O(sqrt(k N)) bound while avoiding ordering steps.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If threshold location stays efficient, the method could support quantum speedups in selection tasks on large unstructured data.
  • Unordered output might simplify integration with other quantum routines that do not require sorted results.
  • The approach could be tested on small instances to check whether the combined threshold-plus-amplification cost stays within the claimed bound.

Load-bearing premise

A threshold near the k-th smallest datum can be located with sufficiently few queries that the overall cost remains O(sqrt(k N)).

What would settle it

A calculation or experiment showing that locating such a threshold requires more than O(sqrt(k N)) queries in the worst case, or that the generalized amplitude amplification extracts the k items at higher cost, would falsify the claim.

Figures

Figures reproduced from arXiv: 1907.03315 by Kohei Miyamoto, Koichi Kise, Masakazu Iwamura.

Figure 1
Figure 1. Figure 1: FIG. 1. Quantum circuit is composed of a digital circuit [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Overview of AA. AA finds one index from [PITH_FULL_IMAGE:figures/full_fig_p003_4.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Quantum circuit of oracle [PITH_FULL_IMAGE:figures/full_fig_p004_8.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Example of the input [PITH_FULL_IMAGE:figures/full_fig_p004_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Example of indices, value and [PITH_FULL_IMAGE:figures/full_fig_p004_7.png] view at source ↗
Figure 9
Figure 9. Figure 9: FIG. 9. The updating process of threshold [PITH_FULL_IMAGE:figures/full_fig_p005_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: FIG. 10 [PITH_FULL_IMAGE:figures/full_fig_p005_10.png] view at source ↗
Figure 12
Figure 12. Figure 12: FIG. 12. This is an example case that each [PITH_FULL_IMAGE:figures/full_fig_p006_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: FIG. 13. An example of quantum circuit [PITH_FULL_IMAGE:figures/full_fig_p009_13.png] view at source ↗
read the original abstract

We propose a new finding $k$-minima algorithm and prove that its query complexity is $\mathcal{O}(\sqrt{kN})$, where $N$ is the number of data indices. Though the complexity is equivalent to that of an existing method, the proposed is simpler. The main idea of the proposed algorithm is to search a good threshold that is near the $k$-th smallest data. Then, by using the generalization of amplitude amplification, all $k$ data are found out of order and the query complexity is $\mathcal{O}(\sqrt{kN})$. This generalization of amplitude amplification is also not well discussed and we briefly prove the query complexity. Our algorithm can be directly adapted to distance-related problems like $k$-nearest neighbor search and clustering and classification. There are few quantum algorithms that return multiple answers and they are not well discussed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a quantum algorithm to find the k smallest elements in an unsorted database of N items. It claims an oracle query complexity of O(√(kN)) by first locating a threshold near the k-th order statistic and then applying a generalized amplitude amplification procedure to extract all k marked items (out of order). The approach is presented as simpler than existing methods while matching their complexity bound, with potential direct adaptation to k-nearest-neighbor search, clustering, and classification. The generalization of amplitude amplification is noted as briefly proved in the text.

Significance. If the O(√(kN)) bound is established with a complete error analysis and the threshold-finding phase is shown to be sub-dominant for arbitrary real-valued inputs, the result would supply a useful primitive for quantum algorithms returning multiple solutions. The claimed simplicity relative to prior work could also aid implementation in distance-based tasks. However, the current presentation supplies no derivation steps, recurrence relations, or worst-case analysis, so the significance remains conditional on verification of the central complexity claim.

major comments (2)
  1. [Abstract / Main idea] Abstract, paragraph beginning 'The main idea...': the threshold-finding phase is described only as 'search a good threshold' with no algorithm, recurrence, or explicit query-cost bound supplied. The overall O(√(kN)) claim requires this phase to use o(√(kN)) queries in the worst case; without that analysis the headline bound is not secured.
  2. [Abstract] Abstract, sentence 'This generalization of amplitude amplification is also not well discussed and we briefly prove the query complexity': no equations, state definitions, or induction steps appear for the generalized amplitude amplification that extracts k items. The central complexity claim therefore rests on an unexpanded argument whose correctness cannot be verified from the supplied text.
minor comments (1)
  1. [Abstract] The abstract states the complexity is 'equivalent to that of an existing method' but does not cite the reference or compare the constants or assumptions; adding the citation would clarify the novelty claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We agree that the abstract and presentation require additional explicit details to fully secure the complexity claims, and we will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract / Main idea] Abstract, paragraph beginning 'The main idea...': the threshold-finding phase is described only as 'search a good threshold' with no algorithm, recurrence, or explicit query-cost bound supplied. The overall O(√(kN)) claim requires this phase to use o(√(kN)) queries in the worst case; without that analysis the headline bound is not secured.

    Authors: We agree that the abstract is too high-level on the threshold-finding phase and that an explicit algorithm, recurrence, and worst-case query-cost bound (showing it is sub-dominant) are needed to establish the O(√(kN)) claim, including for arbitrary real-valued inputs and with complete error analysis. We will revise the manuscript to supply these details in both the abstract and the body. revision: yes

  2. Referee: [Abstract] Abstract, sentence 'This generalization of amplitude amplification is also not well discussed and we briefly prove the query complexity': no equations, state definitions, or induction steps appear for the generalized amplitude amplification that extracts k items. The central complexity claim therefore rests on an unexpanded argument whose correctness cannot be verified from the supplied text.

    Authors: We agree that the brief proof of the generalized amplitude amplification lacks the requested equations, state definitions, and induction steps, making verification difficult from the current text. We will expand this section in the revised manuscript to include those elements. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is an algorithmic construction without self-referential reductions.

full rationale

The abstract and description present a new quantum algorithm whose claimed O(sqrt(kN)) query complexity rests on two steps: locating a threshold near the k-th order statistic and applying a generalized amplitude amplification whose query cost is 'briefly proved.' No equations, fitted parameters, or self-citations appear in the supplied text. The threshold-search precondition is described only at a high level without an explicit recurrence or worst-case bound, but this is an incompleteness in the proof rather than a definitional loop (no quantity is defined in terms of itself). The generalization of amplitude amplification is presented as an independent technical contribution. Because none of the enumerated circularity patterns (self-definitional, fitted-input-as-prediction, load-bearing self-citation, etc.) are instantiated by quoted text, the score remains low.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are stated. Standard quantum-oracle and amplitude-amplification assumptions are implicitly required but not enumerated.

pith-pipeline@v0.9.0 · 5671 in / 1139 out tokens · 19056 ms · 2026-05-25T01:22:11.275344+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages · 6 internal anchors

  1. [1]

    Many quantum circuits use both a digital circuit and an analog circuit

    We have to mention that the input and output of this digi- tal circuit can be superposition in this paper. Many quantum circuits use both a digital circuit and an analog circuit. Moreover, quantum bits sometimes go back and force digital representation and analog representation. We use AA as a base of our explanation. AA searches one index that satisfies a...

    work page

  2. [2]

    d is a dimension of g(x)

    The gate complexity of this oracle g is Og(log d) as we described in Section II. d is a dimension of g(x). In other words, d is a number of quantum bit. For more detail, see [14, 16–18]. The input x and output g(x) of quantum circuit g is also binary representation and can be superposed. Therefore output can be superposed if input index x is superposed. F...

    work page

  3. [3]

    However, we x g x |0⟩ CM P |0⟩ |0⟩ ft(x) |0⟩ g |0⟩ |0⟩ T |0⟩ FIG

    In this circuit, the upper input x and the middle output ft(x) are used in AA and other inputs and outputs are not used. However, we x g x |0⟩ CM P |0⟩ |0⟩ ft(x) |0⟩ g |0⟩ |0⟩ T |0⟩ FIG. 8. Quantum circuit of oracle ft. The index t is created by the gate T in the circuit. In this example, CMP gate is symmetry. The center input is for output ft(x) and abov...

    work page

  4. [4]

    have to keep unchanged of inputs and outputs so as not to influence the states of ft(x)

    Otherwise, returns 1. have to keep unchanged of inputs and outputs so as not to influence the states of ft(x). IV. FINDING MINIMUM ALGORITHM We begin with presenting an overview of FM al- gorithm because it is a simple application of AA and helps understand the succeeding algorithms. An ex- ample of the procedure of the algorithm is shown in Figure

    work page

  5. [5]

    Oracle ft(x) is a function that marks index x such that g(x) < g (t)

    This algorithm finds the minimum from D with the complexity of Oq( √ N ) by iteratively up- dating threshold index t by oracle ft. Oracle ft(x) is a function that marks index x such that g(x) < g (t). That is, ft(x) = { 1, if g(x) < g (t), 0, if g(x) ≥ g(t). (2) The oracle marks the indices that have smaller val- ues than the value of threshold t. Setting ...

    work page

  6. [6]

    Select threshold index t from D uniformly at random

    work page

  7. [7]

    (a) Find index x such that ft(x) = 1

    Repeat the following process more than 22.5 √ N + 1.4 log2 N times. (a) Find index x such that ft(x) = 1. (b) Set the found index x as the threshold index t

    work page

  8. [8]

    5 small g(x) big t → Step 1 f (x) = 1 f (x) = 0 Step 2 f (x) = 1 t f (x) = 0 Step 3 f (x) = 1 t f (x) = 0 Step 4 f (x) = 1 t f (x) = 0 Step 5 t f (x) = 0 FIG

    Return t as the index that has the minimum value in D. 5 small g(x) big t → Step 1 f (x) = 1 f (x) = 0 Step 2 f (x) = 1 t f (x) = 0 Step 3 f (x) = 1 t f (x) = 0 Step 4 f (x) = 1 t f (x) = 0 Step 5 t f (x) = 0 FIG. 9. The updating process of threshold t in FM algorithm. The vertical axis represents the value of in dices. When the first threshold t is select...

    work page

  9. [9]

    t is randomly chosen from T

    work page

  10. [10]

    In the case of 2, which is the best case, such t is ob- tained by finding maximum algorithm [26]

    t is selected so as to maximize g(t). In the case of 2, which is the best case, such t is ob- tained by finding maximum algorithm [26]. Hence, its computational burden is O( √ k). It can be ig- nored, as it is small enough compared to the com- plexity of the whole algorithm (i.e., O( √ kN )). In addition to that, we have to keep the elements of T without d...

    work page

  11. [11]

    Initialize set T as randomly chosen k indices from D

    work page

  12. [12]

    (a) Randomly select a threshold index t from T

    Repeat the following forever. (a) Randomly select a threshold index t from T . (b) Find index x such that fT (x) = 1. (c) Find tmax such that tmax = argmax t∈ T g(t) [27]. (d) Replace threshold index tmax with x. In this algorithm, T is updated in a step-by-step manner and each updating step replaces the index that has the maximum value in T with the foun...

    work page

  13. [13]

    Apply FM algorithm and save the indices of the lastly found k thresholds

    work page

  14. [14]

    Once we find such a threshold, we can find all marked k′ indices by applying searching all marked k-indices algorithm

    Apply the binary search on the k indices of thresholds. Once we find such a threshold, we can find all marked k′ indices by applying searching all marked k-indices algorithm. This algorithm searches all el- ements in the set {x | x ∈ D, f (x) = 1 }. For sim- plicity, we assume that O(k′) = O(k). Let T be a set of already found indices in the step of searchi...

    work page

  15. [15]

    Apply FM algorithm to D and save the last k indices of FM algorithm step

    work page

  16. [16]

    The comparison key is |M F M| that is derived by QC algorithm

    Search threshold index tk′ by a binary search on k indices. The comparison key is |M F M| that is derived by QC algorithm

    work page

  17. [17]

    The total query complexity is given as O( √ N log k) + O( √ kN ) = O( √ kN )

    Apply finding all marked k-indices algorithm with threshold tk′. The total query complexity is given as O( √ N log k) + O( √ kN ) = O( √ kN ). (10) —— VII. CONCLUSION In this paper, we proposed a new finding k-minima algorithm and derived its query complexity. Our al- gorithm is easier to understand and more elegant than D¨ urr’s algorithm [2]. Finding k-mi...

    work page

  18. [18]

    A Quantum Algorithm for Finding the Minimum

    Christoph D¨ urr and Peter Høyer. A quantum al- gorithm for finding the minimum. arXiv preprint quant-ph/9607014, 1996

    work page internal anchor Pith review Pith/arXiv arXiv 1996

  19. [19]

    Quantum query complexity of some graph problems

    Christoph D¨ urr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing , 35(6):1310–1328, 2006

    work page 2006

  20. [20]

    Quantum counting

    Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum counting. In International Colloquium on Automata, Languages, and Programming , pages 820–831. Springer, 1998

    work page 1998

  21. [21]

    Quantum amplitude amplification and estimation

    Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Jr. Samuel J. Lomonaco, editor, Quantum Computation and Quantum Information , volume 305, pages 53–74. American Mathematical Society, 2002. 8

    work page 2002

  22. [22]

    Tight bounds on quantum searching

    Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik , 46(4-5):493–505, 1998

    work page 1998

  23. [23]

    Lov K. Grover. A fast quantum mechanical algo- rithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996

    work page 1996

  24. [24]

    Quantum search algorithms

    Andris Ambainis. Quantum search algorithms. ACM SIGACT News , 35(2):22–35, 2004

    work page 2004

  25. [25]

    A new quantum lower bound method, with an application to strong direct product theorem for quantum search

    Andris Ambainis. A new quantum lower bound method, with an application to strong direct product theorem for quantum search. arXiv preprint quant- ph/0508200, 2005

    work page arXiv 2005

  26. [26]

    Quantum and classical strong direct product theorems and optimal time-space trade- offs

    Hartmut Klauck, Robert ˇSpalek, and Ronald De Wolf. Quantum and classical strong direct product theorems and optimal time-space trade- offs. SIAM Journal on Computing , 36(5):1472–1493, 2007

    work page 2007

  27. [27]

    A note on the search for k elements via quantum walk

    Sebastian D¨ orn and Thomas Thierauf. A note on the search for k elements via quantum walk. Information Processing Letters, 110(22):975–978, 2010

    work page 2010

  28. [28]

    Quantum speed-up for unsupervised learn- ing

    Esma A ¨ ımeur, Gilles Brassard, and S´ ebastien Gambs. Quantum speed-up for unsupervised learn- ing. Machine Learning, 90(2):261–287, 2013

    work page 2013

  29. [29]

    Quantum Algorithms for Nearest-Neighbor Methods for Supervised and Unsupervised Learning

    Nathan Wiebe, Ashish Kapoor, and Krysta Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. arXiv preprint arXiv:1401.2142 , 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  30. [30]

    Quantum clustering algorithms

    Esma A ¨ ımeur, Gilles Brassard, and S´ ebastien Gambs. Quantum clustering algorithms. In Proceed- ings of the 24th international conference on machine learning, pages 1–8, 2007

    work page 2007

  31. [31]

    Quantum algorithms for supervised and unsupervised machine learning

    Seth Lloyd, Masoud Mohseni, and Patrick Reben- trost. Quantum algorithms for supervised and unsupervised machine learning. arXiv preprint arXiv:1307.0411, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  32. [32]

    An introduction to quantum machine learn- ing

    Maria Schuld, Ilya Sinayskiy, and Francesco Petruc- cione. An introduction to quantum machine learn- ing. Contemporary Physics, 56(2):172–185, 2015

    work page 2015

  33. [33]

    Creating super- positions that correspond to efficiently integrable probability distributions

    Lov Grover and Terry Rudolph. Creating super- positions that correspond to efficiently integrable probability distributions. arXiv preprint quant- ph/0208112, 2002

    work page arXiv 2002

  34. [34]

    Quantum Networks for Generating Arbitrary Quantum States

    Phillip Kaye and Michele Mosca. Quantum networks for generating arbitrary quantum states. arXiv preprint quant-ph/0407102, 2004

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  35. [35]

    Efficient state preparation for a register of quantum bits

    Andrei N Soklakov and R¨ udiger Schack. Efficient state preparation for a register of quantum bits. Physical Review A , 73(1):012307, 2006

    work page 2006

  36. [36]

    An improved quan- tum fourier transform algorithm and applications

    Lisa Hales and Sean Hallgren. An improved quan- tum fourier transform algorithm and applications. In Foundations of Computer Science, 2000. Proceed- ings. 41st Annual Symposium on , pages 515–525, 2000

    work page 2000

  37. [37]

    Quantum lower bounds by polynomials

    Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf. Quantum lower bounds by polynomials. Journal of the ACM , 48(4):778–797, 2001

    work page 2001

  38. [38]

    Nielsen and Isaac L

    Michael A. Nielsen and Isaac L. Chuang. Quan- tum Computation and Quantum Information . Cam- bridge University Pr., 2001

    work page 2001

  39. [39]

    Quantum lower bounds by quan- tum arguments

    Andris Ambainis. Quantum lower bounds by quan- tum arguments. Journal of Computer and System Sciences, 64(4):750–767, 2002

    work page 2002

  40. [40]

    All Quantum Adversary Methods are Equivalent

    Robert Spalek and Mario Szegedy. All quantum adversary methods are equivalent. arXiv preprint quant-ph/0409116, 2004

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  41. [41]

    A new quantum lower bound method, with applications to direct product theorems and time- space tradeoffs

    Andris Ambainis, Robert ˇSpalek, and Ronald de Wolf. A new quantum lower bound method, with applications to direct product theorems and time- space tradeoffs. Algorithmica, 55(3):422–461, 2009

    work page 2009

  42. [42]

    Quantum analog-digital conversion

    Kosuke Mitarai, Masahiro Kitagawa, and Keisuke Fujii. Quantum analog-digital conversion. Physical Review A , 99(1):012301, 2019

    work page 2019

  43. [43]

    A Quantum Algorithm for finding the Maximum

    Ashish Ahuja and Sanjiv Kapoor. A quantum al- gorithm for finding the maximum. arXiv preprint quant-ph/9911082, 1999

    work page internal anchor Pith review Pith/arXiv arXiv 1999

  44. [44]

    Appendix A: Complexity of Searching All Marked k-Indices Algorithm The problem to search all marked k-indices from D and its query complexity are briefly discussed in [7– 11]

    Though this process is not described in [2], we add this because we think it is required for conversion. Appendix A: Complexity of Searching All Marked k-Indices Algorithm The problem to search all marked k-indices from D and its query complexity are briefly discussed in [7– 11]. Here, we will give the complexity of the problem in an easy-to-understand way...

    work page

  45. [45]

    Find one index m from M by using AA

    work page

  46. [46]

    By updating f (x) to f ′(x) to remove already found indices

    Remove m from M . By updating f (x) to f ′(x) to remove already found indices. f ′(x) = { 1, if f (x) = 1 and x /∈ T, 0, if f (x) = 0 or x ∈ T. (A1) This f ′(x) needs additional quantum circuit on f (x). However, such quantum circuit is not complex, be- cause we can easily make superposition of the already found indices T in Og(log N ) [14, 16–18]. Figure...

    work page

  47. [47]

    (a) Search one index m ∈ M from D by using AA and f ′(x)

    Repeat the following process O(k) times. (a) Search one index m ∈ M from D by using AA and f ′(x). (b) Add a found index m to T . 9 |0⟩ I CM P |0⟩ |0⟩ • |0⟩ x f x |0⟩ • |0⟩ |0⟩ f ′(x) FIG. 13. An example of quantum circuit f ′. The gate T creates the superposition of already found indices in T . The gate f is an original oracle of AA that finds one index f...

    work page