first-quantum-algorithms.Rmd

---
output:
  pdf_document: default
  html_document: default
---


# 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, name="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, name="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, name="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, name="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. 
```




## Phase estimation {#section:phaseestimation}

<!--
# TODO Improve QFT part with other non-Fourier transform (wavelet, fourier on groups..)
# It would be cool to have some non-trivial facts about the QFT 
# (like how to see it as a mapping between elements of a group to a Hilbert space).
# But also it would be even better to have more quantum transform, like the Wavelet transfrom.
# This can be really helpful in the context of group-theoretical machine learning.
# labels: good first issue, help wanted, enhancement
-->


```{theorem, phase-estimation, name="Phase estimation [@Kitaev1995QuantumProblem]"}
Let $U$ be a unitary operator with eigenvectors $\ket{v_j}$ and eigenvalues $e^{i \theta_j}$ for $\theta_j \in [-\pi, \pi]$, i.e. we have $U\ket{v_j} = e^{i \theta_j}\ket{v_j}$ for $j \in [n]$. For a precision parameter $\epsilon > 0$, there exists a quantum algorithm that runs in time $O(T(U)\log(\frac{n}{\varepsilon}))$ and with probability $1 - 1/poly(n)$ maps a state $\ket{\phi_i} = \sum_{j \in [n]} \alpha_j\ket{v_j}$ to the state $\sum_{j \in [n]} \alpha_j \ket{v_j}\ket{\bar{\theta_j}}$ such that $|\bar{\theta}_j - \theta_j| < \varepsilon$ for all $j \in [n]$.
```


```{theorem, phase-estimation-errors, name="Error and probability of failure of phase estimation [@NC02] Section 5.2 and [@nannicini2019fast]"}
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 [@NC02], there have been various improvements [@ahmadi2010quantum] 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$.
\paragraph{Remark.} Note that the same algorithm described in theorem \@ref(thm:phase-estimation) can be made ''consistent'', in the sense of [@ta2013inverting] and [@A12]. 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.








<!-- % We also describe another simple method of getting such consistent phase estimation, which is to combine phase estimation estimates that are obtained for two different precision values. Let us assume that the  -->
<!-- % eigenvalues for the unitary $U$ are $e^{2\pi i \theta_{i}}$ for $\theta_{i} \in [0, 1]$. First, we perform phase estimation with precision $\frac{1}{N_{1}}$ where $N_{1}=2^{l}$ is a power  -->
<!-- % of $2$. We repeat this procedure $O(\log N/\theta^{2})$ times and output the median estimate. If the value being estimated  -->
<!-- % is $\frac{\lambda + \alpha }{2^{l}}$ for $\lambda \in \Z$ and $\alpha \in [0,1]$ and $|\alpha - 1/2 | \geq \theta'$ for an explicit constant $\theta'$ (depending on $\theta$) then  -->
<!-- % with probability at least $1-1/\text{poly}(N)$ the median estimate will be unique and will equal to $1/2^{l}$ times the closest integer to $(\lambda+ \alpha)$.  -->
<!-- % In order to also produce a consistent estimate for the eigenvalues for the cases where the above procedure fails, we perform a second phase estimation with precision $2/3N_{1}$.  -->
<!-- % We repeat this procedure as above for $O(\log N/\theta^{2})$ iterations and taking the median estimate. The second procedure fails to produce a consistent estimate only  -->
<!-- % for eigenvalues $\frac{\lambda + \alpha }{2^{l}}$ for $\lambda \in \Z$ and $\alpha \in [0,1]$ and $|\alpha - 1/3 | \leq \theta'$ or $|\alpha - 2/3 | \leq \theta'$ for a suitable constant  -->
<!-- % $\theta'$. Since the cases where the two procedures fail are mutually exclusive, one of them succeeds with probability $1-1/\text{poly}(N)$. The estimate produced  -->
<!-- % by the phase estimation procedure is therefore deterministic with very high probability. In order to complete this proof sketch, we would have to give explicit values of the constants $\theta$ and $\theta'$  -->
<!-- % and the success probability, using the known distribution of outcomes for phase estimation.  -->


## Grover's algorithm, amplitude amplification and amplitude estimation

<!-- TODO: with high probability? how many other gates? -->

```{theorem, grover, name="Grover's algorithm"}
Let $N=2^n$ for $n>0$. 
Given quantum oracle access $O_x: \ket{i}\mapsto\ket{i}\ket{x_i}$ 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, thm-ampest-orig, name="Amplitude estimation, [@brassard2002quantum]"}
Given a quantum algorithm $$A:\ket{0} \to \sqrt{p}\ket{y,1} + \sqrt{1-p}\ket{G,0}$$ where $\ket{G}$ 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, thm-ampest-orig-precise, name="Amplitude estimation [@brassard2002quantum], formulation of [@montanaro2015quantum]"} 
There is a quantum algorithm called amplitude estimation which takes as input one copy of a quantum state $\ket{\psi}$, a unitary transformation $U=2\ket{\psi}\bra{\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=\braket{\psi|P|\psi}$, 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 [@brassard2002quantum]  [@grover2005fixed], which was then optimized in [@yoder2014fixed]. These versions do not require to know the number of iterations in advance. These results foundamentally leverage the observation reprted in Proposition \@ref(prp:qesa-observation).

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 [@NC02]) [@grinko2019iterative], [@aaronson2020quantum]. 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, amp-amp-est-simple, name="Amplitude amplification and estimation [@kerenidis2017quantumsquares]" } 
If there is a unitary operator $U$ such that $U\ket{0}^{l}= \ket{\phi} = \sin(\theta) \ket{x, 0} + \cos(\theta) \ket{G, 0^\bot}$ then  $\sin^{2}(\theta)$ can be estimated to multiplicative error $\eta$ in time $O(\frac{T(U)}{\eta \sin(\theta)})$ and $\ket{x}$ can be generated in expected time $O(\frac{T(U)}{\sin (\theta)})$ where $T(U)$ is the time to implement $U$.
```