# Mod2 VQLS: A Variational Quantum Algorithm for Solving Systems of Linear Equations Modulo 2
## 1 Introduction  
This report describes a new quantum hybrid algorithm for solving systems of linear equations modulo 2. In such problems, we want to find an \(n\)-vector \(x\) such that \(Ax=b\), where \(A\) is an \(m\times n\) matrix and \(b\) is an \(m\)-vector, all values are 0 or 1, and arithmetic is performed modulo 2, so that \(1+1=0\). Linear equations with binary coefficients are less ubiquitous than those with real coefficients, but they still have key mathematical applications and commercial uses. For example, solving binary linear equations is an important step in state-of-the-art sieving approaches to integer factorization, in which we want to find large square numbers that are products of combinations of numbers whose prime factors are known, which means we want their exponents to be even [1; 2]. This paper presents a new quantum hybrid algorithm for solving systems of binary linear equations, which as far as we know is the first to apply quantum computing to this problem. The solution's approach has two steps. First, we define a quantum circuit implementing matrix-vector products over the relevant finite vector spaces. Our circuit has one gate for each non-zero entry in the coefficient matrix. Then, we derive a variational cost function that can be optimized in order to produce solutions to the given system. This frames the problem as one of optimizing a variational quantum circuit, which has become a standard approach in quantum machine learning on NISQ (noisy intermediate-scale quantum) hardware ([3], Chapter 5). Solving systems of simultaneous linear equations is a standard problem, and is most familiar in situations where the coefficients in the equations are real or complex numbers. When the coefficient matrix is not square, direct methods leveraging the LU or QR decompositions emerge as the natural choice [4]. Obtaining these factorizations incurs a computational cost of \(O(mn^{2})\), which sets a useful baseline expectation for such algorithms. As shown in Section 6, the Mod2 VQLS approach uses a number of matrix-vector productcalculations, which scales linearly in the system dimension. It is also comparable to the state-of-the art block Wiedemann method, which also leverages sparsity in the coefficient matrix. We note that the block Wiedemann method has been used in recent record-breaking RSA factorization calculations [5]. The rest of the paper is organized as follows. Section 2 introduces quantum gates and circuits used throughout the paper. Section 3 explains the construction of a quantum circuit that implements the crucial matrix-vector multiplication operation for binary-valued matrices and vectors. Section 4 pairs this circuit with a variational component that can be optimized in a hybrid quantum-classical computing framework in order to solve linear systems. In particular, this section introduces a simple rotations ansatz that is especially well-suited to the problem. Section 5 presents initial proof-of-concept experiments, showing that in low dimensions, with the rotations ansatz, the number of iterations needed to find a solution scales linearly in the number of dimensions (with a scaling factor around 4). Section 6 compares the method introduced here with established classical and quantum alternatives, and Section 7 discusses more of the potential applications. We shall use the following notation throughout. We let \(\mathbb{F}_{2}\) denote the field with the two elements \(\{0,1\}\). (In other works, \(\mathbb{F}_{2}\) is sometimes written as \(\mathbb{Z}_{2}\cong\mathbb{Z}/2\mathbb{Z}\), or \(GF(2)\), where \(GF\) stands for Galois Field.) Addition in \(\mathbb{F}_{2}\) is written using the symbol \(\oplus\), so that \(0\oplus 0=0\), \(0\oplus 1=1\oplus 0=1\), and \(1\oplus 1=0\). We fix an \(m\times n\) matrix \(A\) and an \(m\)-vector \(b\) with \(a_{ij},b_{i}\in\mathbb{F}_{2}\). In addition, we let \(x\) denote an arbitrary element of \(\mathbb{F}_{2}^{n}\).