EPIQUANTI : Quantum Fourier Transform

Lien de la note Hackmd

Overview

Three kind of quantum advantage

• Oracle-based
• Adiabatic optimisation
• Simulation of quantum systems

Quer model and Oracles

Oracle: boite noire qui repond oui ou non a une question

In the query model, you are given access to some function $f$, giving a Y/N answer to all inputs in polynomial time. This function is called the blac-box, or the oracle. An oracle with input $i$ and output $x_i$ can be described by the unitary operation

\[O_x:\vert i,b\rangle\to\vert i, b\otimes x_i\rangle\]

By linearity, this oracle gate can be applied to quantum superpositions. In order to measure the time complexity of an algorithm, one determines the number of queries it makes to the oracle.

\[U_TO_xU_{T-1}O_x\dots O_xU_1O_xU_0\vert 0\dots0\rangle\]

Quantum Fourier Transform

DFT Recap

Given a vector $x$ of dimension $2^N$ with components $x_j$, the Discrete Fourier Transform of a vect $x$ is avector $y$ of dimension $2^N$

\[y_k=\sum_{j=0}^{2^N-1}x_je^{2ipi jk/2^N}\]

Matrix-vector multiplication takes $O(2^{2N})$ steps. The Fast Fourier Transform algorithm reduces this to $O(N2^N)$, which renders DFT computable in linear time

This is done by exploiting symmetry of the DFT matrix representation

Ket Notation

A state on $N$ qubits corresponds to a vector $x$ of dimension $2^N$ with components $x_j$. Take the computational basis:

The Fourier transform of state $\vert x\rangle$ is a state $\vert y\rangle$, i.e. vector of $2^N$ components $y_k$

\[\vert y\rangle = \sum_{k=0}^{2^N-1}y_k\vert k\rangle = \sum_{\lambda=0}^{2^N-1}\sum_{j=0}^{2^N-1}e^{2i\pi j\frac{k}{2^N}}x_j\vert j\rangle\]

1 qubit case

Exploiting the symmetry

Let us see how the QFT acts upon a computational basis vector. By linearity of QM, this will suffice for any quantum state

Notice that the $\omega_{N_j}$ in ($\vert 0\gt\omega_{N_j}1\gt$) depends on the integer value, i.e. on the value of all the qubits

This is implemented by performing controlled rotations on each qubit. The number of controlled rotations is the number of remaining qubits in the QFT.

This means that one needs around $N\times (N-1)/2$ gates to implement DFT

Runtime analysis

• Number of gates: $N(N+1)/2$
• Last reversed-ordering step: $sN/2$ swap gates, each needing 3 CNOTs
• Then the QFT on $N$ qubits has a runtime of $O(N^2)$ while the FFT takes about $O(N2^N)$ steps. So we have obtainend an exponential speed-up

Quantum Phase Estimation

Goal and assumptions

The most salient application of QFT is the Quantum Phase Estimation routine, which is the workhorse behind several quantum algorithms featuring exponential speed-up, such as Shor’s algorithm and Quantum Matrix Inversion

Goal: Estimate the eigenvalue $\lambda=\exp(2\pi\phi)$ associated to a given eigenvector $\vert u\rangle$ of a unitary operator $U$

Two assumptions uynderly the QPE routine:

• Implement the gate $U^k$ in a controlled way with states from $t$ qubit register and non-negative $K$
• Prepare the state $\vert u\rangle$ as input. This can be relaxed at the expense of introducing randomness

Circuit for QPE

The QPE algorithm ises 2 different qubit registers

• Register 1: necessary to implement the controlled $U$ gate. The length of this register determines the accuracy of the phase estimation
• Register 2: Used to prepare the state $\vert u\rangle$. The lenght will depend on the problem under consideration

The number $\phi = 0.\phi_0\phi_1\phi_2\phi_3\dots$ can be expressed in binary form:

\[\phi = \sum_{j=0}^{+\infty}\phi_j2^{-j-1}\]

The QFT needs $O(t^2)$ gates. The number of needed gates is polynomial in the number of bits $\phi$. It can be shown that if the binary fraction expression of $\phi$ is truncated to some bit length the error can be controlled with logarithmic overhead

Amplitude Amplification

Classical motivation

Given the promise that ther is only one tagged marble in this jar containing $N$ crystal marbles, how many times, on average, do you need to randomly draw a marble before finding it ?

• Given a set of $N=2^n$ databases entries, with $n$ the number of bits used to denote the address of an entry, and no knowledge about the database searching for a particular entry takes on average $N/2$ querie, and $N$ queries in the worst case
• In the quantum case, this can be sped up to abour $\sqrt{N}$ queries thanks to Grover’s algorithm

Grover’s algorithm

Les us assume that the database of size $N=2^n$ can be indexed by $n$ qubits. Starting with:

\[\vert +++\dots+\rangle = H^{\otimes n}\vert 000\dots0\rangle=\frac{1}{\sqrt{2^n}}(\vert 000\dots0\rangle+\vert 000\dots1\rangle + \vert 111\dots0\rangle + \vert 111\dots1\rangle)\]

The problem is to find indices of the states that correspon to a ‘tagged’ solution.

GA finds thos indexes by successive applications of an oracle gate (which can identify such a solution) and a diffusion gate

A signle Grover iteration consists of 4 steps:

1. Phase Oracle
2. H wall
3. Phase Gate
4. H wall

The oracle gate

A phase oracle checks, via the black-box function $f$, whether the entry is part of the solution space and, if it is, it flips te sign of the corresponding index. otherwise it does nothing.

Setps 2, 3,and 4 are collectively known as the mean-reflection operation

Geometric interpretation

Given that $m\lt\lt N=2^n$ entries are solutions to the search problem, a Grover iteration can be seen as a small rotation in the $2$-dimensional subspace spanned by $\vert\phi_{YES}\rangle$ and $\vert\phi_{NO}\rangle$