Quantum Determinant Estimation

• URL: http://arxiv.org/abs/2504.07497v1
• Date: Thu, 10 Apr 2025 06:53:37 GMT
• Title: Quantum Determinant Estimation
• Authors: J. Agerskov, K. Splittorff,
• Abstract summary: A quantum algorithm for computing the determinant of a unitary matrix $Uin U(N)$ is given.<n>The algorithm requires no preparation of eigenstates of $U$ and estimates the phase of the determinant to $t$ binary digits accuracy.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A quantum algorithm for computing the determinant of a unitary matrix $U\in U(N)$ is given. The algorithm requires no preparation of eigenstates of $U$ and estimates the phase of the determinant to $t$ binary digits accuracy with $\mathcal{O}(N\log^2 N+t^2)$ operations and $tN$ controlled applications of $U^{2^m}$ with $m=0,\ldots,t-1$. For an orthogonal matrix $O\in O(N)$ the algorithm can determine with certainty the sign of the determinant using $\mathcal{O}(N\log^2 N)$ operations and $N$ controlled applications of $O$. An extension of the algorithm to contractions is discussed.

Related papers

• A quantum algorithm for estimating the determinant [4.369550829556577]
  The algorithm estimates the determinant of an $n times n$ positive sparse matrix to an accuracy $epsilon$ in time $cal O(log n/epsilon3)$. The quantum spectral sampling algorithm generalizes to estimating any quantity $sum_j f(lambda_j)$, where $lambda_j$ are the matrix eigenvalues.
  arXiv  Detail & Related papers  (2025-04-15T10:32:36Z)
• 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)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• 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)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Quantum machine learning with subspace states [8.22379888383833]
  We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum sampling algorithm that samples from the distribution $Pr[S]= det(X_SX_ST)$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(dlog n)$. The second is a quantum singular value estimation algorithm for compound matrices $mathcalAk$, the speedup for this algorithm is potentially exponential.
  arXiv  Detail & Related papers  (2022-01-31T19:34:47Z)
• 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)
• Quantum algorithm for matrix functions by Cauchy's integral formula [1.399948157377307]
  We consider the problem of obtaining quantum state $lvert f rangle$ corresponding to vector $f(A)boldsymbolb$. We propose a quantum algorithm that uses Cauchy's integral formula and the trapezoidal rule as an approach that avoids eigenvalue estimation.
  arXiv  Detail & Related papers  (2021-06-15T12:10:16Z)
• 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)

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.