Quantum Algorithms for Calculating Determinant and Inverse of Matrix and Solving Linear Algebraic Systems

Zenchuk, Alexander I.; Bochkin, Georgii A.; Qi, Wentao; Kumar, Asutosh; Wu, Junde

doi:10.2478/qic-2025-0010

Full Article

1.

Introduction

Quantum algorithms exploiting principles of quantum physics can be run on quantum computers and promise to offer considerable advantages over classical counterparts. Algorithms for quantum calculations are an increasingly prominent field in quantum information research. Notable examples include Shor’s factoring algorithm [1,2], Deutsch parallelism [3], Grover’s search algorithm [4], Quantum Fourier transform [5–7], and Quantum phase estimation [7,8]. Further advancements include the HHL algorithm for solving systems of linear equations [9–16], in which the crucial point is the conditional rotation of the state of the one-qubit ancilla. This operation, where inversion of the eigenvalue requires involving classical computing, is placed between the blocks of the direct and inverse phase estimation algorithms. HHL algorithm exponentiates a Hermitian matrix of the considered linear system, which can be performed via the Trotterization formula [17,18]. There is extensive literature devoted to improvement of this algorithm, especially its scaling and complexity [19–28]. However, the principal problem of eigenvalue inversion is not resolved via quantum methods yet. For this purpose, for instance, quantum state tomography can be used to obtain the eigenvalues of the exponent of Hermitian operator (the matrix of the linear system) [17]. Nevertheless, the HHL algorithm combining the phase estimation and classical inversion of eigenvalues is very popular in implementation of various algorithms of quantum computation, and it is widely applicable in quantum machine learning [11,29,30]. In particular, it is applied in the least-square linear-regression algorithms [31–33] working with large data sets, in quantum algorithms for singular-value decomposition [21,34], in algorithms for solving linear [35] and nonlinear [36] differential equations.

Another method of matrix inversion is presented in [37,38]. Both algorithms are based on the singular value decomposition and apply the function evaluation problem [21] to approximate the inverse of singular values by oddpolynomial, which requires introducing a special scale parameter whose value depends on the length of the interval including nonzero eigenvalues.

We also refer to algorithms for matrix manipulations based on the Trotterization method and the Baker-Champbell-Hausdorff formula for exponentiating matrices [39]. In [21], algebraic manipulations with matrices are implemented using unitary transformations that include the matrices as specific blocks (block-encoding model). A similar blockencoding approach was used in the algorithm of [40] to embed the inverse of the matrix of an algebraic system into the unitary transformation. In [41], an algorithm for matrix multiplication using binary encoding of matrix elements in the states of quantum systems followed by binary multiplication using Toffoli gates was proposed. Matrix multiplication over rings, including the multiplication of Boolean matrices, was studied in [42].

In our recent work [43], we presented alternative algorithms for matrix manipulations, such as sum and product of two matrices, calculation of determinant, matrix inversion, and solving linear systems, based on special unitary transformations of a quantum system. The main distinction of these algorithms from those mentioned above is the encoding of matrix elements into the pure states of specific (sub)systems as the probability amplitudes. However, the realization of those unitary operators in terms of the basic quantum operations was not explored in that study.

Later, in [44], we proposed the implementation of unitary transformations corresponding to vector inner product, matrix sum, and product using multi-qubit conditional operators (reducible to Toffoli gates) and Hadamard transformations, including the ancilla measurement for garbage removal. The depth of these algorithms increases logarithmically with the matrix dimension, or even remains independent of it (in the case of matrix sum), demonstrating the advantage of these algorithms compared to their classical counterparts.

In this paper, we propose quantum algorithms for determinant and inversion of matrix with their application to solving systems of linear equations. The principal part of these algorithms is the algorithm for computing the determinant of a square matrix. It is built on the ideas of Refs. [43,44]:

-
Encode matrix elements into the states of certain quantum subsystems through probability amplitudes in such a way that all necessary multiplications of matrix elements are performed automatically and appear in the probability amplitudes of the initial state of the whole system;
-
Use multiqubit control-SWAP and control-Z operators together with ancilla to organize proper signs of each term in the superposition state and collect them in a certain state of the considered system;
-
Use ancilla measurement to remove the garbage and present the desirable result as a pure state of a certain quantum system. Normalization of this state is defined at the stage of ancilla measurement.

We follow the above steps to propose an algorithm for calculating the determinant of a square matrix whose N rows are encoded into the pure states of N separate quantum subsystems. Notice that creating such initial states is a special problem in itself, but we do not discuss this problem here. The state of the whole system results in all possible products of N elements from different rows. One only needs to select the proper products to calculate the determinant. We propose such an algorithm and construct the quantum circuit realizing it. While developing the algorithm, our focus is on the space and depths of its specific blocks. Essentially, our algorithm is a quantum realization of the cofactor expansion of the classical algorithm, whose depth exponentially increases with matrix dimension. However, the resulting depth of our algorithm is O(N log² N) (or O(N² log N) in the worst case) with space of O(N log N) qubits. The final step of this algorithm is the one-qubit ancilla measurement which removes all the garbage. The probability of obtaining the required result of the ancilla measurement (which is 1) diminishes exponentially as the matrix dimension N increases, necessitating an exponentially larger number of algorithm evaluations. This is a central problem that we plan to investigate in future work.

It is remarkable that the minor modification of the algorithm for calculating the determinant yields an alternative quantum algorithm for matrix inversion using its definition in terms of algebraic complements. We again use the row-wise encoding of the matrix elements into the state of a quantum system so that all necessary products of matrix elements appear automatically in the superposition state. One thus only needs to properly sort these products. The depth of this algorithm is O(N² log N) (or O(N² log² N) in the worst case) and the space is O(N log N) qubits. Based on such inversion algorithm we develop an alternative algorithm for solving systems of linear algebraic equations. Thus, we do not use Trotterization methods and classical subroutine for inversion of eigenvalues. Therefore, the proposed algorithm is purely quantum in nature, and it gives an alternative avenue to the inversion algorithm considered in [9,17,28]. The estimations for the depth and space of this algorithm remain the same.

We also emphasize that, in comparison with inversion algorithms in [37,38], which approximately calculate the inverse eigenvalues, our algorithm constructs exact (up to the available accuracy of realization of quantum operations) inverse matrix without appealing to its eigenvalues which provides certain advantages of the matrix-encoding approach.

Regarding the question of algorithmic complexity, we remark that the specialized classical techniques of matrix manipulations facilitate a reduction in the depth of the algorithms for determinant calculation to O(log² N) [45,46] with the size O(N^2.496). In our study, we employ the Leibniz formula as a definition for the matrix determinant and define the inverse matrix in terms of the algebraic complements. Our quantum algorithms based on these definitions demonstrate clear advantages over their classical counterparts. It is plausible that the adaptation of specific classical algorithms for matrix operations into their quantum equivalents could yield further enhancements in the efficiency and complexity of quantum algorithms designed for calculating determinants and inverse matrices. However, this particular aspect is not addressed in the present paper. The primary contribution of our work lies in promoting the representation of matrix elements as probability amplitudes of pure states, and we elucidate the benefits of this representation in relation to standard algorithms for matrix manipulations.

The paper is organized as follows. The algorithm for calculating the matrix determinant is proposed in Section 2. This algorithm is taken as a basis for the algorithm calculating the inverse matrix presented in Section 3. Based on those results, the algorithm for solving systems of linear algebraic equations is proposed in Section 4. The main results are discussed in Section 6. The special subroutine for the controlled measurement is presented in Section 5. Appendix A contains the modified algorithms for matrix multiplication and examples of realization of the algorithms developed in this paper.

2.

Determinant

To calculate the determinant of N × N matrix Ã (we assume N = 2ⁿ) with elements aj_k(j, k = 0, 1, …, N – 1), 1 $\tilde{A} = (\begin{matrix} a_{00} & a_{01} & \dots & a_{0 (N - 1)} \\ a_{10} & a_{11} & \dots & a_{1 (N - 1)} \\ \dots & \dots & \dots & \dots \\ a_{(N - 2) 0} & a_{(N - 2) 1} & \dots & a_{(N - 2) (N - 1)} \\ a_{(N - 1) 0} & a_{(N - 1) 1} & \dots & a_{(N - 1) (N - 1)} \end{matrix}),$ we encode each row consisting of N elements into the pure state |Ψ_j〉 of the n-qubit subsystem S_j, 2 $| Ψ_{j} 〉 = \sum_{k = 0}^{N - 1} a_{j k} | k 〉_{S_{j}}, j = 0, 1, \dots, N - 1,$ where k in the state |k〉_{S_j} is the binary encoding of the integer k, therefore all states |k〉_{S_j} with fixed j are mutually orthogonal. We shall note that encoding the elements of the matrix into the probability amplitudes of a quantum state is not a simple problem, but we do not consider aspects of creating such states in this paper. Representing rows of the matrix Ã in the form of pure states (2) creates N obvious constraints for the matrix elements a_ij because of the normalization of pure states: 3 $\sum_{k = 0}^{N - 1} | a_{j k} |^{2} = 1, j = 0, \dots, N - 1.$

These constraints can be circumvented by incorporating additional terms with different probability amplitudes into the states |Ψ_i〉, but this issue will be addressed in future study. The whole system is the union of the subsystems, $S = \underset{j}{\cup} S_{j}$ , and the pure state of the whole system reads 4 $\begin{array}{l} | Φ_{0} 〉 & = | Ψ_{0} 〉 \dots | Ψ_{N - 1} 〉 \\ = \sum_{k_{0}, \dots, k_{N - 1} = 0}^{N - 1} a_{0 k_{0}} \dots a_{(N - 1) k_{N - 1}} \times {| k_{0} 〉}_{S_{0}} \dots {| k_{N - 1} 〉}_{S_{N - 1}} \end{array},$ which includes N^(S) = nN qubits. In computing the determinant, we need only those terms in which all k_j are different. We select these terms from the whole pure state of our system: 5 $| Φ_{0} 〉 = \sum_{\begin{matrix} k_{0}, \dots, k_{N - 1} = 0 \\ k_{0} \neq \dots \neq k_{N - 1} \end{matrix}}^{N - 1} a_{0 k_{0}} \dots a_{(N - 1) k_{N - 1}} \times | k_{0} 〉_{S_{0}} \dots | k_{N - 1} 〉_{S_{N - 1}} + | g_{1} 〉_{S},$ where |g₁〉_S collects all extra terms which form the garbage to be removed later. We emphasize that the selection of the needed terms in (5) is quite a formal procedure, at this stage we don’t do anything to label these terms. We will do this later by introducing the ancillae B and removing all the garbage via the ancilla measurement, see Eqs. (19), (20) and Figure 2. We have to arrange the appropriate signs for each term of the first part on the right-hand side of (5). This can be achieved by setting the subsystem S_j (in each term) into the state |j〉 using the SWAP operators together with sign-switching. This pair of operators performs permutation and changes the sign of the term.

Thus, our purpose is to exchange the states of subsystems S_j(j = 0, …, N – 1) so that the state of the subsystem S_k becomes |k〉S_k in each term of the first part of superposition state (5). For that we introduce the projectors $P_{S_{j}}^{(k)}$ , 6 $\begin{array}{l} P_{S_{j}}^{(k)} = | k 〉_{S_{j}}_{S_{j}} 〈 k |, \\ k = 0, \dots N - 2, j = k + 1, \dots N - 1, \end{array}$ and the ñ_k-qubit ancillae A_k, (ñ_k = ⌈log(N – k)⌉, k = 0, … N – 2). The ancilla A_k serves to save the index j of the subsystem S_j whose state is |k〉 with j > k. Therefore, the number of qubits ñ_k in A_k is less than n = log N unless k = 0, 1: ñ_k≤ n.

For instance, in Figure 2 for the case N = 4, there are three ancillae A₀, A₁, A₂. Ancilla A₂has to encode either only one state |2〉_S₃ or nothing, therefore one qubit is enough: we can encode |2〉_S₃ by the state |1〉_A₂ of ancilla A₂. Next, A₁ has to encode two states |1〉_S₂ and |1〉_S₂ or nothing. Two qubits are enough for that: |1〉_S₂ → |1〉_A₁, |1〉_S₃ → |2〉_A₁. Similarly, A₀ requires 2 qubits as well: |0〉_S₁ → |1〉_A₀, |0〉_S₂ → |2〉_A₀, |0〉_S₃ → |3〉_A₀. Thus, we have the map 7 $| k 〉_{S_{j}} \to | \tilde{j} 〉_{A_{k}},$ which can be realized as follows.

Using the projector $P_{S_{j}}^{(k)}$ and ancilla A_k we can prepare the operator V_{S_jA_k}, which relates the index j of S_j to the appropriate state $| \tilde{j} 〉_{A_{k}}$ of the ancilla A_k: 8 $V_{S_{j} A_{k}} = P_{S_{j}}^{(k)} \otimes Z_{k} (j) σ_{k j}^{(x)} + (I_{S_{j}} - P_{S_{j}}^{(k)}) \otimes I_{A_{k}},$ where $σ_{k j}^{(x)}$ includes the set of σ^(x)-operators which change the ground state of the ancilla A_k to the state $| \tilde{j} 〉_{A_{k}}$ , subscripts k and j are related to k and j in the map (7). For instance, to map the state |0〉_S₂ into the state |2〉_A₀ of the two-qubit ancilla A₀ we need to apply σ^(x) to the second qubits of A₀, i.e., $σ_{02}^{(x)} = I \otimes σ^{(x)}$ , where I is the identity operator applied to the first qubit of A₀; Z_k(j) changes the sign of the ancilla state $| \tilde{j} 〉_{A_{k}}$ (essentially, it counts swaps and can be represented by either the σ^(z)-operator applied to one of the excited qubits, orby the σ^(x)σ^(z)σ^(x)-operator applied to one of the ground-state qubits (only to one!) of A_k).

It is hard to derive the explicit formula for Z_k(j) in general case, but it can be simply done in any particular case. For instance, in the above example of the transformation |0〉_S₂ → |2〉_A₀ we can set Z₀ (2) = I ⊗σ^(z). Thus, the operator V_{S_jA_k} acts as follows. If the state of S_j is |k〉_{S_j}, then the state of A_k becomes $| \tilde{j} 〉_{A_{k}}$ , otherwise the state of A_k remains |0〉_{A_k}.

To arrange the exchange of states between S_j and S_k, we introduce the projectors $P_{A_{j}}^{(j)}$ , 9 $\begin{array}{l} P_{A_{k}}^{(j)} = | \tilde{j} 〉_{A_{k}}_{A_{k}} 〈 \tilde{j} |, k = 0, \dots N - 2, \\ j = k + 1, \dots N - 1, \tilde{j} = 0, \dots N - k - 2, \tilde{j} = j - k - 1, \end{array}$ and construct the operators U_{S_kS_j}: 10 $U_{S_{k} S_{j}} = (S W A P_{S_{k}, S_{j}} \otimes P_{A_{k}}^{(j)} + I_{S_{k} S_{j}} \otimes (I_{A_{k}} - P_{A_{k}}^{(j)})), k \neq j .$

Here, the operator SWAP_{S_k,S_j} swaps the states of the subsystems S_k and S_j by swapping states of appropriate qubits of these subsystems. Thus, the operator U_{S_kS_j} swaps the states of S_k and S_j if only the state of A_k is $| \tilde{j} 〉_{A_{k}}$ . Otherwise the states of the above subsystems remain unchanged.

The circuits for the operators V_{S_jA_k} and $U_{S_{k} S_{j}}^{(k)}$ are given in Figure 1a (the general matrix case) and in Figure 1b (the particular 4 × 4-matrix case).

The depth of each operator V_{S_jA_k} is O(n) (due to the projectors $P_{S_{j}}^{(k)}$ with n control qubits and we assume that all σ^(x)-operators of $σ_{k j}^{(x)}$ are applied in parallel to different qubits of A_k), while the depth of U_{S_kS_j} is the depth of the control-SWAP-operator, which includes n swaps each controlled by n qubits, i.e., the total depth is nO(n) = O(n²). Theoretically, it can be implemented with less operations but this would not change the asymptotic complexity of the circuit.

Applying the operators 11 $W_{k} = \prod_{j = k + 1}^{N - 1} U_{S_{k} S_{j}} V_{S_{j} A_{k}}, k = 0, \dots, N - 2,$ to the state |Φ₀〉|0〉_A, we put the subsystem S_k into the state |k〉_{S_k} in each term of the first part of (5). Although W_k has the product of N – k – 1 pairs of U- and V-operators, only one pair of such operators is applied to each particular term in |Φ₀〉 which is due to the structure of the projector operators $P_{S_{j}}^{(k)}$ . We assume that this means the UV-products can be applied in parallel and thus the depth of W_k is O(n) + O(n²) = O(n²). Otherwise we have to multiply the obtained depth by O(N). The operator $\prod_{k = 0}^{N - 2} W_{k}$ provides the needed sign of the probability amplitudes which will compose the expression for the determinant. To collect all of them in a single probability amplitude we apply the Hadamard transformation to each qubit of ancillae A_k, k = 0, …, N – 2, and denote this transformation H_A, i.e. 12 $H_{A} = H_{A_{0}} \dots H_{A_{N - 2'}} H_{A_{k}} = \otimes_{k = 0}^{{\tilde{n}}_{k} - 1} H .$

There are Ñ Hadamard operators in H_A,

13

\tilde{N} = \sum_{k = 0}^{N - 2} {\tilde{n}}_{k} = O (N \log N) .

Applying the operator $W_{S A}^{(1)}$ , 14 $W_{S A}^{(1)} = H_{A} \prod_{k = 0}^{N - 2} W_{k},$ to the state |Φ₀〉|0〉_A, $A = \cup_{k = 0}^{N - 2} A_{k}$ , and selecting the terms which carry the information about the determinant (these terms correspond to the ground state of A) we obtain 15 $\begin{array}{l} | Φ_{1}^{(D)} 〉 = W_{S A}^{(1)} | Φ_{0} 〉 | 0 〉_{A} \\ = \frac{\det (\tilde{A})}{2^{\tilde{N} / 2}} | 0 〉_{S_{0}} | 1 〉_{S_{1}} \dots | N - 1 〉_{S_{N - 1}} | 0 〉_{A} + | g_{2} 〉_{S A} . \end{array}$

Here we introduce the determinant det(Ã) represented by the Leibniz formula, 16 $\det (\tilde{A}) = \sum_{k_{0} \neq \dots \neq k_{N - 1}} ϵ_{k_{0} \dots k_{N - 1}} a_{k_{0} 0} \dots a_{k_{N - 1} (N - 1)},$ where ϵ_{k₀…k_N–1} is the permutation tensor: $ϵ_{k_{0} \dots k_{N - 1}} = {\begin{array}{l} {(- 1)}^{perm (k_{0} \dots k_{N - 1})}, & k_{0} \neq k_{1} \neq \dots \neq k_{N - 1} \\ 0 & otherwise \end{array} .$

The depth of W⁽¹⁾ is O(Nn²). Next, we can set states of all S_j in the first term of $| Φ_{1}^{(D)} 〉$ into the |0〉_{S_j} states. To this end we apply the σ^x-operators to the excited qubits of S, i.e. prepare the operator X_S. 17 $X_{S} = \prod_{j = 1}^{N - 1} X_{S_{j}} (j),$ with X_Sj(j) being the set of σ^(x) operators acting on the excited qubits of S_j in the state |j〉_{S_j}. The depth of X_S is O(1). Applying X_S to $| Φ_{1}^{(D)} 〉$ we obtain: 18 $\begin{array}{l} | Φ_{2}^{(D)} 〉 = X_{S} | Φ_{1}^{(D)} 〉 \\ = \frac{\det (\tilde{A})}{2^{\tilde{N} / 2}} | 0 〉_{S} | 0 〉_{A} + {| g_{3} 〉}_{S A} . \end{array}$

We note that the operator H_A in $W_{S A}^{(1)}$ and operator X_S can be applied simultaneously because they affect different qubits. We separate them to underline the distinction in their functions. Next, we remove the garbage. For that we introduce the projector P_SA = |0〉_S|0〉_{A A} 〉0|_S〉0|, include the one-qubit ancilla B in the ground state, and construct the operator $W_{S A B}^{(2)}$ , 19 $W_{S A B}^{(2)} = P_{S A} σ_{B}^{(x)} + (I_{S A} - P_{S A}) I_{B},$ whose depth is O(Nn + Nn) = O(Nn). Applying it to $| Φ_{2}^{(D)} 〉 | 0 〉_{B}$ we obtain 20 $\begin{array}{l} | Φ_{3}^{(D)} 〉 = W_{S A B}^{(2)} | Φ_{2}^{(D)} 〉 | 0 〉_{B} \\ = \frac{\det (\tilde{A})}{2^{\tilde{N} / 2}} | 0 〉_{S} | 0 〉_{A} | 1 〉_{B} + {| g_{3} 〉}_{S A} | 0 〉_{B} . \end{array}$

Now we measure the ancilla B with the output |1〉_B. The probability of this result of measurement is 2^−Ñ|det(Ã)|². After the measurement we get the following state: 21 $| Φ_{4}^{(D)} 〉 = | Ψ_{out}^{(D)} 〉 | 0 〉_{A}, | Ψ_{out}^{(D)} 〉 = \arg (\det (\tilde{A})) | 0 〉_{S},$

The particular circuit for calculating the 4 × 4 determinant using the proposed algorithm is given in Figure 2. The circuit for the determinant of N × N matrix includes N log N qubits of the subsystem S, Ñ = O(N log N) qubits of subsystem A, and one qubit of ancilla B, therefore the space of this circuit is O(N log N) qubits.

3.

Inverse Matrix

We remark here that the minor modification of the algorithm for calculating the determinant of a square N × N matrix in Section 2 allows to calculate the inverse of a square (N – 1) × (N – 1) matrix. Moreover, this modification leads to a minor increase in the depth of the algorithm which becomes O(N² log N) instead of O(N log² N) in the algorithm for calculating the determinant. These facts motivate working out the quantum inversion algorithm based on the definition of the inverse matrix in terms of algebraic complements, although quantum analogs of other algorithms of matrix inversion might be more promising.

3.1.

Preliminary Consideration

We impose a special structure on the elements in the first row and first column of the matrix Ã given in (1): 22 $a_{i 0} = q, a_{0 j} = 1 / \sqrt{N}, i, j = 0, \dots, N - 1,$ i.e., 23 $\tilde{A} = (\begin{matrix} \frac{1}{\sqrt{N}} & \frac{1}{\sqrt{N}} & \dots & \frac{1}{\sqrt{N}} \\ q & a_{11} & \dots & a_{1 (N - 1)} \\ q & a_{21} & \dots & a_{2 (N - 1)} \\ \dots & \dots & \dots & \dots \\ q & a_{(N - 1) 1} & \dots & a_{(N - 1) (N - 1)} \end{matrix}) .$

The algorithm discussed below allows to invert the (N – 1) × (N – 1) matrix A (rather than the matrix Ã itself) which is embedded into Ã, 24 $A = (\begin{matrix} a_{11} & \dots & a_{1 (N - 1)} \\ a_{21} & \dots & a_{2 (N - 1)} \\ \dots & \dots & \dots \\ a_{(N - 1) 1} & \dots & a_{(N - 1) (N - 1)} \end{matrix}) .$

According to the standard definition, the element $A_{j i}^{- 1}$ of the inverse matrix is expressed in terms of the minor M_ij obtained by removing the ith row and jth column of A: 25 $A_{j i}^{- 1} = \frac{{(- 1)}^{i + j} M_{i j}}{\det (A)} .$

From another point of view, the minor M_ij appears among the terms included in det(Ã). In fact, one of the terms in this determinant is following (remove the (i + 1)th row and 1st column from Ã; notice that (i + 1)th row contains the elements q, a_i1, a_i3, …, a_i_(N–1)): 26 $\frac{{(- 1)}^{i + 2} q}{\sqrt{N}} | \begin{matrix} 1 & \dots & 1 \\ a_{11} & \dots & a_{1 (N - 1)} \\ \dots & \dots & \dots \\ a_{(i - 1) 1} & \dots & a_{(i - 1) (N - 1)} \\ a_{(i + 1) 1} & \dots & a_{(i + 1) (N - 1)} \\ \dots & \dots & \dots \\ a_{(N - 1) 1} & \dots & a_{(N - 1) (N - 1)} \end{matrix} |,$

In turn, this term includes the following term (remove the 1st row and jth column from the determinant (26); the jth column contains the elements 1, a_1j, a_2j, …, a_(N–1)j): 27 $\begin{array}{l} - \frac{{(- 1)}^{i + j} q}{\sqrt{N}} | \begin{matrix} a_{11} & \dots & a_{1 (j - 1)} & a_{1 (j + 1)} & \dots & a_{1 (N - 1)} \\ \dots & \dots & \dots & \dots & \dots & \dots \\ a_{(i - 1) 1} & \dots & a_{(i - 1) (j - 1)} & a_{(i - 1) (j + 1)} & \dots & a_{(i - 1) (N - 1)} \\ a_{(i + 1) 1} & \dots & a_{(i + 1) (j - 1)} & a_{(i + 1) (j + 1)} & \dots & a_{(i + 1) (N - 1)} \\ \dots & \dots & \dots \\ a_{(N - 1) 1} & \dots & a_{(N - 1) (j - 1)} & a_{(N - 1) (j + 1)} & \dots & a_{(N - 1) (N - 1)} \end{matrix} | \\ = - \frac{q}{\sqrt{N}} (^{- 1) i + j} M_{i j} = - \frac{\det (A) q}{\sqrt{N}} A_{j i}^{- 1} . \end{array}$

Thus, each element $A_{j i}^{- 1}$ of the inverse matrix is included into det(Ã) up to a factor which is the same for all elements. All that remains is to extract all the terms composing the element $A_{j i}^{- 1}$ from those composing det( Ã) and encode them into the proper state of some quantum subsystem. We show that this can be simply realized.

3.2.

Basic Algorithm

The circuit for the algorithm is presented in Figure 3. According to (2), the pure state |Φ₀〉 of the whole system is given in (4) with normalization (3) and constraints (22) for the elements in the first row and first column of the matrix Ã, see (23). From this state, we select only those terms that compose the determinant of Ã and therefore contain the terms that appear in the resulting inverse matrix $A^{- 1}$ , i.e., we consider |Φ₀〉 in form (5).

However, not all terms in the first part of |Φ₀〉 are needed in our algorithm. We have to keep only those of them that include the 1st power of the factor q, (see constraints (22)), i.e., exactly one state |0〉_{S_j}, 1 ≤ j ≤ N – 1, can appear in the product |k₁〉_S₁ … |k_N–1〉_{S_N–1}. We also have to associate each of the probability amplitudes in (5) with the appropriate element $A_{j i}^{- 1}$ of the inverse matrix. To do so, we introduce two n-qubit subsystems R and C whose basis states serve to enumerate, respectively, rows and columns of the inverse matrix A⁻¹.

To select the terms that compose $A_{j i}^{- 1}$ from the superposition state we use the projector 28 $P_{i j} = | 0 〉_{S_{i}}_{S_{i}} 〈_{0 | \otimes | j 〉 S_{0}}_{S_{0}} 〈 j |, i, j = 1, \dots, N - 1.$

The idea is that this projector allows labeling the 1st and (j + 1)th (j = 0, …, N – 1) columns and the 1st and (i + 1)th (0 ≤ i ≤ N – 1) rows in the matrix Ã(23). As a result, we select those terms from the superposition state whose probability amplitudes compose M_ij.

Now we can construct the controlled operator 29 $W_{S R C}^{(i j)} = P_{i j} \otimes σ_{R^{(j)} C^{(i)}}^{(x)} + (I_{S} - P_{i j}) \otimes I_{R C} .$

This operator conditionally applies $σ_{R^{(j)} C^{(i)}}^{(x)}$ which is the product of σ^(x) (acting on the subsystems R and C) such that $σ_{R^{(j)} C^{(i)}}^{(x)} | 0 〉_{R} | 0 〉_{C} = | j 〉_{R} | i 〉_{C}$ . The depth of $W_{S R C}^{(i j)}$ is O(n). To establish it we use the fact that the controlled operator $W_{S R C}^{(i j)}$ with n-qubit controlling register can be represented in terms of Toffoli gates by a circuit of depth O(n) [47] and require that all σ^(x) operators in $σ_{R^{(j)} C^{(i)}}^{(x)}$ can be applied simultaneously. Applying the operator ${\hat{W}}_{S R C} = \prod_{i = 1}^{N - 1} \prod_{j = 1}^{N - 1} W_{S R C}^{(i j)}$ (whose depth is O(N²n)) to |Φ₀〉|0〉_R|0〉_C we obtain 30 $\begin{array}{l} | Φ_{1} 〉 = {\hat{W}}_{S R C} | Φ_{0} 〉 | 0 〉_{R} | 0 〉_{C} \\ = \frac{1}{\sqrt{N}} \sum_{i = 1}^{N - 1} \sum_{j = 1}^{N - 1} \sum_{\begin{matrix} k_{1} \dots k_{i - 1}, k_{i + 1} \dots k_{N - 1} = 0 \\ \begin{matrix} 0 \neq k_{1} \neq \dots \neq k_{i - 1} \\ \neq k_{i + 1} \neq \dots \neq k_{N - 1} \neq j \end{matrix} \end{matrix}}^{N - 1} a_{1 k_{1}} \dots a_{(i - 1) k_{i - 1}} a_{i 0} a_{(i + 1) k_{i + 1}} \dots a_{(N - 1) k_{N - 1}} \times \\ | j 〉_{S_{0}} | k_{1} 〉_{S_{1}} \dots | k_{i - 1} 〉_{S_{i - 1}} | 0 〉_{S_{i}} | k_{i + 1} 〉_{S_{i + 1}} \dots | k_{N - 1} 〉_{S_{N - 1}} | j 〉_{R} | i 〉_{C} + | g_{2} 〉_{S R C}, \end{array}$ where a_i0 = q. In the RHS of (30), the first part collects those terms of the state |Φ₁〉 that are labeled by the states |j〉_R and |i〉_C of the subsystems R and C, respectively, with j > 0 and i > 0. That is why the states of S₀ and S_i are, respectively, |j〉_S₀ and |0〉_{S_i} in the selected part of |Φ₁〉. Now we have to arrange the proper sign of each term in the first part of (30). According to Section 3.1, this can be done by calculating the determinant of Ã using the algorithm (1) proposed in Section 2. Applying the transformation $W_{S A}^{(1)}$ given in (14) to |Φ₁〉 we obtain 31 $\begin{array}{l} | Φ_{2} 〉 = W_{S A}^{(1)} | Φ_{1} 〉 | 0 〉_{A} \\ \begin{array}{l} = - \frac{q \det (A)}{2^{(\tilde{N} + n) / 2}} \sum_{i = 1}^{N - 1} \sum_{j = 1}^{N - 1} A_{j i}^{- 1} | 0 〉_{S_{0}} | 1 〉_{S_{1}} \\ \dots \otimes | N - 1 〉_{S_{N - 1}} | j 〉_{R} | i 〉_{C} | 0 〉_{A} + | g_{3} 〉_{S R C A} . \end{array} \end{array}$

Next, applying the operator $X_{S} = \prod_{j = 1}^{N - 1} X_{S_{j}} (j)$ given in (17) to |Φ₂〉 we obtain (we note that the subsystem $S = \cup_{j = 0}^{N - 1} S_{j}$ has the same number of qubits in both the algorithm of determinant calculation and the algorithm of matrix inversion, therefore we can apply the same operator X_S in both cases) 32 $\begin{array}{l} | Φ_{3} 〉 = X_{S} | Φ_{2} 〉 \\ = - \frac{q \det (A)}{2^{(\tilde{N} + n) / 2}} \sum_{i = 1}^{N - 1} \sum_{j = 1}^{N - 1} A_{j i}^{- 1} | 0 〉_{S} | j 〉_{R} | i 〉_{C} | 0 〉_{A} + | g_{4} 〉_{S R C A}, \end{array}$

Finally, applying $W_{S A B}^{(2)}$ (19) to |Φ₃〉|0〉_B we obtain 33 $\begin{array}{l} | Φ_{4} 〉 = W_{S A B}^{(2)} | Φ_{3} 〉 | 0 〉_{B} \\ = \sum_{i = 1}^{N - 1} \sum_{j = 1}^{N - 1} {\tilde{a}}_{j i} | 0 〉_{S} | j 〉_{R} | i 〉_{C} | 0 〉_{A} | 1 〉_{B} \\ + | g_{5} 〉_{S R C A} | 0 〉_{B}, \end{array}$ where 34 ${\tilde{a}}_{j i} = - \frac{q \det (A) A_{j i}^{- 1}}{2^{(\tilde{N} + n) / 2}} .$

The depth of the operator $D_{S A B} = W_{S A B}^{(2)} X_{S} W_{S A}^{(1)}$ (under certain assumptions on the physical realization of the operator W_k, see Eq. (11)) is O(Nn²) < O(N²n) (the depth of ${\hat{W}}_{S R C}$ ). After measuring the ancilla B to get the output |1〉 with the probability $\frac{q^{2} | \det (A) |^{2}}{2^{\tilde{N} + n}} G^{2} ~ 2^{- O (\tilde{N})} = 2^{- O (N n)})$ , $G = \sqrt{\sum_{i, j = 1}^{N - 1} | A_{i j}^{- 1} |^{2}}$ , we get the desired result 35 $| Φ_{5} 〉 = | Ψ_{o u t} 〉 | 0 〉_{S} | 0 〉_{A},$ where 36 $| Ψ_{o u t} 〉 = G^{- 1} \sum_{i = 1}^{N - 1} \sum_{j = 1}^{N - 1} A_{j i}^{- 1} | j 〉_{R} | i 〉_{C} = G^{- 1} | A^{- 1} 〉 .$

The state |Ψ_out〉 encodes A⁻¹ in the normalized form, i.e., 〈Ψ_out|Ψ_out〉 = 1, while the state $| A^{- 1} 〉 = \sum_{i = 1}^{N - 1} \sum_{j = 1}^{N - 1} A_{j i}^{- 1} | j 〉_{R} | i 〉_{C}$ is not normalized. The depth of the discussed algorithm for matrix inversion is determined by the operator ${\hat{W}}_{S R C}$ and equals O(N² log N). The circuit includes N log N qubits of the subsystem S, Ñ = O(N log N) qubits of the ancilla A, one qubit of the ancilla B, and 2 log N qubits of R and C, thus the space of this circuit is approximated by the space of the circuit for calculating the determinant which is O(N log N).

We note that this depth is obtained under the assumption that the depth of the operator $W_{S A}^{(1)}$ in (14) is N log² N. If this depth is N² log² N, then the depth of the matrix inversion algorithm is also N² log² N.

4.

Solving Systems of Linear Algebraic Equations

Having constructed the inverse matrix A⁻¹ encoded into the state of the subsystem R ∪ C, we obtain a tool for solving a system of linear algebraic equations represented in the matrix form, Ax = b, whose solution reads x = A⁻¹b.

Therefore, we have to apply the multiplication algorithm proposed in Ref. [44] (see also Appendix A.1, for its modified version) to the matrices A⁻¹ and b. The structure of the circuit is shown in Figure 4a. A more detailed circuit is presented in Figure 4b.

Notice that we can use the same ancillae in both blocks of this circuit (ancillae are not shown in Figure 4a). Moreover, the subsystem S encoding the matrix A can be used as ancilla in further calculations.

In this case we do not measure ancillae B (unlike Section 3.2) and thus start with the state |Φ₄〉 given in (33). The vector b is encoded as 37 $| b 〉 = \sum_{j = 0}^{N - 1} b_{j} | j 〉_{b}, b_{0} = 0, \sum_{j = 1}^{N - 1} | b_{j} |^{2} = 1.$

The zero value for b₀ is prescribed by the encoding of A⁻¹ in (36), where the 0-states of R and C are not used. Out of system S ∪ A (which forms an ancilla in Figure 4b), we take the one-qubit ancilla $\tilde{B}$ needed in the multiplication algorithm and neglect other qubits. We also apply the operator X_B = σ^(x) to invert the state of B. Thus, the state of the whole system reads 38 $\begin{array}{l} | Φ_{5}^{(L)} 〉 = X_{B} | Φ_{4} 〉 | b 〉 | 0 〉_{\tilde{B}} \\ = \sum_{i, j, l = 1}^{N - 1} {\tilde{a}}_{j l} b_{i} | j 〉_{R} | l 〉_{C} | i 〉_{b} | 0 〉_{B} | 0 〉_{\tilde{B}} + | g_{1} 〉_{R C b} | 1 〉_{B} | 0 〉_{\tilde{B}} . \end{array}$

Now we refer to the Appendix, Section A.1, where the matrix multiplication algorithm is described. Applying the result of this Appendix we identify K = N, M = 1 and replace the subsystems R₁, C₁, R₂ with R, C, b, while the subsystem C₂ is not used because the second matrix in our multiplication is just a column. Thus, $W_{C_{1} R_{2}}^{(1)}$ in (A5) becomes $W_{C b}^{(1)}$ , $W_{C_{1}}^{(2)}$ in (A7) becomes $W_{C}^{(2)}$ , while the operator $W_{C_{1} R_{2} \tilde{B}}^{(3)}$ in (A8) must be modified including the projector acting on B, i.e., the new operator reads: 39 $\begin{array}{l} P_{C B b} = | 0 〉_{C} | 0 〉_{B} | 0 〉_{b} C 〈 0 |_{B} 〈 0 | b 〈 0 |, \\ W_{C B b \tilde{B}}^{(3)} = P_{C B b} \otimes σ_{\tilde{B}}^{(x)} + (I_{C B b} - P_{C B b}) \otimes I_{\tilde{B}} . \end{array}$

Applying the operator $W_{C B b \tilde{B}}^{(3)} W_{C}^{(2)} W_{C b}^{(1)}$ to $| Φ_{5}^{(L)} 〉$ (38) we obtain 40 $\begin{array}{l} | Φ_{6}^{(L)} 〉 = W_{C B b B}^{(3)} W_{C}^{(2)} W_{C b}^{(1)} | Φ_{5}^{(L)} 〉 = \\ \frac{1}{2^{n / 2}} (\sum_{j_{1} = 1}^{N - 1} \sum_{j = 1}^{N - 1} {\tilde{a}}_{j_{1} j} b_{j} {| j_{1} 〉}_{R} | 0 〉_{C} | 0 〉_{b}) | 0 〉_{B} | 1 〉_{\hat{B}} + \\ {| g_{2} 〉}_{R C b} | 1 〉_{B} | 0 〉_{_{\tilde{B}}} . \end{array}$

Performing measurement over $\tilde{B}$ with the output $| 1 〉_{\tilde{B}}$ we remove garbage and obtain 41 $\begin{array}{l} | Φ_{7}^{(L)} 〉 = | Ψ_{out}^{(L)} 〉 | 0 〉_{C} | 0 〉_{b} | 0 〉_{B}, \\ | Ψ_{out}^{(L)} 〉 = G^{- 1} \sum_{j_{1} = 1}^{N - 1} \sum_{j = 1}^{N - 1} A_{j_{1} j}^{- 1} b_{j} {| j_{1} 〉}_{R} = G^{- 1} | x 〉_{R}, \end{array}$ where $| x 〉_{R} = \sum_{j = 1}^{N - 1} A_{j_{1} j}^{- 1} b_{j} | j_{1} 〉_{R}$ is an unnormalized vector, the normalization $G = (^{\sum_{i} | x_{i} |^{2}) 1 / 2}$ , $x_{i} = \sum_{j = 1}^{(N - 1)} A_{i j}^{- 1} b_{j}$ , is known from the probability of the above measurement which equals (qGdet(A))²/2^Ñ+2n due to the expression (34) for ${\tilde{a}}_{j l}$ . Thus, the probability is ∼ 1/2^Ñ+2n = 2^−O(Nn). We note that, although we use two algorithms (matrix inversion and matrix multiplication), only one measurement is performed to remove all the garbage. The result is stored in the register R. The depth of the whole algorithm is defined by the depth of the subroutine inverting A and thus equals O(N²n). In comparison with the circuit for inverse matrix, the circuit in Figure 4b includes log N qubits encoding the column b and thus the space remains essentially O(N log N).

5.

Controlled Measurement

In all algorithms presented above the weak point is the small probability of success in the measurement of the ancilla state. In fact, this probability is ∼ 2^{−O(N log N)} in all cases, in other words, it exponentially decreases with an increase in the dimensionality N of the matrix Ã (1). To smooth this effect we suggest to replace the usual ancilla measurement by the controlled measurement [48], which can be presented as a special subroutine.

We call B the one-qubit ancilla whose state we have to measure and write the state of the whole system as 42 $| χ_{0} 〉 = G^{- 1} (| E 〉 | 1 〉_{B} + | F 〉 | 0 〉), 〈 E | F 〉 = 0,$ where only the state |E〉 contains the useful information, $G = \sqrt{〈 E | E 〉 + 〈 F | F 〉}$ is the normalization, and the states |E〉 and |F〉 are not normalized. First, before measurement, we double the state of ancilla adding one more one-qubit ancilla $\tilde{B}$ in the ground state and apply the C-NOT $C N O T_{B \tilde{B}} = | 1 〉_{B B} {〈 1 | \otimes σ_{\tilde{B}}^{(x)} + | 0 〉}_{B B} 〈 0 | \otimes I_{\tilde{B}}$ , where $σ_{B}^{(x)}$ and $I_{\tilde{B}}$ are, respectively, σ^(x) and the identity operator applied to the ancilla $\tilde{B}$ . We have 43 $\begin{array}{l} | χ_{1} 〉 = C N O T_{B \tilde{B}} | χ_{0} 〉 | 0 〉_{\tilde{B}} = \\ G (| E 〉 | 1 〉_{B} | 1 〉_{\tilde{B}} + | F 〉 | 0 〉_{B} | 0 〉_{\tilde{B}}) . \end{array}$

Now we introduce the controlled measurement 44 $M_{B \tilde{B}} = | 1 〉_{B B} {〈 1 | \otimes M_{\tilde{B}} + | 0 〉}_{B B} 〈 0 | \otimes I_{\tilde{B}},$ where $M_{\tilde{B}}$ is the measurement operator applied to $\tilde{B}$ . Applying the operator $M_{B \tilde{B}}$ to |X₁〉 we have $| χ_{2} 〉 = M_{B \tilde{B}} | χ_{1} 〉 = | Ψ_{o u t} 〉 | 1 〉_{B}, | Ψ_{o u t} 〉 = (^{〈 E | E 〉) - 1 / 2} | E 〉 .$

In this way we avoid necessity of performing multiple runs of the algorithm to get the needed result of the ancilla measurement. However, we also lose the possibility to define the normalization (〈E|E〉)^1/2, which might be important information. For instance, in the algorithm for determinant calculation this normalization equals the absolute value of the matrix determinant, which is the half of useful information (another half is the phase). But in the other two algorithms this normalization doesn’t include the principal information. So, getting information about that normalization is the problem to be resolved. Another problem is the practical realization of the above controlled measurement that is also beyond the scope of this paper. The circuit for the subroutine of controlled measurement is shown in Figure 5.

6.

Conclusions

We propose two quantum algorithms for matrix manipulation, which are calculating the determinant and matrix inversion. Both are based on special row-wise encoding of the matrix elements in the pure states of quantum subsystems.

The algorithm for computing the determinant of a square matrix is discussed in detail. It uses multiqubit control-SWAP and control-Z operations. The depth of this algorithm is O(N log² N). This algorithm utilized the subroutine realizing the completely antisymmetric tensor ε (operator $W_{S A}^{(1)}$ ) that may have relevance in other algorithms. The outcome of this algorithm is split into two components: the absolute value of the determinant of the matrix A, denoted as |det(A)|, and the argument of the determinant of the matrix A, denoted as arg(det(A)). The first part is obtained from the measurement of an ancilla (although the probability of the needed outcome in such measurement decreases exponentially with N), while the argument of the determinant remains embedded in the probability amplitude of the output state $| Ψ_{o u t}^{(D)} 〉$ . The size of the subsystem S encoding the matrix A is N log N, the size of ancillae A_k, k = 0, …, N – 2, is Ñ = O(N log N). Both these sizes serve to estimate the space of the whole algorithm which is O(N log N) qubits.

It is remarkable that the (N – 1) × (N – 1)-matrix inversion algorithm is essentially the algorithm for calculating the determinant of the N × N matrix obtained by replacing the first row by the row of $1 / \sqrt{N}$ and the first column by the column of q’s (up to the diagonal element). This special encoding provides the superposition of all products of matrix elements which are necessary for calculating minors included into the definition of the inverse matrix. The algorithm distributes these products with proper signs among the appropriate inverse-matrix elements which are encoded into the quantum state of certain subsystem thus forming the output state. The depth of the circuit is O(N² log N).

As an application of inversion we develop the algorithm for solving systems of linear algebraic equations. This algorithm consists of two blocks: matrix inversion and matrix multiplication. At that, the matrix inversion is the most resource-consuming block which finally determines the depth of the algorithm (which is O(N² log N)), and probability of the required ancilla state after measurement, ∼ 2^{−O(N log N)}. We have to note that the depths of the algorithms for calculating the determinant and matrix inverse were obtained under the assumption that the U-, V- operators in (11) can be applied in parallel. Otherwise we have to change the depths O(N log² N) and O(N² log N) to O(N² log ²N) in both cases.

We emphasize that the matrix-multiplication algorithm is modified in comparison with that proposed in [44]. The detailed description of the modified version is presented in Appendix, Section A.1.

One notable aspect is the use of ancillae to gather all the garbage generated during the calculation, which can then be discarded with a measurement of a one-qubit ancilla. The weak point of algorithms is the probability of obtaining the required state of ancilla after measuring. This probability is ∼ 2^{−O(N log N)} in all three algorithms.

Combining the algorithm of matrix inversion with the algorithm of matrix multiplication we demonstrate the usage of two types of matrix encoding into the state of a quantum system. The first one is the row-wise encoding used in the input of both algorithm for calculating the determinant of the N × N matrix and matrix inversion algorithm (for simplicity, we assume that N = 2ⁿ). It requires N subsystems of log N qubits each, and the state of ith subsystem encodes the elements of the ith row of the matrix. The result of matrix inversion is stored in the two subsystems of log N qubits each. These subsystems enumerate rows and columns, respectively. This form of encoding of the inverse matrix allows to perform its multiplication with column b properly encoded in the state of log N-qubit subsystem to obtain the solution x of the linear system. This solution is a column whose elements are encoded into the state of a log N-qubit subsystem R.

Quantum Algorithms for Calculating Determinant and Inverse of Matrix and Solving Linear Algebraic Systems

Full Article

Paradigm

My account