Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.04560

Quantum Submodular Maximization

Yonggang Jiang, Xiaoming Sun, Penghui Yao, Zekun Ye, Jialin Zhang, Zhijie Zhang

quant-phcs.CCcs.DSSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper studies the quantum value-query complexity of maximizing nonnegative submodular functions, both without constraints and, for monotone objectives, under a cardinality budget $k$ on an $n$-element ground set. Access is through an exact reversible digital value oracle; queries may address infeasible sets. For unconstrained maximization, it gives an expected $(1/2-\varepsilon)$-approximation using $O(\varepsilon^{-4}\log(2n/\varepsilon)\log(2/\varepsilon))$ queries. For fixed accuracy, this is $O(\log n)$, versus the classical $\Omega(n/\log n)$ requirement for any fixed expected ratio above $1/4$. For monotone cardinality-constrained maximization, a bounded-error $(1-1/e-\varepsilon)$-approximation uses $\widetilde O(\min\{\varepsilon^{-3}\sqrt n,\varepsilon^{-4}n/k\})$ queries. At fixed density $k=cn$, the bound becomes $O_{\varepsilon,c}(\log n)$, yielding an exponential separation when $c<1-1/e-\varepsilon$. Both algorithms extract simultaneous marginal statistics from local measurements of Boolean phase states. The unconstrained algorithm combines Fourier-based gradient reconstruction with noisy simultaneous double greedy and random restrictions. The constrained algorithm estimates random-order marginal scores, certifies batches by exact value checks, and amortizes amplitude-amplification cost against obtained gain. Quantum hybrid arguments applied to hidden-instance constructions give exponential lower bounds above the classical approximation thresholds: $\exp(\Omega(\varepsilon^2n))$ beyond $1/2$, and $\exp(\Omega(\varepsilon^2k))$ beyond $1-1/e$ when $k/n\le\varepsilon$. A further $\Omega_a(\sqrt{n/k})$ bound holds for constant approximation ratio $a$. The results bound queries, not runtime, gate complexity, or output cost. They rely on exact value access; the unconstrained algorithm permits exact unrestricted inter-query operations. The cardinality bounds remain unmatched for growing $k$, and the exponential lower bounds leave possible quadratic improvements unresolved.

Likely largely AI-generatedAI use disclosed
assisted in exploring algorithmic ideas, developing and refining proofs of the approximation and running-time guarantees, examining connections to related work, and drafting and revising the manuscript.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
62 pages; abstract shortened for arXiv

Related papers

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 $δ$.

quant-pharXiv:2610.01940•Oct 2, 2026•0 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.

•Dec 19, 2025•0 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803•Oct 6, 2026•1 citation

Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss

Hao Wang, Zhang, Chenyi, Tongyang Li

The problem of minimizing the maximum of $N$ convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring $O(Nε^{-2/3} + ε^{-8/3})$ queries to a first-order oracle to compute an $ε$-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of $\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})$. On the other hand, we prove that quantum algorithms must take $\tildeΩ(\sqrt{N}ε^{-2/3})$ queries to a first order quantum oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic factors.

arXiv:2402.12745•Feb 20, 2024•1 citation

Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4 more

We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of $n$-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error $Θ(n^{-1/2})$ requires $Ω(n)$ membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within $Θ(n^{-3/2})$ distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real $n\times n$ matrix requires at least $n/2$ matrix-vector product queries. The construction also yields an $Ω(n)$ phase-query lower bound for estimating the minimum eigenvalue of a real symmetric $n\times n$ matrix to additive accuracy $Θ(n^{-2})$. These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an $Ω(\min\{\sqrtκ,n\})$ gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and $κ$-smooth functions, which is optimal up to a logarithmic factor.

quant-pharXiv:2609.09035•Sep 9, 2026•0 citations

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin +4 more

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.

arXiv:2611.09809•Nov 6, 2026•0 citations
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 kkk on an nnn-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)(1/2-\varepsilon)(1/2−ε)-approximation using only Oε(log⁡n)O_\varepsilon(\log n)Oε​(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/41/41/4 requires Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) 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−ε)(1-1/e-\varepsilon)(1−1/e−ε)-approximation using O~ε(min⁡{n,n/k})\widetilde O_\varepsilon(\min\{\sqrt n,n/k\})Oε​(min{n​,n/k}) queries. When k=o(n)k=o(n)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=cnk=cnk=cn for any fixed rational c<1−1/e−εc<1-1/e-\varepsilonc<1−1/e−ε, the query complexity reduces to Oε,c(log⁡n)O_{\varepsilon,c}(\log n)Oε,c​(logn), yielding an exponential separation from the classical Ω(n/log⁡n)Ω(n/\log n)Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp⁡(Ω(ε2n))\exp(Ω(\varepsilon^2n))exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε1/2+\varepsilon1/2+ε without constraints, and exp⁡(Ω(ε2k))\exp(Ω(\varepsilon^2k))exp(Ω(ε2k)) queries for exceeding 1−1/e+ε1-1/e+\varepsilon1−1/e+ε when k/n≤εk/n\le\varepsilonk/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
The paper studies the quantum value-query complexity of maximizing nonnegative submodular functions, both without constraints and, for monotone objectives, under a cardinality budget kkk on an nnn-element ground set. Access is through an exact reversible digital value oracle; queries may address infeasible sets.
For unconstrained maximization, it gives an expected (1/2−ε)(1/2-\varepsilon)(1/2−ε)-approximation using O(ε−4log⁡(2n/ε)log⁡(2/ε))O(\varepsilon^{-4}\log(2n/\varepsilon)\log(2/\varepsilon))O(ε−4log(2n/ε)log(2/ε)) queries. For fixed accuracy, this is O(log⁡n)O(\log n)O(logn), versus the classical Ω(n/log⁡n)\Omega(n/\log n)Ω(n/logn) requirement for any fixed expected ratio above 1/41/41/4. For monotone cardinality-constrained maximization, a bounded-error (1−1/e−ε)(1-1/e-\varepsilon)(1−1/e−ε)-approximation uses O~(min⁡{ε−3n,ε−4n/k})\widetilde O(\min\{\varepsilon^{-3}\sqrt n,\varepsilon^{-4}n/k\})O(min{ε−3n​,ε−4n/k}) queries. At fixed density k=cnk=cnk=cn, the bound becomes Oε,c(log⁡n)O_{\varepsilon,c}(\log n)Oε,c​(logn), yielding an exponential separation when c<1−1/e−εc<1-1/e-\varepsilonc<1−1/e−ε.
Both algorithms extract simultaneous marginal statistics from local measurements of Boolean phase states. The unconstrained algorithm combines Fourier-based gradient reconstruction with noisy simultaneous double greedy and random restrictions. The constrained algorithm estimates random-order marginal scores, certifies batches by exact value checks, and amortizes amplitude-amplification cost against obtained gain.
Quantum hybrid arguments applied to hidden-instance constructions give exponential lower bounds above the classical approximation thresholds: exp⁡(Ω(ε2n))\exp(\Omega(\varepsilon^2n))exp(Ω(ε2n)) beyond 1/21/21/2, and exp⁡(Ω(ε2k))\exp(\Omega(\varepsilon^2k))exp(Ω(ε2k)) beyond 1−1/e1-1/e1−1/e when k/n≤εk/n\le\varepsilonk/n≤ε. A further Ωa(n/k)\Omega_a(\sqrt{n/k})Ωa​(n/k​) bound holds for constant approximation ratio aaa.
The results bound queries, not runtime, gate complexity, or output cost. They rely on exact value access; the unconstrained algorithm permits exact unrestricted inter-query operations. The cardinality bounds remain unmatched for growing kkk, and the exponential lower bounds leave possible quadratic improvements unresolved.
Given oracle access to an unknown unitary U=eiHU=e^{iH}U=eiH , the fractional query problem asks how many queries are required to implement a noninteger power Ut=eitHU^t=e^{itH}Ut=eitH, 0<t<10<t<10<t<1, when the spectrum is separated from the branch cut by a gap δδδ. Quantum singular value transformation gives an upper bound of O ⁣(1δlog⁡1ε)O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)O(δ1​logε1​) queries for approximation error ε\varepsilonε. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any NNN-query circuit to the approximation of eitθe^{itθ}eitθ by a trigonometric polynomial with degree bounded by O(N)O(N)O(N), together with Remez inequality. This allows us to establish the lower bound of Ωτ ⁣(1δlog⁡1ε)Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Ωτ​(δ1​logε1​). Consequently, the optimal query complexity for fractional query problem is Θτ ⁣(1δlog⁡1ε)Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)Θτ​(δ1​logε1​), 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 Ωτ ⁣(log⁡1ε)Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)Ωτ​(logε1​) bound uniform to δδδ.
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.
We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most qqq oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision εεε requires Θ(1qε2)Θ(\frac{1}{q ε^2})Θ(qε21​) queries; (ii) (Unbiased) Amplitude estimation up to a precision εεε requires Θ(p(1−p)qε2)Θ(\frac{p(1-p)}{q ε^2})Θ(qε2p(1−p)​) queries; (iii) Search among NNN items requires Θ(Nq)Θ(\frac{N}{q})Θ(qN​) queries; (iv) Two level AND-OR tree (AND of mmm ORs, with nnn inputs to each OR) requires Θ(nmq)Θ(\frac{nm}{q})Θ(qnm​) queries. All of these bounds are optimal up to a constant factor, for all qqq from 1, corresponding to the classical complexity, to Q(f)Q(f)Q(f), the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.
The problem of minimizing the maximum of NNN convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nε−2/3+ε−8/3)O(Nε^{-2/3} + ε^{-8/3})O(Nε−2/3+ε−8/3) queries to a first-order oracle to compute an εεε-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of NNN convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O~(Nε−5/3+ε−8/3)\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})O~(N​ε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3)\tildeΩ(\sqrt{N}ε^{-2/3})Ω~(N​ε−2/3) queries to a first order quantum oracle, showing that our dependence on NNN is optimal up to poly-logarithmic factors.
We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of nnn-dimensional ellipsoids. We focus on linear optimization with an explicitly given objective, where the feasible set is accessed through a membership oracle. We show that any algorithm that, for every unit linear objective, returns an exactly feasible point with additive objective error Θ(n−1/2)Θ(n^{-1/2})Θ(n−1/2) requires Ω(n)Ω(n)Ω(n) membership queries, where the ellipsoids are contained in the unit ball. The same lower bound can be shown to hold if the returned point is only required to be approximately feasible, within Θ(n−3/2)Θ(n^{-3/2})Θ(n−3/2) distance from the feasible set. This resolves an open question posed by Chakrabarti, Childs, Li, and Wu~(\textit{Quantum}, 2020) and by van Apeldoorn, Gilyén, Gribling, and de Wolf~(\textit{Quantum}, 2020). Coupled with the upper bounds in these papers, the query complexity of high-accuracy convex optimization is characterized tightly up to logarithmic factors. The proof is built around a lower bound for determinant computation that is derived via a novel polynomial method based on Fourier-rank. In the continuous matrix phase-query model, computing the determinant of a real n×nn\times nn×n matrix requires at least n/2n/2n/2 matrix-vector product queries. The construction also yields an Ω(n)Ω(n)Ω(n) phase-query lower bound for estimating the minimum eigenvalue of a real symmetric n×nn\times nn×n matrix to additive accuracy Θ(n−2)Θ(n^{-2})Θ(n−2). These results extend the determinant and minimum-eigenvalue lower bounds of Childs, Hung, and Li~(ICALP 2021) from finite fields to the real-valued setting. Based on the same constructions, we also prove an Ω(min⁡{κ,n})Ω(\min\{\sqrtκ,n\})Ω(min{κ​,n}) gradient-query lower bound for constant-accuracy optimization of 111-strongly convex and κκκ-smooth functions, which is optimal up to a logarithmic factor.
Beyond the n/2n/2n/2 Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every nnn-bit Boolean function with bounded error using n/2+O(n)n/2+O(\sqrt n)n/2+O(n​) quantum queries. In contrast, parity can be computed exactly using ⌈n/2⌉\lceil n/2\rceil⌈n/2⌉ queries, but whether an additive overhead beyond n/2n/2n/2 is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring n/2+Ω(n1/3)n/2+Ω(n^{1/3})n/2+Ω(n1/3) quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using n/2+O(n1/3)n/2+O(n^{1/3})n/2+O(n1/3) quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.