Try   HackMD

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
xi
can be described by the unitary operation

Ox:|i,b|i,bxi

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.

UTOxUT1OxOxU1OxU0|00

Quantum Fourier Transform

DFT Recap

Given a vector

x of dimension
2N
with components
xj
, the Discrete Fourier Transform of a vect
x
is avector
y
of dimension
2N

yk=j=02N1xje2ipijk/2N

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Matrix-vector multiplication takes

O(22N) steps. The Fast Fourier Transform algorithm reduces this to
O(N2N)
, 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
2N
with components
xj
. Take the computational basis:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

The Fourier transform of state

|x is a state
|y
, i.e. vector of
2N
components
yk

|y=k=02N1yk|k=λ=02N1j=02N1e2iπjk2Nxj|j

1 qubit case

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Notice that the

ωNj in (
|0>ωNj1>
) 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×(N1)/2 gates to implement DFT

Runtime analysis

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  • 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(N2)
    while the FFT takes about
    O(N2N)
    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

λ=exp(2πϕ) associated to a given eigenvector
|u
of a unitary operator
U

Two assumptions uynderly the QPE routine:

  • Implement the gate
    Uk
    in a controlled way with states from
    t
    qubit register and non-negative
    K
  • Prepare the state
    |u
    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
    |u
    . The lenght will depend on the problem under consideration

The number

ϕ=0.ϕ0ϕ1ϕ2ϕ3 can be expressed in binary form:

ϕ=j=0+ϕj2j1

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

The QFT needs

O(t2) gates. The number of needed gates is polynomial in the number of bits
ϕ
. It can be shown that if the binary fraction expression of
ϕ
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 ?

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  • Given a set of
    N=2n
    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
    N
    queries
    thanks to Grover's algorithm

Grover's algorithm

Les us assume that the database of size

N=2n can be indexed by
n
qubits. Starting with:

|++++=Hn|0000=12n(|0000+|0001+|1110+|1111)

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

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

A signle Grover iteration consists of 4 steps:

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

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

Geometric interpretation

Given that

m<<N=2n entries are solutions to the search problem, a Grover iteration can be seen as a small rotation in the
2
-dimensional subspace spanned by
|ϕYES
and
|ϕNO

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →