Quantum Algorithms for Matrix Operations of Row Addition, Row Swapping, Trace Calculation and Transpose

Yu-Hang Liu; Yuan-Hong Tao; Jing-Run Lan; Shao-Ming Fei

doi:10.2478/qic-2025-0031

Full Article

1.

Introduction

Quantum computations offer exponential speedups over their classical counterparts by leveraging the principles of quantum mechanics. In 1980 Benioff and Manin [1] proposed the concept of quantum computing, and Feynman [2] introduced the theoretical framework of a quantum computer in 1982. In 1985 Deutsch [3] proposed the quantum parallel algorithm, showcasing the significant computational advantages of quantum computing over classical methods.

In 1994 Shor [4,5] presented a quantum algorithm for prime factorization, drawing widespread attention to the advantages of quantum computing in solving certain problems. Grover [6] followed in 1996 with a quantum search algorithm, further demonstrating quantum computing’s potential in data search applications. In 2009 the HHL algorithm [7,8] was developed for solving linear systems of equations, greatly advancing the quantum algorithm researches. Several renowned quantum operations, such as quantum Fourier transform [9–11] and quantum phase estimation [11,12], have significantly contributed to the field.

Matrix operations serve as the core computational power support for quantum algorithms. The efficient quantum implementation of its basic operations (including row transformation, transposition, and trace calculation, etc.) holds significant theoretical and practical value. In quantum chemistry simulations [13], the elementary row transformation of matrices can rapidly simplify the Hamiltonian matrix, reducing the time complexity of solving molecular energy spectra from the polynomial level of classical algorithms to the logarithmic level. Matrix Transpose operation enables the efficient analysis of molecular symmetry, while the calculation of the matrix trace can directly yield key physical quantities such as the number of electrons. In quantum cryptography [14], elementary row transformation can optimize the encoding of quantum states to enhance security. Matrix Transpose can achieve efficient information routing in quantum communication networks, and the matrix trace can be used for the integrity detection of quantum states. In the field of quantum machine learning [15], elementary row transformation can accelerate the feature extraction of Quantum Support Vector Machines (QSVMs). Matrix Transpose can improve the backpropagation efficiency of quantum neural networks, and the matrix trace operation can quickly calculate kernel functions to evaluate model performance. Given the wide-ranging influence of matrix operations in interdisciplinary fields, exploring efficient quantum computing methods to solve matrix-related algebraic problems has become a current research hotspot.

In recent years, researchers have proposed several quantum algorithms for matrix operations. For example, the Trotter approximation formula [16] has been utilized to simulate quantum circuits, addressing complex operations such as matrix addition, multiplication and Kronecker products. Quantum algorithms for computing vector inner products [17–22] have also been developed. These algorithms leverage the superposition and entanglement of qubits and have potential applications in fields like machine learning and data processing. Based on a “sender-receiver” quantum computing model, in 2022 Wen-Tao Qi et al. [19] proposed a class of quantum algorithms for matrix operations, including matrix-vector multiplication, matrix-matrix multiplication, matrix addition, determinant computation and matrix inversion. In 2023 A.I. Zenchuk et al. [20] further developed the idea of using specific types of unitary transformations to implement linear algebra protocols according to multi-qubit Toffoli gates and the simplest single-qubit operations. Auxiliary measurements were employed to remove redundant information and extract desired results. Building on this work, in 2024 they [21] also introduced a method to encode the N rows of a matrix into pure states of N independent quantum subsystems. By selecting appropriate unitary operators, the determinant can be computed efficiently. Based on this, they [22] proposed a variational quantum singular value decomposition method based on matrix encoding, which reduced the number of measurements through controlled measurement. Furthermore, in 2025 they [23] discussed the method of encording unnormalized matrices, and the system encoding the matrix was extended adding one more probability amplitude that satisfy the normalization condition.

However, these quantum algorithms for basic matrix operations still face challenges such as high computational complexity and low success probabilities, which limit their broader applicability.

The elementary row transformations of matrices play significant roles in solving linear systems of equations, determining matrix rank, finding invertible matrices and simplifying determinant computations, with wide-ranging value in both theoretical research and practical applications. In quantum computing, elementary row transformations can simplify matrices for efficient linear equation solving, provide theoretical support for matrix decomposition, advance large-scale matrix operations, and help to interpret the geometric meanings of linear transformations. These contributions offer new insights into the designs of quantum algorithms. Currently, there are no specialized quantum algorithms specifically designed for elementary row transformations of matrices.

Drawing on the foundational ideas from [20], this paper proposes algorithms for two elementary row transformations of matrices, transpose and trace of matrices, along with their corresponding quantum circuits. These algorithms collectively involve the following key steps:

Construction of the initial state: matrix elements are first encoded into the probability amplitudes of quantum pure states by using tensor product operations.
Information separation and labeling: combining multi-qubit control operators with ancillary states, where the ancillary states are used to accurately label the useful and redundant parts of the information, achieving effective separation of the data.
State swaping operations: depending on the specific algorithms, C-SWAP operations are flexibly employed to precisely exchange the states of two quantum bits.
State superposition processing: Hadamard operators are applied to induce superposition states among quantum bits.
Measurement on the ancillary states: auxiliary measurement techniques are used to eliminate redundant information, ensuring that the desired results are accurately reflected in the probability amplitudes of the final state.

This paper focuses on the core algorithm layer of quantum computers and aims to design a set of quantum circuit schemes for implementing basic matrix operations. The research is carried out under the following premise: the input state, which is the quantum state encoding matrix elements, is successfully prepared. On this basis, we systematically construct a quantum circuit architecture capable of performing basic matrix operations such as row transformation transposition, and trace calculation.

This approach is of great value in the current development of quantum computing. On the one hand, quantum state preparation and quantum state measurement, as crucial aspects in quantum computing, have attracted much attention on conducting specialized studies. Transforming classical matrices into quantum pure states is a fundamental issue that needs to be addressed in the field of quantum state preparation. Moreover, converting the results of quantum state measurements into classical data interpretable by humans makes quantum readout the core part of quantum state measurement research. On the other hand, the algorithm designed in this paper fully considers the compatibility with quantum state preparation and quantum state measurement schemes, laying a solid foundation for the rapid deployment and application of quantum computers after they become practically implementable in the future.

The remainder of this paper is organized as follows: Section 2 introduces quantum algorithms for two types of elementary matrix transformations. Section 3 presents quantum algorithms for computing the trace and the transposition of a matrix. Conclusion is given in section 2.

2.

Two Types of Elementary Row Transformations

This section presents quantum algorithms for two types of elementary row transformations of an N × M matrix A = {a_ij} (N = 2ⁿ, M = 2^m), including adding one row to another and swapping two rows.

2.1.

Adding One Row of a Matrix to Another Row

For the quantum algorithm that adds one row of a matrix to another, the quantum circuit diagram is shown in Figure 1. This algorithm requires two pure states and four auxiliary states, and is divided into seven steps.

The following steps give rise to the algorithm of adding the (k + 1)th row of a matrix A to the (l + 1)th row with 0 ≤ l, k ≤ N – 1.

Step 1: Prepare the initial state

First, introduce an n-qubits register R₁ and an m-qubit register C₁, which are used to enumerate the rows and columns of matrix A, respectively. The entries a_ij of the matrix A are then encoded into a pure state as follows, $| Ψ_{1} 〉 = \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}}, \sum_{i j} | a_{i j} |^{2} = 1,$ \left| {{{\rm{\Psi }}_1}} \right\rangle = \sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}} } {\left| j \right\rangle _{{C_1}}},\;\;\sum\limits_{ij} {|{a_{ij}}{|^2} = 1,} where |i〉 is the binary representation of i.

Next, introduce an N-dimensional auxiliary column vector Z (with the elements of the k + 1 and the l + 1 rows being $\frac{1}{\sqrt{2}}$ {1 \over {\sqrt 2 }}, and all other elements being 0), along with an n-qubit register R₂. The elements of Z are then encoded into pure states as follows, $| Ψ_{2} 〉 = \frac{1}{\sqrt{2}} ({| k 〉}_{R_{2}} + {| l 〉}_{R_{2}}) .$ \left| {{{\rm{\Psi }}_2}} \right\rangle = {1 \over {\sqrt 2 }}\left( {{{\left| k \right\rangle }_{{R_2}}} + {{\left| l \right\rangle }_{{R_2}}}} \right).

The initial state of the entire system is then given by 1 $\begin{array}{l} | Φ_{0} 〉 & = & | Ψ_{1} 〉 \otimes | Ψ_{2} 〉 \\ = & \frac{1}{\sqrt{2}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} \\ + \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}}) . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_0}} \right\rangle } \hfill & = \hfill & {\left| {{{\rm{\Psi }}_1}} \right\rangle \otimes \left| {{{\rm{\Psi }}_2}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 2 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \left. {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}} } } \right).} \hfill \cr }

Step 2: Label the two states of R₂

In order to accurately separate the useful and useless information terms in |Φ₀〉 for subsequent calculations, we need to label the two states of R₂ in |Φ₀〉 accordingly.

Introduce a 1-qubit auxiliary B₁ in state |0〉_B₁, and the following control operator, $W_{R_{2} B_{1}}^{(1)} = P_{R_{2}} \otimes σ_{B_{1}}^{(x)} + (I_{R_{2}} - P_{R_{2}}) \otimes I_{B_{1}},$ W_{{R_2}{B_1}}^{(1)} = {P_{{R_2}}} \otimes \sigma _{{B_1}}^{(x)} + ({I_{{R_2}}} - {P_{{R_2}}}) \otimes {I_{{B_1}}}, where P_R₂ = |k〉_R₂_R₂〈k| is a projection operator, $σ_{B_{1}}^{(x)}$ \sigma _{{B_1}}^{(x)} is the standard Pauli matrix, and I_B₁ is the identity operator acting on B₁. Applying the operator $W_{R_{2} B_{1}}^{(1)}$ W_{{R_2}{B_1}}^{(1)} to |Φ₀〉|0〉_B₁, we get 2 $\begin{array}{l} | Φ_{1} 〉 & = & W_{R_{2} B_{1}}^{(1)} | Φ_{0} 〉 \otimes {| 0 〉}_{B_{1}} \\ = & \frac{1}{\sqrt{2}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| 1 〉}_{B_{1}} \\ + \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| 0 〉}_{B_{1}}) . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_0}} \right\rangle } \hfill & = \hfill & {W_{{R_2}{B_1}}^{(1)}\left| {{{\rm{\Phi }}_0}} \right\rangle \otimes {{\left| 0 \right\rangle }_{{B_1}}}} \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 2 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| 1 \right\rangle }_{{B_1}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \left. {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| 0 \right\rangle }_{{B_1}}}} } } \right).} \hfill \cr }

That is, for the term where the state of R₂ is |k〉_R₂, it is labeled by |1〉_B₁, and for the term where the state of R₂ is |l〉_R₂, it is labeled by |0〉_B₁.

Kitaev A. Y. et al. [24] represented an important result: A control operator with n control qubits can be represented by O(n) Toffoli gates. Since the above control operator $W_{R_{2} B_{1}}^{(1)}$ W_{{R_2}{B_1}}^{(1)} has an n-qubit control register, it can be expressed by using O(n) Toffoli gates. Therefore, the circuit complexity for computing |Φ₁〉 is O(n) = O(log N).

Step 3: Separate the useful information from the redundant information

To precisely extract the element located at the (k + 1)th row of the second term in |Φ₁〉, from the terms in |Φ₁〉 labeled by |0〉_B₁ we only extract the terms where R₁ is in the state |k〉_R₁. To do so, we introduce a 1-qubit auxiliary B₂ in the state |0〉_B₂, and the following control operator, $W_{R_{1} B_{1} B_{2}}^{(2)} = P_{R_{1} B_{1}} \otimes σ_{B_{2}}^{(x)} + (I_{R_{1} B_{1}} - P_{R_{1} B_{1}}) \otimes I_{B_{2}},$ W_{{R_1}{B_1}{B_2}}^{(2)} = {P_{{R_1}{B_1}}} \otimes \sigma _{{B_2}}^{(x)} + ({I_{{R_1}{B_1}}} - {P_{{R_1}{B_1}}}) \otimes {I_{{B_2}}}, where P_R₁B₁ = |k〉_R₁ |0〉_{B₁ R₁}〈k|_B₁ 〈0| is a projection operator.

Applying the operator $W_{R_{1} B_{1} B_{2}}^{(2)}$ W_{{R_1}{B_1}{B_2}}^{(2)} to |Φ₁〉|0〉_B₂, we obtain 3 $\begin{array}{l} | Φ_{2} 〉 & = & W_{R_{1} B_{1} B_{2}}^{(2)} | Φ_{1} 〉 \otimes | 0 〉_{B_{2}} \\ = & \frac{1}{\sqrt{2}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} | i 〉_{R_{1}} | j 〉_{C_{1}} | k 〉_{R_{2}} | 1 〉_{B_{1}} | 0 〉_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{k j} | k 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | 0 〉_{B_{1}} | 1 〉_{B_{2}}) \\ + | g_{1} 〉 R_{1} C_{1} R_{2} | 0 〉_{B_{1}} | 0 〉_{B_{2}} . \end{array}$ \matrix{ {|{\Phi _2}\rangle } \hfill & = \hfill & {W_{{R_1}{B_1}{B_2}}^{(2)}|{\Phi _1}\rangle \otimes |0{\rangle _{{B_2}}}} \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 2 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}} } |i{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|k{\rangle _{{R_2}}}|1{\rangle _{{B_1}}}|0{\rangle _{{B_2}}}} \right.} \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {{a_{kj}}} |k{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|0{\rangle _{{B_1}}}|1{\rangle _{{B_2}}}} \right)} \hfill \cr {} \hfill & {} \hfill & { + |{g_1}\rangle {R_1}{C_1}{R_2}|0{\rangle _{{B_1}}}|0{\rangle _{{B_2}}}.} \hfill \cr }

The control operator $W_{R_{1} B_{1} B_{2}}^{(2)}$ W_{{R_1}{B_1}{B_2}}^{(2)} has n + 1 control qubits, so it can be represented in terms of O(n) Toffoli gates and the circuit complexity for computing |Φ₂〉 is O(n) = O(log N).

Step 4: Use C-SWAP gate to exchange the states of R₁ and R₂ marked by |1〉_B₂

To add the (k + 1)th row to the (l + 1)th row, we apply a C-SWAP gate operation to the terms in |Φ₂〉 labeled by |1〉_B₂, which swaps the states of R₁ and R₂. This operation is given by the following gate, $W_{R_{1} R_{2} B_{2}}^{(3)} = S W A P_{R_{1}, R_{2}} \otimes {| 1 〉}_{B_{2} B_{2}} 〈 1 | + I_{R_{1} R_{2}} \otimes {| 0 〉}_{B_{2} B_{2}} 〈 0 | .$ W_{{R_1}{R_2}{B_2}}^{(3)} = SWA{P_{{R_1},{R_2}}} \otimes {\left| 1 \right\rangle _{{B_2}\;{B_2}}}\left\langle 1 \right| + {I_{{R_1}{R_2}}} \otimes {\left| 0 \right\rangle _{{B_2}\;{B_2}}}\left\langle 0 \right|.

Applying $W_{R_{1} R_{2} B_{2}}^{(3)}$ W_{{R_1}{R_2}{B_2}}^{(3)} to |Φ₂〉 we obtain 4 $\begin{array}{l} | Φ_{3} 〉 & = & W_{R_{1} R_{2} B_{2}}^{(3)} | Φ_{2} 〉 \\ = & \frac{1}{\sqrt{2}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| 1 〉}_{B_{1}} {| 0 〉}_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{k j} {| l 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| 0 〉}_{B_{1}} {| 1 〉}_{B_{2}}) \\ + | g_{1} 〉 R_{1} C_{1} R_{2} {| 0 〉}_{B_{1}} {| 0 〉}_{B_{2}} . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_3}} \right\rangle } \hfill & = \hfill & {W_{{R_1}{R_2}{B_2}}^{(3)}\left| {{{\rm{\Phi }}_2}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 2 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| 1 \right\rangle }_{{B_1}}}{{\left| 0 \right\rangle }_{{B_2}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \left. {\sum\limits_{j = 0}^{M - 1} {{a_{kj}}{{\left| l \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| 0 \right\rangle }_{{B_1}}}{{\left| 1 \right\rangle }_{{B_2}}}} } \right)} \hfill \cr {} \hfill & {} \hfill & { + \left| {{g_1}} \right\rangle {R_1}{C_1}{R_2}{{\left| 0 \right\rangle }_{{B_1}}}{{\left| 0 \right\rangle }_{{B_2}}}.} \hfill \cr }

Note that the SWAPs in the control operator $W_{R_{1} R_{2} B_{2}}^{(3)}$ W_{{R_1}{R_2}{B_2}}^{(3)} have common single control qubit and are related to different pairs of qubits. Therefore, they can be applied simultaneously.

Step 5: Label the useful and redundant information

To effectively avoid mixing useful and useless information terms in the subsequent computation process, we introduce an auxiliary qubit B₃ in state |0〉_B₃, together with the projection operator P_B₁B₂ = |00〉_{B₁ B₂ B₁B₂}〈00|. We use B₃ to label the useful and useless information terms in |Φ₃〉 accordingly by using the following control operator, $W_{B_{1} B_{2} B_{3}}^{(4)} = P_{B_{1} B_{2}} \otimes σ_{B_{3}}^{(x)} + (I_{B_{1} B_{2}} - P_{B_{1} B_{2}}) \otimes I_{B_{3}} .$ W_{{B_1}{B_2}{B_3}}^{(4)} = {P_{{B_1}{B_2}}} \otimes \sigma _{{B_3}}^{(x)} + ({I_{{B_1}{B_2}}} - {P_{{B_1}{B_2}}}) \otimes {I_{{B_3}}}.

Applying $W_{B_{1} B_{2} B_{3}}^{(4)}$ W_{{B_1}{B_2}{B_3}}^{(4)} to |Φ₃〉|0〉_B₃ we obtain 5 $\begin{array}{l} | Φ_{4} 〉 & = & W_{B_{1} B_{2} B_{3}}^{(4)} | Φ_{3} 〉 {| 0 〉}_{B_{3}} \\ = & \frac{1}{\sqrt{2}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| 1 〉}_{B_{1}} {| 0 〉}_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{k j} {| l 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| 0 〉}_{B_{1}} {| 1 〉}_{B_{2}}) {| 0 〉}_{B_{3}} \\ + | g_{1} 〉 R_{1} C_{1} R_{2} B_{1} B_{2} {| 1 〉}_{B 3} . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_4}} \right\rangle } \hfill & = \hfill & {W_{{B_1}{B_2}{B_3}}^{(4)}\left| {{{\rm{\Phi }}_3}} \right\rangle {{\left| 0 \right\rangle }_{{B_3}}}} \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 2 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| 1 \right\rangle }_{{B_1}}}{{\left| 0 \right\rangle }_{{B_2}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \left. {\sum\limits_{j = 0}^{M - 1} {{a_{kj}}{{\left| l \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| 0 \right\rangle }_{{B_1}}}{{\left| 1 \right\rangle }_{{B_2}}}} } \right){{\left| 0 \right\rangle }_{{B_3}}}} \hfill \cr {} \hfill & {} \hfill & { + \left| {{g_1}} \right\rangle {R_1}{C_1}{R_2}{B_1}{B_2}{{\left| 1 \right\rangle }_{B3}}.} \hfill \cr }

In this way, |0〉_B₃ (|1〉_B₃) labels the useful (useless) information terms.

Since the control operator $W_{B_{1} B_{2} B_{3}}^{(4)}$ W_{{B_1}{B_2}{B_3}}^{(4)} has two control qubit, its computational complexity is O(1).

Step 6: Use a Hadamard gate for information superposition

Applying the Hadamard operator $W_{B_{1} B_{2}}^{(5)} = H^{\otimes 2}$ W_{{B_1}{B_2}}^{(5)} = {H^{ \otimes 2}} to B₁ and B₂, we obtain 6 $\begin{array}{l} | Φ_{5} 〉 & = & W_{B_{1} B_{2}}^{(5)} | Φ_{4} 〉 \\ = & \frac{1}{{(\sqrt{2})}^{3}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} \\ + \sum_{j = 0}^{M - 1} a_{k j} {| l 〉}_{R_{1}} {| j 〉}_{C_{1}}) {| k 〉}_{R_{2}} {| 0 〉}_{B_{1}} {| 0 〉}_{B_{2}} {| 0 〉}_{B_{3}} \\ + | g_{2} 〉 R_{1} C_{1} R_{2} B_{1} B_{2} B_{3} . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_5}} \right\rangle } \hfill & = \hfill & {W_{{B_1}{B_2}}^{(5)}\left| {{{\rm{\Phi }}_4}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {{{\left( {\sqrt 2 } \right)}^3}}}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \left. {\sum\limits_{j = 0}^{M - 1} {{a_{kj}}{{\left| l \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}} } \right){{\left| k \right\rangle }_{{R_2}}}{{\left| 0 \right\rangle }_{{B_1}}}{{\left| 0 \right\rangle }_{{B_2}}}{{\left| 0 \right\rangle }_{{B_3}}}} \hfill \cr {} \hfill & {} \hfill & { + \left| {{g_1}} \right\rangle {R_1}{C_1}{R_2}{B_1}{B_2}{{\left| 1 \right\rangle }_{B3}}.} \hfill \cr }

Here, the terms in the state |0〉_B₁|0〉_B₂|0〉_B₃ are retained, which contain all the information required for further process. The remaining terms are represented as |g₂〉_{R₁C₁R₂B₁B₂B₃}.

Since only two Hadamard gates are used here, the circuit complexity is O(1).

Step 7: Measure the auxiliary state B₁B₂B₃ using |000〉_B₁B₂B₃

By measuring the auxiliary B₁B₂B₃ in the state |000〉_B₁B₂B₃, we get 7 $| Φ_{6} 〉 = | Ψ_{o u t} 〉 {| k 〉}_{R_{2}},$ \left| {{{\rm{\Phi }}_6}} \right\rangle = \left| {{{\rm{\Psi }}_{out}}} \right\rangle {\left| k \right\rangle _{{R_2}}}, where 8 $\begin{array}{l} | Ψ_{o u t} 〉 & = & \frac{1}{G} (\sum_{i \neq l} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} \\ + \sum_{j = 0}^{M - 1} (a_{l j} + a_{k j}) {| l 〉}_{R_{1}} {| j 〉}_{C_{1}}) \end{array}$ \matrix{ {\left| {{{\rm{\Psi }}_{out}}} \right\rangle } \hfill & = \hfill & {{1 \over G}\left( {\sum\nolimits_{i \ne l} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {({a_{lj}} + {a_{kj}}){{\left| l \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}} } \right)} \hfill \cr } with the normalization $G = {(\sum_{i \neq l} \sum_{j} {| a_{i j} |}^{2} + \sum_{j} {| a_{k j} + a_{l j} |}^{2})}^{1 / 2} .$ G = {\left( {\sum\limits_{i \ne l} {\sum\limits_j {{{\left| {{a_{ij}}} \right|}^2} + \sum\limits_j {{{\left| {{a_{kj}} + {a_{lj}}} \right|}^2}} } } } \right)^{1/2}}.

The success probability is $\frac{G^{2}}{8}$ {{{G^2}} \over 8}. This probability clearly depends only on the matrix elements a_ij and is independent of the matrix dimension.

The overall computational complexity of the algorithm is O(n), mainly determined by $W_{R_{2} B_{1}}^{(1)}$ W_{{R_2}{B_1}}^{(1)} and $W_{R_{1} B_{1} B_{2}}^{(2)}$ W_{{R_2}{B_1}{B_2}}^{(2)}.

2.2

Swapping Two Rows of a Matrix

For the quantum algorithm that swaps two rows of a matrix, the quantum circuit diagram is shown in Figure 2. The algorithm requires two pure states and four auxiliaries, and is divided into seven steps to swap the (k + 1)th and (l + 1)th rows of matrix A (0 ≤ l, k ≤ N – 1).

Step 1: Prepare the initial state

First, introduce an n-qubit register R₁ and an m-qubit register C₁, which enumerate the rows and columns of the matrix A, respectively. The elements of the matrix A are then encoded into the following pure state, $| Ψ_{1} 〉 = \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}}, \sum_{i j} | a_{i j} |^{2} = 1,$ \left| {{{\rm{\Psi }}_1}} \right\rangle = \sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}},\;\;\sum\limits_{ij} {|{a_{ij}}{|^2} = 1,} } }

Next, introduce an N × N auxiliary matrix Z such that the elements in the (l + 1)-th row and (k + 1)-th column, the (k + 1)-th row and (k + 1)-th column, and the (l + 1)-th row and (l + 1)-th column are $\frac{1}{\sqrt{3}}$ {1 \over {\sqrt 3 }}, the rest elements are 0; along with two n-qubit registers R₂ and C₂. The elements of Z are then encoded into the following pure state, $| Ψ_{2} 〉 = \frac{1}{\sqrt{3}} ({| l 〉}_{R_{2}} {| k 〉}_{C_{2}} + {| k 〉}_{R_{2}} {| k 〉}_{C_{2}} + {| l 〉}_{R_{2}} {| l 〉}_{C_{2}}) .$ \left| {{{\rm{\Psi }}_2}} \right\rangle = {1 \over {\sqrt 3 }}\left( {{{\left| l \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}} + {{\left| k \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}} + {{\left| l \right\rangle }_{{R_2}}}{{\left| l \right\rangle }_{{C_2}}}} \right).

The initial state is of the form, 9 $\begin{array}{l} | Φ_{0} 〉 & = & | Ψ_{1} 〉 \otimes | Ψ_{2} 〉 \\ = & \frac{1}{\sqrt{3}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| k 〉}_{C_{2}} \\ + \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| k 〉}_{C_{2}} \\ + \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| l 〉}_{C_{2}}) . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_0}} \right\rangle } \hfill & = \hfill & {\left| {{{\rm{\Psi }}_1}} \right\rangle \otimes \left| {{{\rm{\Psi }}_2}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 3 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}}} } } \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| l \right\rangle }_{{C_2}}}} } } \right).} \hfill \cr }

Step 2: Label the distinct states of R₂ and C₂

To accurately separate the useful from the useless information terms in |Φ₀〉, introduce an auxiliary qubit B₁ in state |0〉_B₁, and the following control operator, $W_{R_{2} C_{2} B_{1}}^{(1)} = P_{R_{2} C_{2}} \otimes σ_{B_{1}}^{(x)} + (I_{R_{2} C_{2}} - P_{R_{2} C_{2}}) \otimes I_{B_{1}},$ W_{{R_2}{C_2}{B_1}}^{(1)} = {P_{{R_2}{C_2}}} \otimes \sigma _{{B_1}}^{(x)} + ({I_{{R_2}{C_2}}} - {P_{{R_2}{C_2}}}) \otimes {I_{{B_1}}}, where P_R₂C₂ = |l〉_R₂|k〉_C₂R₂〈l|_C₂〈k| is the projection operator. Applying $W_{R_{2} C_{2} B_{1}}^{(1)}$ W_{{R_2}{C_2}{B_1}}^{(1)} to |Φ₀〉|0〉_B₁, we get 10 $\begin{array}{l} | Φ_{1} 〉 & = & W_{R_{2} C_{2} B_{1}}^{(1)} | Φ_{0} 〉 \otimes {| 0 〉}_{B_{1}} \\ = & \frac{1}{\sqrt{3}} (\sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| k 〉}_{C_{2}} {| 1 〉}_{B_{1}} \\ + \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| k 〉}_{C_{2}} {| 0 〉}_{B_{1}} \\ + \sum_{i = 0}^{N - 1} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| l 〉}_{C_{2}} {| 0 〉}_{B_{1}}) . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_1}} \right\rangle } \hfill & = \hfill & {W_{{R_2}{C_2}{B_1}}^{(1)}\left| {{{\rm{\Phi }}_0}} \right\rangle \otimes {{\left| 0 \right\rangle }_{{B_1}}}} \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 3 }}\left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}}{{\left| 1 \right\rangle }_{{B_1}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}}{{\left| 0 \right\rangle }_{{B_1}}}} } } \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{i = 0}^{N - 1} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| l \right\rangle }_{{C_2}}}{{\left| 0 \right\rangle }_{{B_1}}}} } } \right).} \hfill \cr }

In this way, the terms where the states of R₂ and C₂ are different are labeled by |1〉_B₁, and the terms where the states of R₂ and C₂ are the same are labeled by |0〉_B₁.

Since the control operator $W_{R_{2} C_{2} B_{1}}^{(1)}$ W_{{R_2}{C_2}{B_1}}^{(1)} has n control qubit, its computational complexity is O(n) = O(log N).

Step 3: Separate the useful information terms from the useless information terms

We proceed to separate the useful information terms from the useless ones.

1)
In the first sum, extract all elements except for those in the (k + 1)th and (l + 1)th rows.
2)
In the second sum, extract all elements in the (l + 1)th row.
3)
In the third sum, extract all elements in the (k + 1)th row.
4)
For the terms in |Φ₁〉 labeled by |1〉_B₁, extract all terms except those where R₁ is in the states |k〉_R₁ and |l〉_R₁.
5)
For the two sums in |Φ₁〉 labeled by |0〉_B₁, extract the terms where R₁ is in the state |l〉_R₁ and the terms where R₁ is in the state |k〉_R₁.

We introduce an auxiliary qubit B₂ in state |0〉_B₂, and use the following control operators, $\begin{array}{l} W^{(1)} & = & P_{R_{1} R_{2}} \otimes σ_{B_{2}^{1}}^{(x)} + (I_{R_{1} R_{2}} - P_{R_{1} R_{2}}) \otimes I_{B_{2}^{1}}, \\ W^{(2)} & = & P_{R_{1} C_{2}} \otimes σ_{B_{2}^{2}}^{(x)} + (I_{R_{1} C_{2}} - P_{R_{1} C_{2}}) \otimes I_{B_{2}^{1}}, \end{array}$ \matrix{ {{W^{(1)}}} \hfill & = \hfill & {{P_{{R_1}{R_2}}} \otimes \sigma _{{B_2}^1}^{(x)} + ({I_{{R_1}{R_2}}} - {P_{{R_1}{R_2}}}) \otimes {I_{{B_2}^1}},} \hfill \cr {{W^{(2)}}} \hfill & = \hfill & {{P_{{R_1}{C_2}}} \otimes \sigma _{{B_2}^2}^{(x)} + ({I_{{R_1}{C_2}}} - {P_{{R_1}{C_2}}}) \otimes {I_{{B_2}^1}},} \hfill \cr } where P_R₁R₂ = |k〉_R₁ |l〉_{R₂ R₁}〈k|_R₂〈l| and P_R₁C₂ = |l〉_R₁ |k〉_{C₂ R₁}〈l|_C₂ 〈k| are projection operators. $σ_{B_{2}^{i}}^{(x)}$ \sigma _{{B_2}^i}^{(x)} and I_B₂i are the operators acting on the i-th qubit of the auxiliary B₂ (i = 1,2).

When $W_{R_{1} R_{2} C_{2} B_{2}}^{(2)} = W^{(2)} W^{(1)}$ W_{{R_1}{R_2}{C_2}{B_2}}^{(2)} = {W^{(2)}}{W^{(1)}} acts on |Φ₁〉|0〉_B₂, we obtain 11 $\begin{array}{l} | Φ_{2} 〉 & = & W_{R_{1} R_{2} C_{2} B_{2}}^{(2)} | Φ_{1} 〉 \otimes {| 0 〉}_{B_{2}} \\ \frac{1}{\sqrt{3}} (\sum_{i \neq l, k} \sum_{j = 0}^{M - 1} a_{i j} {| i 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| k 〉}_{C_{2}} {| 1 〉}_{B_{1}} {| 00 〉}_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{l j} {| l 〉}_{R_{1}} {| j 〉}_{C_{1}} {| k 〉}_{R_{2}} {| k 〉}_{C_{2}} {| 0 〉}_{B_{1}} {| 01 〉}_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{k j} {| k 〉}_{R_{1}} {| j 〉}_{C_{1}} {| l 〉}_{R_{2}} {| l 〉}_{C_{2}} {| 0 〉}_{B_{1}} {| 10 〉}_{B_{2}}) \\ + {| g_{1} 〉}_{R_{1}} {_{C_{1}}}_{R_{2}} {_{C_{2}}}_{B_{1}}_{B_{2}} . \end{array}$ \matrix{ {\left| {{{\rm{\Phi }}_2}} \right\rangle } \hfill & = \hfill & {W_{{R_1}{R_2}{C_2}{B_2}}^{(2)}\left| {{{\rm{\Phi }}_1}} \right\rangle \otimes {{\left| 0 \right\rangle }_{{B_2}}}} \hfill \cr {} \hfill & {} \hfill & {{1 \over {\sqrt 3 }}\left( {\sum\limits_{i \ne l,k} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}{{\left| i \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}}{{\left| 1 \right\rangle }_{{B_1}}}{{\left| {00} \right\rangle }_{{B_2}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \sum\limits_{j = 0}^{M - 1} {{a_{lj}}{{\left| l \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| k \right\rangle }_{{R_2}}}{{\left| k \right\rangle }_{{C_2}}}{{\left| 0 \right\rangle }_{{B_1}}}{{\left| {01} \right\rangle }_{{B_2}}}} } \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {{a_{kj}}{{\left| k \right\rangle }_{{R_1}}}{{\left| j \right\rangle }_{{C_1}}}{{\left| l \right\rangle }_{{R_2}}}{{\left| l \right\rangle }_{{C_2}}}{{\left| 0 \right\rangle }_{{B_1}}}{{\left| {10} \right\rangle }_{{B_2}}}} } \right)} \hfill \cr {} \hfill & {} \hfill & { + {{\left| {{g_1}} \right\rangle }_{{R_1}}}{{_{{C_1}}}_{{R_2}}}{{_{{C_2}}}_{{B_1}}}_{{B_2}}.} \hfill \cr }

That is, the terms labeled by |1〉_B₁ |00〉_B₂, |0〉_B₁ |01〉_B₂ and |0〉_B₁ |10〉_B₂ are the useful information terms required by the algorithm, while the other terms are the useless information terms denoted by |g₁〉_{R₁C₁R₂C₂B₁B₂}.

Since the control operator $W_{R_{1} R_{2} C_{2} B_{2}}^{(2)}$ W_{{R_1}{R_2}{C_2}{B_2}}^{(2)} has 2n control qubit, its computational complexity is O(n) = O(log N).

Step 4: Use C-SWAP gates to swap the states of R₁ and R₂, as well as the states of R₁ and C₂

To swap the (k + 1)th and (l + 1)th rows of the matrix, we apply C-SWAP gate to the terms in |Φ₂〉 labeled by |10〉_B₂ and |01〉_B₂, so as to swap the states of R₁ and R₂, as well as the states of R₁ and C₂. Denote $\begin{array}{l} W^{(1)} & = & S W A P_{R_{1}, C_{2}} \otimes {| 1 〉}_{B_{2}^{1}}_{B_{2}^{1}} 〈 1 | + I_{R_{1} C_{2}} \otimes {| 0 〉}_{B_{2}^{1}}_{B_{2}^{1}} 〈 0 |, \\ W^{(2)} & = & S W A P_{R_{1}, R_{2}} \otimes {| 1 〉}_{B_{2}^{2}}_{B_{2}^{2}} 〈 1 | + I_{R_{1} R_{2}} \otimes {| 0 〉}_{B_{2}^{2}}_{B_{2}^{2}} 〈 0 |, \end{array}$ \matrix{ {{W^{(1)}}} \hfill & = \hfill & {SWA{P_{{R_1},{C_2}}} \otimes {{\left| 1 \right\rangle }_{{B_2}^1\;}}_{{B_2}^1}\left\langle 1 \right| + {I_{{R_1}{C_2}}} \otimes {{\left| 0 \right\rangle }_{{B_2}^1}}{\;_{{B_2}^1}}\left\langle 0 \right|,} \hfill \cr {{W^{(2)}}} \hfill & = \hfill & {SWA{P_{{R_1},{R_2}}} \otimes {{\left| 1 \right\rangle }_{{B_2}^2\;}}_{{B_2}^2}\left\langle 1 \right| + {I_{{R_1}{R_2}}} \otimes {{\left| 0 \right\rangle }_{{B_2}^2}}{\;_{{B_2}^2}}\left\langle 0 \right|,} \hfill \cr } where |1〉_B₂¹ stands for that the first qubit of B₂ is in the state |1〉, and |1〉_B₂² for that the second qubit of B₂ in the state |1〉.

Applying $W_{R_{1} R_{2} C_{2} B_{2}}^{(3)} = W^{(2)} W^{(1)}$ W_{{R_1}{R_2}{C_2}{B_2}}^{(3)} = {W^{(2)}}{W^{(1)}} to |Φ₂〉, we obtain 12 $\begin{array}{l} | Φ_{3} 〉 & = & W_{R_{1} R_{2} C_{2} B_{2}}^{(3)} | Φ_{2} 〉 \\ = & \frac{1}{\sqrt{3}} (\sum_{i \neq l, k} \sum_{j = 0}^{M - 1} a_{i j} | i 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | k 〉_{C_{2}} | 1 〉_{B_{1}} | 00 〉_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{l j} | k 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | k 〉_{C_{2}} | 0 〉_{B_{1}} | 01 〉_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{k j} | l 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | k 〉_{C_{2}} | 0 〉_{B_{1}} | 10 〉_{B_{2}}) + \\ + {| g_{2} 〉}_{R_{1} C_{1} R_{2} C_{2} B_{1} B_{2}} . \end{array}$ \matrix{ {\left| {{\Phi _3}} \right\rangle } \hfill & = \hfill & {W_{{R_1}{R_2}{C_2}{B_2}}^{(3)}\left| {{\Phi _2}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 3 }}\left( {\sum\limits_{i \ne l,k} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}|i{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|1{\rangle _{{B_1}}}|00{\rangle _{{B_2}}}} } } \right.} \hfill \cr {} \hfill & {} \hfill & { + \sum\limits_{j = 0}^{M - 1} {{a_{lj}}|k{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|0{\rangle _{{B_1}}}|01{\rangle _{{B_2}}}} } \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {{a_{kj}}|l{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|0{\rangle _{{B_1}}}|10{\rangle _{{B_2}}}} } \right) + } \hfill \cr {} \hfill & {} \hfill & { + {{\left| {{g_2}} \right\rangle }_{{R_1}{C_1}{R_2}{C_2}{B_1}{B_2}}}.} \hfill \cr }

The SWAP gates transfer the elements originally in the (k + 1)th row to the (l + 1)th row in the terms labeled by |0〉_B₁ |01〉_B₂, and the elements originally in the (l + 1)th row to the (k + 1)th row in the terms labeled by |0〉_B₁ |10〉_B₂.

Note that the SWAPs in the control operator $W_{R_{1} R_{2} B_{2}}^{(3)}$ W_{{R_1}{R_2}{B_2}}^{(3)} have common single control qubit and are related to different pairs of qubits. Therefore, they can be applied simultaneously.

Step 5: Label the useful and useless information terms

Introduce an auxiliary qubit B₃ in state |0〉_B₃. To use B₃ to label the useful and useless information terms in |Φ₃〉, we apply the following control operator, $W_{B_{1} B_{2} B_{3}}^{(4)} = V^{(1)} V^{(2)} V^{(3)},$ W_{{B_1}{B_2}{B_3}}^{(4)} = {V^{(1)}}{V^{(2)}}{V^{(3)}}, where $V^{(i)} = P_{B_{1} B_{2}}^{(i)} \otimes σ_{B_{3}}^{(x)} + (I_{B_{1} B_{2}} - P_{B_{1} B_{2}}) \otimes I_{B_{3}}$ {V^{(i)}} = P_{{B_1}{B_2}}^{(i)} \otimes \sigma _{{B_3}}^{(x)} + \left( {{I_{{B_1}{B_2}}} - {P_{{B_1}{B_2}}}} \right) \otimes {I_{{B_3}}}, with the projection operators $P_{B_{1} B_{2}}^{(i)} (i = 1, 2, 3)$ P_{{B_1}{B_2}}^{(i)}(i = 1,2,3) given by $\begin{array}{l} P_{B_{1} B_{2}}^{(1)} & = & | 100 〉_{B_{1} B_{2}}_{B_{1}}_{B_{2}} 〈 100 |, \\ P_{B_{1} B_{2}}^{(2)} & = & | 001 〉_{B_{1} B_{2}}_{B_{1}}_{B_{2}} 〈 001 |, \\ P_{B_{1} B_{2}}^{(3)} & = & | 010 〉_{B_{1} B_{2}}_{B_{1}}_{B_{2}} 〈 010 | . \end{array}$ \matrix{ {P_{{B_1}{B_2}}^{(1)}} \hfill & = \hfill & {|100{\rangle _{{B_1}{B_2}}}{\;_{{B_1}}}_{{B_2}}\langle 100|,} \hfill \cr {P_{{B_1}{B_2}}^{(2)}} \hfill & = \hfill & {|001{\rangle _{{B_1}{B_2}}}{\,_{{B_1}}}_{{B_2}}\langle 001|,} \hfill \cr {P_{{B_1}{B_2}}^{(3)}} \hfill & = \hfill & {|010{\rangle _{{B_1}{B_2}}}{\;_{{B_1}}}_{{B_2}}\langle 010|.} \hfill \cr }

Acting $W_{B_{1} B_{2} B_{3}}^{(4)}$ W_{{B_1}{B_2}{B_3}}^{(4)} on |Φ₃〉|0〉_B₃. we obtain 13 $\begin{array}{l} | Φ_{4} 〉 & = & W_{B_{1} B_{2} B_{3}}^{(4)} | Φ_{3} 〉 | 0 〉_{B_{3}} \\ = & \frac{1}{\sqrt{3}} (\sum_{i \neq l, k} \sum_{j = 0}^{M - 1} a_{i j} | i 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | k 〉_{C_{2}} | 1 〉_{B_{1}} | 00 〉_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{l j} | k 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | k 〉_{C_{2}} | 0 〉_{B_{1}} | 01 〉_{B_{2}} \\ + \sum_{j = 0}^{M - 1} a_{k j} | l 〉_{R_{1}} | j 〉_{C_{1}} | l 〉_{R_{2}} | k 〉_{C_{2}} | 0 〉_{B_{1}} | 10 〉_{B_{2}}) | 1 〉_{B_{3}} \\ + {| g_{2} 〉}_{R_{1} C_{1} R_{2} C_{2} B_{1} B_{2}} | 0 〉_{B_{3}} . \end{array}$ \matrix{ {\left| {{\Phi _4}} \right\rangle } \hfill & = \hfill & {W_{{B_1}{B_2}{B_3}}^{(4)}\left| {{\Phi _3}} \right\rangle |0{\rangle _{{B_3}}}} \hfill \cr {} \hfill & = \hfill & {{1 \over {\sqrt 3 }}\left( {\sum\limits_{i \ne l,k} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}} } |i{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|1{\rangle _{{B_1}}}|00{\rangle _{{B_2}}}} \right.} \hfill \cr {} \hfill & {} \hfill & { + \sum\limits_{j = 0}^{M - 1} {{a_{lj}}} |k{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|0{\rangle _{{B_1}}}|01{\rangle _{{B_2}}}} \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {{a_{kj}}} |l{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|0{\rangle _{{B_1}}}|10{\rangle _{{B_2}}}} \right)|1{\rangle _{{B_3}}}} \hfill \cr {} \hfill & {} \hfill & { + {{\left| {{g_2}} \right\rangle }_{{R_1}{C_1}{R_2}{C_2}{B_1}{B_2}}}|0{\rangle _{{B_3}}}.} \hfill \cr }

Here, |1〉_B₃ labels the useful information term, while |0〉_B₃ labels the useless information term.

Since the control operator $W_{B_{1} B_{2} B_{3}}^{(4)}$ W_{{B_1}{B_2}{B_3}}^{(4)} has one control qubit, its computational complexity is O(1).

Step 6: Use Hadamard gates for information superposition

Applying the Hadamard operator $W_{B_{1} B_{2}}^{(5)} = H^{\otimes 3}$ W_{{B_1}{B_2}}^{(5)} = {H^{ \otimes 3}} to B₁ and B₂, we have 14 $\begin{array}{l} | Φ_{5} 〉 & = & W_{B_{1} B_{2}}^{(5)} | Φ_{4} 〉 \\ = & \frac{1}{{(\sqrt{2})}^{3} \cdot \sqrt{3}} (\sum_{i \neq l, k} \sum_{j = 0}^{M - 1} a_{i j} | i 〉_{R_{1}} | j 〉_{C_{1}} \\ + \sum_{j = 0}^{M - 1} a_{l j} | k 〉_{R_{1}} | j 〉_{C_{1}} + \sum_{j = 0}^{M - 1} a_{k j} | l 〉_{R_{1}} | j 〉_{C_{1}}) \\ | l 〉_{R_{2}} | k 〉_{C_{2}} | 0 〉_{B_{1}} | 00 〉_{B_{2}} | 1 〉_{B_{3}} + {| g_{3} 〉}_{R_{1} C_{1} R_{2} C_{2} B_{1} B_{2} B_{3}}, \end{array}$ \matrix{ {\left| {{\Phi _5}} \right\rangle } \hfill & = \hfill & {W_{{B_1}{B_2}}^{(5)}\left| {{\Phi _4}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {{{(\sqrt 2 )}^3}\cdot\sqrt 3 }}\left( {\sum\limits_{i \ne l,k} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}} } |i{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}} \right.} \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {{a_{lj}}} |k{\rangle _{{R_1}}}|j{\rangle _{{C_1}}} + \sum\limits_{j = 0}^{M - 1} {{a_{kj}}} |l{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}} \right)} \hfill \cr {} \hfill & {} \hfill & {|l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}|0{\rangle _{{B_1}}}|00{\rangle _{{B_2}}}|1{\rangle _{{B_3}}} + {{\left| {{g_3}} \right\rangle }_{{R_1}{C_1}{R_2}{C_2}{B_1}{B_2}{B_3}}},} \hfill \cr } where the terms in the state |0〉_B₁|00〉_B₂|1〉_B₃ are retained, the other terms are denoted by |g₃〉_{R₁C₁R₂B₁B₂B₃}.

At this point, we have successfully swaped the elements of the (k + 1) -th row of matrix A with the corresponding elements of the (l + 1)-th row.

Since only three Hadamard gates are used here, the circuit complexity is O(1).

Step 7: Measure the auxiliary B₁B₂B₃ in the state |0001〉_B₁B₂B₃

We measure the auxiliary B₁B₂B₃ in the state |0001〉_B₁B₂B₃ to remove the useless information terms, and obtain 15 $| Φ_{6} 〉 = | Ψ_{o u t} 〉 | l 〉_{R_{2}} | k 〉_{C_{2}},$ \left| {{\Phi _6}} \right\rangle = \left| {{\Psi _{out}}} \right\rangle |l{\rangle _{{R_2}}}|k{\rangle _{{C_2}}}, where 16 $\begin{array}{l} | Ψ_{o u t} 〉 & = & (\sum_{i \neq l, k} \sum_{j = 0}^{M - 1} a_{i j} | i 〉_{R_{1}} | j 〉_{C_{1}} \\ + \sum_{j = 0}^{M - 1} a_{l j} | k 〉_{R_{1}} | j 〉_{C_{1}} + \sum_{j = 0}^{M - 1} a_{k j} | l 〉_{R_{1}} | j 〉_{C_{1}}) . \end{array}$ \matrix{ {\left| {{\Psi _{out}}} \right\rangle } \hfill & = \hfill & {\left( {\sum\limits_{i \ne l,k} {\sum\limits_{j = 0}^{M - 1} {{a_{ij}}} } |i{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}} \right.} \hfill \cr {} \hfill & {} \hfill & {\left. { + \sum\limits_{j = 0}^{M - 1} {{a_{lj}}} |k{\rangle _{{R_1}}}|j{\rangle _{{C_1}}} + \sum\limits_{j = 0}^{M - 1} {{a_{kj}}} |l{\rangle _{{R_1}}}|j{\rangle _{{C_1}}}} \right).} \hfill \cr }

The success probability is $\frac{1}{24}$ {1 \over {24}}. This probability is independent of the matrix dimension.

The overall computational complexity of the algorithm is O(n), mainly determined by $W_{R_{2} C_{2} B_{1}}^{(1)}$ W_{{R_2}{C_2}{B_1}}^{(1)} and $W_{R_{1} R_{2} C_{2} B_{2}}^{(2)}$ W_{{R_1}{R_2}{C_2}{B_2}}^{(2)}.

For specific examples of this algorithm, please refer to Appendix A.

3.

Matrix Trace Calculation and Transpose

In this section we present quantum algorithms for trace calculation of an N × N matrix and transposition of an N × M matrix.

3.1.

Matrix Trace Calculation

The quantum circuit for calculating the trace of the matrix S is shown in Figure 3. Assume that a matrix S={a_ik} is of size N × N with N = 2ⁿ. This algorithm requires one pure state and three auxiliary qubits, and is divided into the following six steps.

Step 1: Prepare the initial state

First, introduce two n-qubit registers R and C, which are used to enumerate the rows and columns of the matrix S, and encode the elements of the matrix S to obtain the following pure initial state, 17 $| Φ_{0} 〉 = \sum_{i = 0}^{N - 1} \sum_{k = 0}^{N - 1} a_{i k} | i 〉_{R} | k 〉_{C}, \sum_{i k} {| a_{i k} |}^{2} = 1.$ \left| {{\Phi _0}} \right\rangle = \sum\limits_{i = 0}^{N - 1} {\sum\limits_{k = 0}^{N - 1} {{a_{ik}}} } |i{\rangle _R}|k{\rangle _C},\quad \sum\limits_{ik} {{{\left| {{a_{ik}}} \right|}^2}} = 1.

Step 2: Mark the terms where the states of R and C are the same

To calculate the sum of the diagonal elements of matrix S, we need to mark the diagonal elements of S, i.e., the terms where the states of registers R and C are the same. To do this, introduce an n-qubit auxiliary A in the state |0〉_A, and an operator $W_{j}^{(m)} = P_{j}^{(m)} \otimes σ_{A^{(j)}}^{(x)} + (I_{j} - P_{j}^{(m)}) \otimes I_{A^{(j)}},$ W_j^{(m)} = P_j^{(m)} \otimes \sigma _{{A^{(j)}}}^{(x)} + \left( {{I_j} - P_j^{(m)}} \right) \otimes {I_{{A^{(j)}}}}, where $P_{j}^{(m)} = {| m_{j} 〉}_{R} {| m_{j} 〉}_{C R} {〈 m_{j} |}_{C} 〈 m_{j} |, m = 0, 1, j = 1, 2, \dots, n$ P_j^{(m)} = {\left| {{m_j}} \right\rangle _R}{\left| {{m_j}} \right\rangle _C}_R{\left. {{m_j}} \right|_C}\langle {m_j}|,m = 0,1,j = 1,2, \ldots ,n, is the projection operator acting on the j-th qubit of registers R and C, $σ_{A^{(j)}}^{(x)}$ \sigma _{{A^{(j)}}}^{(x)} is the Pauli matrix acting on the j-th qubit of auxiliary A, I_A^(j) is the identity operator acting on the j-th qubit of auxiliary A.

Applying the operator $W_{R C A}^{(1)} = \prod_{j = 1}^{n} W_{j}^{0} W_{j}^{1}$ W_{RCA}^{(1)} = \prod\nolimits_{j = 1}^n {W_j^0} W_j^1 to |Φ₀〉|0〉_A, we obtain 18 $\begin{array}{l} | Φ_{1} 〉 & = & W_{R C A}^{(1)} | Φ_{0} 〉 | 0 〉_{A} \\ = & (\sum_{i = 0}^{N - 1} a_{i i} | i 〉_{R} | i 〉_{C}) | N - 1 〉_{A} + {| g_{1} 〉}_{R C A} . \end{array}$ \matrix{ {\left| {{\Phi _1}} \right\rangle } \hfill & = \hfill & {W_{RCA}^{(1)}\left| {{\Phi _0}} \right\rangle |0{\rangle _A}} \hfill \cr {} \hfill & = \hfill & {\left( {\sum\limits_{i = 0}^{N - 1} {{a_{ii}}} |i{\rangle _R}|i{\rangle _C}} \right)|N - 1{\rangle _A} + {{\left| {{g_1}} \right\rangle }_{RCA}}.} \hfill \cr }

In the process of realizing the quantum state |Φ₁〉, we check whether the j-th qubits of registers R and C are the same. If their j-th qubits are the same, the j-th qubit of A is flipped from |0〉 to |1〉. If the states of all n qubits of R and C are the same, the states of all n qubits of A are flipped from |0〉_A to |N – 1〉_A.

The control operator $W_{R C A}^{(1)}$ W_{RCA}^{(1)} has 2n control qubits, so the circuit complexity for computing |Φ₁〉 is O(n).

Step 3: Mark the useful and useless information terms

Currently, all useful information terms are stored in the first sum of |Φ₁〉, while the second sum |g₁〉_RCA represents useless information terms that are not needed by the algorithm.

To separately mark the useful and useless information terms in the state |Φ₁〉, we introduce the projection operator P_A = |N – 1〉_A _A 〈N – 1|, and a 1-qubit auxiliary B₁ in the state |0〉_B₁. The control operator $W_{A B_{1}}^{(2)} = P_{A} \otimes σ_{B_{1}}^{(x)} + (I_{A} - P_{A}) \otimes I_{B_{1}}$ W_{A{B_1}}^{(2)} = {P_A} \otimes \sigma _{{B_1}}^{(x)} + \left( {{I_A} - {P_A}} \right) \otimes {I_{{B_1}}} is then applied to A and B₁, giving rise to 19 $\begin{array}{l} | Φ_{2} 〉 & = & W_{A B_{1}}^{(2)} | Φ_{1} 〉 | 0 〉_{B_{1}} \\ = & (\sum_{i = 0}^{N - 1} a_{i i} | i 〉_{R} | i 〉_{C}) \otimes | N - 1 〉_{A} \otimes | 1 〉_{B_{1}} \\ + {| g_{1} 〉}_{R C A} \otimes | 0 〉_{B_{1}} . \end{array}$ \matrix{ {\left| {{\Phi _2}} \right\rangle } \hfill & = \hfill & {W_{A{B_1}}^{(2)}\left| {{\Phi _1}} \right\rangle |0{\rangle _{{B_1}}}} \hfill \cr {} \hfill & = \hfill & {\left( {\sum\limits_{i = 0}^{N - 1} {{a_{ii}}} |i{\rangle _R}|i{\rangle _C}} \right) \otimes |N - 1{\rangle _A} \otimes |1{\rangle _{{B_1}}}} \hfill \cr {} \hfill & {} \hfill & { + {{\left| {{g_1}} \right\rangle }_{RCA}} \otimes |0{\rangle _{{B_1}}}.} \hfill \cr }

Here, the useful information terms are marked by |1〉_B₁, and the useless information terms are marked by |0〉_B₁.

Since the control operator $W_{A B_{1}}^{(2)}$ W_{A{B_1}}^{(2)} has n control qubits, its computational complexity is O(n) = O(log N).

Step 4: Use the Hadamard gate for information superposition

Up to this point, we have obtained the diagonal elements of S. To compute the sum we apply the Hadamard operator $W_{R C A}^{(3)} = H^{\otimes 3 n}$ W_{RCA}^{(3)} = {H^{ \otimes 3n}} to all qubits in |Φ₂〉 except for the auxiliary B₁. We get 20 $\begin{array}{l} | Φ_{3} 〉 & = & W_{R C A}^{(3)} | Φ_{2} 〉 \\ = & \frac{1}{2^{3 n / 2}} (\sum_{i = 0}^{N - 1} a_{i i}) | 0 〉_{R} | 0 〉_{C} | 0 〉_{A} | 1 〉_{B_{1}} + {| g_{2} 〉}_{R C A B_{1}} . \end{array}$ \matrix{ {\left| {{\Phi _3}} \right\rangle } \hfill & = \hfill & {W_{RCA}^{(3)}\left| {{\Phi _2}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {{1 \over {{2^{3n/2}}}}\left( {\sum\limits_{i = 0}^{N - 1} {{a_{ii}}} } \right)|0{\rangle _R}|0{\rangle _C}|0{\rangle _A}|1{\rangle _{{B_1}}} + {{\left| {{g_2}} \right\rangle }_{RCA{B_1}}}.} \hfill \cr }

In the state |Φ₃〉, we select the terms in the state |0〉_r|0〉_C|0〉_A|1〉_B₁, as these terms contain all the useful information required for the trace calculation. The other terms are represented by |g₂〉_RCAB₁.

Since 3n Hadamard gates are used here, the circuit complexity is O(n).

Step 5: Re-mark the useful and useless information terms

Since new useless information terms were generated in the previous step and the useful information is stored in the first term of |Φ₃〉, we need to re-mark the useful and useless information terms. To do this, we introduce an auxiliary qubit B₂ in state |0〉_A₂, as well as the projection operator P_RCAB₁ = |0〉_R|0〉_C|0〉_A|1〉_B₁ _R〈0|_C〈0|_A〈0|_B₁ 〈1|. We apply the following control operator $W_{R C A B_{1} B_{2}}^{(4)} = P_{R C A B_{1}} \otimes σ_{B_{2}}^{(x)} + (I_{R C A B_{1}} - P_{R C A B_{1}}) \otimes I_{B_{2}}$ W_{RCA{B_1}{B_2}}^{(4)} = {P_{RCA{B_1}}} \otimes \sigma _{{B_2}}^{(x)} + \left( {{I_{RCA{B_1}}} - {P_{RCA{B_1}}}} \right) \otimes {I_{{B_2}}} to |Φ₃〉 ⊗ |0〉_B₂. We obtain 21 $\begin{array}{l} | Φ_{4} 〉 & = & W_{R C A B_{1} B_{2}}^{(4)} | Φ_{3} 〉 | 0 〉_{B_{2}} \\ = & \frac{1}{2^{3 n / 2}} (\sum_{i = 0}^{N - 1} a_{i i}) | 0 〉_{R} | 0 〉_{C} | 0 〉_{A} | 1 〉_{B_{1}} | 1 〉_{B_{2}} \\ + {| g_{2} 〉}_{R C A B_{1}} | 0 〉_{B_{2}} . \end{array}$ \matrix{ {\left| {{\Phi _4}} \right\rangle } \hfill & = \hfill & {W_{RCA{B_1}{B_2}}^{(4)}\left| {{\Phi _3}} \right\rangle |0{\rangle _{{B_2}}}} \hfill \cr {} \hfill & = \hfill & {{1 \over {{2^{3n/2}}}}\left( {\sum\limits_{i = 0}^{N - 1} {{a_{ii}}} } \right)|0{\rangle _R}|0{\rangle _C}|0{\rangle _A}|1{\rangle _{{B_1}}}|1{\rangle _{{B_2}}}} \hfill \cr {} \hfill & {} \hfill & { + {{\left| {{g_2}} \right\rangle }_{RCA{B_1}}}|0{\rangle _{{B_2}}}.} \hfill \cr }

Here, the useful information terms are marked by |1〉_B₂, and the useless information terms are marked by |0〉_B₂.

Since the control operator $W_{R C A B_{1} B_{2}}^{(4)}$ W_{RCA{B_1}{B_2}}^{(4)} has 3n + 1 control qubit, its computational complexity is O(n).

Step 6: Measure the auxiliary qubit B₂ in the state |1〉_B₂

The trace of the matrix S is stored in the quantum state |Φ₄〉 in the form of probability amplitudes, with the useful information marked by |1〉_B₂. To extract the useful information, we measure the auxiliary qubit B₂ in the state |1〉_B₂, and obtain 22 $| Φ_{5} 〉 = \frac{\sum_{i = 0}^{N - 1} a_{i i}}{| \sum_{i = 0}^{N - 1} a_{i i} |} | 0 〉_{R} | 0 〉_{C} | 0 〉_{A} | 1 〉_{B_{1}} .$ \left| {{\Phi _5}} \right\rangle = {{\sum\nolimits_{i = 0}^{N - 1} {{a_{ii}}} } \over {\left| {\sum\nolimits_{i = 0}^{N - 1} {{a_{ii}}} } \right|}}|0{\rangle _R}|0{\rangle _C}|0{\rangle _A}|1{\rangle _{{B_1}}}.

The trace is obtained based on the measurement probability $\frac{{| \sum_{i = 0}^{N - 1} a_{i i} |}^{2}}{2^{3 n}}$ {{{{\left| {\sum\nolimits_{i = 0}^{N - 1} {{a_{ii}}} } \right|}^2}} \over {{2^{3n}}}}. This probability is related of the matrix dimension.

The overall computational complexity of the algorithm is O(n), mainly determined by $W_{R C A}^{(1)}, W_{A B_{1}}^{(2)}, W_{R C A}^{(3)}$ W_{RCA}^{(1)},W_{A{B_1}}^{(2)},W_{RCA}^{(3)} and $W_{R C A B_{1} B_{2}}^{(4)}$ W_{RCA{B_1}{B_2}}^{(4)}

3.2.

Matrix Transpose

The quantum circuit for matrix transpose is shown in Figure 4. Assume that a matrix S={a_ik} is of size N × M with N = 2ⁿ and M = 2^m. The algorithm requires two pure states and is divided into two steps.

Step 1: Prepare the initial state

First, introduce an n -qubit register R and an m-qubit register C, where R and C enumerate the rows and columns of the matrix S, respectively. The elements of matrix S are encoded into the following pure state, $| Ψ 〉 = \sum_{i = 0}^{N - 1} \sum_{k = 0}^{M - 1} a_{i k} | i 〉_{R} | k 〉_{C}, \sum_{i k} {| a_{i k} |}^{2} = 1,$ |\Psi \rangle = \sum\limits_{i = 0}^{N - 1} {\sum\limits_{k = 0}^{M - 1} {{a_{ik}}} } |i{\rangle _R}|k{\rangle _C},\quad \sum\limits_{ik} {{{\left| {{a_{ik}}} \right|}^2}} = 1,

Then, introduce a pure state |0〉_D for an m-qubit register D. The initial state is give by 23 $\begin{array}{l} | Φ_{0} 〉 & = & | 0 〉_{D} \otimes | Ψ 〉 \\ = & \sum_{i = 0}^{N - 1} \sum_{k = 0}^{M - 1} a_{i k} | 0 〉_{D} | i 〉_{R} | k 〉_{C} . \end{array}$ \matrix{ {\left| {{\Phi _0}} \right\rangle } \hfill & = \hfill & {|0{\rangle _D} \otimes |\Psi \rangle } \hfill \cr {} \hfill & = \hfill & {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{k = 0}^{M - 1} {{a_{ik}}} } |0{\rangle _D}|i{\rangle _R}|k{\rangle _C}.} \hfill \cr }

Step 2: Use a SWAP gate to exchange the states of D and C

We use a SWAP gate to exchange the states of the D and C registers. The operator SWAP_DC is applied to |Φ₀〉, yielding 24 $\begin{array}{l} | Φ_{1} 〉 & = & S W A P_{D C} | Φ_{0} 〉 \\ = & | Ψ_{o u t} 〉 | 0 〉_{C}, \end{array}$ \matrix{ {\left| {{\Phi _1}} \right\rangle } \hfill & = \hfill & {SWA{P_{DC}}\left| {{\Phi _0}} \right\rangle } \hfill \cr {} \hfill & = \hfill & {\left| {{\Psi _{out}}} \right\rangle |0{\rangle _C},} \hfill \cr } where 25 $| Ψ_{o u t} 〉 = (\sum_{i = 0}^{N - 1} \sum_{k = 0}^{M - 1} a_{i k} | k 〉_{D} | i 〉_{R}) .$ \left| {{\Psi _{out}}} \right\rangle = \left( {\sum\limits_{i = 0}^{N - 1} {\sum\limits_{k = 0}^{M - 1} {{a_{ik}}} } |k{\rangle _D}|i{\rangle _R}} \right).

Now, the new rows and new columns of the current target matrix are enumerated by the states D and R respectively. Clearly, the success probability of this algorithm is 1.

Since the exchange operator SWAP_DC only involves exchange operations when acting on different qubit pairs, its computational complexity is O(m).

Remark 1.

Formally the non-square matrix can be made a square matrix by including the proper number of zero rows or columns. In this case transposition of non-square matrix can be done as a transposition of a square matrix, i.e. by the swap operator SWAP_RC. The complexity of this operation is O(n).

4.

Conclusion

We have developed quantum algorithms for two types of elementary row transformations of matrices, the trace and transpose of matrices. The operational mechanism of all these algorithms is as follows: First, construct the initial state of the entire system. Second, utilize unitary operations and ancillary qubits to mark the information items required by the algorithm. Third, apply the Hadamard transformation to superpose these information items. Finally, measure the ancillary qubits to eliminate the useless information items and retain only the useful ones.

In all these algorithms, the final result is stored in the probability amplitude of certain quantum states. Our success probability for adding one row of a matrix to another is $\frac{G^{2}}{8}$ {{{G^2}} \over 8}. The success probability for swapping two rows of a matrix is $\frac{1}{24}$ {1 \over {24}}, while the success probability of matrix transpose is 1. The success probability for the trace calculation is $\frac{{| \sum_{i = 0}^{N - 1} a_{i i} |}^{2}}{2^{3 n}}$ {{{{\left| {\sum\nolimits_{i = 0}^{N - 1} {{a_{ii}}} } \right|}^2}} \over {{2^{3n}}}}. The success probabilities either depend solely on the elements of the matrix itself, or are fixed or related to the dimensions of the matrix. The larger the dimension, the smaller the success probability. To address this challenge, amplitude amplification techniques may be employed. It is worth noting that the computational complexity of these algorithms is related to the dimension of the matrices. It increases logarithmically as the matrix dimension grows. Specifically, the computational complexity is O(n) for elementary row operations and trace calculation, and O(m) for matrix transpose.

It would be desired to develop new methods to improve the success probability given by the final measurement in the algorithm, or explore the designs of other quantum algorithms for matrix operations based on multi-qubit Toffoli type gates and the simplest single qubit operations. It would be also interesting to conduct further researches on quantum algorithms for other matrix operations.

Quantum Algorithms for Matrix Operations of Row Addition, Row Swapping, Trace Calculation and Transpose

Full Article

Paradigm

My account