PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana, Dylan Herman, Junhyung Lyle Kim, Guneykan Ozgul, Nadezhda Voronova

arXiv:2609.09035v2quant-phcs.DSmath.OC

TL;DR

The paper addresses the conjectured query cost of quantum optimization from membership using a Fourier-rank lower-bound method. It establishes an Ω(n) membership-query lower bound for high-accuracy optimization on explicit ellipsoids, while leaving an intermediate accuracy regime open.

  • Problem

    The query cost of implementing quantum optimization from membership remains open, with a conjecture that some n-dimensional convex bodies require Ω(n) membership queries.

    Source: §1.1 · p. 3

  • Method

    The proof uses a Fourier-rank polynomial method to establish determinant hardness, then adapts the argument to membership queries for hard ellipsoids.

    Source: §1.2 · p. 5

  • Results

    Ω(n) membership queries are necessary when ε/R ≤ 1/(200√n) for optimization over the paper’s ellipsoid family.

    Source: §1.2 · p. 3, Discussion · p. 42

  • Takeaways & Limitations

    The result proves Conjecture 1.1 for an explicit family of centered ellipsoids.

    Source: §1.2 · p. 3

    The query complexity remains open for ε/R between order n^-1/2 and order n^-1/4; the bounds use different models and hard families.

    Source: Discussion · p. 42

Abstract

from arXiv · show

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 $\Theta(n^{-1/2})$ requires $\Omega(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 $\Theta(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\'en, 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 $\Omega(n)$ phase-query lower bound for estimating the minimum eigenvalue of a real symmetric $n\times n$ matrix to additive accuracy $\Theta(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 $\Omega(\min\{\sqrt\kappa,n\})$ gradient-query lower bound for constant-accuracy optimization of $1$-strongly convex and $\kappa$-smooth functions, which is optimal up to a logarithmic factor.

Changes from Version 1

Version 2 strengthens the lower bounds and adds a detailed comparison with concurrent work; it also clarifies the precision regime and open questions.

Changes from Version 1

  • Version 2 strengthens the lower bound to Ω(n) using a reduction based on the optimal value of one random linear objective.It also strengthens the gradient-query lower bound for strongly convex quadratics to Ω(min{√κ, n}) at accuracy 1/200; the inverse-iteration argument is retained in Section 7.Source: Changes from Version 1 · p. 1
  • Version 2 adds a detailed comparison with Childs’s concurrent, independent work, which obtains similar results through closely related techniques.The comparison was not possible in Version 1 because Childs’s paper was not yet publicly available.Source: Changes from Version 1 · pp. 1–2
  • Version 2 clarifies the precision regime for the lower bounds and gives a more concrete discussion of open questions.Source: Changes from Version 1 · p. 2

1 Introduction

The introduction presents quantum query lower bounds for high-accuracy optimization over explicit ellipsoids, derived from determinant hardness via Fourier rank, alongside lower bounds for minimum-eigenvalue estimation and strongly convex quadratic optimization. It also compares the membership-oracle results with Gaussian-witness results, describes strengths of the Fourier-rank method, and outlines the paper’s sections.

1.1 Motivation

  • The work resolves the conjectured Ω(n) membership-query lower bound for quantum optimization, following earlier Ω(√n) bounds by Chakrabarti, Childs, Li, and Wu and van Apeldoorn, Gilyén, Gribling, and de Wolf.The conjecture concerned a family of convex bodies and remained open even when an interior point was given.Source: §1.1 · p. 3, §1.2 · p. 3

1.2 Contributions

  • Ω(n) membership queries are required to optimize every unit linear objective over the explicit ellipsoid family with additive error 1/(200√n), even allowing Θ(n^-3/2) approximate feasibility.The centered ellipsoids lie inside the unit ball and contain a ball of radius Θ(n^-1); the same lower bound holds for smaller objective error.Source: §1.2 · pp. 3–4
  • In the continuous matrix phase-query model, determinant computation requires at least n/2 queries, while estimating a real symmetric matrix’s minimum eigenvalue to Θ(n^-2) accuracy requires Ω(n).The eigenvalue lower bound follows by using the symmetric part of the hard determinant instances: its minimum eigenvalue distinguishes the determinant components at this accuracy.Source: §1.2 · pp. 4, 6
  • Ω(min{√κ, n}) gradient-phase queries are required for constant-accuracy optimization of 1-strongly convex, κ-smooth quadratic functions, optimal up to logarithmic factors.The bound applies to algorithms returning additive objective error at most 1/200 with probability at least 2/3.Source: §1.2 · p. 4
  • The Fourier-rank method tracks matrix-frequency rank: after T phase queries, output probabilities have rank at most 2T, and determinant is orthogonal to every frequency of rank below n.A reflection fixes each such low-rank frequency while reversing the determinant sign, so fewer than n/2 queries yield no Haar-average advantage over random guessing.Source: §1.2 · pp. 5–6

1.3 Related work

  • The ellipsoid lower bound matches the eO(n) membership-query complexity of prior quantum algorithms up to logarithmic factors.This result concerns sequential membership queries in the high-accuracy regime.Source: §1.3 · pp. 7–8
  • The first version used inverse iteration for an Ω(n/(log n log log n)) bound at order n^-4 accuracy; the present version uses one random objective and removes logarithmic factors.The first-version accuracy is relative to the outer radius.Source: §1.3 · p. 8
  • Ω(n) membership queries suffice as a lower bound at accuracy 1/(200√n), with the same bound for approximately feasible optimization.The accuracy is relative to the outer radius.Source: §1.3 · p. 8
  • Ω(min{√κ,n}) gradient queries are required for constant-accuracy optimization of strongly convex quadratics, matching accelerated gradient descent and conjugate gradient up to a logarithmic factor.The stated accuracy is 1/200.Source: §1.3 · p. 8
  • Childs’s Gaussian witnesses cover matrix functions and function-evaluation optimization beyond this paper’s scope, while Fourier-rank separates query cost from target choice and yields exact determinant-prediction orthogonality below n/2 queries.The Fourier-rank method also applies directly to Boolean membership phases, which are L2 limits of rank-one-frequency exponentials.Source: §1.3 · pp. 8–9

1.4 Organization

  • The paper defines query models, develops Fourier-rank bounds for determinant and minimum-eigenvalue estimation, constructs hard ellipsoids, proves optimization bounds, and presents an inverse-iteration argument and a continuous-register extension.These topics are organized across Sections 2–7 and Appendix A.Source: §1.4 · p. 9

2 Preliminaries

The preliminaries distinguish the finite-register membership model used for optimization from the continuous matrix phase model used for determinant and eigenvalue bounds. They also establish the geometric conventions, optimization guarantees, and Fourier tools used in the proofs.

2 Preliminaries

  • Determinant and eigenvalue bounds use a continuous matrix phase oracle, while optimization uses a binary membership oracle on finite represented points.The two arguments share a Fourier-rank obstruction, not an oracle simulation.Source: §2 · p. 9, §2.4 · p. 12

2.1 Basic notation

  • The notation takes log to mean the natural logarithm and orders symmetric-matrix eigenvalues from largest to smallest, with λmin(A) = λn(A).It also defines trace, rank, column space, positive definiteness, and the positive-semidefinite order.Source: §2.1 · pp. 9–10
  • The setup assumes known radii 0 < r ≤ R enclosing K, defines K+δ and K−δ neighborhoods, and fixes unit-sphere and orthogonal-group notation.Source: §2.1 · pp. 9–10

2.2 Defining a discretized membership oracle

  • Membership queries use a finite grid fixed before K is chosen; it can be arbitrarily fine, and the lower bound does not depend on its spacing.Source: §2.2 · p. 10
  • Exact membership counts boundary points as inside; weak membership permits either answer in the δmem boundary band, and the lower bounds apply to every admissible weak oracle without overhead.Source: §2.2 · p. 10

2.3 Optimization guarantees

  • Exactly feasible optimization requires an output in K; approximate feasibility permits an output up to δ outside K while comparing against the optimum over K−δ.For the approximate guarantee, the geometry lemma supplies a point in K within δ of the output.Source: §2.3 · p. 11

2.4 The continuous matrix phase-query model

  • The continuous phase model is an ideal L2 oracle with rank-one frequency matrices; finite-precision standard-basis encoding need not yield the same bilinear phase.The matrix lower bounds are proved directly for PQ, whereas the optimization lower bound uses only the finite binary membership oracle.Source: §2.4 · pp. 11–12

2.5 Fourier approximations

  • Fejér means average partial Fourier sums with a nonnegative, unit-mass kernel and converge at continuity points; for finitely many jumps, convergence also holds almost everywhere and in L2.Source: §2.5 · p. 12

3 Lower bounds on determinant and eigenvalue estimation

This section develops Fourier-rank and determinant-based reductions to establish matrix phase-query lower bounds for determinant prediction and minimum-eigenvalue estimation. It covers determinant prediction with an n/2-query lower bound and minimum-eigenvalue estimation for real symmetric matrices to Θ(n⁻²) accuracy, including odd dimensions.

3.1 The Fourier-rank polynomial method

  • The method tracks Fourier-frequency matrix rank rather than polynomial degree; each query increases amplitude rank by at most one, and forming an outcome probability doubles the rank bound.For an algorithm outputting a prediction in {−1, +1}, its Haar-average success probability for predicting F(Q) is exactly 1/2.Source: §3.1 · pp. 13–14

3.2 The determinant lower bound

  • Fewer than n/2 matrix phase queries yield exactly 1/2 Haar-average determinant-prediction success, implying worst-case lower bounds for orthogonal and general real matrices.Each matrix phase query has Fourier-rank cost at most one; every function of Fourier rank below n has zero Haar correlation with the determinant.Source: §3.2 · pp. 15–16, §3.1 · p. 15

3.3 From determinant to minimum-eigenvalue estimation

  • n/4 queries are necessary for even n to estimate λmin(SQ) within gn/3 with success at least 2/3, giving Ω(n) queries at Θ(n^-2) accuracy.With high probability, the determinant components have minimum eigenvalues separated by a gap of order n^-2, enabling determinant classification from the estimate.Source: §3.3 · pp. 17–18
  • The determinant reduction converts T queries to SQ into 2T determinant queries, yielding T ≥ n/4.The reduction's Haar-average success probability is strictly greater than 1/2.Source: §3.3 · p. 19
  • At accuracy Θ(n^-2), minimum-eigenvalue estimation for real symmetric n × n matrices requires Ω(n) matrix phase queries in every dimension.For odd n, the construction applies in dimension n −1 and appends a known eigenvalue.Source: §3.3 · p. 19

4 From determinant hardness to convex optimization

This section connects determinant-sign hardness to convex optimization by constructing ellipsoids that encode the determinant sign and proving membership-query hardness via Fourier rank. It also shows that a predictor based on scalar estimates for a random objective can distinguish determinant components with success probability slightly above one half.

4.1 The hard family of ellipsoids

  • A positive-definite matrix AQ defines centered hard ellipsoids whose bottom eigenvalue encodes determinant sign: it is 2gd and simple on the negative regular event, versus at least 3gd on the positive event.Source: §4 · p. 19, §4.1 · p. 20

4.2 Determinant hardness for membership queries

  • Exact membership queries require at least d/2 calls to predict det Q with success above 1/2, because each query adds at most one Fourier rank; the bound also holds for continuous query registers.The finite-grid theorem gives the lower bound, and a corollary extends it to exact coherent queries on a sigma-finite query space.Source: §4.2 · pp. 21, 23

4.3 A random objective separates the determinant components

  • A random sign objective separates determinant components by constants: when det Q = −1, its objective value is large with constant probability, while the positive-component constant is small.The negative-component argument uses the small eigenvalue of AQ and the objective's overlap with its eigenvector.Source: §4.3 · pp. 23–24

4.4 A determinant predictor from one random objective

  • The determinant predictor reuses one random sign vector across 125 independent estimates, takes their median, and outputs −1 above 9/16; estimates within 1/200 meet the stated threshold conditions.Each estimate is assumed to be close to the objective statistic with probability at least 2/3.Source: §4.4 · p. 25
  • The determinant predictor succeeds with probability greater than 1/2 + 1/2000, averaged over Q, v, and the procedure’s internal randomness.Lemma 4.8 states this result for the predictor under its scalar-estimate condition.Source: §4.4 · p. 25
  • Using the median of 125 independent executions, a strict majority of estimates within 1/200 of Z(Q, v) ensures the median is also within 1/200.Hoeffding’s inequality bounds the probability that at most half of the executions succeed by exp(−125/18) < 1/1000.Source: §4.4 · p. 26
  • The analysis averages over the two determinant components, which have equal Haar measure, to obtain the predictor’s overall success bound.On the positive component, the proof bounds the probability of a wrong prediction when a strict majority of scalar estimates succeeds.Source: §4.4 · p. 26

5 Main result: optimization lower bounds

The section combines determinant prediction with a membership-query determinant lower bound to establish a linear query lower bound for optimization over hard ellipsoids.

5.1 Linear membership-query lower bounds

  • For either exact- or approximate-feasibility conditions, any optimizer requires at least n/500 membership queries on the hard family.The theorem’s bound is T ≥ d/250 ≥ n/500.Source: §5.1 · p. 27
  • The lower bound holds on every nonempty finite query grid fixed independently of Q and also for exact coherent membership on L2(R^n) ⊗ C^2.The theorem applies at every scale of the hard ellipsoids; choosing the scale can normalize the outer radius to one.Source: §5 · p. 26, §5.1 · pp. 27–28
  • The proof converts optimization outputs into estimates of a determinant-related quantity, then applies the determinant predictor lower bound.With 125 independent invocations, the predictor has Haar-average success probability greater than 1/2, yielding the membership-query bound.Source: §5.1 · pp. 27–28
  • The unit-ball family has an inner radius r = Θ(n^-1), and the lower bound applies to every body and every unit objective.The reduction initially uses normalized sign-vector objectives; success on all unit objectives is sufficient.Source: §5.1 · pp. 27–28

6 First-order optimization of smooth and strongly convex functions

The section constructs hard strongly convex quadratics from the same matrices used for the determinant lower bound, then transfers that hardness to gradient queries. It establishes a lower bound with min{√κ, n} dependence in the ideal continuous-register model.

6.1 The hard family of quadratics

  • The hard family uses padded, normalized Hessians to produce quadratics that are 1-strongly convex and κ-smooth.The construction chooses a hard block dimension based on the condition number and pads it with known coordinates.Source: §6 · p. 28, §6.1 · p. 29

6 First-order optimization of smooth and strongly convex functions

  • The gradient-oracle equivalence is stated for the ideal continuous-register model, not for finite-precision encodings.The normalization also does not identify precision and condition number in every normalization of the hard family.Source: §6 · pp. 28–29, §6.2 · p. 31

6.2 A linear gradient-query lower bound

  • An approximate minimizer yields an estimate of a determinant-related quantity, allowing the random-objective predictor to transfer determinant hardness to optimization.Each gradient phase query uses at most two matrix phase queries, so 125 invocations using T gradient queries give a predictor using at most 250T matrix phase queries.Source: §6.2 · pp. 30–31, §6.1 · p. 30
  • The gradient-query lower bound has min{√κ, n} dependence and is optimal up to a logarithmic factor.The theorem concerns constant-accuracy optimization of explicit 1-strongly convex, κ-smooth quadratics.Source: §6.2 · p. 30
  • For q < 200, two functions with disjoint success regions show that at least one gradient query is necessary.A zero-query algorithm has the same output distribution on both functions and cannot succeed with probability at least 2/3 on each.Source: §6.2 · pp. 30–31

7 The inverse-iteration argument from the first version

This section develops inverse-iteration reductions from convex optimization to determinant prediction, using optimizer calls to approximate inverse applications. It establishes membership-query lower bounds for exactly and approximately feasible optimization, including linear bounds at the original accuracy scales, and a gradient-query lower bound for strongly convex quadratics.

7 The inverse-iteration argument from the first version

  • The inverse-iteration reduction uses O(log d log log d) optimizer invocations with adaptively chosen objectives and the events E_d,± to distinguish determinant cases.A random sign initialization has constant probability of overlapping the exceptional eigenvector, and repeated approximate inverse applications amplify that component.Source: §7 · p. 32, §7.2 · p. 33

7.1 An optimizer approximately applies the inverse

  • An exactly feasible near-maximizer for a unit objective yields a computable approximate inverse application: scale the returned point by its objective value to approximate B^-1b.The section applies this reduction with B = AQ; one optimizer invocation and classical postprocessing suffice for each approximate inverse application.Source: §7.1 · pp. 32–33

7.2 Using inverse iteration to predict the determinant

  • Using W fresh optimizer invocations, one can predict det Q for Q ∼ µ_d with average success at least 1/2 + 1/50; the only oracle calls are optimizer membership queries.The bounds are k + 1 ≤ 8 log n, m ≤ 147 log log n, and W ≤ 1176 log n log log n.Source: §7.2 · pp. 35–36

7.3 Lower bound for exactly feasible optimization

  • T ≥ n/(4704 log n log log n) membership queries are required for exactly feasible optimization on an explicit ellipsoid family, for every fixed finite grid of exact membership queries.The optimizer must work for all family members and all unit objectives.Source: §7.3 · p. 37

7.4 Lower bound for approximately feasible optimization

  • Approximately feasible outputs require a separate reduction: replace the output analytically by a nearby feasible witness, then use the original output to construct an approximate inverse application.The feasibility tolerance must be small enough to preserve both inverse iteration and the final maximum-objective-value test.Source: §7.4 · pp. 37–38
  • Theorem 7.10 establishes a membership-query lower bound for approximately feasible optimization on its ellipsoid family, with tolerance scaled to Θ(n^-2).The proof scales the ellipsoid by n^2, converting the unscaled Θ(n^-4) tolerance to Θ(n^-2) without changing the membership-query reduction.Source: §7.4 · p. 39
  • The lower bounds of Theorems 7.7 and 7.10 also hold with exact coherent membership queries on L2(R^n) ⊗ C^2.For the hard ellipsoids, continuity of the membership-predicate maps lets the proof replace the finite-register query theorem while leaving the rest of the reduction unchanged.Source: §7.4 · p. 40

7.5 Comparison with the linear lower bound

  • Theorem 7.12 gives linear membership-query lower bounds for both exactly and approximately feasible optimization, with feasibility guarantees, geometric parameters, and oracle models unchanged.The bounds apply to the families and accuracy parameters of Theorems 7.7 and 7.10 for all sufficiently large n.Source: §7.5 · p. 40

7.6 Strongly convex quadratics

  • Theorem 7.13 gives a gradient phase-query lower bound of C q log(2 + q) log log(3 + q) for an explicit family of 1-strongly convex, κ-smooth quadratics.The bound holds for quantum algorithms succeeding with probability at least 2/3 in the worst case.Source: §7.6 · p. 41

Discussion

The discussion identifies open questions about extending Fourier-rank lower bounds and about optimization complexity across an intermediate accuracy range. In the stated high-accuracy regime, membership-query complexity is eΘ(n), while comparison with first-order bounds is limited by different query models.

Discussion

  • The paper leaves open whether Fourier-rank methods extend to lower bounds beyond the problems considered and whether threshold-degree or approximate-degree variants can be developed.The comparison uses the normalization ε/R for this paper and ε/(GR) for the result of Garg, Kothari, Netrapalli, and Sherif.Source: Discussion · p. 42
  • When ε/R ≤ 1/(200√n), Ω(n) membership queries are necessary and the known quantum algorithms use eO(n), giving eΘ(n) complexity.The discussion compares this regime with first-order bounds for Lipschitz functions on a ball.Source: Discussion · p. 42
  • For first-order queries, Ω((GR/ε)^2) queries are necessary when dimension is at least eO((GR/ε)^4), and projected subgradient descent matches with O((GR/ε)^2) queries.These bounds concern function values and subgradients for Lipschitz functions on a ball.Source: Discussion · p. 42
  • The membership-query bounds for ellipsoids and first-order bounds for Lipschitz functions use different models, and neither applies when ε/R lies between order n^-1/2 and n^-1/4.The paper leaves open whether complexity is eΘ(min{n, (R/ε)^2}) throughout that intermediate range.Source: Discussion · p. 42

AI Usage Disclosure

The authors describe how language models contributed ideas to the proof development across versions. They distinguish model-generated suggestions from the authors’ verification and responsibility for the paper’s technical claims.

AI Usage Disclosure

  • For version 1, the authors attribute to language models the Fourier-rank notion and identify the determinant-to-optimization bridge as the main AI contribution to the reduction.Earlier attempts to prove a lower bound from Fourier-rank considerations were incorrect because of scaling issues in quantizing classical matrix-vector lower bounds.Source: AI Usage Disclosure · pp. 42–43
  • The authors report that GPT-5.6 Sol suggested a determinant-lower-bound route that sidestepped scaling issues and produced an essentially complete convex-optimization lower-bound proof, later polished and verified by the authors.The authors say the proof was substantially rewritten for clarity.Source: AI Usage Disclosure · p. 43
  • The authors state that they manually verified each technical claim made by the language model and accept responsibility for the correctness of all results.Source: AI Usage Disclosure · p. 43

Disclaimer

The document is an informational paper prepared by JPMorgan Chase’s Global Technology Applied Research center, not its Research Department. It disclaims warranties and liability and is not investment research or advice.

Disclaimer

  • The paper is for informational purposes and is not a product of JPMorgan Chase’s Research Department or its affiliates.Source: Disclaimer · p. 43
  • JPMorgan Chase and its affiliates disclaim explicit or implied warranties and liability related to the document’s completeness, accuracy, reliability, or potential legal, compliance, tax, or accounting effects.Source: Disclaimer · p. 43
  • The document is not investment research or advice, nor a recommendation, offer, or solicitation concerning securities, financial instruments, products, or services.Source: Disclaimer · p. 43

A Continuous exact membership queries

For a continuous L2 query register, an exact membership query increases Fourier rank by at most one. The resulting rank bound yields average success probability 1/2 when 2T < n for the determinant decision problem.

A Continuous exact membership queries

  • Fejér approximants establish the rank-one statement through a strong L2 limit, with each finite sum preserving the required rank space.The limit remains in the closed rank space.Source: A Continuous exact membership queries · p. 48
  • The Fejér sums are analytic approximants, not unitary or physically implementable queries.They establish the analytic limit rather than adding query operations to the algorithm.Source: A Continuous exact membership queries · p. 48
  • An exact membership query fixes the z = 0 component and multiplies the z = 1 component by the threshold phase, increasing rank by at most one.The same rank-growth statement applies to the query and its inverse.Source: A Continuous exact membership queries · p. 49
  • When 2T < n, determinant correlation is zero and the decision procedure’s average success probability is 1/2.The determinant-correlation argument proves the continuous-query lower bound.Source: A Continuous exact membership queries · p. 49
  • Changing membership on a query-point set of measure zero leaves a continuous L2-register oracle unchanged, and the same non-strict boundary convention works across register types.For finite or countable registers, threshold equality is Haar-null as a function of Q.Source: A Continuous exact membership queries · p. 49
Loading 2609.09035v2…