Quantum Approximate k-Minimum Finding

Gao, Minbo; Ji, Zhengfeng; Wang, Qisheng

doi:10.4230/LIPIcs.ESA.2025.51

Quantum Approximate $\bm{k}$ -Minimum Finding

Minbo Gao

Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing, China
University of Chinese Academy of Sciences, Beijing, China Zhengfeng Ji

Department of Computer Science and Technology, Tsinghua University, Beijing, China Qisheng Wang

School of Informatics, University of Edinburgh, UK

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, 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.

Keywords and phrases:

Quantum Computing, Quantum Algorithms, Quantum Minimum Finding

Funding:

Zhengfeng Ji: ZJ was supported by National Natural Science Foundation of China (Grant No. 12347104 and No. 61832015), Beijing Natural Science Foundation (Grant No. Z220002), and a startup funding from Tsinghua University.

Qisheng Wang: QW was supported by the Engineering and Physical Sciences Research Council under Grant EP/X026167/1.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum query complexity ; Theory of computation

\rightarrow

Design and analysis of algorithms

Related Version:

Full Version: https://arxiv.org/abs/2412.16586 [16]

Acknowledgements:

The authors thank Mingsheng Ying and François Le Gall for helpful suggestions and discussions. Minbo Gao would like to thank François Le Gall for supporting his visit to Nagoya University where part of the work was completed.

Funding:

MG and ZJ were supported by National Key Research and Development Program of China (Grant No. 2023YFA1009403).

DOI:

10.4230/LIPIcs.ESA.2025.51

Event:

33rd Annual European Symposium on Algorithms (ESA 2025)

Editors:

Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Quantum minimum finding was initially proposed in [14], with a direct but clever use of Grover search [19]. They showed that given quantum query access to $n$ unordered elements (with exact values), one can find the smallest one with an optimal quantum query complexity $\Theta\lparen\sqrt{n}\rparen$ , which quadratically outperforms any classical algorithms. As a generalization, quantum $k$ -minimum finding was later developed in [13], which finds the $k$ smallest elements from $n$ elements with an optimal quantum query complexity $\Theta\lparen\sqrt{nk}\rparen$ . Quantum $k$ -minimum finding for exact values turns out to have various applications in different fields, e.g., minimum spanning tree and strong connectivity in graph theory [13], clustering [3, 27] and $k$ -nearest neighbor [43] in machine learning (see also [37, 7]), and pattern matching [34] and other string problems [42, 4, 24] in stringology.

The traditional quantum ( $k$ -)minimum finding works when the elements are comparable by their exact values. However, it does not apply to the numerical case, where the values of the elements can be computed by (stochastic) numerical methods. Notably, this case often appears in practice, especially when the values of the elements are estimated by quantum subroutines such as quantum phase estimation [25, 31] and amplitude estimation [9]. A typical example is the quantum SDP (semi-definite program) solver proposed in [40, 8, 39], where the ground energy of a Hamiltonian is found by a quantum minimum finding over approximate quantum phases. To facilitate the discussion of the numerical scenarios and the composability of quantum $k$ -minimum finding, we introduce an abstract type of quantum oracle for numerical inputs, called approximate oracle. In an approximate oracle, each query returns a superposition of approximate values of the queried element to high precision and with high success probability (see Definition 5 for the formal definition). This is a very general definition which meets the requirement for all known situations where quantum $k$ -minimum finding is used as a subroutine. A key question is then

How to solve quantum $k$ -minimum finding problem with an approximate oracle?

This question is not only of theoretical interest, but also holds significant practical value. The solution turns out to be more subtle as one may initially expect. To address this problem clearly, we propose two (weak and strong) definitions of approximate minimum index sets as characterizations of the required output in $k$ -minimum finding algorithms, naturally generalizing the requirement of the approximate minimum finding problem. We give almost optimal quantum algorithms for computing these sets with $\widetilde{O}\lparen\sqrt{nk}\rparen$ queries to the approximate oracle. Finally, we showcase two applications of our algorithms: identifying the $k$ smallest expectation values and determining the $k$ lowest ground state energies of a Hamiltonian.

1.1 Approximate Oracles and Approximate Minimum Index Sets

Before presenting our main results, we define the concept of approximate oracle, explain why the standard algorithm for quantum $k$ -minimum finding fail in this case, and define the concept of approximate minimum index set as an appropriate output.

1.1.1 Approximate Oracles

In the standard setting of quantum ( $k$ -)minimum finding (see [14, 13]), an exact oracle for the input data is assumed, which always returns the exact function value for each query. The assumption of an exact oracle is reasonable in the case where the input data is previously known or is produced by deterministic algorithms. However, it fails to describe the situation where the input data is generated by randomized or quantum numerical algorithms.

Generally speaking, for a randomized numerical algorithm that estimates a real number $x$ , its output is a random variable $X$ , such that the distance between $X$ and $x$ is no more than $\varepsilon$ with probability at least $1-\delta$ . We will call $\varepsilon$ the precision parameter and $\delta$ the error parameter from now on. If the values are estimated using quantum algorithms, a general situation is that the estimated values are stored in a quantum state in superposition. Hence, it is natural to consider the following definition of approximate oracles. An $(\varepsilon,\delta)$ -approximate oracle for the input $x_{i}$ ’s is a quantum unitary operator that with probability at least $1-\delta$ , outputs a quantum state which is a superposition of estimated values for $x_{i}$ within $\varepsilon$ distance upon querying $i$ . The formal definition of approximate oracle can be found in Definition 5. This input model works well with two widely-used quantum procedures for quantum numerical computations, namely phase estimation and amplitude estimation.

There are other input unitary oracle models, such as the bounded-error oracle [21, 42], and untrustworthy oracle [32]. We summarize their properties in the following table, with a detailed discussion in Section 3.1.

Table 1: Different Unitary Oracle Models for Minimum Finding.

	Allows Error	Considers Precision	Complexity of Min Finding
Exact oracle [13]	$\times$	$\times$	$O(\sqrt{n})$
Bounded-error oracle [42]	$\checkmark$	$\times$	$\widetilde{O}(\sqrt{n})$
Untrustworthy oracle [32]	$\checkmark$	$\checkmark$	$\widetilde{O}(\sqrt{n(1+\Delta)})$ ¹¹1 $\Delta$ is the upper bound on the number of elements within any interval of unit length.
Approximate oracle	$\checkmark$	$\checkmark$	$\widetilde{O}(\sqrt{n})$

1.1.2 Approximate Minimum Index Set

When discussing the $k$ -minimum finding problem, it is important to define what conditions of the output, which we call the approximate minimum index set, need to satisfy. For reason to be clear later, we will consider both the weak and strong approximate minimum index sets.

As a warm-up, let us consider what we can learn from the randomized numerical algorithms. Suppose that there are $n$ elements $x_{1},x_{2},\dots,x_{n}$ , and for each $j\in[n]$ , a random result $X_{j}$ is generated by a randomized numerical algorithm, that is $\varepsilon$ -close to the actual value $x_{j}$ with probability at least $1-\delta$ . With this as the input oracle, it may be impossible for us to find out the $k$ smallest elements in extreme cases, for example, when all elements are $\varepsilon$ -close to each other. As a compromise, we seek an approximate solution instead.

For the minimum finding problem, the authors of [40] implicitly gave a characterization of the approximate minimum index, namely an index $j$ whose value $x_{j}$ is $\varepsilon$ -close to the true minimum value. This characterization, however, could be interpreted and generalized in various different ways when $k$ -minimum finding is considered.

Weak Approximate Minimum Index Set.

One way to understand the approximate minimum index is that the solution we find are entry-wise $\varepsilon$ -close to the ideal solution. Generalizing this idea to the $k$ -minimum case, we propose the definition of the weak approximate minimum index set, which requires the approximate solution to be entry-wise $\varepsilon$ -close to the $k$ minima (see Definition 11 for a formal definition).

Strong Approximate Minimum Index Set.

The other way to interpret the approximate minimum is to regard it as an $\varepsilon$ -approximate version of a global condition. To be more precise, the minimum has the property that it is no more than all other elements; and the approximate minimum index requires this condition to hold within at most $\varepsilon$ -error. Generalizing this idea to the $k$ -minimum case, we propose the definition of the strong approximate minimum index set, which requires the approximate solution to be bounded by the other values whose indices are not in the set within at most $\varepsilon$ -error (see Definition 13 for a formal definition).

Relationships between the two definitions.

To the best of our knowledge, neither of the above definitions has been proposed for $k\geq 2$ , and their relationships are not well understood before. Although the above definitions are equivalent for $k=1$ , this equivalence does not hold for larger $k$ anymore. In the paper, we show that a strong approximate minimum index set must be a weak one, but not vice versa (see Section 4 for more details). We also note that, in certain scenarios, a strong $(k,\varepsilon)$ -approximate minimum index set is needed and a weak one does not suffice (see Remark 2 for more details).

1.2 Main Results

Given an approximate oracle as an input, we design almost optimal quantum algorithms for $k$ -minimum finding, based on the concepts of weak and strong approximate minimum index sets.

Theorem 1 (Quantum Approximate $k$ -minimum Finding, informal version of Theorem 17 and Theorem 18).

Suppose $V$ is an $(\varepsilon,\delta)$ -approximate oracle for a vector $v\in\mathbb{R}^{n}$ , where $\delta>0$ is sufficiently small, and suppose $k$ is the desired number of minimal indices.

$\blacksquare$

Weak Approximate Minimum Index Set Finding: There is a quantum algorithm that, with high probability, outputs a weak $(k,2\varepsilon)$ -approximate minimum index set $S$ for $v$ , using $\widetilde{O}\lparen\sqrt{nk}\rparen$ queries to $V$ .
$\blacksquare$

Strong Approximate Minimum Index Set Finding: There is a quantum algorithm that, with high probability, outputs a strong $(k,7\varepsilon)$ -approximate minimum index set $S$ for $v$ , using $\widetilde{O}\lparen\sqrt{nk}\rparen$ queries to $V$ .

Actually, a weak approximate minimum index set is not necessarily a strong one (see Example 15). This is because the weak approximate minimum index set focuses on entry-wise approximation while the strong one considers the global property that small values should not be ignored. The need of strong approximate minimum index sets exists in quantum machine learning. For example, in [15], a strong approximate minimum index set is required; in case the approximate minimum index set is weak, their key intermediate conclusion [15, Proposition D.12] no longer holds. Due to the well-known $\Omega\lparen\sqrt{nk}\rparen$ bound of quantum $k$ -minimum finding [13], and the exact oracle being a special case of the approximate oracle, our algorithms for approximate $k$ -minimum finding achieves almost optimal query complexity for this problem.

The assumption that $\delta$ needs to be sufficiently small is not critical in applications. In fact, by applying the median trick to the approximate oracle, similar to techniques used in phase estimation and amplitude estimation [30], the failure probability could be reduced with an extra logarithmic overhead if it is smaller than $1/3$ .

1.3 Techniques

The algorithm for finding a weak minimum index set serves as the basis of the algorithm for finding a strong index set, although the techniques used in designing these algorithms are quite different. We now present the techniques for both algorithms separately.

To design a quantum algorithm for finding the weak approximate minimum index set, we first observe an important property of the weak approximate minimum index set which we call error-tolerant incrementability (Proposition 12). This property allows us to add an “approximately” $(k+1)$ smallest entry to a weak $(k,\varepsilon)$ -approximate minimum index set and form a weak $(k+1,\varepsilon)$ -approximate minimum index set. It serves as the key property in demonstrating weak approximate minimum index set finding (see the full version, specially [16, Theorem A.1]), and enables us to solve the weak $k$ -minimum finding problem by repeatedly applying the quantum approximate minimum finding with an approximate oracle [40, 11]. We can therefore mimic the way how the quantum $k$ -minimum finding [13] can be solved using original quantum minimum finding [14]. To be more concrete, our algorithm (Algorithm 1) works as follows: in the $j$ -th iteration of the $k$ runs, the algorithm finds an element not selected yet with value (approximately) no greater than the $\lparen k-j+1\rparen$ -th element. While this approach may seem adaptable to more general cases, it turns out that it can only return a weak approximate minimum index set, since strong approximate minimum index sets do not exhibit the error-tolerant incrementability property.

Nevertheless, we still manage to design a quantum algorithm for finding a strong approximate minimum index set with several additional new ideas. The key insight is that the algorithm for finding a weak approximate minimum index set could be used to estimate the value of the $k$ -th smallest element approximately. Thus, we could set a threshold $u$ which is slightly smaller than the value of the $k$ -th smallest element. The threshold $u$ can be understood as a filter, capturing small elements that must not be ignored. Having obtained the threshold $u$ , we focus on all estimates with value lower than $u$ (including those estimates whose corresponding elements are larger than $u$ ), and then sample (at most) $\widetilde{O}\lparen k\rparen$ indices. From these, we can find $k$ indices that form a strong approximate minimum index set.

More specifically, we begin with a quantum state $\lvert\Phi\rangle=\frac{1}{\sqrt{n}}\sum_{j=1}^{n}\lvert j\rangle\lvert\Lambda% _{j}\rangle$ , where $\lvert\Lambda_{j}\rangle=\sum_{\nu}\alpha_{j,\nu}\lvert\nu\rangle$ is a superposition of all possible estimates of the $j$ -th element. If we focus on the register containing the estimate values $\nu$ , then we can write $\lvert\Phi\rangle=\sum_{\nu}\lvert S_{\nu}\rangle\lvert\nu\rangle$ , where $\lvert S_{\nu}\rangle$ is a superposition of indices. If we now condition on whether $\nu$ is lower than the threshold $u$ , the quantum state can be written as $\lvert\Phi\rangle=\lvert\Phi_{\leq u}\rangle+\lvert\Phi_{>u}\rangle$ , where $\lvert\Phi_{\leq u}\rangle=\sum_{\nu\leq u}\lvert S_{\nu}\rangle\lvert\nu\rangle$ . By quantum amplitude amplification [9], we can sample one index from $\lvert\Phi_{\leq u}\rangle$ by using $O\lparen 1/\lVert\lvert\Phi_{\leq u}\rangle\rVert\rparen$ queries to the unitary oracle that prepares $\lvert\Phi\rangle$ . Using an argument similar to the coupon collector’s problem, we prove that sampling sufficiently many (precisely, $\Theta\lparen n\lVert\lvert\Phi_{\leq u}\rangle\rVert^{2}\rparen$ ) times will collect all the “small” elements with high probability. Finally, we use simple post-processing to find a strong approximate minimum index set (see Section 6 for more details).

1.4 Applications

Our algorithms for finding approximate minimum index sets can be applied to several practical scenarios, some of which are formally discussed in Section 7.

Approximate ${k}$ minima in multiple expectations.

Given purified access to $n$ quantum states ${\{\rho_{j}\}}_{j=1}^{n}$ , and block-encoding access (see Definition 4) to $n$ observables ${\{O_{j}\}}_{j=1}^{n}$ , the task is to approximately find the $k$ minimal values among expectations $\operatorname{tr}\lparen O_{j}\rho_{j}\rparen$ . The expectation $\operatorname{tr}\lparen O\rho\rparen$ of an observable $O$ with respect to a quantum state $\rho$ can be estimated, for example, by the Hadamard test [2] or quantum measurements. The problem has been considered in the literature in various situations where, in most of the cases, the same quantum state are used for different observables. These include quantum SDP solvers [8, 40, 39], shadow tomography [22, 1, 10] and multiple expectation estimation [23]. By our quantum approximate $k$ -minimum finding with amplitude estimation, we can find an $\varepsilon$ -approximate of the $k$ minimal expectations in $\widetilde{O}\lparen\sqrt{nk}/\varepsilon\rparen$ time.

Approximate ${k}$ ground state energies.

Given block-encoding access to a Hamiltonian with the known eigenbasis, our algorithm can be used to find an $\varepsilon$ -approximate of the $k$ ground state energies in $\widetilde{O}\lparen\sqrt{nk}/\varepsilon\rparen$ time, which could be seen as a generalization of the approximate ground state energy finding [40].

In the special case when the Hamiltonian is diagonal (i.e., with the computational basis as its eigenbasis), our quantum algorithm for approximate $k$ -minimum finding can be used in quantum multi-Gibbs sampling [15]. See Remark 2 for a more detailed discussion.

$\blacktriangleright$ Remark 2.

For the special case where the approximate oracle is implemented by quantum amplitude estimation, a quantum $k$ -minimum finding was claimed in [15]. However, an error in their Theorem C.3 was found due to their incorrect error-reduction of consistent quantum amplitude estimation. Nevertheless, using our quantum strong approximate $k$ -minimum finding with an approximate oracle, we can fill the gaps in their proof, and their result still holds.

2 Preliminaries

2.1 Notations

For $n\in\mathbb{Z}_{+}$ , we use $[n]$ to denote the set $\{1,2,\dots,n\}$ , and we set $[0]=\emptyset$ for convenience. $\mathbb{R}^{n}_{\geq 0}$ stands for the set of $n$ -dimensional vectors with non-negative entries. For sets $A$ and $B$ , we use $A-B$ to denote the set consisting of the elements in $A$ but not in $B$ . We assume the readers are familiar with the basic knowledge of quantum computing (see [31] for a reference). In this paper, when discussing the query complexity of $U$ , we assume having query access to $U$ , $U^{\dagger}$ and their controlled versions.

2.2 Concepts in Quantum Computing

We use a quantum data structure called $\mathsf{QSet}$ to store the found indices in our algorithm. The functionality of this data structure is characterized by the following proposition.²²2If we allow the use of quantum(-read classical-write) random access memory (QRAM) (see [6] for a more detailed discussion), all these operations could be implemented efficiently (i.e., in $\widetilde{O}(1)$ one- and two-qubit gates and QRAM read and write operations).

Proposition 3.

There is a quantum data structure $\mathsf{QSet}$ that supports the following operations.

$\blacksquare$

Initialization $\mathsf{QSet.Initialize}(n)$ : return an instance $\mathcal{S}$ of $\mathsf{QSet}$ , with a set $S$ initialized to empty set which can store at most $n$ elements.
$\blacksquare$

Add $\mathsf{S.Add}(j)$ for an $j\in[n]$ : insert the element $j$ into the set $S$ .
$\blacksquare$

Hide $\mathsf{S.Hide}()$ : output a unitary satisfying $\mathsf{S.Hide}()\lvert i\rangle\lvert j\rangle=\lvert i\rangle\lvert 2\times% \mathbf{1}_{S}(i)+j\rangle$ for any computational basis $\lvert j\rangle$ , where $\mathbf{1}_{S}(\cdot)$ is the indicator function of the set $S$ , i.e, $\mathbf{1}_{S}(i)=1$ if $i\in S$ , and $\mathbf{1}_{S}(i)=0$ if $i\in[n]-S$ .

Block-encoding is a very useful concept in quantum algorithms proposed in [17], and we recall its definition as follows.

Definition 4 (Block-encoding [17, Definition 24]).

Let $A$ be a linear operator acting on an $s$ -qubit Hilbert space. For $\alpha,\varepsilon>0$ and integer $a$ , we say an $(a+s)$ -qubit unitary operator $U$ is an $(\alpha,a,\varepsilon)$ -block-encoding of $A$ , if $\lVert A-\alpha\langle 0\rvert^{\otimes a}U\lvert 0\rangle^{\otimes a}\rVert\leq\varepsilon$ .

When $a$ and $\varepsilon$ could be omitted (for instance, $a=O(1)$ and $\varepsilon=0$ , or the values of $a$ and $\varepsilon$ have shown up in previous context), we simply call $U$ an $\alpha$ -block-encoding of $A$ .

3 Approximate Oracle

Definition 5 (Approximate Oracle).

Suppose $v=(v_{1},\ldots,v_{n})\in\mathbb{R}^{n}_{\geq 0}$ is an $n$ -dimensional vector with $v_{j}\in\mathopen{[}0,1\mathclose{]}$ for $j\in[n]$ . For $\varepsilon\in\mathopen{[}0,1/2\mathclose{)}$ and $\delta\in\mathopen{[}0,1/2\mathclose{)}$ , a unitary $V$ is called an $(\varepsilon,\delta)$ -approximate oracle for $v$ , if it satisfies $V\lvert i\rangle\lvert j\rangle=\lvert i\rangle\lvert\Lambda_{i}+j\rangle$ for all $i\in[n]$ , where

\lvert\Lambda_{i}+j\rangle=\sqrt{p_{i}^{\varepsilon}}\lvert\Lambda_{i}^{% \varepsilon}+j\rangle+\sqrt{1-p_{i}^{\varepsilon}}\lvert\Lambda_{i}^{% \varepsilon\perp}+j\rangle,

is a normalized state in a $d$ -dimensional space, $\lvert\Lambda_{i}^{\varepsilon}+j\rangle=\sum_{\nu\colon\lvert\nu-v_{i}\rvert% \leq\varepsilon}\alpha_{\nu}^{\lparen i\rparen}\lvert\nu+j\rangle$ , $\lvert\Lambda_{i}^{\varepsilon\perp}+j\rangle$ is the state orthogonal to $\lvert\Lambda_{i}^{\varepsilon}+j\rangle$ , and $p^{\varepsilon}_{i}\geq 1-\delta$ for all $i\in[n]$ .³³3We also allow the case where $V$ produces ancillary states, namely $V\lvert i\rangle\lvert j\rangle\lvert 0\rangle=\lvert i\rangle\lvert\Lambda_{i% }+j\rangle\lvert\psi_{j}\rangle$ , which will not influence our proofs.

$\blacktriangleright$ Remark 6.

In simple words, the definition states that $V$ is an $(\varepsilon,\delta)$ -approximate oracle for $v$ , if for each $i\in[n]$ , by querying $i$ , with probability at least $1-\delta$ , $V$ will return (a superposition) of estimated values in $\mathopen{[}v_{i}-\varepsilon,v_{i}+\varepsilon\mathclose{]}$ . As an example, such a scenario shows up when the phase estimation procedure is used to estimate the values of $v_{i}$ .

By using the median trick [30], we have the following proposition stating that the success probability of the approximate oracle can be efficiently amplified.

Proposition 7 (Failure probability reduction of the approximate oracle).

Suppose $v\in\mathbb{R}^{n}$ is an $n$ -dimensional vector and $V$ is an $(\varepsilon,\delta)$ -approximate oracle for $v$ , for some $\varepsilon\in(0,1/2)$ and $\delta\in(0,1/3)$ . Then, for any $\delta^{\prime}\in\mathopen{(}0,\delta\mathclose{)}$ , one can construct an $(\varepsilon,\delta^{\prime})$ -approximate oracle for $v$ , using $O\lparen\log\lparen\delta/\delta^{\prime}\rparen\rparen$ queries to $V$ .

3.1 Comparisons of Different Oracles

In this part, we briefly investigate different input oracles considered in previous literature for the quantum minimum finding problem, namely the bounded-error oracle and the untrustworthy oracle.

Bounded-error Oracle.

As the name suggests, bounded-error considers the case when only bounded-error access to the input is provided for computation tasks, such as quantum search [21] and quantum minimum finding [42]. This kind of oracle model could return the correct exact answer with bounded error (i.e., high probability), while the exact oracle returns the correct exact answer with certainty. Therefore, bounded-error oracle could be seen as a slight generalization of the exact oracle. Their computational powers are close, as the bounded-error oracle can simulate the exact oracle by majority voting with logarithmic repetitions.

Untrustworthy Oracle.

The precision issue for the oracle model motivates researchers to consider another oracle model [32], which we call the untrustworthy oracle.⁴⁴4The untrustworthy oracle is originally called “noisy oracle” in [32]. However, we renamed it according to its behavior, to avoid the conflict with the noisy oracle related to physical noises. The untrustworthy oracle will return the correct comparison result between two elements if they are far away enough; and an unknown, possibly adversary (but deterministic) comparison result, if the distance between them is less than a fixed threshold $\varepsilon$ . In this model, quantum minimum finding over $n$ elements could be done in time $\widetilde{O}\lparen\sqrt{n(1+\Delta)}\rparen$ , where $\Delta$ is the upper bound on the number of elements within any interval of length $\varepsilon$ . The result shows that, achieving quadratic speedup for the minimum finding in this model may pose strict requirements on the inputs.

We note that our definition of approximate oracle includes exact oracle and bounded-error oracle as special cases. In fact, a bounded-error oracle with bounded-error $\delta$ is a $(0,\delta)$ -approximate oracle by definition. The approximate oracle model is generally incomparable to the untrustworthy oracle, see Remark 8 for a detailed discussion.

$\blacktriangleright$ Remark 8.

The untrustworthy oracle is incomparable with the approximate oracle. This can be seen from two perspectives. First, the latter cannot simulate the former, because the comparison between close elements by the approximate oracle is always in superposition. Second, the former reveals more information than the latter when comparing two elements $x_{1},x_{2}$ with distance slightly above the threshold, say $\lvert x_{1}-x_{2}\rvert=1.1\varepsilon$ . In this case, the former returns the correct comparison with certainty, while the latter may not be able to even distinguish the two elements (in extreme cases, the approximate values of the two elements $x_{1},x_{2}$ can be the same, i.e. $\lparen x_{1}+x_{2}\rparen/2$ , with certainty).

There are other types of input oracles that are quantum channels due to imperfect implementations and noise; they were considered in the unstructured search problem in the literature, e.g., [38, 5, 26, 35, 20, 36]. In particular, in [35, 36], it was shown that no quadratic speedup exists in the presence of (constant-rate) depolarizing or dephasing noise after each application of the exact oracle. By contrast, the bounded-error, untrustworthy and approximate oracles are all unitary.

4 Approximate ${k}$ -Minimum Index Set: Weak and Strong Definitions

The problem of finding the smallest element from a set of $n$ numbers using an oracle that provides an approximate value has been a topic of interest in quantum computation studies, specifically quantum algorithms for optimization tasks [40, 11]. As discussed in Section 3, a natural setup where the values of vector $v$ are prepared involves employing the amplitude estimation procedure with a limited precision parameter $\varepsilon$ using $V$ . Given the limitation of the estimation precision, it is reasonable to expect that we could only find an approximate minimum value that is $O\lparen\varepsilon\rparen$ -close to the true minimum. We also observe that, instead of finding the approximate minimum value, it suffices to find the index of the approximate minimum value. Thus, motivated by prior results (Theorem 50 in [40] and Theorem 2.4 in [11]), we present the following notion of $\varepsilon$ -approximate minimum index, which were implicit in those prior works.

Definition 9 (Approximate Minimum Index).

Let $v=\lparen v_{1},v_{2},\dots,v_{n}\rparen\in\mathbb{R}^{n}_{\geq 0}$ be an $n$ -dimensional vector. Suppose the coordinates of $v$ are sorted from small to large as

v_{s_{1}}\leq v_{s_{2}}\leq v_{s_{3}}\leq\cdots\leq v_{s_{n}},

then, an $\varepsilon$ -approximate minimum index for $v$ is an index $i\in[n]$ satisfying $v_{i}\leq v_{s_{1}}+\varepsilon$ .

$\blacktriangleright$ Remark 10.

For some $v$ and $\varepsilon$ , there may exist multiple indices that are $\varepsilon$ -approximate minimum indices of $v$ . For instance, if $v=(1,1,\ldots,1)\in\mathbb{R}^{n}$ , then, for any $\varepsilon>0$ and any $j\in[n]$ , $j$ is an $\varepsilon$ -approximate minimum index of $v$ by definition.

In simple terms, $i$ is an $\varepsilon$ -approximate minimum index for $v$ if $v_{i}\leq\min_{j\in[n]}v_{j}+\varepsilon$ . Therefore, after identifying an $\varepsilon$ -approximate minimum index $i$ , one can use amplitude estimation to obtain an $\varepsilon$ -approximate estimate of $v_{i}$ , which is $O(\varepsilon)$ -close to the actual minimum $\min_{j\in[n]}v_{j}$ .

Interestingly, generalizing this concept for finding $k$ smallest elements approximately is challenging. In this section, we introduce two definitions of the approximate $k$ -minimum index set, extending the notion of approximate minimum index in two distinct ways. Furthermore, we explore the relationships between these definitions.

We first propose the definition of weak $(k,\varepsilon)$ -approximate minimum index set, which requires that after sorting the elements in the set from small to large, they are entry-wise $\varepsilon$ -close to the real minima.

Definition 11 (Weak Approximate Minimum Index Set).

Let $v=\lparen v_{1},v_{2},\dots,v_{n}\rparen\in\mathbb{R}^{n}_{\geq 0}$ be an $n$ -dimensional vector. Suppose the coordinates of $v$ are sorted from small to large as $v_{s_{1}}\leq v_{s_{2}}\leq v_{s_{3}}\leq\cdots\leq v_{s_{n}}$ . A set $S$ of size $k$ is called a weak $(k,\varepsilon)$ -approximate minimum index set for $v$ if there is an enumeration $i_{1},i_{2},\ldots,i_{k}$ of elements of $S$ such that $v_{s_{j}}\leq v_{i_{j}}\leq v_{s_{j}}+\varepsilon$ for all $j\in[k]$ .

The following incrementability property plays a crucial role in finding weak approximate minimum index sets. Essentially, it states that from a weak $(k,\varepsilon)$ -approximate minimum index set, we can add an index whose value is no more than the $(k+1)$ -smallest value plus $\varepsilon$ , yielding a weak $(k+1,\varepsilon)$ -approximate minimum index set. This is also stated and proved in [16, Proposition A.2] in the full version.

Proposition 12 (Error-tolerant Incrementability).

Let $v\in\mathbb{R}^{n}_{\geq 0}$ be an $n$ -dimensional vector, and its coordinates can be sorted as $v_{s_{1}}\leq v_{s_{2}}\leq\cdots\leq v_{s_{n}}$ . Suppose $S$ is a weak $(k,\varepsilon)$ -approximate minimum index set for a positive integer $k\in[n-1]$ and a positive real $\varepsilon$ . Let $a_{k+1}\in[n]-S$ be an index satisfying $v_{a_{k+1}}\leq v_{s_{k+1}}+\varepsilon$ . Then, $S\cup\{a_{k+1}\}$ is a weak $(k+1,\varepsilon)$ -approximate minimum index set for $v$ .

Next, we introduce a strong notion of approximate minimum index set, as the weaker version might not be adequate for certain applications. The definition builds upon the following characterization of a $k$ -minimum index set: For a set $S\subseteq[n]$ of size $k$ that constitutes a $k$ -minimum index set, it holds that $v_{j}\geq v_{i}$ for every $i\in S$ and $j\in[n]-S$ . In other words, the inequality $\max_{i\in S}v_{i}\leq v_{j}$ must be satisfied for every $j\in[n]-S$ . If we relax these constraints to allow for an epsilon margin of error, we obtain the following definition.

Definition 13 (Strong Approximate Minimum Index Set).

Let $v=\lparen v_{1},v_{2},\dots,v_{n}\rparen\in\mathbb{R}^{n}_{\geq 0}$ be an $n$ -dimensional vector. Then, a set $S=\{i_{1},i_{2},\dots,i_{k}\}\subseteq[n]$ of size $k$ is called a strong $(k,\varepsilon)$ -approximate minimum index set for $v$ , if for all $j\in[n]-S$ , we have $\max_{i\in S}v_{i}\leq v_{j}+\varepsilon$ .

As the name suggests, a strong $(k,\varepsilon)$ -approximate minimum index set is also a weak $(k,\varepsilon)$ -approximate minimum index set, and we formally state this proposition as follows, which is also stated and proved in [16, Proposition A.7] in the full version.

Proposition 14.

For an $n$ -dimensional vector $v\in\mathbb{R}^{n}_{\geq 0}$ , let $S\subseteq[n]$ with size $k$ be a strong $(k,\varepsilon)$ -approximate minimum index set for $v$ . Then, $S$ is also a weak $(k,\varepsilon)$ -approximate minimum index set for $v$ .

However, a weak $(k,\varepsilon)$ -approximate minimum index set is not necessarily a strong one. In particular, the strong approximate minimum index set is not error-tolerant incrementable, which is shown in the following example.

Example 15 (No Error-Tolerant Incrementability for Strong Approximate Minimum Index Set).

Consider a $5$ -dimensional vector $v=(0.1,0.2,0.3,0.4,0.5)$ . Let $\varepsilon=0.15$ . By definition, $\{2\}$ is a strong $(1,\varepsilon)$ -approximate minimum index set for $v$ . Also, for the index $3$ , we know $v_{3}=0.3\leq v_{2}+\varepsilon$ . Therefore, by definition, $\{2,3\}$ is a weak $(2,\varepsilon)$ -approximate minimum index set for $v$ . However, since $0.3>0.1+\varepsilon$ , $\{2,3\}$ is not a strong $(2,\varepsilon)$ -approximate minimum index set for $v$ .

This illustration could be extended to encompass arbitrary values of $n$ and $k$ , demonstrating that for any fixed constant $c\geq 1$ , there exists a weak $(k,\varepsilon)$ -approximate minimum index set that is not a strong $(k,c\varepsilon)$ -approximate minimum index set.

5 Quantum Algorithms for Finding Weak Approximate Minimum Index Sets

In this section, we will develop an approximate version of $k$ -minimum finding that enables us to find a weak $(k,\varepsilon)$ -approximate minimum index set, given access to an approximate oracle. The technique of generalized minimum finding from [40] is an important subroutine in our algorithm, which could be stated as follows.

Theorem 16 (Generalized Minimum Finding, [40, Theorem 49]).

Let $n$ be a positive integer, and $\delta\in\mathopen{(}0,1/3\mathclose{)}$ . Suppose $U$ is an $n\times n$ unitary operator satisfying $U\lvert 0\rangle=\sum_{\ell=1}^{n}\sqrt{p_{\ell}}\lvert\psi_{\ell}\rangle% \lvert x_{\ell}\rangle$ , where $p_{\ell}\in\mathopen{[}0,1\mathclose{]}$ , $\sum_{\ell=1}^{n}p_{\ell}=1$ , $\lvert\psi_{\ell}\rangle$ are normalized states, and $\left\{\,x_{\ell}\colon\ell\in[n]\,\right\}$ are distinct real numbers satisfying $x_{1}<x_{2}<\cdots<x_{n}$ . Let $X$ denote a discrete random variable with $p_{\ell}=\Pr\left\lparen X=x_{\ell}\right\rparen$ , and $M\in\mathopen{(}0,1\mathclose{]}$ be a lower bound on the probability $\Pr\lparen X\leq m\rparen$ for some $m\in\mathbb{R}$ . Then, there exists a quantum algorithm $\mathsf{FindMin}\lparen U,M,\delta\rparen$ that, with probability at least $1-\delta$ , outputs a state $\lvert\psi_{i}\rangle\lvert x_{i}\rangle$ where $x_{i}\leq m$ , using $\widetilde{O}\lparen 1/\sqrt{M}\rparen$ queries to $U$ .

Using this theorem, we can establish the following result for finding a weak $(k,\varepsilon)$ -approximate minimum index set, extending and generalizing the approximate minimum finding procedure proposed in [40]. To express the algorithm more compactly, let $\mathsf{Uniform}$ be a unitary such that $\mathsf{Uniform}\lvert 0\rangle=\frac{1}{\sqrt{n}}\sum_{j=1}^{n}\lvert j\rangle$ , which can be implemented by $\widetilde{O}(1)$ one- and two-qubit gates.

Algorithm 1

\mathsf{FindApproxWeakMin}\lparen V,k,\varepsilon,\delta\rparen

.

Theorem 17 (Approximate Weak Minimum Index Set Finding).

Suppose $v=(v_{1},\ldots,v_{n})\in\mathbb{R}^{n}_{\geq 0}$ is an $n$ -dimensional vector with $v_{j}\in\mathopen{[}0,1\mathclose{]}$ for $j\in[n]$ . For $\varepsilon\in\mathopen{[}0,1/2\mathclose{)}$ and $\delta\in\mathopen{[}0,1/2\mathclose{)}$ , let $V$ be a $d$ -dimensional $(\varepsilon,\delta)$ -approximate oracle for $v$ , Then, there is a quantum algorithm $\mathsf{FindApproxWeakMin}\lparen V,k,\varepsilon,\delta\rparen$ that, with probability at least $1-\delta-\widetilde{O}(nd\delta\sqrt{kd})$ , outputs a weak $(k,O(\varepsilon))$ -approximate minimum index set $S$ for $v$ , using $\widetilde{O}\lparen\sqrt{nk}\rparen$ queries to $V$ .

The proof of this theorem is given in the full version (see [16, Theorem B.4]).

We further note that, the failure probability could be made to $1-O(\delta)$ by introducing an extra logarithmic multiplicative term in query complexity as Proposition 7 suggests.

6 Quantum Algorithms for Finding Strong Approximate Minimum Index Set

In this section, we present a quantum algorithm, $\mathsf{FindApproxStrongMin}$ , which returns a strong approximate minimum index set. This algorithm builds on the method used for finding a weak approximate minimum index set.

The core idea of our algorithm is to first employ the algorithm $\mathsf{FindApproxWeakMin}$ for an estimate $v_{\textup{g}}$ of the $k$ -th smallest entry of $v$ , and then repeatedly sample from an “amplified” approximate oracle which facilitates querying entries that are approximately less than $v_{\textup{g}}-5\varepsilon$ . The algorithm, explicitly given in Algorithm 2 uses two key subroutines $\mathsf{QCount}(V,c,\delta)$ and $\mathsf{AmpSamp}(V,c,\delta)$ where $V$ is an approximate oracle for the vector $v$ , $c$ is a positive number, and $\delta\in\mathopen{[}0,1/2\mathclose{]}$ . The goal of $\mathsf{QCount}(V,c,\delta)$ is to approximately estimate the amplitude of all indices whose estimated value is no more than $c$ , while the goal of $\mathsf{AmpSamp}(V,c,\delta)$ is to perform amplitude amplification on this state to achieve constant success probability. The formal statements of these procedures can be found in the full version, particularly in [16, Proposition C.3, Proposition C.6].

To describe the algorithm concisely, we use $\mathsf{ApproxQuery}\lparen V,i\rparen$ to denote a single computational measurement result of the state $V\lvert i\rangle\lvert 0\rangle$ . For an index set $S\subseteq[n]$ , $\mathsf{ApproxQuery}\lparen V,S\rparen$ represents the collection of computational measurement outcomes of $V\lvert i\rangle\lvert 0\rangle$ for all $i\in S$ .

Algorithm 2

\mathsf{FindApproxStrongMin}\lparen V,k,\varepsilon,\delta\rparen

.

The following theorem states the correctness and the time efficiency of this algorithm.

Theorem 18 (Approximate Strong Minimum Index Set Finding).

Suppose $v=(v_{1},\ldots,v_{n})\in\mathbb{R}^{n}_{\geq 0}$ is an $n$ -dimensional vector with $v_{j}\in\mathopen{[}0,1\mathclose{]}$ for $j\in[n]$ . For $\varepsilon\in\mathopen{[}0,1/2\mathclose{)}$ , $\delta\in\mathopen{[}0,1/2\mathclose{)}$ , and $\delta_{0}\in\mathopen{[}0,1/2\mathclose{)}$ , let $V$ be a $d$ -dimensional $(\varepsilon,\delta_{0})$ -approximate oracle for $v$ , Then, there is a quantum algorithm $\mathsf{FindApproxStrongMin}\lparen V,k,\varepsilon,\delta\rparen$ that, with probability at least $1-\delta-\widetilde{O}(nd\delta_{0}\sqrt{kd})$ , outputs a strong $(k,O(\varepsilon))$ -approximate minimum index set $S$ for $v$ , using $\widetilde{O}\lparen\sqrt{nk}\rparen$ queries to $V$ .

Due to the length limit, we leave a complete proof to Appendix C in [16] in the full version.

7 Applications

7.1 Approximate ${k}$ -minimum Expectations

As an application of our quantum approximate $k$ -minimum finding algorithms, we address the problem of finding approximate $k$ minima in multiple expectations. This can be directly solved by combining our algorithms with quantum amplitude estimation. The formal statement of the problem is as follows.

Definition 19 (Approximate $k$ -minimum Expectations).

For a positive integer $n$ , let $\{\rho_{i}\}_{i=1}^{n}$ be a set of $s$ -qubit density matrices, and $\{O_{i}\}_{i=1}^{n}$ be a set of $s$ -qubit positive semi-definite observables with $\lVert O_{i}\rVert\leq 1$ for $i\in[n]$ . Given the unitary $U$ being the purified access to $\rho_{i}$ , i.e., $U\lvert i\rangle_{A}\lvert 0\rangle_{B}\lvert 0\rangle_{C}=\lvert i\rangle_{A}% \lvert\rho_{i}\rangle_{BC},\text{such that }\operatorname{tr}_{C}\left\lparen\lvert\rho_{i}\rangle\langle\rho_{i}% \rvert\right\rparen=\rho_{i}$ , and a unitary $V=\sum_{j\in[n]}\lvert j\rangle\langle j\rvert\otimes V_{j}$ , where $V_{j}$ is a $1$ -block-encoding of the observable $O_{j}$ for each $j\in[n]$ . The approximate $k$ -minimum expectations problem requires to find a strong $(k,\varepsilon)$ -approximate minimum index set for the vector $v$ with coordinates $v_{i}=\operatorname{tr}\lparen O_{i}\rho_{i}\rparen$ .

By leveraging our algorithms for finding strong approximate minimum index sets alongside quantum expectation estimation algorithms, we present the following theorem, which effectively addresses the problem of finding approximate $k$ -minimum expectations.

Theorem 20.

For a positive integer $n$ , let $\{\rho_{i}\}_{i=1}^{n}$ be a set of $s$ -qubit density matrices with purified access $U_{\rho}$ , and let $\{O_{i}\}_{i=1}^{n}$ be a set of $s$ -qubit positive semi-definite observables with block-encoding access $V$ where $\lVert O_{i}\rVert\leq 1$ for $i\in[n]$ . Then, there is a quantum algorithm $\mathsf{FindApproxExpectationMin}\lparen U_{\rho},V,k,\varepsilon,\delta\rparen$ that, with probability at least $1-\delta$ , finds a strong $(k,\varepsilon)$ -approximate minimum index set for the vector $v$ with coordinates $v_{i}=\operatorname{tr}\lparen O_{i}\rho_{i}\rparen$ , using $\widetilde{O}\lparen\sqrt{nk}/\varepsilon\rparen$ queries to $U_{\rho}$ and $V$ .

Proof.

See [16, Theorem D.5] in the full version. $\hfill\blacktriangleleft$

7.2 Approximate ${k}$ -ground Energy Problem

We now turn to the approximate $k$ -ground state energy problem, a generalization of the task of approximating the ground state energy of a Hamiltonian. The formal definition of the problem is as follows.

Definition 21 (Approximate $k$ -ground State Energy).

Let $H$ be a Hamiltonian acting on $n$ -dimensional Hilbert space satisfying $\lVert H\rVert\leq\beta$ , with a spectral decomposition $H=\sum_{j=1}^{n}\lambda_{j}\lvert\varphi_{j}\rangle\langle\varphi_{j}\rvert$ . Assume that the eigenvalues ${\{\lambda_{j}\}}_{j=1}^{n}$ of $H$ can be sorted as $\lambda_{s_{1}}\leq\lambda_{s_{2}}\leq\cdots\leq\lambda_{s_{n}}$ . Let a unitary $U_{\textup{enc}}$ be an $1$ -block encoding of $H$ , and $U_{\textup{basis}}$ be a unitary satisfying $U_{\textup{basis}}\lvert j\rangle\lvert 0\rangle=\lvert j\rangle\lvert\varphi_% {j}\rangle$ . For a positive integer $k$ and a positive real number $\varepsilon$ , the approximate $(k,\varepsilon)$ -ground state energy problem is to find a strong $(k,\varepsilon)$ -approximate minimum index set for the vector $v$ with coordinates $v_{i}=\lambda_{i}$ .

By integrating our quantum algorithms for finding strong approximate minimum index sets with quantum phase estimation, we present the following theorem that effectively solves the problem of finding approximate $k$ -ground state energy, as also stated and proved in [16, Theorem D.9] in the full version.

Theorem 22.

For $k\in\mathbb{N}^{+}$ and $\varepsilon,\delta\in\mathopen{(}0,1/3\mathclose{)}$ , there is a quantum algorithm that, with probability at least $1-\delta$ , solves the problem defined in Definition 21 using $\widetilde{O}\lparen\beta\sqrt{nk}/\varepsilon\rparen$ queries to $U_{\textup{enc}}$ and $U_{\textup{basis}}$ .

$\blacktriangleright$ Remark 23.

The algorithm described in Theorem 22 can be employed in the case when the Hamiltonian is diagonal (with respect to the computational basis, i.e., $U_{\textup{basis}}\lvert j\rangle\lvert 0\rangle=\lvert j\rangle\lvert j\rangle$ ). This scenario aligns precisely with the particular case discussed in Line 2 of Algorithm 2 in [15]. We therefore address the issue noted in Remark 2.

8 Discussion

In this paper, we carefully examined quantum algorithms for $k$ -minimum finding with access to approximate oracles for function values. We introduced two distinct notions of approximate minimum index sets. The weak notion is defined entry-wise and possesses an error-tolerant incrementability property, which facilitates the design of efficient algorithms. However, this notion may be insufficient for certain applications. To address this, we introduced a stronger notion of approximate minimum index sets and developed algorithms by combining the weak $k$ -minimum finding algorithm with a coupon collector argument. We also discussed two potential applications related to the expectations of observables and the ground energy of Hamiltonians. Several intriguing open problems remain as a result of our work.

$\blacksquare$

The query complexity of the approximate minimum index set finding problem is not optimal yet. Is it possible to remove the extra logarithmic factors from the query complexity in Theorem 1?
$\blacksquare$

Can we approximate the $k$ ground state energies of a Hamiltonian without knowing its eigenbasis?
$\blacksquare$

Can we find more types of input oracles for the minimum finding problem which are reasonable abstractions of practical scenarios? Is it possible to design algorithms for minimum finding using these oracles with optimal query complexity?
$\blacksquare$

Can we find more applications of quantum approximate $k$ -minimum finding? We believe that our quantum algorithms in Theorem 1 could be applicable in other scenarios.

References

[1] Scott Aaronson. Shadow tomography of quantum states. SIAM Journal on Computing, 49(5):STOC18–368–STOC18–394, 2020. doi:10.1137/18M120275X.
[2] Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55(3):395–421, 2009. doi:10.1007/s00453-008-9168-0.
[3] Esma Aïmeur, Gilles Brassard, and Sébastien Gambs. Quantum speed-up for unsupervised learning. Machine Learning, 90(2):261–287, 2013. doi:10.1007/s10994-012-5316-5.
[4] Shyan Akmal and Ce Jin. Near-optimal quantum algorithms for string problems. Algorithmica, 85(8):2260–2317, 2023. doi:10.1007/s00453-022-01092-x.
[5] Andris Ambainis, Arturs Bačkurs, Nikolajs Nahimovs, and Alexander Rivosh. Grover’s algorithm with errors. In Proceedings of the 8th International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, pages 180–189, 2012. doi:10.1007/978-3-642-36046-6_17.
[6] Simon Apers and Ronald de Wolf. Quantum speedup for graph sparsification, cut approximation, and Laplacian solving. SIAM Journal on Computing, 51(6):1703–1742, 2022. doi:10.1137/21M1391018.
[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195–202, 2017. doi:10.1038/nature23474.
[8] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 27:1–27:14, 2019. doi:10.4230/LIPIcs.ICALP.2019.27.
[9] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Information, volume 305, pages 53–74. American Mathematical Society, 2002. doi:10.1090/conm/305/05215.
[10] Costin Bădescu and Ryan O’Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398–1411. Association for Computing Machinery, 2021. doi:10.1145/3406325.3451109.
[11] Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, volume 261, pages 38:1–38:21, 2023. doi:10.4230/LIPIcs.ICALP.2023.38.
[12] Ronald de Wolf. Quantum computing: Lecture notes, 2023. arXiv:1907.09415.
[13] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. doi:10.1137/050644719.
[14] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. ArXiv e-prints, 1996. arXiv:quant-ph/9607014.
[15] Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. Logarithmic-regret quantum learning algorithms for zero-sum games. In Advances in Neural Information Processing Systems, volume 36, pages 31177–31203, 2023. URL: https://proceedings.neurips.cc/paper_files/paper/2023/hash/637df18481a6aa74238bd2cafff94cb9-Abstract-Conference.html.
[16] Minbo Gao, Zhengfeng Ji, and Qisheng Wang. Quantum approximate $k$ -minimum finding, 2024. The full version of this paper also includes references [12, 18, 28, 29, 33, 41]. arXiv:2412.16586.
[17] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366.
[18] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation, 2022. arXiv:2203.15993.
[19] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212–219, 1996. doi:10.1145/237814.237866.
[20] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. The NISQ complexity of collision finding. In Proceedings of the 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3–32, 2024. doi:10.1007/978-3-031-58737-5_1.
[21] Peter Høyer, Michele Mosca, and Ronald de Wolf. Quantum search on bounded-error inputs. In Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, pages 291–299, 2003. doi:10.1007/3-540-45061-0_25.
[22] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. doi:10.1038/s41567-020-0932-7.
[23] William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O’Brien, Nathan Wiebe, and Ryan Babbush. Nearly optimal quantum algorithm for estimating multiple expectation values. Physical Review Letters, 129:240501, December 2022. doi:10.1103/PhysRevLett.129.240501.
[24] Ce Jin and Jakob Nogler. Quantum speed-ups for string synchronizing sets, longest common substring, and $k$ -mismatch matching. ACM Transactions on Algorithms, 20(4):32:1–32:36, 2024. doi:10.1145/3672395.
[25] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv e-prints, 1995. arXiv:quant-ph/9511026.
[26] Dmitry Kravchenko, Nikolajs Nahimovs, and Alexander Rivosh. Grover’s search with faults on some marked elements. International Journal of Foundations of Computer Science, 29(4):647–662, 2018. doi:10.1142/S0129054118410095.
[27] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. ArXiv e-prints, 2013. arXiv:1307.0411.
[28] Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical Review Letters, 118:010501, January 2017. doi:10.1103/PhysRevLett.118.010501.
[29] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3:163, July 2019. doi:10.22331/q-2019-07-12-163.
[30] Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11–12):1053–1068, November 2009. doi:10.26421/QIC9.11-12-8.
[31] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.
[32] Yihui Quek, Clement Canonne, and Patrick Rebentrost. Robust quantum minimum finding with an application to hypothesis selection. ArXiv e-prints, 2020. arXiv:2003.11777.
[33] Patrick Rall. Quantum algorithms for estimating physical quantities using block encodings. Phys. Rev. A, 102:022408, August 2020. doi:10.1103/PhysRevA.102.022408.
[34] H. Ramesh and V. Vinay. String matching in $\widetilde{O}(\sqrt{n}+\sqrt{m})$ quantum time. Journal of Discrete Algorithms, 1(1):103–110, 2003. doi:10.1016/S1570-8667(03)00010-8.
[35] Ansis Rosmanis. Quantum search with noisy oracle. ArXiv e-prints, 2023. arXiv:2309.14944.
[36] Ansis Rosmanis. Addendum to “quantum search with noisy oracle”. ArXiv e-prints, 2024. arXiv:2405.11973.
[37] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172–185, 2015. doi:10.1080/00107514.2014.964942.
[38] Neil Shenvi, Kenneth R. Brown, and K. Birgitta Whaley. Effects of a random noisy oracle on search algorithm complexity. Physical Review A, 68(5):052313, 2003. doi:10.1103/PhysRevA.68.052313.
[39] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 99:1–99:15, 2019. doi:10.4230/LIPIcs.ICALP.2019.99.
[40] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-Solvers: Better upper and lower bounds. Quantum, 4:230, 2020. doi:10.22331/q-2020-02-14-230.
[41] Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory, 70(12):8791–8805, 2024. doi:10.1109/tit.2024.3447915.
[42] Qisheng Wang and Mingsheng Ying. Quantum algorithm for lexicographically minimal string rotation. Theory of Computing Systems, 68(1):29–74, 2024. doi:10.1007/s00224-023-10146-8.
[43] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information and Computation, 15(3–4):316–356, 2015. doi:10.26421/QIC15.3-4-7.

[bib.bib1] [1] Scott Aaronson. Shadow tomography of quantum states. SIAM Journal on Computing, 49(5):STOC18–368–STOC18–394, 2020. doi:10.1137/18M120275X.

[bib.bib2] [2] Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55(3):395–421, 2009. doi:10.1007/s00453-008-9168-0.

[bib.bib3] [3] Esma Aïmeur, Gilles Brassard, and Sébastien Gambs. Quantum speed-up for unsupervised learning. Machine Learning, 90(2):261–287, 2013. doi:10.1007/s10994-012-5316-5.

[bib.bib4] [4] Shyan Akmal and Ce Jin. Near-optimal quantum algorithms for string problems. Algorithmica, 85(8):2260–2317, 2023. doi:10.1007/s00453-022-01092-x.

[bib.bib5] [5] Andris Ambainis, Arturs Bačkurs, Nikolajs Nahimovs, and Alexander Rivosh. Grover’s algorithm with errors. In Proceedings of the 8th International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, pages 180–189, 2012. doi:10.1007/978-3-642-36046-6_17.

[bib.bib6] [6] Simon Apers and Ronald de Wolf. Quantum speedup for graph sparsification, cut approximation, and Laplacian solving. SIAM Journal on Computing, 51(6):1703–1742, 2022. doi:10.1137/21M1391018.

[bib.bib7] [7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195–202, 2017. doi:10.1038/nature23474.

[bib.bib8] [8] Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 27:1–27:14, 2019. doi:10.4230/LIPIcs.ICALP.2019.27.

[bib.bib9] [9] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Information, volume 305, pages 53–74. American Mathematical Society, 2002. doi:10.1090/conm/305/05215.

[bib.bib10] [10] Costin Bădescu and Ryan O’Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1398–1411. Association for Computing Machinery, 2021. doi:10.1145/3406325.3451109.

[bib.bib11] [11] Yanlin Chen and Ronald de Wolf. Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints. In Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, volume 261, pages 38:1–38:21, 2023. doi:10.4230/LIPIcs.ICALP.2023.38.

[bib.bib12] [12] Ronald de Wolf. Quantum computing: Lecture notes, 2023. arXiv:1907.09415.

[bib.bib13] [13] Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla. Quantum query complexity of some graph problems. SIAM Journal on Computing, 35(6):1310–1328, 2006. doi:10.1137/050644719.

[bib.bib14] [14] Christoph Dürr and Peter Høyer. A quantum algorithm for finding the minimum. ArXiv e-prints, 1996. arXiv:quant-ph/9607014.

[bib.bib15] [15] Minbo Gao, Zhengfeng Ji, Tongyang Li, and Qisheng Wang. Logarithmic-regret quantum learning algorithms for zero-sum games. In Advances in Neural Information Processing Systems, volume 36, pages 31177–31203, 2023. URL: https://proceedings.neurips.cc/paper_files/paper/2023/hash/637df18481a6aa74238bd2cafff94cb9-Abstract-Conference.html.

[bib.bib16] [16] Minbo Gao, Zhengfeng Ji, and Qisheng Wang. Quantum approximate $k$ -minimum finding, 2024. The full version of this paper also includes references [12, 18, 28, 29, 33, 41]. arXiv:2412.16586.

[bib.bib17] [17] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. doi:10.1145/3313276.3316366.

[bib.bib18] [18] András Gilyén and Alexander Poremba. Improved quantum algorithms for fidelity estimation, 2022. arXiv:2203.15993.

[bib.bib19] [19] Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212–219, 1996. doi:10.1145/237814.237866.

[bib.bib20] [20] Yassine Hamoudi, Qipeng Liu, and Makrand Sinha. The NISQ complexity of collision finding. In Proceedings of the 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 3–32, 2024. doi:10.1007/978-3-031-58737-5_1.

[bib.bib21] [21] Peter Høyer, Michele Mosca, and Ronald de Wolf. Quantum search on bounded-error inputs. In Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, pages 291–299, 2003. doi:10.1007/3-540-45061-0_25.

[bib.bib22] [22] Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020. doi:10.1038/s41567-020-0932-7.

[bib.bib23] [23] William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O’Brien, Nathan Wiebe, and Ryan Babbush. Nearly optimal quantum algorithm for estimating multiple expectation values. Physical Review Letters, 129:240501, December 2022. doi:10.1103/PhysRevLett.129.240501.

[bib.bib24] [24] Ce Jin and Jakob Nogler. Quantum speed-ups for string synchronizing sets, longest common substring, and $k$ -mismatch matching. ACM Transactions on Algorithms, 20(4):32:1–32:36, 2024. doi:10.1145/3672395.

[bib.bib25] [25] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. ArXiv e-prints, 1995. arXiv:quant-ph/9511026.

[bib.bib26] [26] Dmitry Kravchenko, Nikolajs Nahimovs, and Alexander Rivosh. Grover’s search with faults on some marked elements. International Journal of Foundations of Computer Science, 29(4):647–662, 2018. doi:10.1142/S0129054118410095.

[bib.bib27] [27] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum algorithms for supervised and unsupervised machine learning. ArXiv e-prints, 2013. arXiv:1307.0411.

[bib.bib28] [28] Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical Review Letters, 118:010501, January 2017. doi:10.1103/PhysRevLett.118.010501.

[bib.bib29] [29] Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3:163, July 2019. doi:10.22331/q-2019-07-12-163.

[bib.bib30] [30] Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11–12):1053–1068, November 2009. doi:10.26421/QIC9.11-12-8.

[bib.bib31] [31] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. doi:10.1017/CBO9780511976667.

[bib.bib32] [32] Yihui Quek, Clement Canonne, and Patrick Rebentrost. Robust quantum minimum finding with an application to hypothesis selection. ArXiv e-prints, 2020. arXiv:2003.11777.

[bib.bib33] [33] Patrick Rall. Quantum algorithms for estimating physical quantities using block encodings. Phys. Rev. A, 102:022408, August 2020. doi:10.1103/PhysRevA.102.022408.

[bib.bib34] [34] H. Ramesh and V. Vinay. String matching in $\widetilde{O}(\sqrt{n}+\sqrt{m})$ quantum time. Journal of Discrete Algorithms, 1(1):103–110, 2003. doi:10.1016/S1570-8667(03)00010-8.

[bib.bib35] [35] Ansis Rosmanis. Quantum search with noisy oracle. ArXiv e-prints, 2023. arXiv:2309.14944.

[bib.bib36] [36] Ansis Rosmanis. Addendum to “quantum search with noisy oracle”. ArXiv e-prints, 2024. arXiv:2405.11973.

[bib.bib37] [37] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. An introduction to quantum machine learning. Contemporary Physics, 56(2):172–185, 2015. doi:10.1080/00107514.2014.964942.

[bib.bib38] [38] Neil Shenvi, Kenneth R. Brown, and K. Birgitta Whaley. Effects of a random noisy oracle on search algorithm complexity. Physical Review A, 68(5):052313, 2003. doi:10.1103/PhysRevA.68.052313.

[bib.bib39] [39] Joran van Apeldoorn and András Gilyén. Improvements in quantum SDP-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, volume 132, pages 99:1–99:15, 2019. doi:10.4230/LIPIcs.ICALP.2019.99.

[bib.bib40] [40] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-Solvers: Better upper and lower bounds. Quantum, 4:230, 2020. doi:10.22331/q-2020-02-14-230.

[bib.bib41] [41] Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory, 70(12):8791–8805, 2024. doi:10.1109/tit.2024.3447915.

[bib.bib42] [42] Qisheng Wang and Mingsheng Ying. Quantum algorithm for lexicographically minimal string rotation. Theory of Computing Systems, 68(1):29–74, 2024. doi:10.1007/s00224-023-10146-8.

[bib.bib43] [43] Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning. Quantum Information and Computation, 15(3–4):316–356, 2015. doi:10.26421/QIC15.3-4-7.

Quantum Approximate 𝒌-Minimum Finding

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Approximate Oracles and Approximate Minimum Index Sets

1.1.1 Approximate Oracles

1.1.2 Approximate Minimum Index Set

Weak Approximate Minimum Index Set.

Strong Approximate Minimum Index Set.

Relationships between the two definitions.

1.2 Main Results

Theorem 1 (Quantum Approximate k-minimum Finding, informal version of Theorem 17 and Theorem 18).

1.3 Techniques

1.4 Applications

Approximate 𝒌 minima in multiple expectations.

Approximate 𝒌 ground state energies.

▶ Remark 2.

2 Preliminaries

2.1 Notations

2.2 Concepts in Quantum Computing

Proposition 3.

Definition 4 (Block-encoding [17, Definition 24]).

3 Approximate Oracle

Definition 5 (Approximate Oracle).

▶ Remark 6.

Proposition 7 (Failure probability reduction of the approximate oracle).

3.1 Comparisons of Different Oracles

Bounded-error Oracle.

Untrustworthy Oracle.

▶ Remark 8.

4 Approximate 𝒌-Minimum Index Set: Weak and Strong Definitions

Definition 9 (Approximate Minimum Index).

▶ Remark 10.

Definition 11 (Weak Approximate Minimum Index Set).

Proposition 12 (Error-tolerant Incrementability).

Definition 13 (Strong Approximate Minimum Index Set).

Proposition 14.

Example 15 (No Error-Tolerant Incrementability for Strong Approximate Minimum Index Set).

5 Quantum Algorithms for Finding Weak Approximate Minimum Index Sets

Theorem 16 (Generalized Minimum Finding, [40, Theorem 49]).

Theorem 17 (Approximate Weak Minimum Index Set Finding).

6 Quantum Algorithms for Finding Strong Approximate Minimum Index Set

Theorem 18 (Approximate Strong Minimum Index Set Finding).

7 Applications

7.1 Approximate 𝒌-minimum Expectations

Definition 19 (Approximate k-minimum Expectations).

Theorem 20.

Proof.

7.2 Approximate 𝒌-ground Energy Problem

Definition 21 (Approximate k-ground State Energy).

Theorem 22.

▶ Remark 23.

8 Discussion

References

Quantum Approximate $\bm{k}$ -Minimum Finding

Theorem 1 (Quantum Approximate $k$ -minimum Finding, informal version of Theorem 17 and Theorem 18).

Approximate ${k}$ minima in multiple expectations.

Approximate ${k}$ ground state energies.

$\blacktriangleright$ Remark 2.

$\blacktriangleright$ Remark 6.

$\blacktriangleright$ Remark 8.

4 Approximate ${k}$ -Minimum Index Set: Weak and Strong Definitions

$\blacktriangleright$ Remark 10.

7.1 Approximate ${k}$ -minimum Expectations

Definition 19 (Approximate $k$ -minimum Expectations).

7.2 Approximate ${k}$ -ground Energy Problem

Definition 21 (Approximate $k$ -ground State Energy).

$\blacktriangleright$ Remark 23.