Quantum Approximate k-Minimum Finding

Minbo Gao, Zhengfeng Ji, Qisheng Wang

TL;DR

This paper introduces a near-optimal quantum algorithm for finding the $k$ smallest elements in a list when you only have access to "noisy" or approximate values. By bridging the gap between theoretical exact-value algorithms and the approximate nature of real-world quantum subroutines, the authors provide a robust tool for tasks like estimating multiple expectation values and finding the lowest energy states of a quantum system.

What Problem Does This Paper Address?

In the world of quantum algorithms, "minimum finding" is a classic problem: given $n$ items, find the smallest one. Standard algorithms like Grover’s search can do this in $O(\sqrt{n})$ queries, and generalizations can find the $k$ smallest items in $O(\sqrt{nk})$ queries.

However, there is a catch: these algorithms usually assume an exact oracle. They assume that when you "query" an item, the computer tells you its exact value. In reality, most quantum subroutines (like Phase Estimation or Amplitude Estimation) don't give exact answers; they provide a superposition of values that are approximately correct with high probability.

Integrating these "noisy" subroutines into a $k$-minimum finding algorithm is surprisingly subtle. If you just plug approximate values into an algorithm designed for exact ones, the errors can accumulate, leading the algorithm to miss the true minima entirely. This paper formalizes how to handle these "approximate oracles" and provides algorithms that maintain the quadratic speedup expected from quantum computing.

Methods

The authors define two new ways to think about an "approximate" answer:

  1. Weak Approximate Minimum Index Set: A set where every index you pick has a value that is $\epsilon$-close to one of the true $k$ smallest values.
  2. Strong Approximate Minimum Index Set: A more rigorous definition where the set is guaranteed not to miss any values that are significantly smaller than the ones selected.

To find these sets, they propose two main algorithms:

  • For the Weak Set: They use a property called error-tolerant incrementability. Essentially, they show that if you have a good set of $k$ minima, you can "increment" it to find the $(k+1)$-th minimum without the errors blowing up.
  • For the Strong Set: This is harder. The algorithm first estimates the value of the $k$-th smallest element to set a "threshold." It then uses Quantum Amplitude Amplification combined with a "coupon collector" logic—sampling enough times to ensure that all elements below that threshold are captured in the final set.

Datasets

As a theoretical paper in quantum complexity, this work does not use empirical datasets or training benchmarks. Instead, it provides mathematical proofs of query complexity and algorithmic correctness.

Key Insights and Ideas

  • The "Approximate Oracle" Framework: The paper provides a rigorous mathematical definition (Definition 3.1) for an oracle that returns a superposition of approximate values. This creates a standard "interface" for future researchers to plug in subroutines like Phase Estimation.
  • Weak vs. Strong: The realization that a "weak" set is not necessarily a "strong" one is a key insight. In some applications (like quantum machine learning), a weak set isn't enough because missing a single very small value can ruin the subsequent calculation.
  • Optimal Scaling: The authors show that even with the added difficulty of approximate values, they can still achieve a query complexity of $\tilde{O}(\sqrt{nk})$. This matches the optimal scaling of the exact-value version of the problem, meaning there is almost no "speed penalty" for dealing with approximation.

Key Results

  • Algorithm Efficiency: The proposed algorithms achieve a query complexity of $\tilde{O}(\sqrt{nk})$. This is a quadratic improvement over classical algorithms, which would require $O(nk)$ or $O(n)$ queries depending on the setup.
  • Application - Multiple Expectations: The authors demonstrate an algorithm to find the $k$ smallest expectation values of $n$ different quantum observables in $\tilde{O}(\sqrt{nk}/\epsilon)$ time.
  • Application - Ground State Energies: They provide a method to find the $k$ lowest energy levels of a Hamiltonian (assuming a known eigenbasis) with the same $\tilde{O}(\sqrt{nk}/\epsilon)$ scaling, generalizing previous work that only looked for the single lowest state.

Limitations and Future Work

  • Logarithmic Overhead: The "almost" in "almost optimal" refers to extra logarithmic factors in the complexity. The authors note that removing these extra factors remains an open challenge.
  • Eigenbasis Requirement: For the Hamiltonian application, the algorithm currently requires the eigenbasis to be known. A major future direction is finding the $k$ lowest energies of a general Hamiltonian where the eigenbasis is unknown.
  • Oracle Variety: The authors suggest exploring other types of "noisy" oracles, such as those that might be subject to physical hardware noise (decoherence) rather than just algorithmic approximation.

Summary updated

Abstract

Quantum $k$-minimum finding is a fundamental subroutine with numerous applications in combinatorial problems and machine learning. Previous approaches typically assume oracle access to exact function values, making it challenging to integrate this subroutine with other quantum algorithms. In this paper, we propose an (almost) optimal quantum $k$-minimum finding algorithm that works with approximate values for all $k \geq 1$, extending a result of van Apeldoorn, Gilyén, Gribling, and de Wolf (FOCS 2017) for $k=1$. As practical applications of this algorithm, we present efficient quantum algorithms for identifying the $k$ smallest expectation values among multiple observables and for determining the $k$ lowest ground state energies of a Hamiltonian with a known eigenbasis.
BibTeX
@inproceedings{gao2025quantum,
  author = {Minbo Gao and Zhengfeng Ji and Qisheng Wang},
  title = {{Quantum Approximate k-Minimum Finding}},
  booktitle = {ESA},
  year = {2025},
  doi = {10.4230/lipics.esa.2025.51},
}

Loading related content...

Figure