Quantum lower bounds for convex optimization and real matrix-vector query problems
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.
Kai: I'm Kai.
Mira: And I'm Mira, here with Lev.
Kai: We're looking at the paper: "Quantum lower bounds for convex optimization and real matrix-vector query problems".
Mira: Here's the gist of the paper. The paper presents novel quantum lower bounds for convex optimization and real matrix-vector query problems, showing that these tasks require super-linear query complexity in terms of the dimension n <ref:2609.056791, nearly matching existing upper bounds.
Kai: Quantum Query Complexity for Optimization The authors establish a lower bound of omega˜(n) for minimizing a convex function over a convex subset using evaluation and membership queries, which is even for quadratic minimization <ref:2609.05679#pg15>.
Mira: This result implies that the best known quantum algorithm achieves at most quadratic speedup over the best known classical algorithm up to log factors <ref:2609.05679#pg19>.
Kai: Furthermore, in the gradient oracle setting, no quantum speedup is known because algorithms work by computing a (sub)gradient using poly(log n) queries <ref:2609.05679#pg19>.
Title and authors: Kai: So we're looking at this paper, "Quantum lower bounds for convex optimization and real matrix-vector query problems," and it's about setting some really high bars on how fast these things can be solved on a quantum computer.
Mira: It looks like the authors are tackling two main areas: minimizing convex functions and these matrix-vector query problems, specifically focusing on lower bounds.
Lev: Lower bounds sound intense when you think about what that actually means for building hardware, because it tells you the absolute minimum number of queries needed to solve something.
Kai: Exactly. They establish a lower bound of Omega(n) for minimizing a convex function over a convex subset using evaluation and membership queries, which is even true for quadratic minimization using matrix-vector queries <ref:2609.05679#pg15>.
Mira: That's significant because it implies that the best known quantum algorithm achieves at most quadratic speedup over the best known classical algorithm up to log factors <ref:2609.05679#pg19>.
Lev: Quadratic speedup means that if a classical computer needs n squared operations, the quantum one is at most n squared over some logarithmic corrections.
Kai: And in the gradient oracle setting, they say no quantum speedup is known because algorithms work by computing a subgradient using poly(log n) queries to an evaluation oracle using Jordan’s gradient estimation algorithm <ref:2609.05679#pg19>.
Mira: That means the added benefit of a gradient oracle isn't translating into any known quantum advantage for optimization, which is a key point they're making.
Lev: It sounds like the complexity in that setting just stays at that poly(log n) level for both sides, classical and quantum <ref:2609.05679#pg19>.
Kai: And when you look at optimization over a fixed unit ball, the lower bound still holds at Omega(n) <ref:2609.05679#pg19>.
Mira: Now let's move to the matrix operations part of this paper, which looks pretty deep. They develop techniques to lower bound quantum query complexity in the matrix-vector model over the reals <ref:2609.05679#pg19>.
Lev: The specific results they prove there are for computing things like the trace and the determinant <ref:2609.05679#pg19>.
Kai: They show an Omega(n/log n) lower bound for computing just the trace <ref:2609.05679#pg19>, and an Omega(n) lower bound for computing the sign of the determinant <ref:2609.05679#pg19>.
Mira: Then they show that computing the magnitude of the determinant requires Omega(n/log n) queries to achieve an additive error epsilon n <ref:2609.05679#pg19>.
Lev: So they're getting down to things like invertibility and matrix inversion, which is a big deal for solving systems of equations.
Kai: They extend these results to matrix inversion, proving an Omega(n/log n) lower bound for computing the first column of the inverse of an invertible matrix A <ref:2609.05679#pg19>.
Mira: This hardness extends to positive definite matrices, which implies that quadratic optimization requires Omega(n/log n) quantum matrix-vector queries <ref:2609.05679#pg19>.
Lev: That means even for the quadratic case, where we have a clean linear-algebraic description, you still need that n over log n complexity for the inversion part <ref:2609.05679#pg19>.
Kai: The technique they use to prove these bounds is called the determinantal witness method <ref:2609.05679#pg19>. It's based on identifying a witness whose Fourier transform vanishes on low-rank matrices and that correlates well with the function being computed <ref:2609.05679#pg19>.
Mira: That sounds clever because it replaces polynomial degree with matrix rank and orthogonality to low-degree polynomials by the vanishing of a certain measure on low-rank Fourier components <ref:2609.05679#pg19>.
Lev: The method constructs dual witnesses that satisfy the conditions of Lemma three point three, leading to lower bounds based on the correlation between the witness and the decision function <ref:2609.05679#pg19>.
Kai: They also formalized this model by discretizing real numbers with arbitrarily high precision, demanding success for every admissible A <ref:2609.05679#pg19>.
Mira: This discretization is crucial because it lets them study the complexity as a function of dimension n, focusing on algorithms that are independent of n when the output error epsilon is small <ref:2609.05679#pg19>.
Lev: The technical detail about how they define a matrix-vector query as a discretized version of Eq. (two) is important for understanding the model setup <ref:2609.05679#pg19>.
Kai: They show that a single matrix-vector query to A can be used to implement a matrix-vector query to AT, or the inverse of such a query, using one matrix-vector query to A <ref:2609.05679#pg19>.
Mira: That's interesting because they are showing that the structure of the matrix itself dictates this lower bound on inversion complexity <ref:2609.05679#pg19>.
Lev: And for optimization, Corollary six point eight suggests that the quantum query complexity of quadratic minimization—and therefore general convex optimization—is Omega(n/log n) <ref:2609.05679#pg19>.
Kai: So to summarize, this paper proves that for these problems, you're facing a lower bound of Omega(n) and nearly linear bounds on matrix operations like trace and determinant when using the determinantal witness method <ref:2609.05679#pg19>.
Mira: The main implication is that while we have quantum algorithms with some speedup, they don't beat the classical complexity in these fundamental settings, up to quadratic speedup <ref:2609.05679#pg19>.
Lev: It settles a lot of the open questions from earlier work on this matrix-vector query model <ref:2609.05679#pg19>.
Kai: For future work, they suggest looking into rank testing and applying these lower bound techniques to problems outside the matrix-vector query model <ref:2609.05679#pg19>.
Mira: It's a solid piece of work because it rigorously sets the limits on what quantum computation can do in these specific, fundamental settings for convex optimization and matrix math <ref:2609.05679#pg1>.
Lev: I think the core message is that even with quantum tools, you still need a significant number of queries to tackle these problems when you're dealing with real matrices <ref:2609.05679#pg19>.
Kai: It shows us exactly where the difficulty lies in using quantum query complexity to solve these tasks <ref:2609.05679#pg1>.
The paper's summary: Kai: So, this paper, "Quantum lower bounds for convex optimization and real matrix-vector query problems," essentially sets new minimum query counts for two big problems using quantum computers on a real matrix setup.
Mira: Right, so they are showing that minimizing a convex function over a set of vectors requires at least Omega of n queries, even in the quadratic case.
Lev: That means no matter how clever the quantum algorithm is, you need that many queries just to get the answer for optimization problems like this.
Kai: And they aren't stopping there; they also lower bound how many matrix-vector queries you need to calculate things like the trace or even the sign of a determinant.
Mira: That’s important because it links these fundamental math operations directly to quantum query complexity in a way that was hard to pin down before.
Lev: The main technique they use is this "determinantal witness method" which identifies special matrices whose Fourier transform vanishes on low-rank components, which then correlates with the function we're trying to compute.
Kai: That method lets them replace ideas about polynomial degree with ideas about matrix rank and how well a certain measure aligns with the function being computed.
Mira: It’s a really neat way to prove these lower bounds because it ties the structure of low-rank matrices into the complexity of the computation directly.
Lev: They also proved this hardness for inverting matrices, showing that you need Omega of n over log n queries just to find one column of an invertible matrix A.
Kai: That’s a concrete number, so it shows that even with a quadratic speedup possible in some scenarios, you still face this linear hurdle for inversion.
Mira: So what this really means for the world is that these lower bounds are nearly matching the best known upper bounds we have right now for these tasks.
Lev: That’s the key point; it suggests that those algorithms three and four are pretty close to being optimal, only hitting a quadratic speedup over classical methods up to some logarithmic factors.
Kai: It also confirms what we already suspected about gradient oracles; no known quantum speedup exists in that setting because you only need poly log n queries for the subgradient.
Mira: So this paper solidifies the idea that for these specific problems, we can't just throw more qubits at it and expect a massive speedup beyond quadratic.
Lev: The focus now shifts to where they stop working, which is proving things outside of this matrix-vector query model, which is a natural next step for future research.
Kai: So while the bounds are tight for what they studied, the real question now becomes whether we can apply these ideas to other kinds of computational problems.
The paper's improvements: Tom: So, this paper isn't just about setting these lower bounds; it suggests some ways to make the whole thing more robust or applicable in different settings.
Kai: Right, they point out that we need to look at rank testing now because those are related ideas, and also how to apply these lower bound techniques to problems that aren't just the matrix-vector query model.
Mira: That makes sense because the current analysis is very specific about how we model real numbers with discretization, so expanding that scope is a big move for the theory.
Lev: If they can successfully apply their witness method to broader problems, it means we might be able to set even more realistic performance expectations for quantum hardware.
Kai: They’re showing that even though the bounds are high, they aren't just theoretical limits; they give us a clear picture of what kind of query complexity we really have to deal with.
Mira: The implication is that it helps researchers decide which specific quantum algorithms are actually worth pursuing for these optimization tasks.
Lev: For hardware guys like me, knowing the exact query complexity helps us figure out if our error correction overhead is actually helping us get closer to those theoretical limits or just adding noise.
Kai: It seems they’re trying to bridge that gap between the high-level math and what we’re actually building on superconducting qubits.
Mira: It suggests that for the next phase, we should focus on how these bounds change when you move away from real matrices into other algebraic structures.
Lev: That moves us toward understanding how query complexity behaves in different mathematical environments, which is crucial for error correction design.
Conclusion: Kai: So, to wrap up on "Quantum lower bounds for convex optimization and real matrix-vector query problems," we’re seeing that these quantum algorithms don't actually offer a speedup over the best classical ones in these core settings, at most quadratic speedup.
Mira: Exactly, it confirms that even with the power of quantum computation, you still need those Omega of n queries for optimization and matrix inversion.
Lev: For our side of things, it means we can set more realistic targets for how hard these problems are to solve on actual hardware where we have finite precision.
Kai: It’s a bit sobering that the gradient oracle setting doesn't show any known quantum speedup either, just poly log n queries for the subgradient calculation.
Mira: That’s a limitation they clearly state; it means adding a gradient oracle doesn't magically unlock massive quantum advantages in optimization yet.
Lev: The method they use, the determinantal witness method, is clever because it connects the function we need to compute directly to low-rank matrix properties via Fourier transforms.
Kai: It’s a solid piece of work because it rigorously proves these limits using a model where real numbers are discretized with arbitrary high precision.
Mira: That discretization is key; it lets them focus on the dimension n dependence without getting bogged down in the messy details of continuous real analysis.
Lev: I think for error correction, this level of lower bound clarity is exactly what we need to plan out our resource requirements for these complex tasks.
Kai: It settles a lot of the open questions from previous work on this matrix-vector query model, giving us solid numbers to work with now.
Mira: So moving forward, the real challenge is figuring out how to apply these kinds of lower bound techniques to problems that fall outside this specific matrix-vector query model.
Lev: That’s where the next big research direction lies; pushing those ideas into other mathematical domains will be important for building more general quantum solvers.
Andrew M. Childs
Joint Center for Quantum Information and Computer Science · Department of Computer Science · Institute for Advanced Computer Studies · University of Maryland
quant-ph, cs.DS, math.OC
Submitted: 2026-09-04
Updated: 2026-10-28
Comments: 29 pages. v2: additional discussion of technical approach in introduction, minor corrections
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 89/100
The gist: The paper presents novel quantum lower bounds for convex optimization and real matrix-vector query problems…
Key concepts
- Quantum Query Complexity
- This measures the minimum number of quantum queries needed by an algorithm to solve a specific problem. The authors show that for convex optimization, this complexity is nearly linear ($ ilde{\Omega}(n)$), meaning quantum algorithms offer only a quadratic speedup over classical methods.
- Determinantal Witness Method
- This is a novel technique used to prove lower bounds. It involves finding a specific mathematical 'witness' whose Fourier transform vanishes on low-rank matrices and which strongly correlates with the function being computed, allowing the authors to bound the required queries.
- Matrix-Vector Query Model
- This formalizes how quantum algorithms interact with an unknown real matrix A. A query allows the algorithm to compute $A|x\rangle$, which is modeled using a discretized phase oracle based on the Fourier transform of the matrix, essential for analyzing query complexity.
- Gradient Oracle Setting
- This setting assumes access to an oracle that provides subgradients of a function $f$. The paper proves no quantum speedup exists here because existing quantum algorithms already use only polynomial ($ ext{poly}(\log n)$) queries to evaluate the evaluation oracle, making the gradient information redundant.
Terminology
Summary
The paper presents novel quantum lower bounds for convex optimization and real matrix-vector query problems, showing that these tasks require super-linear query complexity in terms of the dimension n <ref:2609. p. 0 p. 1056791, nearly matching existing upper bounds. p. 0
Quantum Query Complexity for Optimization
The authors establish a lower bound of omega˜(n) for minimizing a convex function over a convex subset using evaluation and membership queries, which is even for quadratic minimization <ref:2609.05679#pg15>. This result implies that the best known quantum algorithm achieves at most quadratic speedup over the best known classical algorithm up to log factors <ref:2609. p. 205679#pg19>. Furthermore, in the gradient oracle setting, no quantum speedup is known because algorithms work by computing a (sub)gradient using poly(log n) queries <ref:2609. p. 005679#pg19>. For optimization over a fixed unit ball, the lower bound remains omega˜(n) <ref:2609. p. 205679#pg19>.
Lower Bounds for Matrix Operations
The paper develops techniques to lower bound quantum query complexity in the matrix-vector model over the reals, proving results for computing the trace and determinant <ref:2609.05679#pg19>. Specifically, they prove an omega(n/ log n) lower bound for computing the trace <ref:2609. p. 205679#pg19>, and an omega(n) lower bound for computing the sign of the determinant <ref:2609. p. 005679#pg19>. Similarly, they show that computing the magnitude of the determinant requires omega(n/ log n) queries to achieve an additive error εn <ref:2609. p. 205679#pg19>.
The Determinantal Witness Method
A novel technique called the determinantal witness method is introduced to prove these lower bounds, based on identifying a witness whose Fourier transform vanishes on low-rank matrices and correlates well with the function being computed <ref:2609.05679#pg19>. This approach replaces polynomial degree with matrix rank and orthogonality to low-degree polynomials by the vanishing of a certain measure on low-rank Fourier components <ref:2609. p. 205679#pg19>. The method is applied to construct dual witnesses that satisfy the conditions of Lemma 3. p. 33, leading to lower bounds based on the correlation between the witness and the decision function <ref:2609. p. 005679#pg19>.
Inversion Hardness and Quadratic Optimization
The paper extends these results to matrix inversion, proving an omega(n/ log n) lower bound for computing the first column of the inverse of an invertible matrix A <ref:2609.05679#pg19>. This hardness extends to positive definite matrices, implying that quadratic optimization requires omega(n/ log n) quantum matrix-vector queries <ref:2609. p. 205679#pg19>. The proof involves a complex reduction from inverting M to inverting A, utilizing the witness correlation bound and Gaussian integration by parts <ref:2609. p. 605679#pg19>.
Technical Details of the Model
The query model is formalized through a discretized version of Eq. (2), where real numbers are represented with arbitrarily high precision, and an algorithm must succeed for every admissible A <ref:2609. p. 105679#pg19>. The analysis relies on Lemma 3. p. 91, which shows that the probability of any measurement outcome has the form Z R2t e 2πi⟨A,M⟩ dµ(M), where µ is an A-independent discrete complex measure <ref:2609. p. 405679#pg19>. The construction of dual witnesses involves defining a function β = det−1 2πi∂X b, which serves as a determinantal witness <ref:2609. p. 605679#pg19>. The final correlation bound in Lemma 6. p. 21 is established by showing that E[q(B)Pθ(B)] ≥ cθ (n − 1)! p. 9 n <ref:2609.05679#pg19>.
Conclusion on Speedup
The overall conclusion is that the algorithms of [3, 4] are nearly optimal, achieving at most quadratic speedup over the best known classical algorithm up to log factors <ref:2609.05679#pg19>. The work suggests several questions for future investigation regarding rank testing and applying these lower bound techniques to problems outside the matrix-vector query model <ref:2609. p. 205679#pg19>. The results are supported by independent work showing nearly linear bounds on quantum query complexity for convex optimization using related techniques <ref:2609. p. 105679#pg19>. No quantum speedup is known in the gradient oracle setting <ref:2609. p. 105679#pg19>.
--- Page 1 ---
Quantum lower bounds for convex optimization and real matrix-vector query problems Andrew M. Childs Joint Center for Quantum Information and Computer Science, Department of Computer Science, and Institute for Advanced Computer Studies University of Maryland Abstract 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 R n with evaluation and membership queries is omega˜(n), nearly matching the best known upper bound. p. 0 In particular, we show this even for quadratic minimization, which is equivalent to inverting an n × n real matrix using matrix-vector queries. p. 0 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. p. 0 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 <ref:2609. p. 005679#pg19>. 1 Introduction Minimizing convex functions is a basic computational problem with broad applications, including combinatorial optimization, machine learning, control systems, signal processing, and finance, among others. p. 0 While convex optimization can be performed efficiently by classical algorithms, prior work has investigated the possibility of even faster algorithms using quantum computation <ref:2609. p. 005679#pg19>. In one natural formulation of this problem, we are given query access to a convex function evaluating f: R n → R at a given point x ∈ R n, an oracle determining whether x ∈ R n belongs to a convex body over which f is to be minimized, and a point in that body. p. 0 Under standard boundedness and well-roundedness assumptions, and suppressing logarithmic dependence on geometric, scale, and accuracy parameters, the best known classical randomized algorithm for this problem uses O˜(n 2) queries [1] (where the tilde indicates that logarithmic factors are neglected), which was recently shown to be nearly optimal [2]. p. 0 There is a quantum algorithm using only O˜(n) queries [3, 4], a quadratic improvement. p. 0 The best quantum lower bound we are aware of is only omega˜(√n) [3,4], leaving open the possibility of anything from a fourth-power quantum speedup to no quantum speedup. p. 0 It is also natural to consider the setting where we additionally have access to an oracle computing the gradient of f at any chosen point. p. 0 Such an oracle captures the scenario where f is described by an explicit formula that can be efficiently differentiated as well as evaluated. p. 0 Indeed, provided f is given as an efficient procedure, automatic differentiation can often be used to efficiently evaluate its gradient [5]. p. 0 In the gradient oracle setting, classical algorithms can perform convex optimization using only O˜(n) queries. p. 0 However, the addition of a gradient oracle does not provide a significant benefit for quantum algorithms—indeed, the algorithms of [3, 4] work by computing a (sub)gradient using poly(log n) queries to an evaluation oracle using Jordan’s gradient estimation algorithm [6]. p. 0 Therefore, no quantum speedup is known in this setting <ref:2609. p. 105679#pg19>. In the work mentioned above, we assume the oracles provide results with arbitrarily high accuracy, we demand that the output is also produced with arbitrarily high accuracy, and we study the query complexity as a function of the dimension n. p. 1 It is also natural to study the complexity as a function of allowed output error ϵ, restricting attention to algorithms whose complexity is independent of n. p. 1 In this setting, given access to evaluation and (sub)gradient oracles, both the classical and quantum query complexities are Θ(1/ϵ 2) (more precisely, they are Θ((GR/ϵ) 2) assuming the function is G-Lipschitz and one is given a point within a distance R of the true minimum), so there is provably no quantum speedup <ref:2609. p. 105679#pg19>. Since this question has essentially been resolved, for the remainder of the paper we focus on dimension dependence for algorithms that achieve arbitrarily small ϵ (in particular, we give a lower bound that holds for ϵ = 1/ poly(n)) <ref:2609. p. 105679#pg19>. An especially simple kind of convex function is a positive definite quadratic form plus a linear term, fA,b(x) = 1/2 x TAx + bTx, where A ∈ R n×n is positive definite (and therefore symmetric) and b ∈ R n. p. 1 The best known quantum query complexity for convex optimization is O˜(n) even for the quadratic case <ref:2609. p. 105679#pg19>. This optimization problem has a clean linear-algebraic description: since ∇fA,b(x) = Ax + b, fA,b(x) is minimized at x = -A−1 b. p. 1 Furthermore, using quantum gradient estimation [6], poly(log n) quantum queries to fA,b suffice to determine b, and also to implement an oracle that produces Ax on input x (a so-called matrix-vector query). p. 1 Conversely, given a matrix-vector query oracle for A and knowledge of the vector b, we can implement fA,b using a constant number of queries. p. 1 Thus, the tasks of minimizing the quadratic function fA,b given an evaluation oracle, and of computing A−1 applied to a particular input vector using matrix-vector queries for A, have the same query complexity up to log factors <ref:2609. p. 105679#pg19>. Clearly, n ideal queries suffice, but lower bounds have been elusive. p. 1 The task of determining properties of a matrix using matrix-vector queries has been widely studied in a classical context (see for example [8,9]) <ref:2609. p. 105679#pg19>. There has been some progress on understanding quantum query complexity in the matrix-vector model over finite fields [10], but only limited progress for real matrices <ref:2609. p. 105679#pg19>. A significant obstacle is that the lower bounds of [10] primarily rely on the polynomial method [11], which does not extend naturally to query problems with continuous input <ref:2609. p. 105679#pg19>. In this paper, we develop techniques for lower bounding quantum query complexity in the matrix-vector model over the reals and use them to resolve the quantum query complexity of convex optimization up to log factors <ref:2609. p. 105679#pg19>. Along the way, we prove other results for the matrix-vector query model, namely for computing the trace and determinant, resolving several open questions from [10] <ref:2609. p. 105679#pg19>. In the matrix-vector query model, for an unknown matrix A, an ideal query acts as UA: x, y⟩ 7→ x, y + Ax⟩ (1) for all x, y ∈ R n. p. 1 It is often more convenient to work with a phase oracle, obtained by conjugating UA by the Fourier transform on the output register, giving UˆA: x, y⟩ 7→ e 2πiyTAxx, y⟩ (2). p. 1 The above formulation is an idealization since real numbers cannot be represented using finitely many bits. p. 1 We address this by defining the problem through discretization, representing real numbers with arbitrarily high precision and demanding that an algorithm produce the answer with arbitrarily high precision. p. 1 We formalize this model in Section 2 below <ref:2609. p. 105679#pg19>. We show query lower bounds using a technique, developed in Section 3, that we call the determinantal witness method <ref:2609. p. 105679#pg19>. This approach uses the simple observation that the A-dependent phase accumulated by a quantum algorithm using t matrix-vector queries is described by a measure over matrices with Fourier components of rank at most t <ref:2609. p. 205679#pg19>. Consequently, we show in Lemma 3. p. 23 that we can lower bound the failure probability of a t-query algorithm by finding a measure that is well-correlated with the function to be computed, and that has no support on Fourier components of rank at most 2t <ref:2609. p. 205679#pg19>.
--- Page 2 ---
To formalize the setting, we define a matrix-vector query as a discretized version of Eq. (2). When provided with query access to a matrix A ∈ R n×n, we are also given a bound Λ ≥∥A∥max:= max i,j∈[n] Aij For a parameter k ∈ N that the algorithm is free to choose, each coordinate of x and y is represented by 2k bits (k bits representing the integer part and sign, and another k bits representing the fractional part), ranging over D:= (−2(2k−1) + 1, −2(2k−1) + 2,. p. 3.., 2(2k−1 − 1)/2 k (where we omit one additional value that could be encoded with 2k bits so that D is closed under negation). p. 3 The corresponding discrete Fourier transform is taken over Z 2(2k-1) <ref:2609. p. 305679#pg19>. The query acts precisely as in Eq. p. 3 (3), i.e., UˆA: x, y⟩ 7→ e 2πiyTAxx, y⟩ (3) where k is left implicit, and the only restriction is that x, y ∈ Dn. p. 3 An algorithm can choose any finite k depending on n, Λ, and the desired accuracy of the computation, but not on the unknown A, and it must succeed for every admissible A. p. 3 As we formalize in Lemma 6. p. 37, a query in this model can effectively compute the application of A to a given vector with arbitrarily high accuracy <ref:2609. p. 305679#pg19>. Note that we need not separately provide inverse queries, since conjugating the output register by the operation y⟩ 7→ -y⟩ maps UˆA to Uˆ−A = Uˆ −1 A, so an inverse query can be exactly simulated with one forward query <ref:2609. p. 305679#pg19>. Similarly, as observed in [10, Theorem 9], a single matrix-vector query to A can be used to implement a matrix-vector query to AT. p. 3 Concretely, letting S swap the two registers of Eq. p. 3 (3), a simple calculation shows that SUˆAS = UˆAT, so we can implement a matrix-vector query to AT, or the inverse of such a query, using one matrix-vector query to A <ref:2609. p. 305679#pg19>. When considering an optimization problem with query access to a function f: R n → R, we are also given a query region K ⊂ R n and a bound Ξ ≥ supx∈Kf(x) For queries to f are provided via a discretized phase oracle Oˆf: x, y⟩ 7→ e 2πiyf(x)x, y⟩ for x ∈ Dn ∩ K and y ∈ D Outside K, the query acts as the identity. p. 3 Again an algorithm may choose any finite k depending on n, Ξ, and the desired accuracy of the computation, but not on the unknown function f <ref:2609. p. 305679#pg19>.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improve quantum optimization by proving that even with access to a gradient oracle, there is
no quantum speedup
over classical algorithms becausethe algorithms of [3, 4] work by computing a (sub)gradient using poly(log n) queries to an evaluation oracle using Jordan’s gradient estimation algorithm [6].
-
Enhance the capability of matrix-vector query models by developing and applying the determinantal witness method to lower bound quantum query complexity for computing the trace, sign of the determinant, and magnitude of the determinant.
-
Develop a framework that allows for proving lower bounds on quantum query complexity in the matrix-vector model over real numbers using discretization, where
we define a matrix-vector query as a discretized version of Eq. (2).
-
Enable more precise quantum algorithms for matrix inversion by establishing a lower bound of Omega(n/log n) queries required to compute the first column of an invertible matrix A, even when considering constraints on the singular values, as shown in Theorem 6.6.
-
Advance convex optimization capabilities by proving that
Corollary 6.8 suggests that the quantum query complexity of quadratic minimization—and therefore general convex optimization—is Omega(n/log n).
Sources
- Efficient Convex Optimization with Membership Oracles
- Near-Optimal Lower Bounds for Randomized Algorithms in Exact Value Zeroth-Order Convex Optimization
- Convex optimization using quantum oracles
- Quantum algorithms and lower bounds for convex optimization
- Automatic differentiation in machine learning: a survey
- No quantum speedup over gradient descent for non-smooth convex optimization
- Querying a Matrix through Matrix-Vector Products
- The gradient complexity of linear regression
- Quantum query complexity with matrix-vector products
- Quantum Lower Bounds by Polynomials
- Communication Lower Bounds Using Dual Polynomials
- Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and pfaffians
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements