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

• URL: http://arxiv.org/abs/2609.05679v1
• Date: Fri, 04 Sep 2026 19:23:24 GMT
• Title: Quantum lower bounds for convex optimization and real matrix-vector query problems
• Abstract summary: We show that the quantum query complexity of minimizing a convex function over a convex subset is $tilde(n)$, nearly matching the best known upper bound.<n>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 a real matrix.
• Score: 1.4044759410670393
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\mathbb{R}^n$ with evaluation and membership queries is $\tildeΩ(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.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Optimal Quantization for Matrix Multiplication [29.75700570685703]
  Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error.<n>A practical low-complexity version of our quantizer achieves performance quite close to optimal.
  arXiv  Detail & Related papers  (2024-10-17T17:19:48Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Exponential quantum advantages for practical non-Hermitian eigenproblems [9.59420259768862]
  We develop a quantum algorithm to address general non-Hermitian eigenvalue problems.<n>Our method combines a fuzzy quantum eigenvalue detector with a divide-and-conquer strategy to efficiently isolate relevant eigenvalues.<n>We discuss the broad applications in detecting spontaneous $PT$-symmetry breaking, estimating Liouvillian gaps, and analyzing classical Markov processes.
  arXiv  Detail & Related papers  (2024-01-22T16:29:08Z)
• Quantum eigenvalue processing [0.0]
  Problems in linear algebra can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary transformations on eigenvalues of block-encoded non-normal operators. We also present a Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra.
  arXiv  Detail & Related papers  (2024-01-11T19:49:31Z)
• Bounding Real Tensor Optimizations via the Numerical Range [0.0]
  We show how the numerical range of a matrix can be used to bound the optimal value of certain optimization problems over real tensor product vectors. Our bound is stronger than the trivial bounds based on eigenvalues, and can be computed significantly faster than bounds provided by semidefinite programming relaxations.
  arXiv  Detail & Related papers  (2022-12-24T20:03:06Z)
• A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected weighted graph [4.045204834863644]
  We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
  arXiv  Detail & Related papers  (2022-03-28T02:24:08Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Symplectic decomposition from submatrix determinants [0.0]
  An important theorem in Gaussian quantum information tells us that we can diagonalise the covariance matrix of any Gaussian state via a symplectic transformation. Inspired by a recently presented technique for finding the eigenvectors of a Hermitian matrix from certain submatrix eigenvalues, we derive a similar method for finding the diagonalising symplectic from certain submatrix determinants.
  arXiv  Detail & Related papers  (2021-08-11T18:00:03Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Quantum query complexity with matrix-vector products [9.192149087264033]
  We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant or rank of a matrix, quantum computers do not provide an speedup over classical computation.
  arXiv  Detail & Related papers  (2021-02-22T20:42:17Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems [58.83118651518438]
  We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $boldsymbolumathrmTboldsymbolMboldsymbolv$ over a fixed field. We provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs.
  arXiv  Detail & Related papers  (2020-06-24T19:33:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.