# 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
The key is to notice that differentiating \(\alpha_{x}\) swaps a sine for a cosine and vice versa; for instance, if \(x_{j}=0\), and we fix \(c_{k}=\cos\left(\frac{\theta_{j}}{2}\right)\) and \(s_{k}=\sin\left(\frac{\theta_{k}}{2}\right)\) for simplicity of notation, we see that  
Figure 5:2  
Theorem 3.2 helps us understand the critical points on the variational cost landscape. In particular, it shows that the gradient \(\
abla\widehat{C}(\theta)\) is smooth, and moreover, each of its entries is a trigonometric polynomial on the \(2n\) variables \(c_{j}=\cos\left(\frac{\theta_{j}}{2}\right)\) and \(s_{j}=\sin\left(\frac{\theta_{j}}{2}\right)\), for \(j=1,\ldots,n\). Thus, every critical point of the cost surface satisfies \(\
abla\widehat{C}=0\). When combined with the Pythagorean identities \(c_{j}^{2}+s_{j}^{2}=1\), the equation \(\
abla\widehat{C}=0\) characterizes an algebraic variety defined by \(2n\) polynomials in \(2n\) variables. Hence [PERSON]'s Theorem [10], Chapter 2 implies that \(\widehat{C}\) has at most \((2n)^{n}\cdot 2^{n}=(4n)^{n}\) real extrema. It is interesting to note that when \((c_{j},s_{j})\) is an \(8n\)-th root of unity, our variational cost can be written in terms of _quantum integers_ or \(q\)_-integers_, which are ubiquitous in \(q\)-calculus, the representation theory of quantized enveloping algebras and quantum groups, and in the theory of crystal bases, amongst others [11; 12; 13; 14; 15]. We conjecture that these points characterize the extrema of our cost function. The conjecture is motivated by the size of the variety characterized by \(\
abla\widehat{C}=0\) together with the Pythagorean identities as computed by Bezout's Theorem and by the explicit computations summarized by Theorem 3.2. Definition 1.: For any complex \(q\
eq 1\) and any integer \(n\), the quantum integer or \(q\)-integer \([n]_{q}\) is defined by  
Figure 5:3  
In this setting, quantum integers appear in the coefficients \(\alpha_{x}(\theta)\). In particular, let \(\theta_{j}=\frac{\pi}{2n}p_{j}\) for any \(p_{j}\in\{0,1,\ldots,4n-1\}\), let \(\xi=e^{\frac{i\pi}{4n}}\) denote a primitive \(8n\)-th root of unity, and notice  
Figure 5:4  
We use the last identity to prove the existence of globally optimal parameters for our variational circuit. It is important to observe these guarantees are not typically offered by VQAs; for instance, QAOA can only guarantee such parameters _in the limit of infinite circuit depth_. We will need the following identities. Lemma 4.: If \(\xi=e^{\frac{i\pi}{4n}}\) denotes a primitive \(8n\)-th root of unity, then the following identities relating \(\xi\)-integers hold:  
Figure 5:5  
Proof. : The lemma follows from direct calculation. For example,  
Figure 5:6The second equality follows because \(\sin\big{(}n\cdot\frac{\pi}{4n}\big{)}=1/\sqrt{2}\) and \(\xi^{2n}=i\), so that \(\xi^{2n}-\xi^{-2n}=2i\). The last equality holds because \(\xi\) is an \(8n\)-th root of unity; in particular, \(\xi^{4 kn}=\xi^{-4 kn}\). Let \(\theta=\frac{\pi}{2n}p\) for some \(p\in\mathbb{Z}^{n}\). First, suppose \(p=2 nx^{\prime}\) for some \(x^{\prime}\in\{0,1\}^{n}\). Then, \(\widehat{C}(\theta)=0\) is a global minimum of \(\widehat{C}\colon\mathbb{R}^{n}\to\mathbb{R}\) if \(x^{\prime}\) satisfies \(Ax^{\prime}=b\); otherwise, \(\widehat{C}(\theta)=1\) is a global maximum of the cost function. Now assume \(p_{1}=\cdots=p_{n}=kn\) for some odd integer \(k\) and let \(\operatorname{rk}(A)\) denote the rank of \(A\) over \(\mathbb{F}_{2}\). In this case, \(\widehat{C}(\theta)=1-2^{-\operatorname{rk}(A)}\). Proof. : First, notice our cost function is non-negative; for any \(\theta\in\mathbb{R}^{n}\), we have  
Figure 5:7  
This follows from Relation (5), which writes \(|\psi(\theta)\rangle\) as a superposition over a tensor product of computational basis states with amplitudes given by \(\alpha_{x}(\theta)\). In addition, \(\widehat{C}\) is bounded above by \(1\) because each \(\alpha_{x}(\theta)^{2}\) is non-negative. This means \(0\leq\widehat{C}(\theta)\leq 1\) for every \(\theta\in\mathbb{R}^{n}\).