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

Abstract

We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)\times (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\times 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 $\sim 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).

16 pages, 6 figures, published manuscript

References in corpus (29)

• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Adiabatic Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• Bounds for the adiabatic approximation with applications to quantum computation
• An approximate Fourier transform useful in quantum factoring
• Preconditioned quantum linear system algorithm
• Prediction by linear regression on a quantum computer
• High-order quantum algorithm for solving linear differential equations
• Efficient quantum algorithm for dissipative nonlinear differential equations
• A quantum linear system algorithm for dense matrices
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Experimental Quantum Computing to Solve Systems of Linear Equations
• The methodology of resonant equiangular composite quantum gates
• Quantum Algorithm for Linear Regression
• Experimental realization of quantum algorithm for solving linear systems of equations
• Solving systems of linear equations on a quantum computer
• Solving Systems of Linear Equations with a Superconducting Quantum Processor
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices
• Quantum algorithms for matrix operations and linear systems of equations
• Matrix manipulations via unitary transformations and ancilla-state measurements
• Approximating the Determinant of Well-Conditioned Matrices by Shallow Circuits
• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms