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.<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.
• Score: 43.53835128052666
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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

• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals. The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• Quantum Determinant Estimation [0.0]
  A quantum algorithm for computing the determinant of a unitary matrix $Uin 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.
  arXiv  Detail & Related papers  (2025-04-10T06:53:37Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  Conditional measurement is involved to avoid small success probability in ancilla measurement. 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)
• 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)
• 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)
• Efficient quantum algorithms for solving quantum linear system problems [0.0]
  We present two quantum algorithms for solving the problem of finding the right singular vector with singular value zero of an augmented matrix $C$. Both algorithms meet the optimal query complexity in $kappa $, and are simpler than previous algorithms.
  arXiv  Detail & Related papers  (2022-08-14T02:49:26Z)
• 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)
• 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)
• 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)
• 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)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.