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?

  • $\begingroup$ Are your variables supposed to be binary? And you're computing modulo 2? $\endgroup$
    – DaftWullie
    Apr 27 at 6:36
  • $\begingroup$ The variables are all binary $\endgroup$ Apr 27 at 6:59
  • $\begingroup$ 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? $\endgroup$ 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.

However, just because you can do this, doesn't mean that you should. Computing the solution to this classically is linear in the number of variables. You should not be solving it by testing all possible examples of the input variables. Grover is usually applied to cases where the classical computation requires exponentially many steps. I think it is extremely unlikely that Grover would give you a computational advantage in this case.

the Grover oracle may be implemented as follows: enter image description here 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.

  • $\begingroup$ I know this is a big ask, but could you show an example circuit? I'm not sure how to implement that multiplication. I'm aware that this is not ideal for Grover's search, I'm just using it as a toy example. $\endgroup$ Apr 27 at 14:42
  • 1
    $\begingroup$ @QuantumLearner My first reactions was "no way!" then realised that because everything is done modulo 2, it's not actually as awful as I first thought... $\endgroup$
    – DaftWullie
    Apr 27 at 15:46
  • $\begingroup$ This is a huge help, thank you $\endgroup$ Apr 27 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.