Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems

• URL: http://arxiv.org/abs/2401.16619v4
• Date: Sun, 15 Dec 2024 08:28:54 GMT
• Title: Purely quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems
• Authors: Alexander I. Zenchuk, Georgii A. Bochkin, Wentao Qi, Asutosh Kumar, Junde Wu,
• Abstract summary: 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.
• Score: 43.53835128052666
• License:
• Abstract: We propose quantum algorithms that are fundamentally quantum in nature for the computation of the determinant and inverse of an $(N-1) \times (N-1)$ matrix, with a computational depth of $O(N^2 \log N)$. This approach is a straightforward modification of the existing algorithm for determining the determinant of an $N \times N$ matrix, which operates with a depth of $O(N \log^2 N)$. The core concept involves encoding each row of the matrix into a pure state of a quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm, in conjunction with the matrix multiplication algorithm discussed in the appendix, facilitates solving systems of linear algebraic equations with a depth of $O(N \log^2 N)$. The measurement of the ancilla state yielding an output of 1 occurs with a probability of approximately $2^{-O(N \log N)}$, and eliminates the extraneous data generated during the computation. We provide suitable circuit designs for all three algorithms, each estimated to require $O(N \log N)$ in terms of space, specifically the number of qubits utilized in the circuit.

Related papers

• 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)
• Scaling of symmetry-restricted quantum circuits [42.803917477133346]
  In this work, we investigate the properties of $mathcalMSU(2N)$, $mathcalM$-invariant subspaces of the special unitary Lie group $SU(2N)$.
  arXiv  Detail & Related papers  (2024-06-14T12:12:15Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [3.4137115855910767]
  We propose a class of randomized quantum algorithms for the task of sampling from matrix functions. Our use of qubits is purely algorithmic, and no additional qubits are required for quantum data structures.
  arXiv  Detail & Related papers  (2023-02-03T17:22:49Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• 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)
• 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)

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.