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:2501.09413

Quantum algorithm for the gradient of a logarithm-determinant

Thomas E. Baker, Jaimie Greasley

Published Jan 16, 2025• 2 citations
arXivHTMLPDF

Abstract

The logarithm-determinant is a widely-present operation in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the pseudo-inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N^2$ elements of the input operator--can be accomplished in $O(k/\varepsilon^2)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix with precision $\varepsilon$. A practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O((k\log_2 N)/\varepsilon^2)$. The method applies widely and converges super-linearly in $k$ when the condition number is high. The best classical method we are aware of scales as $N$. Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as $O(\log_2 N/\varepsilon^2)$. The output is given in $O(1)$ queries of an oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning.

DOI
10.48550/arxiv.2501.09413

Related papers

Quantum algorithms for training Gaussian processes

Zhikuan Zhao, Jack Fitzsimons, Michael A. Osborne +2 more

Gaussian processes (GPs) are important models in supervised machine learning. Training in Gaussian processes refers to selecting the covariance functions and the associated parameters in order to improve the outcome of predictions, the core of which amounts to evaluating the logarithm of the marginal likelihood ($\mathrm{LML}$) of a given model. The $\mathrm{LML}$ gives a concrete measure of the quality of prediction that a GP model is expected to achieve. The classical computation of the $\mathrm{LML}$ typically carries a polynomial time overhead with respect to the input size. We propose a quantum algorithm that computes the logarithm of the determinant of a Hermitian matrix, which runs in logarithmic time for sparse matrices. This is applied in conjunction with a variant of the quantum linear system algorithm that allows for logarithmic-time computation of the form ${\mathbf{y}}^{T}{A}^{\ensuremath{-}1}\mathbf{y}$, where $\mathbf{y}$ is a dense vector and $A$ is the covariance matrix. We hence show that quantum computing can be used to estimate the $\mathrm{LML}$ of a GP with exponentially improved efficiency under certain conditions.

arXiv:1803.10520•Physical Review A•Jul 8, 2019•28 citations

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén, Srinivasan Arunachalam, Nathan Wiebe

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function f : Rd → R by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d.One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

•Jan 6, 2019•40 citations

Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

Yanqiao Wang, Jin-Peng Liu

We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix $M$ is chosen so that the target operator is a block of $\text{sign}(M)$ or is recovered from blocks of $(I-\text{sign}(M))/2$. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.

quant-pharXiv:2604.25333•Apr 29, 2026•10 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

•Jul 24, 2020•0 citations

Optimizing quantum optimization algorithms via faster quantum gradient computation

András Gilyén, Srinivasan Arunachalam, Nathan Wiebe

We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f : ℝd → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).

arXiv:1711.00465•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2019•139 citations

A Quantum Algorithm for Computing All Eigenvalues and Eigenstates of Sparse Hermitian Matrices

Krishnakanta Barik, Goutam Paul

Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values $\braket{x|M|x}$, where $\ket{x}$ is a prepared eigenstate and $M$ is an observable. For an $n \times n$ $s$-sparse Hermitian matrix $H$, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in $\mathcal{O}(n^3)$ time. Exploiting sparsity, the Lanczos method computes all eigenvalues in $\mathcal{O}(n^2 s)$ time in exact arithmetic, but recovering all eigenvectors still requires $\mathcal{O}(n^3)$ time. In contrast, our algorithm runs in time $\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})$, where $Δ_{\min}$ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to $Δ_{\min}^{-1} = \mathcal{O}(n)$, the most favorable scaling for $n$ distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to $s = o(\sqrt{n}/\log n)$, the proposed algorithm achieves an improved asymptotic runtime over the classical $\mathcal{O}(n^3)$ approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.

arXiv:2611.16610•Nov 12, 2026•0 citations
The logarithm-determinant is a widely-present operation in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the pseudo-inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all N2N^2N2 elements of the input operator--can be accomplished in O(k/ε2)O(k/\varepsilon^2)O(k/ε2) time in the idealized case for kkk relevant eigenvectors of the input matrix with precision ε\varepsilonε. A practical implementation of the required operator will likely need log⁡2N\log_2Nlog2​N overhead, giving an overall complexity of O((klog⁡2N)/ε2)O((k\log_2 N)/\varepsilon^2)O((klog2​N)/ε2). The method applies widely and converges super-linearly in kkk when the condition number is high. The best classical method we are aware of scales as NNN. Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as O(log⁡2N/ε2)O(\log_2 N/\varepsilon^2)O(log2​N/ε2). The output is given in O(1)O(1)O(1) queries of an oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning.
Gaussian processes (GPs) are important models in supervised machine learning. Training in Gaussian processes refers to selecting the covariance functions and the associated parameters in order to improve the outcome of predictions, the core of which amounts to evaluating the logarithm of the marginal likelihood (LML\mathrm{LML}LML) of a given model. The LML\mathrm{LML}LML gives a concrete measure of the quality of prediction that a GP model is expected to achieve. The classical computation of the LML\mathrm{LML}LML typically carries a polynomial time overhead with respect to the input size. We propose a quantum algorithm that computes the logarithm of the determinant of a Hermitian matrix, which runs in logarithmic time for sparse matrices. This is applied in conjunction with a variant of the quantum linear system algorithm that allows for logarithmic-time computation of the form ${\mathbf{y}}^{T}{A}^{\ensuremath{-}1}\mathbf{y}$, where y\mathbf{y}y is a dense vector and AAA is the covariance matrix. We hence show that quantum computing can be used to estimate the LML\mathrm{LML}LML of a GP with exponentially improved efficiency under certain conditions.
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued function f : Rd → R by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d.One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
We develop operator-output quantum algorithms for matrix equations and matrix functions using matrix-sign embeddings. For each problem, an augmented matrix MMM is chosen so that the target operator is a block of sign(M)\text{sign}(M)sign(M) or is recovered from blocks of (I−sign(M))/2(I-\text{sign}(M))/2(I−sign(M))/2. We approximate the half-plane sign by a logarithmic-sinc formula and implement the shifted inverse families by scaled multiplexing with node-dependent rebalancing. For ordinary Sylvester equations, this yields a block-encoding of the solution with query complexity linear in the relevant conditioning parameters and logarithmic in the inverse error tolerance, under either a field-of-values (FoV) gap or a strip-resolvent bound. The same method extends to generalized Sylvester and Lyapunov equations, principal square and inverse square roots, matrix geometric means, and continuous-time algebraic Riccati equations (CARE), with explicit query-complexity and block-encoding-normalization bounds that cover non-normal and non-diagonalizable cases.
This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.
We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate realvalued function f : ℝd → ℝ by evaluating it at only a logarithmic number of times in superposition. Our algorithm is an improved version of Jordan's gradient computation algorithm [28], providing an approximation of the gradient ▽f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that objective functions arising from variational quantum circuits usually satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d. One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
Computation of eigenvalues and eigenvectors of a sparse Hermitian matrix is a fundamental problem in algebra, arising both as a problem of independent interest and as a key subroutine in a wide range of computational and scientific applications. In this work, we develop a quantum algorithm that determines the spectrum of a sparse Hermitian matrix, defined as the set of its distinct eigenvalues, and for each eigenvalue, prepares a corresponding eigenvector as a quantum state in its eigenspace. The eigenvalues are represented as binary strings with a prescribed precision, while the corresponding eigenvectors are kept as quantum states, eliminating the need to reconstruct their classical counterparts. The algorithm instead enables estimation of expectation values ⟨x∣M∣x⟩\braket{x|M|x}⟨x∣M∣x⟩, where ∣x⟩\ket{x}∣x⟩ is a prepared eigenstate and MMM is an observable. For an n×nn \times nn×n sss-sparse Hermitian matrix HHH, dense methods based on Householder tridiagonalization and QR iteration compute all eigenvalues and eigenvectors in O(n3)\mathcal{O}(n^3)O(n3) time. Exploiting sparsity, the Lanczos method computes all eigenvalues in O(n2s)\mathcal{O}(n^2 s)O(n2s) time in exact arithmetic, but recovering all eigenvectors still requires O(n3)\mathcal{O}(n^3)O(n3) time. In contrast, our algorithm runs in time O~(ns2log⁡2n/Δmin⁡)\tilde{\mathcal{O}}(n s^2 \log^2 n / Δ_{\min})O~(ns2log2n/Δmin​), where Δmin⁡Δ_{\min}Δmin​ denotes the minimum spectral gap of the normalized matrix. For inverse gaps up to Δmin⁡−1=O(n)Δ_{\min}^{-1} = \mathcal{O}(n)Δmin−1​=O(n), the most favorable scaling for nnn distinct eigenvalues, attained by nearly uniformly spaced spectra such as those of perfect-state-transfer spin chains and the Sylvester-Kac matrix, and for sparsity up to s=o(n/log⁡n)s = o(\sqrt{n}/\log n)s=o(n​/logn), the proposed algorithm achieves an improved asymptotic runtime over the classical O(n3)\mathcal{O}(n^3)O(n3) approach for computing all eigenvalues and eigenvectors, under standard sparse-access assumptions.