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:2504.07497 · Physical Review A

Quantum determinant estimation

J. Agerskov, K. Splittorff

Published Jun 13, 2025• 0 citations
arXivHTMLPDF

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.

DOI
10.1103/mr7q-3z8s

Related papers

Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues

Abhijeet Alase, Salini Karuvade

Quantum algorithms for estimating the eigenvalues of matrices, including the phase estimation algorithm, serve as core subroutines in a wide range of quantum algorithms, including those in quantum chemistry and quantum machine learning. The standard quantum eigenvalue (phase) estimation algorithm accepts a Hermitian (unitary) matrix and a state in an unknown superposition of its eigenstates as input, and coherently records the estimates for real eigenvalues (eigenphases) in an ancillary register. Extension of quantum eigenvalue and phase estimation algorithms to the case of non-normal input matrices is obstructed by several factors such as non-orthogonality of eigenvectors, existence of generalized eigenvectors and the fact that eigenvalues may lie anywhere on the complex plane. In this work, we propose a novel approach for estimating the eigenvalues of non-normal matrices based on preparation of a state that we call the "resolvent state". We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix, achieving complexities that match the best known results while operating under significantly relaxed assumptions on the non-real part of the spectrum. The resolvent-based approach that we introduce also extends to estimating eigenvalues that lie on a parametrized complex curve, subject to explicitly stated conditions, thereby paving the way for a new paradigm of parametric eigenvalue estimation.

arXiv:2410.04837•Oct 7, 2024•7 citations

Solovay–Kitaev Approximations of Special Orthogonal Matrices

Anuradha Mahasinghe, Sachiththa Bandaranayake, Kaushika De Silva

The circuit-gate framework of quantum computing relies on the fact that an arbitrary quantum gate in the form of a unitary matrix of unit determinant can be approximated to a desired accuracy by a fairly short sequence of basic gates, of which the exact bounds are provided by the Solovay–Kitaev theorem. In this work, we show that a version of this theorem is applicable to orthogonal matrices with unit determinant as well, indicating the possibility of using orthogonal matrices for efficient computation. We further develop a version of the Solovay–Kitaev algorithm and discuss the computational experience.

Advances in Mathematical Physics•Jun 24, 2020•4 citations

Quantum phase processing and its applications in estimating phase and entropies

Youle Wang, Lei Zhang, Zhan Yu +1 more

Quantum computing can provide speedups in solving many problems as the evolution of a quantum system is described by a unitary operator in an exponentially large Hilbert space. Such unitary operators change the phase of their eigenstates and make quantum algorithms fundamentally different from their classical counterparts. Based on this unique principle of quantum computing, we develop an algorithmic toolbox, quantum phase processing, that can directly apply arbitrary trigonometric transformations to eigenphases of a unitary operator. The quantum phase processing circuit is constructed simply, consisting of single-qubit rotations and controlled unitaries, typically using only one ancilla qubit. Besides the capability of phase transformation, quantum phase processing in particular can extract the eigeninformation of quantum systems by simply measuring the ancilla qubit, making it naturally compatible with indirect measurement. Quantum phase processing complements another powerful framework known as quantum singular value transformation and leads to more intuitive and efficient quantum algorithms for solving problems that are particularly phase related. As a notable application, we propose a quantum phase estimation algorithm without quantum Fourier transform, which requires the fewest ancilla qubits and matches the best performance so far. We further exploit the power of our method by investigating a plethora of applications in Hamiltonian simulation, entanglement spectroscopy, and quantum entropy estimation, demonstrating improvements or optimality for almost all cases.

arXiv:2209.14278•Physical Review A•Dec 13, 2023•50 citations

A quantum algorithm for estimating the determinant

Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone

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 $ε$ in time ${\cal O}(\log n/ε^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(λ_j)$, where $λ_j$ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function $Z(β) =\sum_j e^{-β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$.

arXiv:2504.11049•Apr 15, 2025•10 citations

Preparation of Approximate Eigenvector by Unitary Operations on Eigenstate in Abrams-Lloyd Quantum Algorithm

Latha S. Warrier

The Abrams-Lloyd quantum algorithm computes an eigenvalue and the corresponding eigenstate of a unitary matrix from an approximate eigenvector Va . The eigenstate is a basis vector in the orthonormal eigenspace. Finding another eigenvalue, using a random approximate eigenvector, may require many trials as the trial may repeatedly result in the eigenvalue measured earlier. We present a method involving orthogonalization of the eigenstate obtained in a trial. It is used as the Va for the next trial. Because of the orthogonal construction, Abrams-Lloyd algorithm will not repeat the eigenvalue measured earlier. Thus, all the eigenvalues are obtained in sequence without repetitions. An operator that anticommutes with a unitary operator orthogonalizes the eigenvectors of the unitary. We implemented the method on the programming language model of quantum computation and tested it on a unitary matrix representing the time evolution operator of a small spin chain. All the eigenvalues of the operator were obtained sequentially. Another use of the first eigenvector from Abrams-Lloyd algorithm is preparing a state that is the uniform superposition of all the eigenvectors. This is possible by nonorthogonalizing the first eigenvector in all dimensions and then applying the Abrams-Lloyd algorithm steps stopping short of the last measurement.

Journal of Computational Methods in Physics•Sep 11, 2013•0 citations

Quantum Algorithms for Calculating Determinant and Inverse of Matrix and Solving Linear Algebraic Systems

Alexander Ivanovich Zenchuk, G. A. Bochkin, Wentao Qi +2 more

Abstract We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an ( N – 1) × ( N – 1) matrix (depth is O ( N 2 log N )) which is a simple modification of the algorithm for calculating the determinant of an N × N matrix (depth is O ( N log 2 N )). The basic idea is to encode each row of the matrix into a pure state of some quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm together with that for matrix multiplication proposed earlier yields the algorithm for solving systems of linear algebraic equations (depth is O ( N log 2 N )). Measurement of the ancilla state with output 1 (probability is ~ 2 − O ( N log N ) ) removes the garbage acquired during calculation. Appropriate circuits for all three algorithms are presented and have the same estimation O ( N log N ) for the space (number of qubits in the circuit).

arXiv:2401.16619•Quantum Information and Computation•May 1, 2025•5 citations
A quantum algorithm for computing the determinant of a unitary matrix U∈U(N)U\in U(N)U∈U(N) is given. The algorithm requires no preparation of eigenstates of UUU and estimates the phase of the determinant to ttt binary digits accuracy with O(Nlog⁡2N+t2)\mathcal{O}(N\log^2 N+t^2)O(Nlog2N+t2) operations and tNtNtN controlled applications of U2mU^{2^m}U2m with m=0,…,t−1m=0,\ldots,t-1m=0,…,t−1. For an orthogonal matrix O∈O(N)O\in O(N)O∈O(N) the algorithm can determine with certainty the sign of the determinant using O(Nlog⁡2N)\mathcal{O}(N\log^2 N)O(Nlog2N) operations and NNN controlled applications of OOO. An extension of the algorithm to contractions is discussed.
Quantum algorithms for estimating the eigenvalues of matrices, including the phase estimation algorithm, serve as core subroutines in a wide range of quantum algorithms, including those in quantum chemistry and quantum machine learning. The standard quantum eigenvalue (phase) estimation algorithm accepts a Hermitian (unitary) matrix and a state in an unknown superposition of its eigenstates as input, and coherently records the estimates for real eigenvalues (eigenphases) in an ancillary register. Extension of quantum eigenvalue and phase estimation algorithms to the case of non-normal input matrices is obstructed by several factors such as non-orthogonality of eigenvectors, existence of generalized eigenvectors and the fact that eigenvalues may lie anywhere on the complex plane. In this work, we propose a novel approach for estimating the eigenvalues of non-normal matrices based on preparation of a state that we call the "resolvent state". We construct the first efficient algorithm for estimating the phases of the unimodular eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix, achieving complexities that match the best known results while operating under significantly relaxed assumptions on the non-real part of the spectrum. The resolvent-based approach that we introduce also extends to estimating eigenvalues that lie on a parametrized complex curve, subject to explicitly stated conditions, thereby paving the way for a new paradigm of parametric eigenvalue estimation.
The circuit-gate framework of quantum computing relies on the fact that an arbitrary quantum gate in the form of a unitary matrix of unit determinant can be approximated to a desired accuracy by a fairly short sequence of basic gates, of which the exact bounds are provided by the Solovay–Kitaev theorem. In this work, we show that a version of this theorem is applicable to orthogonal matrices with unit determinant as well, indicating the possibility of using orthogonal matrices for efficient computation. We further develop a version of the Solovay–Kitaev algorithm and discuss the computational experience.
Quantum computing can provide speedups in solving many problems as the evolution of a quantum system is described by a unitary operator in an exponentially large Hilbert space. Such unitary operators change the phase of their eigenstates and make quantum algorithms fundamentally different from their classical counterparts. Based on this unique principle of quantum computing, we develop an algorithmic toolbox, quantum phase processing, that can directly apply arbitrary trigonometric transformations to eigenphases of a unitary operator. The quantum phase processing circuit is constructed simply, consisting of single-qubit rotations and controlled unitaries, typically using only one ancilla qubit. Besides the capability of phase transformation, quantum phase processing in particular can extract the eigeninformation of quantum systems by simply measuring the ancilla qubit, making it naturally compatible with indirect measurement. Quantum phase processing complements another powerful framework known as quantum singular value transformation and leads to more intuitive and efficient quantum algorithms for solving problems that are particularly phase related. As a notable application, we propose a quantum phase estimation algorithm without quantum Fourier transform, which requires the fewest ancilla qubits and matches the best performance so far. We further exploit the power of our method by investigating a plethora of applications in Hamiltonian simulation, entanglement spectroscopy, and quantum entropy estimation, demonstrating improvements or optimality for almost all cases.
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×nn \times nn×n positive sparse matrix to an accuracy εεε in time O(log⁡n/ε3){\cal O}(\log n/ε^3)O(logn/ε3), exponentially faster than previously existing classical or quantum algorithms that scale linearly in nnn. The quantum spectral sampling algorithm generalizes to estimating any quantity ∑jf(λj)\sum_j f(λ_j)∑j​f(λj​), where λjλ_jλj​ are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function Z(β)=∑je−βEjZ(β) =\sum_j e^{-βE_j}Z(β)=∑j​e−βEj​ of a Hamiltonian system with energy eigenvalues EjE_jEj​, and of the entropy $ S =-\sum_j p_j \log p_j$ of a density matrix with eigenvalues pjp_jpj​.
The Abrams-Lloyd quantum algorithm computes an eigenvalue and the corresponding eigenstate of a unitary matrix from an approximate eigenvector Va . The eigenstate is a basis vector in the orthonormal eigenspace. Finding another eigenvalue, using a random approximate eigenvector, may require many trials as the trial may repeatedly result in the eigenvalue measured earlier. We present a method involving orthogonalization of the eigenstate obtained in a trial. It is used as the Va for the next trial. Because of the orthogonal construction, Abrams-Lloyd algorithm will not repeat the eigenvalue measured earlier. Thus, all the eigenvalues are obtained in sequence without repetitions. An operator that anticommutes with a unitary operator orthogonalizes the eigenvectors of the unitary. We implemented the method on the programming language model of quantum computation and tested it on a unitary matrix representing the time evolution operator of a small spin chain. All the eigenvalues of the operator were obtained sequentially. Another use of the first eigenvector from Abrams-Lloyd algorithm is preparing a state that is the uniform superposition of all the eigenvectors. This is possible by nonorthogonalizing the first eigenvector in all dimensions and then applying the Abrams-Lloyd algorithm steps stopping short of the last measurement.
Abstract We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an ( N – 1) × ( N – 1) matrix (depth is O ( N 2 log N )) which is a simple modification of the algorithm for calculating the determinant of an N × N matrix (depth is O ( N log 2 N )). The basic idea is to encode each row of the matrix into a pure state of some quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm together with that for matrix multiplication proposed earlier yields the algorithm for solving systems of linear algebraic equations (depth is O ( N log 2 N )). Measurement of the ancilla state with output 1 (probability is ~ 2 − O ( N log N ) ) removes the garbage acquired during calculation. Appropriate circuits for all three algorithms are presented and have the same estimation O ( N log N ) for the space (number of qubits in the circuit).