ABSTRACT
We describe the Grover's amplification algorithm. We represent n state by a superposition, each state has the same real positive amplitude. A parallel computation is applied to all the n states, and the state with the solution is marked by a minus sign, the amplitude is now negative. We then apply a linear operation that is based on Householder reflection, by the reflection the value of the marked amplitude grows linearly. For dimensions higher than four, the operations of marking and Householder reflection must be repeated https://www.w3.org/1998/Math/MathML"> n https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math5_1.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> times, since at each step the amplitude only grows linearly. After https://www.w3.org/1998/Math/MathML"> n https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781003374404/4745344c-4074-4386-85e6-ca8a3849de1f/content/math5_2.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> steps we measure the solution. The algorithm guarantees us a quadratic speed up over a classical computer that would require n steps. Grover's amplification algorithm is optimal, one can prove that a better algorithm cannot exist. We will demonstrate the principles of Grover's amplification using the matrix notation using NumPy. Then we explain how to represent the algorithm with quantum gates by a qiskit example of three qubits representing eight states using one and two rotations.
