A quantum algorithm for estimating the determinant

• URL: http://arxiv.org/abs/2504.11049v2
• Date: Thu, 01 May 2025 11:30:45 GMT
• Title: A quantum algorithm for estimating the determinant
• Authors: Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone,
• Abstract summary: The algorithm estimates the determinant of an $n times n$ positive sparse matrix to an accuracy $epsilon$ in time $cal O(log n/epsilon3)$.<n>The quantum spectral sampling algorithm generalizes to estimating any quantity $sum_j f(lambda_j)$, where $lambda_j$ are the matrix eigenvalues.
• Score: 4.369550829556577
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an $n \times n$ positive sparse matrix to an accuracy $\epsilon$ in time ${\cal O}(\log n/\epsilon^3)$, exponentially faster than previously existing classical or quantum algorithms that scale linearly in $n$. The quantum spectral sampling algorithm generalizes to estimating any quantity $\sum_j f(\lambda_j)$, where $\lambda_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z(\beta) =\sum_j e^{-\beta E_j}$ of a Hamiltonian system with energy eigenvalues $E_j$, and of the entropy $ S =-\sum_j p_j \log p_j$ of a density matrix with eigenvalues $p_j$.

Related papers

• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  Conditional measurement is involved to avoid small success probability in ancilla measurement.<n>The objective function for the algorithm can be obtained probabilistically via measurement of the state of a one-qubit subsystem.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Quantum algorithm for the gradient of a logarithm-determinant [0.0]
  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.
  arXiv  Detail & Related papers  (2025-01-16T09:39:31Z)
• 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.<n>This approach is a straightforward modification of the existing algorithm for determining the determinant of an $N times N$ matrix.<n>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)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
  arXiv  Detail & Related papers  (2023-11-07T22:52:56Z)
• Do you know what q-means? [45.810803542748495]
  We present an improved version of the quantum algorithm originally proposed by Kerenidis, Landman, Luongo, and Prakash (NeurIPS')<n>Our algorithm does not rely on quantum linear algebra primitives of prior work, but instead only uses QRAM to prepare simple states.<n>We also present a "dequantized" algorithm for $varepsilon$-$k$-means which runs in $Obig.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Quantum Algorithm for Matrix Logarithm by Integral Formula [0.0]
  Recently, a quantum algorithm that computes the state $|frangle$ corresponding to matrix-vector product $f(A)b$ is proposed. We propose a quantum algorithm, which uses LCU method and block-encoding technique as subroutines.
  arXiv  Detail & Related papers  (2021-11-17T05:46:12Z)
• Improved quantum lower and upper bounds for matrix scaling [0.0]
  We investigate the possibilities for quantum speedups for classical second-order algorithms. We show that there can be essentially no quantum speedup in terms of the input size in the high-precision regime. We give improved quantum algorithms in the low-precision regime.
  arXiv  Detail & Related papers  (2021-09-30T17:29:23Z)
• 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)
• Hutch++: Optimal Stochastic Trace Estimation [75.45968495410048]
  We introduce a new randomized algorithm, Hutch++, which computes a $(1 pm epsilon)$ approximation to $tr(A)$ for any positive semidefinite (PSD) $A$. We show that it significantly outperforms Hutchinson's method in experiments.
  arXiv  Detail & Related papers  (2020-10-19T16:45:37Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• 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.