Chapter 4 Review of famous quantum algorithms

In this chapter we will explore some introductory quantum algorithms. Some of them are not particularly related to data analysis or machine learning, but given their potential to help us better understand the model of quantum computation that we adopt, we decided it was important to report them here. Others will prove to be really useful subroutines for the quantum machine learning practitioner.

Definition 4.1 (Constant function) A function \(f :\{0,1\}^n \mapsto \{0,1\}\) is constant if \(f(x)=0 \forall x \in \{0,1\}^n\) or \(f(x)=1 \forall x \in \{0,1\}^n\).
Definition 4.2 (Balanced function) A function \(f :\{0,1\}^n \mapsto \{0,1\}\) is balanced if \(f(x)=0\) for half of the inputs and \(f(x)=1\) for the other half.
Theorem 4.1 (Deutsch-Josza) Assume to have quantum access to a unitary \(U_f\) that computes the function \(f :\{0,1\}^n \mapsto \{0,1\}\), which is either constant or balanced. There is a quantum algorithm that decides which is the case with probabiliy \(1\), using \(U_f\) only once and using \(O(\log(n))\) other gates.
Theorem 4.2 (Bernstein-Vazirani) Assume to have quantum access to a unitary \(U_f\) that computes the function \(f :\{0,1\}^n \mapsto \{0,1\}\), which computes \(f(x \cdot a) = (x,a) = ( \sum_i^n x_i a_i )\mod 2\) for a secret string \(a \in \{0,1\}^n\). There is a quantum algorithm that learns \(a\) with probability \(1\), using \(U_f\) only once and \(O(\log(n))\) other gates.

4.1 Phase estimation

Theorem 4.3 (Phase estimation [26]) Let \(U\) be a unitary operator with eigenvectors \(|v_j\rangle\) and eigenvalues \(e^{i \theta_j}\) for \(\theta_j \in [-\pi, \pi]\), i.e. we have \(U|v_j\rangle = e^{i \theta_j}|v_j\rangle\) for \(j \in [n]\). For a precision parameter \(\epsilon > 0\), there exists a quantum algorithm that runs in time \(O(\frac{T(U)\log(n)}{\epsilon}))\) and with probability \(1 - 1/poly(n)\) maps a state \(|\phi_i\rangle = \sum_{j \in [n]} \alpha_j|v_j\rangle\) to the state \(\sum_{j \in [n]} \alpha_j |v_j\rangle|\bar{\theta_j}\rangle\) such that \(|\bar{\theta}_j - \theta_j| < \epsilon\) for all \(j \in [n]\).
Theorem 4.4 (Error and probability of failure of phase estimation [1] Section 5.2 and [27]) Let \(0.a=a_1, \dots a_q\) be the output of phase estimation when applied to an eigenstate with phase \(\phi\). If we use \(q+\lceil\log(2+\frac{1}{2\delta})\rceil\) qubits of precision, the first \(q\) bits of \(a\) will be accurate with probability at least \(1-\delta\), i.e. \[Pr[|\phi - \sum_{j=1}^q a_j2^{-j}| \leq 2^{-q}] \geq 1-\delta\]
While the standard implementation of phase estimation is based on the quantum Fourier transform (QFT) circuit [1], there have been various improvements [28] which try to soften the dependence on the QFT circuit, while retaining the accuracy guarantees offered by the QFT in estimating the angles \(\theta_j\).

Note that the same algorithm described in theorem 4.3 can be made ‘’consistent’’, in the sense of [29] and [30]. While in the original formulation of phase estimation two different runs might return different estimates for \(\overline{\theta}_j\), with a consistent phase estimation this estimate is fixed, with high probability. This means that the error between two different runs of phase estimation is almost deterministic.

4.2 Grover’s algorithm, amplitude amplification and amplitude estimation

Theorem 4.5 (Grover’s algorithm) Let \(N=2^n\) for \(n>0\). Given quantum oracle access \(O_x: |i\rangle\mapsto|i\rangle|x_i\rangle\) to a vector \(x=\{0,1\}^N\) where only one element of \(x\) is 1, there is a quantum algorithm that finds the index of that element using \(O_x\) only \(O(\sqrt{N})\) times.

This problem can be generalized to the case where there are multiple elements “marked” as good solutions. If we know the number of solutions in advance, the algorithm can be modified such that it fails with probability 0.

Amplitude amplification and amplitude estimation are two of the workhorses of quantum algorithms.

Theorem 4.6 (Amplitude estimation, [31]) Given a quantum algorithm \[A:|0\rangle \to \sqrt{p}|y,1\rangle + \sqrt{1-p}|G,0\rangle\] where \(|G\rangle\) is some garbage state, then the amplitude estimation algorithm, using exactly \(P\) iterations of the algorithm \(A\) for any positive integer \(P\), outputs \(\tilde{p}\) \((0 \le \tilde p \le 1)\) such that \[ |\tilde{p}-p|\le 2\pi \frac{\sqrt{p(1-p)}}{P}+\left(\frac{\pi}{P}\right)^2 \] with probability at least \(8/\pi^2\). If \(p=0\) then \(\tilde{p}=0\) with certainty, and if \(p=1\) and \(P\) is even, then \(\tilde{p}=1\) with certainty.
Theorem 4.7 (Amplitude estimation [31], formulation of [32]) There is a quantum algorithm called amplitude estimation which takes as input one copy of a quantum state \(|\psi\rangle\), a unitary transformation \(U=2|\psi\rangle\langle\psi|-I\), a unitary transformation \(V=I-2P\) for some projector \(P\), and an integer \(t\). The algorithm outputs \(\tilde{a}\), an estimate of \(a=\langle\psi|P|\psi\rangle\), such that: \[|\tilde{a}-a| \leq 2\pi\frac{\sqrt{a(1-a)}}{t} + \frac{\pi^2}{t^2}\] with probability at least \(8/\pi^2\), using \(U\) and \(V\) \(t\) times each. If \(a=0\) then \(\tilde{a}=0\) with certainty, and if \(a=1\) and \(t\) is even, then \(\tilde{a}=1\) with certainty.

In the original version of the Grover’s algorithm we assume to know the number of marked elements, and therefore we can derive the correct number of iterations. Later on, a fixed-point version of amplitude amplification was proposed [31] [33], which was then optimized in [34]. These versions do not require to know the number of iterations in advance. These results foundamentally leverage the observation reprted in Proposition 5.1.

Recently, various researches worked on improvements of amplitude estimation by getting rid of the part of the original algorithm that performed the phase estimation (i.e. the Quantum Fourier Transform [1]) [35], [36]. As the QFT is not a NISQ subroutine, these results bring more hope to apply these algorithms in useful scenarios in the first quantum computers.

Perhaps a simpler formulation, which hides the complexity of the low-level implementation of the algorithm, and is thus more suitable to be used in quantum algorithms for machine learning is the following:

Lemma 4.1 (Amplitude amplification and estimation [9]) If there is a unitary operator \(U\) such that \(U|0\rangle^{l}= |\phi\rangle = \sin(\theta) |x, 0\rangle + \cos(\theta) |G, 0^\bot\rangle\) then \(\sin^{2}(\theta)\) can be estimated to multiplicative error \(\eta\) in time \(O(\frac{T(U)}{\eta \sin(\theta)})\) and \(|x\rangle\) can be generated in expected time \(O(\frac{T(U)}{\sin (\theta)})\) where \(T(U)\) is the time to implement \(U\).
Theorem 4.8 (Variable Time Search [37]) Let \(\mathcal A_1, \ldots, \mathcal A_n\) be quantum algorithms that return true or false and run in unknown times \(T_1, \ldots, T_n\), respectively. Suppose that each \(\mathcal A_i\) outputs the correct answer with probability at least \(2/3\). Then there exists a quantum algorithm with success probability at least \(2/3\) that checks whether at least one of \(\mathcal A_i\) returns true and runs in time \[\widetilde O\left(\sqrt{T_1^2+\ldots+T_n^2}\right).\]