Extended Quantum Computing Patterns

Increase the probability of finding a solution

For a specific indicator function \(f\) the corresponding function table may list all possible solutions of a problem, i.e. \(f(x)=1 \Leftrightarrow x\) is a solution to the problem.
When the corresponding state is measured, a solution can be found with a certain probability. Since measuring destroys the state, the computation has to be repeated if no solution is found by the measurement in order to be able to do another measurement of the state. To keep computational costs low, a mechanism without measurements is required.

–

The overall state is transformed such that the probability of measuring certain values of interest increases with every iteration by modifying their amplitude (Brassard et al. 2002). This is done via the help of a phase shift \(S_G^\pi\), which changes the sign of the phase of elements in the set of solutions \(G\) while all other elements remain unchanged. Another phase shift that is used is \(S_0^\pi\) which changes only the sign of the zero state \(\newcommand{\state}[1]{{\left| #1 \right>}} \state{0}\). Suppose there is an algorithm \(U\) for computing approximate solutions (without any measurements). The following unitary operation can be defined:

If the success probability of the algorithm \(U\) is \(t\), the average amount of iterations required to find a solution is \(1/t\). It is assumed that \(\newcommand{\state}[1]{{\left| #1 \right>}}U\state{0}\) has a non-zero amplitude in \(G\), otherwise, there cannot be a speedup. If U indeed has this property, the above-defined unitary operation \(Q\) will create a solution within \(O(\sqrt{1/t})\) iterations, i.e., a quadratic speedup can be achieved. The amount of iterations to be realized by \(Q\) is about \(\newcommand{\state}[1]{{\left| #1 \right>}} \frac{\pi}{4} \frac{1}{P_G U \state{0}}\), where \(P_G\) is the projection onto the subspace spanned by \(G\).

The probability of measuring a solution is increased.

–

A Function Table \(S_G^\pi\) which is also a special case of a Phase Shift is used within the unitary operation \(Q\). A unitary operation that implements amplitude amplifications can be provided as an Oracle.

Examples of algorithms that use amplitude amplification are the algorithms of Grover and Simon, as well as the HHL algorithm (Harrow, Hassidim and Lloyd 2009). Amplitude amplification is also used in the state preparation algorithm of (Sanders et al. 2019). In (Brassard et al. 2002), more algorithms making use of amplitude amplification are discussed.

Grover's Algorithm (PlanQK) HHL Algorithm (PlanQK)