# Mod2 VQLS: A Variational Quantum Algorithm for Solving Systems of Linear Equations Modulo 2
## 6 Related Classical and Quantum Methods for Solving Linear Systems
### Quantum Linear Solvers  
Important families of quantum linear solvers are based on the renowned HHL algorithm of [PERSON], [PERSON], and [PERSON] [23], and the VQLS (Variational Quantum Linear Solver) algorithm of [9]. The HHL algorithm is an exact method for solving linear equations, with several papers proposing applications and improvements including [24], though also with significant caveats [25]. The VQLS approach is more recent, from the current era where variational methods are expected to perform well on real NISQ hardware, which has already encouraged subsequent research into VQLS, including the use of dynamic ansatze [26], comparing different optimizers [21], and applications to differential equations [27]. Mod2 VQLS is different from these methods, particularly with its support for binary vectors, and non-square matrices. To date, works on matrix multiplication and solving linear equations using quantum computing have addressed the cases of real- and complex-valued matrices. (This is sometimes stated explicitly, and sometimes implied by the assumption that the vector coordinates are represented by complex amplitudes.) The recent work of [27] adapts the VQLS of [9] to finite-element methods for solving differential equations, but here the 'elements' are subdomains supporting a function, not elements of a finite field, and the functions in question are still continuous. As far as we know, our proposal here is the first attempt to address this problem with matrices over \(\mathbb{F}_{2}\), or any finite field. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline  & & \multicolumn{3}{c}{**Brickwork Ansatz**} & \multicolumn{3}{c}{**Rotation Ansatz**} \\
**Dim** & **Solved** & **Valid** & **Invalid** & **Average** & **Solved** & **Valid** & **Invalid** & **Average** \\  & & **Solns** & **Solns** & **Iterations** & & **Solns** & **Solns** & **Iterations** \\ \hline
1 & 8 & 8 & 2 & 1 & 10 & 10 & 0 & 2 \\
2 & 10 & 16 & 4 & 1.7 & 10 & 14 & 0 & 3.7 \\
3 & 10 & 14 & 5 & 1 & 10 & 11 & 0 & 9.2 \\
4 & 9 & 9 & 1 & 38.8 & 10 & 11 & 0 & 16.3 \\
5 & 10 & 19 & 0 & 93.2 & 10 & 11 & 0 & 17.3 \\
6 & 10 & 15 & 0 & 177.4 & 10 & 11 & 0 & 18.9 \\
7 & 10 & 11 & 1 & 86.2 & 10 & 10 & 0 & 24.6 \\
8 & 10 & 11 & 0 & 120.2 & 10 & 10 & 0 & 29.4 \\
9 & 10 & 10 & 0 & 122.4 & 10 & 10 & 0 & 33.5 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Experimental results using brickwork and rotation ansatze in various dimensions, using 10 randomly generated matrices in each dimension, showing how many valid and invalid solutions were proposed, and how many iterations were used, by each method. Figure 7: Average number of iterations needed to find a solution for each dimension using the rotations ansatz. The number of iterations grows approximately linearly, with a slope just under 4. In addition, Mod2 VQLS can tackle matrices of any size and rank, whereas both HHL and VQLS are restricted to square matrices with full rank. This again is sometimes stated explicitly, and sometimes implied by the assumption that the matrix operator \(A\) is a quantum unitary operator. Indeed, the runtime of both HHL and VQLS depends on the condition number of the coefficient matrix, so effectively they assume the coefficient matrix is not only invertible, but _robustly_ so (well-conditioned). When \(A\) is square, and moreover enjoys additional structural properties like invertibility, symmetry, or positive-definiteness, faster iterative methods including various Krylov subspace iterations and conjugate gradient are available [28]. The ability to work with matrices of different sizes and ranks is especially beneficial for solving problems where the matrix sizes are not fixed in advance. A case-in-point is the integer factoring problems investigated by [2], which motivated the development of Mod2 VQLS. In this application, each equation (each row of the matrix \(A\)) is discovered independently in a massively parallel data collection phase.