Understanding mathematics of Grover’s algorithm
Paweł J. Szabłowski
Abstract
Abstract We analyze the mathematical structure of the classical Grover’s algorithm and put it within the framework of linear algebra over the complex numbers. We also generalize it in the sense, that we are seeking not the one ‘chosen’ element (sometimes called a ‘solution’) of the dataset, but a set of m such ‘chosen’ elements (out of $$n>m)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>></mml:mo><mml:mi>m</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math> . Besides, we do not assume that the so-called initial superposition is uniform. We assume also that we have at our disposal an oracle that ‘marks,’ by a suitable phase change $$\varphi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>φ</mml:mi></mml:math> , all these ‘chosen’ elements. In the first part of the paper, we construct a unique unitary operator that selects all ‘chosen’ elements in one step. The constructed operator is uniquely defined by the numbers $$\varphi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>φ</mml:mi></mml:math> and $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>α</mml:mi></mml:math> which is a certain function of the coefficients of the initial superposition. Moreover, it is in the form of a composition of two so-called reflections. The result is purely theoretical since the phase change required to reach this heavily depends on $$\alpha $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>α</mml:mi></mml:math> . In the second part, we construct unitary operators having a form of composition of two or more reflections (generalizing the constructed operator) given the set of orthogonal versors. We find properties of these operations, in particular, their compositions. Further, by considering a fixed, ‘convenient’ phase change $$\varphi ,$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>φ</mml:mi><mml:mo>,</mml:mo></mml:mrow></mml:math> and by sequentially applying the so-constructed operator, we find the number of steps to find these ‘chosen’ elements with great probability. We apply this knowledge to study the generalizations of Grover’s algorithm ( $$m=1,\phi =\pi $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>ϕ</mml:mi><mml:mo>=</mml:mo><mml:mi>π</mml:mi></mml:mrow></mml:math> ), which are of the form, the found previously, unitary operators.