Quantum Approximate $k$-Minimum Finding

Minbo Gao, Zhengfeng Ji, Qisheng Wang

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.

Introduction

In the landscape of quantum algorithms, minimum finding is a classic problem: given $n$ items, find the smallest one. Standard algorithms like Grover’s search can achieve this in $O(\sqrt{n})$ queries, and generalizations can find the $k$ smallest items in $O(\sqrt{nk})$ queries. However, these algorithms usually assume an exact oracle—the assumption that querying an item returns its exact value.

In reality, most quantum subroutines, such as Phase Estimation or Amplitude Estimation, provide a superposition of values that are only approximately correct with high probability. Integrating these "noisy" subroutines into a $k$-minimum finding algorithm is surprisingly subtle; simply plugging approximate values into exact-value algorithms can lead to error accumulation and incorrect results. This paper formalizes how to handle these "approximate oracles" while maintaining the quadratic speedup expected from quantum computing.

The Approximate Oracle Framework

The authors define a rigorous mathematical framework (Definition 3.1) for an oracle that returns a superposition of approximate values. This creates a standard "interface" for future researchers to plug in various quantum subroutines.

Comparison of quantum minimum finding algorithms under different oracle models for the $k=1$ case.

As shown in the table above, the proposed Approximate Oracle model bridges the gap between theoretical exact-value algorithms and the approximate nature of real-world quantum subroutines. It allows for both error and precision considerations while achieving a query complexity of $\tilde{O}(\sqrt{n})$ for the single minimum case, matching the optimal scaling of more restricted models.

Methodology: Weak vs. Strong Approximation

The paper distinguishes between two ways to define an approximate minimum set:

  1. Weak Approximate Minimum Index Set: A set where every selected index has a value $\epsilon$-close to one of the true $k$ smallest values. The authors find this using error-tolerant incrementability, showing that a set of $k$ minima can be "incremented" to find the $(k+1)$-th minimum without the errors blowing up.
  2. Strong Approximate Minimum Index Set: A more rigorous definition where the set is guaranteed not to miss any values significantly smaller than the ones selected. This algorithm estimates the value of the $k$-th smallest element to set a "threshold" and then uses Quantum Amplitude Amplification combined with "coupon collector" logic to ensure all elements below that threshold are captured.

As a theoretical work in quantum complexity, these results are established through mathematical proofs of query complexity rather than empirical benchmarks.

Key Results and Applications

The proposed algorithms 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 applications include:

  • Multiple Expectation Values: An algorithm to find the $k$ smallest expectation values of $n$ different quantum observables in $\tilde{O}(\sqrt{nk}/\epsilon)$ time.
  • Ground State Energies: 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.

Discussion and Future Work

While the algorithms are near-optimal, the "almost" refers to extra logarithmic factors in the complexity. Removing these factors remains an open challenge. Furthermore, the Hamiltonian application currently requires a known eigenbasis; a major future direction is finding the $k$ lowest energies of a general Hamiltonian where the eigenbasis is unknown. Finally, the authors suggest exploring other types of noisy oracles, such as those subject to physical hardware noise like decoherence.

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},
}
Figure