Quantum Determinant Estimation

J. Agerskov and K. Splittorff · 2025

Read Quantum Determinant Estimation by J. Agerskov and K. Splittorff (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-07497.txt.

Introduction

Agerskov and Splittorff give a quantum algorithm for matrix determinants in a 2025 paper. The determinant of a unitary matrix carries a phase that quantum hardware can read. Their method skips the costly step of preparing eigenstates. It reads the phase to a chosen number of binary digits with a cost that grows gently with matrix size.

For plain rotation-type matrices, the method settles the determinant's sign for sure at similar cost. The pair also discuss stretching the method to matrices that shrink vectors. Operation counts are stated in full, so readers can weigh the method against classical routes. The paper serves quantum algorithm designers.

Catalog record

CREATORJ. Agerskov and K. Splittorff
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE24 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-07497

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Determinant Estimation J. Agerskov and K. Splittorff Abstract A quantum algorithm for computing the determinant of a unitary matrix U ∈ U ⁡ ( N ) U\in U(N) is given. The algorithm requires no preparation of eigenstates of U U and estimates the phase of the determinant to t t binary digits accuracy with 𝒪 ⁡ ( N ​ log 2 ​ N + t 2 ) \mathcal{O}(N\log^{2}N+t^{2}) operations and t ​ N tN controlled applications of U 2 m U^{2^{m}} with m = 0 , … , t − 1 m=0,\ldots,t-1 . For an orthogonal matrix O ∈ O ⁡ ( N ) O\in O(N) the algorithm can determine with certainty the sign of the determinant using 𝒪 ⁡ ( N ​ log 2 ​ N ) \mathcal{O}(N\log^{2}N) operations and N N controlled applications of O O . An extension of the algorithm to contractions is discussed. I Introduction The ability of quantum algorithms to solve certain problems significantly faster than any known classical algorithms, has sparked immense interest in developing quantum computers. The advantage of quantum algorithms is in some cases exponential [ 1 ] , and the range of applications is ever increasing [ 2 ] . A prime example is the Quantum Phase Estimation (QPE) algorithm [ 3 , 4 , 5 ] which allows to estimate an eigenvalue of a unitary matrix to exponential accuracy. This fundamental algorithm is used in applications ranging from prime factorization [ 6 ] to solving systems of linear equations [ 7 ] and estimation of the ground state energy of Hamiltonians [ 1 ] . The aim of the present paper is to introduce a quantum algorithm which can evaluate the determinant of a unitary matrix to exponential accuracy. The motivation for developing a quantum algorithm which estimates the determinant is manifold; for example 1) the determinant enters as a tool in many computational strategies [ 8 ] 2) determinants occurs naturally in partition functions where fermions have been integrated out [ 9 ] 3) the determinant is a global property of the matrix, that is a property which is not associated with a single eigenstate of the matrix. The Quantum Determinant Estimation (QDE) introduced here estimates the phase of the determinant of a unitary matrix U\in U(N) . The QDE algorithm relies on two key ingredients: First, if we perform a change of basis with U , the completely antisymmetric state is invariant up a multiplicative factor given by the determinant of U . Second, the ability of the standard QPE algorithm to estimate a phase to high accuracy efficiently. The combination of these two ingredients allows the QDE algorithm to estimate the phase of the determinant to t binary digits accuracy with \mathcal{O}(N\log^{2}N+t^{2}) operations and Nt controlled applications of U^{2^{m}} where m=0,\ldots,t-1 . Note that while the QPE algorithm requires the preparation of the eigenstate belonging to the eigenvalue we wish to estimate (or at least a state with a significant overlap with this eigenstate), the QDE algorithm introduced here does not require preparation of any eigenstate of U . Instead it requires the preparation of a completely antisymmetric state which is independent of U . Just as the order finding in Shors algorithm [ 6 ] can be viewed as a special case of QPE for a certain unitary and a clever choice of initial state [ 1 ] , the QDE algorithm can be viewed as an application of the QPE algorithm for the matrix U^{\otimes N} applied to a completely antisymmetric state. In this formulation of the QDE algorithm, we use the fact that any completely antisymmetric state, made up of a basis of the Hilbert space, is an eigenstate of U^{\otimes N} with eigenvalue equal to \det(U) . As an application of the QDE algorithm we show that it can determine with certainty the sign of the determinant of an orthogonal matrix with \mathcal{O}(N\log^{2}N) operations and N controlled applications of O . A quantum algorithm for determinant estimation has been studied recently in [ 10 , 11 ] and we compare the performance of the QDE algorithm with that of [ 10 , 11 ] below. Quantum algorithms to estimate the log-determinant by means of spectral sampling have been introduced in [ 12 , 13 , 14 ] . We comment on assumptions and runtimes of these algorithms compared to QDE. We introduce one possible extension of the QDE algorithm from unitary matrices to contractions, and discuss its performance. The paper is organized as follows: First the QDE algorithm is presented in Section II and in Section III the performance of the QDE algorithm is considered. In Section IV the QDE algorithm is reformulated as a special case of the QPE algorithm. The application of the QDE algorithm to orthogonal matrices is presented in section V . We compare the QDE algorithm to existing algorithms in Section VI and discuss one possible extension to non-unitary matrices in Section VII . Finally Section VIII contains a summery and outlook. II Quantum Determinant Estimation The task: Given a unitary matrix U\in U(N) , the task is to provide an estimate of the determinant \displaystyle\det(U)=e^{i\phi_{U}}\ . (1) The QDE algorithm will provide an estimate of \phi_{U} which is accurate to t -binary digits. The algorithm: The key ingredient in the QDE algorithm is the identity \displaystyle\sum_{\sigma\in S_{N}}{\rm sgn}(\sigma)|U\sigma(1),\ldots,U\sigma(N)\rangle=\det(U)\sum_{\sigma\in S_{N}}{\rm sgn}(\sigma)|\sigma(1),\ldots,\sigma(N)\rangle\ . (2) Here S_{N} denotes the symmetric group over the set \{1,\ldots,N\} and {\rm sgn}(\sigma) is the sign of the element \sigma\in S_{N} . The identity states that a completely antisymmetric tensorspaceproduct of any basis of the Hilbert space, transforms trivially under U up to multiplication by the determinant of U . As the determinant of a unitary matrix is a complex phase, \det(U)=e^{i\phi_{U}} , we can combine the identity ( 2 ) with a slightly modified form of the QPE algorithm and get an estimate of \phi_{U} to t binary digits accuracy. The steps of the QDE algorithm are given in Table 1 and the corresponding quantum circuit is displayed in Figure II . The algorithm employs two registers: Register 1 with t qubits and Register 2 with N\log(N) qubits. The identity ( 2 ) is sometimes taken to be the very definition of the determinant, see eg. [ 15 ] , and it holds for matrices beyond unitary. For completeness we demonstrate in Appendix A that ( 2 ) is consistent with a perhaps more familiar expression for the determinant. Operation State Operations Reference Initial |0\rangle|0,\ldots,0\rangle Orh.n. |0\rangle|1,\ldots,N\rangle \mathcal{O}(N\log(N/e)) QFT \frac{1}{\sqrt{2^{t}}}\sum_{j=0}^{2^{t}-1}|j\rangle|1,\ldots,N\rangle \mathcal{O}(t) [ 1 ] Asym \frac{1}{\sqrt{2^{t}}}\sum_{j=0}^{2^{t}-1}|j\rangle\frac{1}{\sqrt{N!}}\sum_{\sigma}{\rm sgn}(\sigma)|\sigma(1),\ldots,\sigma(N)\rangle \mathcal{O}(N\log^{2}N) [ 16 ] cU^{\otimes N} \frac{1}{\sqrt{2^{t}}}\sum_{j=0}^{2^{t}-1}|j\rangle|\frac{1}{\sqrt{N!}}\sum_{\sigma}{\rm sgn}(\sigma)|U^{j}\sigma(1),\ldots,U^{j}\sigma(N)\rangle \mathcal{O}(tN) cU^{2^{m}} =\frac{1}{\sqrt{2^{t}}}\sum_{j=0}^{2^{t}-1}e^{i\phi_{U}j}|j\rangle|\frac{1}{\sqrt{N!}}\sum_{\sigma}{\rm sgn}(\sigma)|\sigma(1),\ldots,\sigma(N)\rangle QFT -1 \frac{1}{2^{t}}\sum_{j,k=0}^{2^{t}-1}e^{i(\phi_{U}-2\pi\frac{k}{2^{t}})j}|k\rangle\frac{1}{\sqrt{N!}}\sum_{\sigma}{\rm sgn}(\sigma)|\sigma(1),\ldots,\sigma(N)\rangle \mathcal{O}(t^{2}) [ 1 ] Measure |k^{\prime}\rangle\frac{1}{\sqrt{N!}}\sum_{\sigma}{\rm sgn}(\sigma)|\sigma(1),\ldots,\sigma(N)\rangle \mathcal{O}(t) Table 1 : The Quantum Determinant Estimation (QDE) algorithm gives an estimate for the phase \phi_{U} of the determinant \det(U)=e^{i\phi_{U}} of a unitary matrix U\in U(N) . The estimate is accurate to t binary digits where t is the number of qubits in the register 1. Assumptions: As the QDE algorithm makes use of a slightly modified form of QPE we assume, as is standard for QPE [ 1 , 4 ] , that we have available black boxes capable of

Read the complete text