# Mod2 VQLS: A Variational Quantum Algorithm for Solving Systems of Linear Equations Modulo 2
## 4 Solving the Linear System Using a Variational Quantum Algorithm
### Rotations Ansatz  
Now we turn to our variational ansatze. The first is a simple rotations pattern that is particularly well-suited for the Mod2 VQLS cost function \(\widehat{C}\). This ansatz is just a product of single-qubit rotations about the \(Y\)-axis; in particular, we take  
\[V(\theta)=\prod_{j=1}^{n}R_{Y}^{j}(\theta_{j}), \tag{4}\]  
Figure 5: Variational circuit for solving \(Ax=b\) as in Example 1 using a brickwork layout ansatz with 2 layers. The gray bars serve as visual aids helping th reader distinguish the different parts of the circuit: initial state creation, variational component, and matrix-vector product. with \(R_{Y}^{j}\) denoting an \(R_{Y}\) rotation applied on the \(j^{\text{th}}\)r qubit and each parameter \(\theta\in[-2\pi,2\pi]^{n}\). This circuit is interesting because it does not add to the overall computational cost of each iteration, and it is amenable to direct mathematical analysis. In particular, we can derive an explicit formula for the variational cost as a function of the circuit parameters. Theorem 3.2: _For each \(x\in\mathbb{F}_{2}^{n}\), define \(\alpha_{x}(\theta)=\prod_{j=1}^{n}\cos(\theta_{j}/2)^{(1-x_{j})}\sin(\theta_{ j}/2)^{x_{j}}\). In addition, let \(A^{-1}(b)=\{x\in\mathbb{F}_{2}^{n}\mid Ax\equiv b\mod 2\}\) denote the inverse image of \(b\) under \(A\). Then,_  
\[\widehat{C}(\theta)=1-\sum_{x\in A^{-1}(b)}\alpha_{x}(\theta)^{2}\]  
_with \(\left|\psi(\theta)\right\rangle=\mathcal{A}V(\theta)\left|0\right\rangle\) and \(V(\theta)\) denoting the ansatz defined by Relation (4)._  
Proof. : The theorem follows from direct calculation. First, note that  
\[R_{Y}(\theta_{j})\left|0\right\rangle=\cos(\theta_{j}/2)\left|0\right\rangle+ \sin(\theta_{j}/2)\left|1\right\rangle.\]  
So, a quick induction, left to the reader as an exercise, shows that  
\[V(\theta)\left|0\right\rangle^{\otimes n}=\bigotimes_{j=1}^{n}\left(R_{Y}^{j }(\theta_{j})\left|0\right\rangle\right)=\bigotimes_{j=1}^{n}\left(\cos( \theta_{j}/2)\left|0\right\rangle+\sin(\theta_{j}/2)\left|1\right\rangle \right)=\sum_{x\in\mathbb{F}_{2}^{n}}\alpha_{x}(\theta)\left|x\right\rangle.\]  
Combined with Theorem 3.1, the last equation yields an expression for our variational quantum state:  
\[\left|\psi(\theta)\right\rangle=\mathcal{A}V(\theta)\left|0\right\rangle^{ \otimes n}=\sum_{x\in\mathbb{F}_{2}^{n}}\alpha_{x}(\theta)\left|x\right\rangle \left|Ax\right\rangle. \tag{5}\]  
We use this expression to compute the variational cost with respect to \(\left|\psi(\theta)\right\rangle\). In particular, let  
\[\mathcal{H}=I\otimes\left|b\right\rangle\left\langle b\right|=\sum_{y\in \mathbb{F}_{2}^{n}}\left|y\right\rangle\left\langle y\right|\otimes\left|b \right\rangle\left\langle b\right|\]  
and use Relation (3) to write  
\[1-\widehat{C}(\theta)=|\left\langle b\left|\right.\psi(\theta)\right\rangle|^ {2}=\left\langle\psi(\theta)\right|\mathcal{H}\left|\psi(\theta)\right\rangle.\]  
Now, since \(\alpha_{x}(\theta)\) is real, we see that  
\[\left\langle\psi(\theta)\right|\mathcal{H}\left|\psi(\theta)\right\rangle =\sum_{x,y}\alpha_{x}(\theta)\alpha_{y}(\theta)\langle x\left| \right.y\rangle\langle Ax\left|\right.b\rangle\langle b\left|\right.Ay\rangle\] \[=\sum_{x\in\mathbb{F}_{2}^{n}}\alpha_{x}(\theta)^{2}|\langle Ax \left|\right.b\rangle|^{2}\] Figure 5:0  
so \(\widehat{C}(\theta)=1-\sum_{x\in A^{-1}(b)}\alpha_{x}(\theta)^{2}\) as desired. Moreover, we can obtain a similar formula for the gradient of the cost function with respect to the circuit parameters. Theorem 3.3: _For each \(j=1,\ldots,n\), the cost function \(\widehat{C}(\theta)\) varies like_  
Figure 5:1_with respect to \(\theta_{j}\). Here, \(\oplus\) denotes binary addition over \(\mathbb{F}_{2}^{n}\) and \(e_{j}\) denotes the \(j\)th standard basis vector in \(\mathbb{F}_{2}^{n}\)._  
Proof. : The theorem follows from a direct computation using the chain rule.