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).
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).
Abstract Fundamental matrix operations and solving linear systems of equations are ubiquitous in scientific investigations. Using the ‘sender-receiver’ model, we propose quantum algorithms for matrix operations such as matrix-vector product, matrix-matrix product, the sum of two matrices, and the calculation of determinant and inverse matrix. We encode the matrix entries into the probability amplitudes of the pure initial states of senders. After applying proper unitary transformation to the complete quantum system, the desired result can be found in certain blocks of the receiver’s density matrix. These quantum protocols can be used as subroutines in other quantum schemes. Furthermore, we present an alternative quantum algorithm for solving linear systems of equations.
We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity O(ε1logm), where m is the number of variables and ε is the target precision, without dependence on the sparsity s, and could possibly be without explicit dependence on condition number κ. This shows a significant improvement over previous quantum linear solvers where the dependence on κ,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most s nonzero entries, we obtain the circuit depth O(ε1logs) using extra O(s) ancilla qubits, so the depth grows only logarithmically with sparsity s. When the sparsity s grows as O(logm), then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.
Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N × N Hermitian matrices, the space cost is log ( N ) + 1 qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O ( N 2 ) , when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems. Published by the American Physical Society 2024
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 determinant sampling algorithm that samples from the distribution Pr[S]=det(XSXST) for ∣S∣=d using O(nd) gates and with circuit depth O(dlogn). The state of art classical algorithm for the task requires O(d3) operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices Ak, the speedup for this algorithm is potentially exponential. It decomposes a (kn) dimensional vector of order-k correlations into a linear combination of subspace states corresponding to k-tuples of singular vectors of A. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from O(n) to O(logn). Our basic tool are quantum subspace states, defined as ∣Col(X)⟩=∑S⊂[n],∣S∣=ddet(XS)∣S⟩ for matrices X∈Rn×d such that XTX=Id, that encode d-dimensional subspaces of Rn. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries Γ(x)=∑ixiZ⊗(i−1)⊗X⊗In−i with O(logn) depth circuits that we term Clifford loaders.
We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function f and a Hermitian matrix A , we compute a matrix element of f ( A ) or a local measurement on f ( A ) | 0 ⟩ ⊗ n , with | 0 ⟩ ⊗ n being an n -qubit reference state vector, in both cases up to additive approximation error. We consider four functions—monomials, Chebyshev polynomials, the time evolution function, and the inverse function—and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm and sparsity), the approximation error, and function-specific parameters. We identify BQP- forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results, we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree poly ( n ) , both problems can be efficiently classically simulated when A has O ( log n ) nonzero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP- in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity O ( log n ) . Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.