Quantum algorithm for the gradient of a logarithm-determinant

• URL: http://arxiv.org/abs/2501.09413v1
• Date: Thu, 16 Jan 2025 09:39:31 GMT
• Title: Quantum algorithm for the gradient of a logarithm-determinant
• Authors: Thomas E. Baker, Jaimie Greasley,
• Abstract summary: The inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N2$ elements of the input operator--can be accomplished in $O(ksigma)$ time. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines.
• Score: 0.0
• License:
• Abstract: The logarithm-determinant is a common quantity 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 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\sigma)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix. A factor $\sigma=\frac1{\varepsilon^3}$ or $-\frac1{\varepsilon^2}\log_2\varepsilon$ depends on the version of the quantum Fourier transform used for a precision $\varepsilon$. Practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O(k\sigma\log_2 N)$. The method applies widely and converges super-linearly in $k$ when the condition number is high. For non-sparse-rank inputs, the algorithm can be evaluated provided that an equal superposition of eigenstates is provided. The output is given in $O(1)$ queries of 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.

Related papers

• Entanglement-Assisted Coding for Arbitrary Linear Computations Over a Quantum MAC [34.32444379837011]
  We study a linear computation problem over a quantum multiple access channel (LC-QMAC) We propose an achievable scheme for LC-QMAC based on the stabilizer formalism and the ideas from entanglement-assisted quantum error-correcting codes (EAQECC)
  arXiv  Detail & Related papers  (2025-01-27T18:35:33Z)
• Quantum spectral method for gradient and Hessian estimation [4.193480001271463]
  Gradient descent is one of the most basic algorithms for solving continuous optimization problems. We propose a quantum algorithm that returns an $varepsilon$-approximation of its gradient with query complexity $widetildeO (1/varepsilon)$. We also propose two quantum algorithms for Hessian estimation, aiming to improve quantum analogs of Newton's method.
  arXiv  Detail & Related papers  (2024-07-04T11:03:48Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms for the computation of the determinant and inverse of an $(N-1) times (N-1)$ matrix. This approach is a straightforward modification of the existing algorithm for determining the determinant of an $N times N$ matrix. We provide suitable circuit designs for all three algorithms, each estimated to require $O(N log N)$ in terms of space.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• A quantum algorithm for computing the Carmichael function [0.0]
  Quantum computers can solve many number theory problems efficiently. This paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired.
  arXiv  Detail & Related papers  (2021-11-03T19:30:27Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  This work examines the computation of higher-order derivatives with respect to the normalization constant for weighted finite-state machines. We provide a general algorithm for evaluating derivatives of all orders, which has not been previously described in the literature. Our algorithm is significantly faster than prior algorithms.
  arXiv  Detail & Related papers  (2021-06-01T19:51:55Z)
• Quantum Algorithm for Fidelity Estimation [8.270684567157987]
  For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem. We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
  arXiv  Detail & Related papers  (2021-03-16T13:57:01Z)
• Efficient algorithm for generating Pauli coordinates for an arbitrary linear operator [0.0]
  We present an efficient algorithm that for our particular basis only involves $mathcal O(mathrm N2logmathrm N)$ operations. Because this algorithm requires fewer than $mathcal O(mathrm N3)$ operations, for large $mathrm N$, it could be used as a preprocessing step for quantum computing algorithms.
  arXiv  Detail & Related papers  (2020-11-17T20:57:39Z)
• 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)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.