Quantum lower bounds for convex optimization and real matrix-vector query problems

Andrew M. Childs

Source-linked AI summary

Quantum lower bounds for convex optimization and real matrix-vector query problems

Andrew M. Childs

arXiv:2609.05679v1Sep 4, 2026quant-phcs.DSmath.OC

TL;DR

The paper develops quantum query lower bounds for convex optimization and real matrix-vector problems using a determinantal witness method. It proves a ˜Ω(n) lower bound for convex optimization and nearly linear or linear lower bounds for matrix inversion and trace.

Problem
The known quantum lower bound for convex optimization was only ˜Ω(√n), leaving open a wide range of possible speedups.
Source: §1 · p. 1
Method
The determinantal witness method constructs a measure correlated with the target function whose Fourier components vanish on low-rank matrices.
Source: §1 · pp. 2–3
Results
˜Ω(n) lower bounds hold for convex optimization, Ω(n/ log n) for computing the first inverse column, and Ω(n/ log n) for computing trace.
Source: §1 · p. 3
Takeaways & Limitations
The convex-optimization lower bound makes the known quantum algorithms nearly optimal up to logarithmic factors.
Source: §1 · p. 3
The optimization hardness result is proved only for quite small inverse-polynomial error, O(n^-49), and tighter error dependence remains open.
Source: §1 · p. 3

Abstract

from arXiv · show

We (the author and the AI systems that did the heavy lifting) show that the quantum query complexity of minimizing a convex function over a convex subset of $\mathbb{R}^n$ with evaluation and membership queries is $\tilde\Omega(n)$, nearly matching the best known upper bound. In particular, we show this even for quadratic minimization, which is equivalent to inverting an $n \times n$ real matrix using matrix-vector queries. We also show linear or nearly linear lower bounds on the quantum query complexity of computing the trace, the sign of the determinant, and the magnitude of the determinant of a real matrix in the matrix-vector query model. We use a novel quantum lower bound technique, the determinantal witness method, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed.

1 Introduction

The paper develops quantum query lower bounds for convex optimization and real matrix-vector tasks, addressing gaps in the known bounds for optimization and limited progress for real matrices. Its determinantal witness method yields a nearly linear lower bound for convex optimization and linear or nearly linear lower bounds for several matrix tasks.

1 Introduction

Earlier bounds left a wide range of possible quantum speedups for convex optimization, while quantum lower-bound progress for matrix-vector queries over real matrices was limited.The paper develops techniques for the real matrix-vector model and resolves optimization query complexity up to logarithmic factors.Source: §1 · pp. 1–2
Quadratic minimization is equivalent up to logarithmic factors to applying A^-1 to a vector with matrix-vector queries, connecting optimization lower bounds to matrix inversion.For a positive definite quadratic, the minimizer is -A^-1b.Source: §1 · p. 2
The determinantal witness method lower-bounds query complexity using a measure correlated with the target function that has no Fourier support on matrices of rank at most 2t.The method constructs such witnesses by applying the Cayley operator to a smooth function of the input matrix.Source: §1 · pp. 2–3
Ω(n/ log n) queries are required for trace, while determinant sign requires Ω(n) and determinant magnitude requires Ω(n/ log n) queries with an n-dependent additive error.The magnitude bound applies under a finite upper bound on matrix-entry magnitudes.Source: §1 · p. 3
Ω(n/ log n) queries are required to compute the first column of a matrix inverse, even at inverse-polynomial accuracy and with polynomial condition number.A reduction extends the result to positive definite matrices.Source: §1 · p. 3
˜Ω(n) lower bounds for convex optimization using evaluation queries hold even over a fixed unit ball, making the known quantum algorithms nearly optimal up to logarithmic factors.The paper also obtains the lower bound when gradient queries are provided, ruling out more than logarithmic quantum speedup in that setting.Source: §1 · p. 3
The optimization lower bound is shown only for quite small inverse-polynomial error, O(n^-49); tightening this error dependence remains open.The paper also leaves rank testing and applications of its techniques beyond the matrix-vector model for future investigation.Source: §1 · p. 3

2 Query model

The query model discretizes both matrix-vector inputs and outputs, while allowing the algorithm to choose the precision parameter. The formulation also supports function evaluation through a phase oracle.

2 Query model

Each coordinate of the query vectors is represented with 2k bits, with values drawn from a finite set D.The algorithm chooses finite k based on n, the entry bound Λ, and desired accuracy, but not on the unknown matrix.Source: §2 · p. 4
For every admissible matrix, a query effectively computes its action on a vector to arbitrarily high accuracy, and the lower bounds hold uniformly in k.Finite Λ lets an algorithm choose sufficiently large k to avoid aliasing.Source: §2 · p. 4
One matrix-vector query can simulate an inverse query and a query to the transposed matrix.The inverse is simulated by negating the output register; the transpose by swapping the two registers.Source: §2 · p. 4
Function queries use a discretized phase oracle on points in K and act as the identity outside K.The oracle applies the phase determined by f(x) and the query value y.Source: §2 · p. 4

3 The determinantal witness method

The determinantal witness method lower-bounds quantum matrix-vector query complexity by relating algorithm outcomes to low-rank matrices. It constructs witnesses whose Fourier transforms vanish on bounded-rank matrices while retaining correlation with the target problem.

3.1 Dual witnesses

Any t-query algorithm’s measurement-outcome probability has a Fourier representation supported on matrices of rank at most t, independent of the discretization level.The representation follows from the form of the query algorithm and applies to more general measurements.Source: §3.1 · p. 5
A dual witness with Fourier transform vanishing on rank-at-most-2t matrices yields a lower bound on the worst-case failure probability of any t-query algorithm.The witness may include a component supported outside the promise set.Source: §3.1 · pp. 5–6

3.2 Determinantal witnesses

The method constructs a determinantal witness by applying the Cayley operator to a Schwartz function, making its Fourier transform a determinant factor times the original transform.For an (r+1)-minor, the resulting Fourier transform vanishes on matrices of rank at most r.Source: §3.2 · pp. 6–7
These constructed measures have Fourier transforms that vanish on bounded-rank matrices, meeting the dual-witness requirement.The determinant of the corresponding minor vanishes whenever the matrix rank is too small.Source: §3.2 · p. 7

4 Trace

The trace lower bound is obtained by applying the determinantal witness method to a decision problem based on the trace. The resulting quantum query complexity is nearly linear in the matrix dimension, even under a finite entry-magnitude bound.

4 Trace

The proof uses a determinantal witness with entrywise factors chosen so its correlation with a trace-threshold decision problem is large.The witness separates diagonal and off-diagonal factors and analyzes the trace dependence through convolution.Source: §4 · pp. 7–8
For even n, the decision problem tests whether tr A is at least (n − 1)/2, with a promise chosen to keep the witness support within the entry bound.The support estimate uses the diagonal and off-diagonal factor ranges.Source: §4 · pp. 8–9
The bounded-error quantum query complexity of computing the trace of an n × n real matrix in the matrix-vector query model, with additive error less than 1/3, is Ω(n/log n), even when entries have magnitude at most 24n^(3/2).Source: §4 · p. 10

5 Determinant

The determinant section establishes linear quantum query hardness for its sign and nearly linear hardness for its magnitude. The sign bound uses a determinantal witness, while the magnitude proof uses a distinct witness suited to an absolute-value decision problem.

5.1 Sign

For the sign problem, the Gaussian-weighted determinant is a dual witness whose Fourier transform vanishes on matrices of rank at most n − 1.The Cayley operator acts on the Gaussian density to produce the determinant factor.Source: §5.1 · p. 11
Deciding the sign of det A for |det A| ≥ 1/8 E|det A| requires Ω(n) quantum matrix-vector queries, even with a finite upper bound on entry magnitudes.The sign argument avoids logarithmic overhead.Source: §5.1 · p. 11

5.2 Magnitude

The sign witness is odd in det A, so the magnitude proof instead uses a witness based on the squared determinant.Its Fourier transform also vanishes on matrices of rank at most n − 1.Source: §5.2 · p. 12
Computing |det A| to within an n-dependent additive error ε_n requires Ω(n/log n) quantum matrix-vector queries, even with a finite entry-magnitude bound.The proof converts a decision-problem lower bound into an estimation lower bound.Source: §5.2 · pp. 14–15
The proof does not establish how the additive-error threshold ε_n scales with n.The authors leave the error scaling of determinant estimation for future work.Source: §5.2 · p. 15

6 Matrix inversion and convex optimization

This section establishes quantum query lower bounds for computing the first column of a matrix inverse and for quadratic minimization, including an Ω(n/log n) bound for positive definite matrices and minimization on the unit ball. It also extends a determinant decision lower bound to positive definite matrices.

6.1 The witness

The passage supports the finding that the specified object vanishes for M ∈ Rₙ₋₁; it does not provide a correlation lower bound.Source: §6.1 · p. 16

6.2 Reduction to a scalar expectation

The reduction uses an identity for det(B) det(∂B) applied to entire functions of u^T B^-1 v, turning the needed quantity into a scalar expectation.The Gaussian integration-by-parts argument handles singular matrices without boundary terms.Source: §6.2 · pp. 17–19

6.3 Proof of the correlation bound

For some cθ and all sufficiently large n, the expectation over u, v, and B of gθ(uᵀB⁻¹v) is at least cθ/n.Conditioned on B and v, uᵀB⁻¹v is a zero-mean Gaussian with variance ||B⁻¹v||².Source: §6.3 · pp. 21–22

6.4 Inversion lower bound

Ω(n/log n) quantum matrix-vector queries are required to compute the first column of an invertible (n+1)×(n+1) matrix’s inverse, including under a promise distinguishing two thresholds for |(A^-1)11|.The threshold decision lower bound assumes fixed θ ≥ 5 and the singular-value promise stated in the theorem.Source: §6.4 · pp. 22–23

6.5 Convex optimization

For quadratic optimization, the inversion argument is adapted to the positive-definite matrix M = A A^T, and a query to M can be implemented with three queries to A.The section notes that the original inversion matrix need not be positive definite.Source: §6.5 · p. 23
Computing the first column of M^-1 for a positive definite real matrix M requires Ω(n/log n) quantum matrix-vector queries.The reduction takes M = AAT; a query to M can be simulated using three queries to A, and one additional query to AT recovers the corresponding inverse column.Source: §6.5 · pp. 25–26
Distinguishing whether det M ≤ (θ* + εn)^2 for positive definite M requires Ω(n/log n) queries, and these instances satisfy ∥M∥max ≤ nΛ^2.Source: §6.5 · p. 26
On K = {x ∈ R^n: ||x|| ≤ 1}, identifying a point for a quadratic function that is 1-Lipschitz, bounded by 1, and 1/(10n^14)-strongly convex requires Ω(n/log n) quantum queries.Source: §6.5 · p. 26

AI statement

The technical approach was developed primarily through conversations with AI systems, while the manuscript was written manually and the author takes sole responsibility for its correctness. AI interactions also informed checking and revisions to the manuscript.

AI statement

AI conversations provided the majority of the technical approach, from generalizing prior results to the reals through extensions to trace, determinant, and inversion lower bounds.Arguments for inversion relied on conjectured random-Gaussian behavior; numerical checks led to analytical observations that enabled a proof.Source: AI statement · p. 27
Further AI interactions helped illuminate discretization of the query model and its connection to convex optimization.Source: AI statement · p. 27
The manuscript was written manually using AI-generated notes, and AI systems checked it for correctness and clarity, finding technical issues that prompted revisions.Source: AI statement · p. 27
The author takes sole responsibility for the correctness of the final manuscript.Source: AI statement · p. 27