# How could one implement a circuit using Grover's algorithm to solve a linear system of equations?

Given the following system:

$$\begin{bmatrix}0 & 1 & 0\\1 & 1 & 1\\1 & 0 & 1\end{bmatrix} \begin{bmatrix}s_2\\ s_1\\ s_0\end{bmatrix} = \begin{bmatrix}0\\ 0\\ 0\end{bmatrix}$$

How could one implement a circuit such that the output is $$|1\rangle$$ when $$|s_0\rangle$$, $$|s_1\rangle$$, and $$|s_2\rangle$$ are solutions? Is this possible using Grover's algorithm and without hardcoding the solutions?

• Are your variables supposed to be binary? And you're computing modulo 2? Apr 27 at 6:36
• The variables are all binary Apr 27 at 6:59
• Close voters: It seems the question did not "need details for clarity" because there's 3 answers and one was accepted. Perhaps write a comment telling us why you think it needs more clarity next time? May 8 at 21:40

You certainly could use Grover's search. You would create 2 registers. This first, of 3 qubits, would effectively store the $$\{s_0,s_1,s_2\}$$. This is the standard register for Grovers on which you apply the Grover iterator. Then, you'd have a second register of at least 3 qubits. You construct the search oracle by evaluating the matrix multiplication on the second register (I say that you need at least 3 qubits, because I haven't checked what you need to implement the calculation reversibly). Then you do a multi-controlled-phase gate which introduces a -1 phase only if all the qubits in the second register were in the 0 state (matching your target on the right-hand side). Then you reverse the computation of the matrix multiplication.
the Grover oracle may be implemented as follows: To understand how this works, focus on the first 3 steps. Look at the pattern of the targets along a given ancilla and how it corresponds to a row in your target matrix.