arXiv:2610.17163

Bosonic unstructured search: quantum enhancement without entanglement

Yu-Xin Wang, Erfan Abbasgholinejad, Supratik Sarkar, Sharoon Austin, Andrew M. Childs, Alexey V. Gorshkov, Mohammad Hafezi

quant-phSubmitted Oct 12, 2026• Announced Oct 13, 2026• 0 citations

arXiv HTML PDF

Abstract

We consider unstructured search using multimode bosonic quantum systems under energy constraints. The task is to locate an unknown marked mode among $N$ possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget $n_{\text{b}}\gg 1$. We analyze a continuous-time phase-shift oracle of strength $B_{0}$, with cost given by the total oracle time, and a discrete oracle with fixed phase $φ_{0}$, with cost given by the number of queries. We give algorithms that identify the target with query complexity $O(\sqrt{N}/{n_{\text{b}}}B_{0})$ for continuous-time oracles or $O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)$ for discrete oracles with $n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)$. In contrast, for discrete oracles with $n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)$, we provide an algorithm using $O(\max\{1,\sqrt{N/n_{\text{b}}|{\sin(φ_{0}/{2})}|}\})$ queries. We also prove matching lower bounds on the query complexity, showing that these algorithms are asymptotically optimal. Furthermore, we show that, in the absence of loss, non-Gaussianity is necessary to achieve the optimal joint query scaling in $N$ and $n_{\text{b}}$, but entanglement is not. Under uniform boson loss at rate $γ$, we prove a query lower bound of $Ω( γN / n _{\text{b}} B_{0}^{2} )$, attained for $γ= Ω(B_{0} \sqrt{n _{\text{b}}/N})$ using coherent-state probes. Finally, we propose experimental implementations using multipass optical microscopy or superconducting circuits as potential routes to speeding up imaging or device calibration with a low boson-number budget.

Related papers

Quantum Search with Noisy Oracle

Ansis Rosmanis

arXiv:2309.14944Sep 26, 20231 citation

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Mehil Agarwal, Shravas Rao, Fang Song

quant-pharXiv:2610.00506Oct 2, 20260 citations

Unstructured search by random and quantum walk

Thomas G. Wong

arXiv:2011.14533Quantum Information and ComputationDec 28, 20216 citations

Quantum Submodular Maximization

Yonggang Jiang, Xiaoming Sun, Penghui Yao +3 more

quant-pharXiv:2610.04560Oct 6, 20260 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

quant-pharXiv:2610.01940Oct 2, 20260 citations

Quantum Query Complexity for Nonstandard Oracles with Tight Bounds and Tradeoffs Beyond Grover

Yalla Jnan Devi Satya Prasad

Dec 19, 20250 citations

arXiv:2610.17163

Bosonic unstructured search: quantum enhancement without entanglement

Yu-Xin Wang, Erfan Abbasgholinejad, Supratik Sarkar, Sharoon Austin, Andrew M. Childs, Alexey V. Gorshkov, Mohammad Hafezi

quant-phSubmitted Oct 12, 2026• Announced Oct 13, 2026• 0 citations

arXiv HTML PDF

Abstract

We consider unstructured search using multimode bosonic quantum systems under energy constraints. The task is to locate an unknown marked mode among

N

possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget

n_{\text{b}}\gg 1

. We analyze a continuous-time phase-shift oracle of strength

B_{0}

, with cost given by the total oracle time, and a discrete oracle with fixed phase

φ_{0}

, with cost given by the number of queries. We give algorithms that identify the target with query complexity

O(\sqrt{N}/{n_{\text{b}}}B_{0})

for continuous-time oracles or

O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)

for discrete oracles with

n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)

. In contrast, for discrete oracles with

n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)

, we provide an algorithm using

O(\max\{1,\sqrt{N/n_{\text{b}}|{\sin(φ_{0}/{2})}|}\})

queries. We also prove matching lower bounds on the query complexity, showing that these algorithms are asymptotically optimal. Furthermore, we show that, in the absence of loss, non-Gaussianity is necessary to achieve the optimal joint query scaling in

N

and

n_{\text{b}}

, but entanglement is not. Under uniform boson loss at rate

γ

, we prove a query lower bound of

Ω( γN / n _{\text{b}} B_{0}^{2} )

, attained for

γ= Ω(B_{0} \sqrt{n _{\text{b}}/N})

using coherent-state probes. Finally, we propose experimental implementations using multipass optical microscopy or superconducting circuits as potential routes to speeding up imaging or device calibration with a low boson-number budget.

Related papers

Quantum Search with Noisy Oracle

Ansis Rosmanis

We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$ -query algorithms in this setting, even for constant $p$ . We show that, for all $p\le 0.99$ , the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$ . The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$. The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

arXiv:2309.14944Sep 26, 20231 citation

Noisy Quantum Query Complexity via Fractional Block Sensitivity

Mehil Agarwal, Shravas Rao, Fang Song

We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ( $\operatorname{fbs}$ ). For a negligent oracle that applies the correct query with probability $1-p$ , we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$ . We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$ . This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$ . For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by $\operatorname{fbs}(f)$ . Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity ($\operatorname{fbs}$). For a negligent oracle that applies the correct query with probability $1-p$, we prove a lower bound in terms of $\operatorname{fbs}(f,0^n)$. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function $f$ can be transformed into a partial function $f'$ whose negligent query complexity essentially preserves the quantum query complexity of $f$. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of $\operatorname{fbs}(f)$ for partial functions in this model. For two other models, we obtain general lower bounds in terms of $\operatorname{fbs}(f)$ for all Boolean functions. For hybrid algorithms using $Q$ coherent and $C$ classical queries, we prove the tradeoff $C+Q^2=Ω(\operatorname{fbs}(f))$. For an IID dephasing noisy model where each query dephases the query-index register at rate $p$ independently, we prove $Ω\!\left(p\,\operatorname{fbs}(f)\right)$ queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by $\operatorname{fbs}(f)$. Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.

quant-pharXiv:2610.00506Oct 2, 20260 citations

Unstructured search by random and quantum walk

Thomas G. Wong

The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$ , the random walks converge to the same evolution, both taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$ . In contrast, the discrete-time quantum walk asymptotically takes $\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$ , while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a success probability of $1$ .The task of finding an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$ queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large $N$, the random walks converge to the same evolution, both taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$. In contrast, the discrete-time quantum walk asymptotically takes $\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$, while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a success probability of $1$.

arXiv:2011.14533Quantum Information and ComputationDec 28, 20216 citations

Quantum Submodular Maximization

Yonggang Jiang, Xiaoming Sun, Penghui Yao +3 more

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$ -element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$ -approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$ -approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$ , our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$ , the query complexity reduces to $O_{\varepsilon,c}(\log n)$ , yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$ . These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint $k$ on an $n$-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected $(1/2-\varepsilon)$-approximation using only $O_\varepsilon(\log n)$ queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above $1/4$ requires $Ω(n/\log n)$ queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a $(1-1/e-\varepsilon)$-approximation using $\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})$ queries. When $k=o(n)$, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when $k=cn$ for any fixed rational $c<1-1/e-\varepsilon$, the query complexity reduces to $O_{\varepsilon,c}(\log n)$, yielding an exponential separation from the classical $Ω(n/\log n)$ lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of $\exp(Ω(\varepsilon^2n))$ queries for achieving a ratio beyond $1/2+\varepsilon$ without constraints, and $\exp(Ω(\varepsilon^2k))$ queries for exceeding $1-1/e+\varepsilon$ when $k/n\le\varepsilon$. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

quant-pharXiv:2610.04560Oct 6, 20260 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$ , $0<t<1$ , when the spectrum is separated from the branch cut by a gap $δ$ . Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$ . We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$ -query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$ , together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ . Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ , showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$ .Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

quant-pharXiv:2610.01940Oct 2, 20260 citations

Quantum Query Complexity for Nonstandard Oracles with Tight Bounds and Tradeoffs Beyond Grover

Yalla Jnan Devi Satya Prasad

Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.

Dec 19, 20250 citations

We consider unstructured search using multimode bosonic quantum systems under energy constraints. The task is to locate an unknown marked mode among

N

possibilities using arbitrary control, subject to a time-averaged mean-boson-number budget

n_{\text{b}}\gg 1

. We analyze a continuous-time phase-shift oracle of strength

B_{0}

, with cost given by the total oracle time, and a discrete oracle with fixed phase

φ_{0}

, with cost given by the number of queries. We give algorithms that identify the target with query complexity

O(\sqrt{N}/{n_{\text{b}}}B_{0})

for continuous-time oracles or

O(\sqrt{N}/n_{\text{b}} |{\sin(φ_{0}/{2})}|)

for discrete oracles with

n_{\text{b}} |{\sin(φ_{0}/{2})}|=O(1)

. In contrast, for discrete oracles with

n_{\text{b}} |{\sin(φ_{0}/{2})}|=Ω(1)

, we provide an algorithm using

O(\max\{1,\sqrt{N/n_{\text{b}}|{\sin(φ_{0}/{2})}|}\})

N

and

n_{\text{b}}

, but entanglement is not. Under uniform boson loss at rate

γ

, we prove a query lower bound of

Ω( γN / n _{\text{b}} B_{0}^{2} )

, attained for

γ= Ω(B_{0} \sqrt{n _{\text{b}}/N})

We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability

p>0

completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum

\mathrm{O}(\sqrt{n})

-query algorithms in this setting, even for constant

p

. We show that, for all

p\le 0.99

, the quantum noisy-query complexity of the unstructured search is

\tildeΘ(\max\{np,\sqrt{n}\})

. The lower bound

Ω(\max\{np,\sqrt n\})

holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

We study quantum query complexity under several models of imperfect oracle access, and develop lower bounds through a common framework based on fractional block sensitivity (

\operatorname{fbs}

). For a negligent oracle that applies the correct query with probability

1-p

, we prove a lower bound in terms of

\operatorname{fbs}(f,0^n)

. We also show, perhaps surprisingly, that negligence need not destroy quantum speedups: any function

f

can be transformed into a partial function

f'

whose negligent query complexity essentially preserves the quantum query complexity of

f

. This gives partial functions with exponential quantum speedups even under negligent queries, and in particular rules out a general lower bound in terms of

\operatorname{fbs}(f)

for partial functions in this model. For two other models, we obtain general lower bounds in terms of

\operatorname{fbs}(f)

for all Boolean functions. For hybrid algorithms using

Q

coherent and

C

classical queries, we prove the tradeoff

C+Q^2=Ω(\operatorname{fbs}(f))

. For an IID dephasing noisy model where each query dephases the query-index register at rate

p

independently, we prove

Ω\!\left(p\,\operatorname{fbs}(f)\right)

queries are necessary. Finally, we introduce a broader family of time-varying dephasing models and identify a variational resource that is always lower bounded by

\operatorname{fbs}(f)

. Computing this resource reduces to a convex optimization problem, providing a simple way to derive lower bounds for new noise schedules. As applications, we recover the hybrid and IID dephasing bounds and determine the query complexity of unstructured search when the dephasing rate grows over time.

The task of finding an entry in an unsorted list of

N

elements famously takes

O(N)

queries to an oracle for a classical computer and

O(\sqrt{N})

queries for a quantum computer using Grover's algorithm. Reformulated as a spatial search problem, this corresponds to searching the complete graph, or all-to-all network, for a marked vertex by querying an oracle. In this tutorial, we derive how discrete- and continuous-time (classical) random walks and quantum walks solve this problem in a thorough and pedagogical manner, providing an accessible introduction to how random and quantum walks can be used to search spatial regions. Some of the results are already known, but many are new. For large

N

, the random walks converge to the same evolution, both taking

N \ln(1/\epsilon)

time to reach a success probability of

1-\epsilon

. In contrast, the discrete-time quantum walk asymptotically takes

\pi\sqrt{N}/2\sqrt{2}

timesteps to reach a success probability of

1/2

, while the continuous-time quantum walk takes

\pi\sqrt{N}/2

time to reach a success probability of

1

We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint

k

on an

n

-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected

(1/2-\varepsilon)

-approximation using only

O_\varepsilon(\log n)

queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above

1/4

requires

Ω(n/\log n)

queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a

(1-1/e-\varepsilon)

-approximation using

\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})

queries. When

k=o(n)

, our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when

k=cn

for any fixed rational

c<1-1/e-\varepsilon

, the query complexity reduces to

O_{\varepsilon,c}(\log n)

, yielding an exponential separation from the classical

Ω(n/\log n)

lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of

\exp(Ω(\varepsilon^2n))

queries for achieving a ratio beyond

1/2+\varepsilon

without constraints, and

\exp(Ω(\varepsilon^2k))

queries for exceeding

1-1/e+\varepsilon

when

k/n\le\varepsilon

. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.

Given oracle access to an unknown unitary

U=e^{iH}

, the fractional query problem asks how many queries are required to implement a noninteger power

U^t=e^{itH}

0<t<1

, when the spectrum is separated from the branch cut by a gap

δ

. Quantum singular value transformation gives an upper bound of

O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)

queries for approximation error

\varepsilon

. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any

N

-query circuit to the approximation of

e^{itθ}

by a trigonometric polynomial with degree bounded by

O(N)

, together with Remez inequality. This allows us to establish the lower bound of

Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)

. Consequently, the optimal query complexity for fractional query problem is

Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)

, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a

Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)

bound uniform to

δ