3
$\begingroup$

I am currently working intensively on the Grover algorithm and have understood the individual "building blocks" of the algorithm so far. There are also references in the literature to Nielsen, e.g. an implementation example, but only for 4 elements.

My question is, of a more general nature. How would you actually implement a gate for more elements than just 4? Is there a general approach? The Grover operator G is composed of the n-fold Hadamard transformation and of the conditional phase change and a renewed H transformation. If I have a unitary matrix, eg. the one for the phase shift in the Grover operator, how can I convict this common unitary matrix?

I summarize briefly:

  1. How do you convert the gates in the Grover algorithm for N bits? Is there a general derivation somewhere?

  2. How can a unitary matrix e.g. the phase shift $ 2 |0\rangle \langle 0| -I $ realize as a gate? Are there any general phrases that might somehow express that?

  3. What does a general construction procedure look like to create a gate from a unitary matrix?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Consider this paper where an implementation of Grover's algorithm is given for three qubits.

The only difficulty when extending to $n$ qubits is that you need a $C^n\operatorname{NOT}$ gate (bit flip oracle) or a $C^{n-1}Z$ gate (phase oracle). The phase oracle is made trivially by combining a $C^{n-1}\operatorname{NOT}$ gate with two Hadamard gates. The multiple controlled $\operatorname{NOT}$ gate is constructed from different Toffoli-gates.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your answer. So how the oracle is composed of Toffoli gates, I roughly understood. But what about the phase oracle? How would this look like Toffoli Gate? $\endgroup$
    – user4961
    Commented Mar 15, 2019 at 17:11
  • $\begingroup$ Apply a Hadamard gate on the last qubit, apply the multiple controlled $\operatorname{NOT}$ and then another Hadamard gate on the last qubit. $\endgroup$
    – nippon
    Commented Mar 15, 2019 at 17:15
  • $\begingroup$ Do you have any reference to the C-Not gate, that you mention a few more parts, where you can read this? There I would be interested in the construction in detail. I know the C-Not gate, but I do not know the n-fold, is there a good source in which you can read this? $\endgroup$
    – user4961
    Commented Mar 20, 2019 at 8:44
  • $\begingroup$ See this question quantumcomputing.stackexchange.com/questions/2177/… $\endgroup$
    – nippon
    Commented Mar 20, 2019 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.