# Mod2 VQLS: A Variational Quantum Algorithm for Solving Systems of Linear Equations Modulo 2
## 3 Implementing the Matrix-Vector Product as a Quantum Circuit  
This section introduces a quantum circuit that implements the binary-valued matrix-vector product \(Ax\), where \(A\) is a matrix and \(x\) is a vector, and both have values in \(\mathbb{F}_{2}\) as defined above. The trick is to notice that binary arithmetic may be implemented with controlled-NOT operations. The NOT gate switches the state of an individual qubit between \(\ket{0}\) and \(\ket{1}\), and the CNOT gate performs such an operation only if the so-called _control_ qubit is in state \(\ket{1}\). In particular, the CNOT gate acts on the two-qubit state \(\ket{y,z}\) as  
\[\text{CNOT}\ket{y,z}=\ket{y,y\oplus z}. \tag{1}\]  
Now let \(\ket{x}=\ket{x_{1},x_{2},\ldots,x_{n}}\) denote the \(n\)-qubit quantum state corresponding to \(x\) and notice that  
\[Ax\equiv \begin{bmatrix}a_{11}x_{1}\oplus\cdots\oplus a_{1n}x_{n}\\ \vdots\\ a_{m1}x_{1}\oplus\cdots\oplus a_{mn}x_{n}\end{bmatrix} \mod 2.\]  
Thus the \(m\)-qubit state \(\ket{Ax}\) can be prepared by applying the quantum circuit  
\[\mathcal{A}=\prod_{j=1}^{n}\mathcal{A}_{j},\quad\text{with}\quad\mathcal{A}_{ j}=\prod_{i=1}^{m}\text{CNOT}(j,n+i)^{a_{ij}} \tag{2}\]  
to the tensor product \(\ket{x}\ket{0}\). Here, \(\text{CNOT}(k,\ell)\) denotes a CNOT gate controlled by the \(k^{\text{th}}\) qubit and targeting the \(\ell^{\text{th}}\) one. The product operator \(\Pi\) in these definitions denotes composition, so it is implemented by applying the gates in sequence. Both products in Relation (2) may be taken in any order. We note that \(\mathcal{A}\) requires \(m+n\) qubits and \(N\) quantum gates, with \(N\) denoting the number of non-zero entries in \(A\). In particular, we obtain the following theorem. Figure 1: Single-qubit gates used in this paper and their corresponding matrices, which operate on the superposition state \(\alpha\ket{0}+\beta\ket{1}\) written as the column vector \( \begin{bmatrix}\alpha&\beta\end{bmatrix} ^{T}\). Figure 2: Two-qubit CNOT (controlled-\(X\)) and controlled-\(Z\) gates. **Theorem 1**. : _Using \(\mathcal{A}\) as in Relation (2), with \(\left|0\right\rangle\) denoting the \(m\)-qubit all-zero state, and with \(\left|x\right\rangle\left|0\right\rangle\) denoting the concatenation / tensor product of \(\left|x\right\rangle\) and \(\left|0\right\rangle\), we have_  
\[\mathcal{A}(\left|x\right\rangle\left|0\right\rangle)=\left|x\right\rangle \left|Ax\right\rangle.\]  
Proof. : The proof follows from an easy argument by induction on \(n\) that is left to the reader: the base case \(n=1\) can be easily established for all \(m\) by verifying that the \(i\)th qubit in the output register is zero precisely when \(a_{ij}=0\), and the inductive step follows from a quick calculation considering the inductive hypothesis and the action of the CNOT gate, as in Relation (1). **Example 1**. : _The following example elucidates Theorem 1. For concreteness, consider the \(2\times 3\) matrix_  
\[A= \begin{bmatrix}1&0&1\\ 1&1&0\end{bmatrix} \quad\text{so that}\quad Ax\equiv \begin{bmatrix}x_{1}\oplus x _{3}\\ x_{1}\oplus x_{2}\end{bmatrix} \mod 2.\]  
_Then_  
\[\mathcal{A}_{1}=\mathrm{CNOT}(1,4)\mathrm{CNOT}(1,5),\quad\mathcal{A}_{2}= \mathrm{CNOT}(2,5),\quad\text{and}\quad\mathcal{A}_{3}=\mathrm{CNOT}(3,4),\]  
_and therefore_  
\[\mathcal{A}\left|x\right\rangle\left|0,0\right\rangle=\mathcal{A}_{3}\mathcal{ A}_{2}\left|x\right\rangle\left|x_{1},x_{1}\right\rangle=\mathcal{A}_{3} \left|x\right\rangle\left|x_{1},x_{1}\oplus x_{2}\right\rangle=\left|x\right\rangle \left|x_{1}\oplus x_{3},x_{1}\oplus x_{2}\right\rangle=\left|x,Ax\right\rangle.\]  
These circuits work because the self-inverse behavior of the \(X\) and CNOT gates is ideal for binary arithmetic over \(\mathbb{F}_{2}\).