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 , 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 and output can be described by the unitary operation
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.
DFT Recap
Given a vector of dimension with components , the Discrete Fourier Transform of a vect is avector of dimension
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 steps. The Fast Fourier Transform algorithm reduces this to , which renders DFT computable in linear time
This is done by exploiting symmetry of the DFT matrix representation
Ket Notation
A state on qubits corresponds to a vector of dimension with components . 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 is a state , i.e. vector of components
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 in () 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 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:
- Last reversed-ordering step: swap gates, each needing 3 CNOTs
- Then the QFT on qubits has a runtime of while the FFT takes about 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 associated to a given eigenvector of a unitary operator
Two assumptions uynderly the QPE routine:
- Implement the gate in a controlled way with states from qubit register and non-negative
- Prepare the state 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 gate. The length of this register determines the accuracy of the phase estimation
- Register 2: Used to prepare the state . The lenght will depend on the problem under consideration
The number can be expressed in binary form:
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 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 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 databases entries, with 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 querie, and queries in the worst case
- In the quantum case, this can be sped up to abour queries thanks to Grover's algorithm
Grover's algorithm
Les us assume that the database of size can be indexed by qubits. Starting with:
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:
- Phase Oracle
- H wall
- Phase Gate
- 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 , 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 entries are solutions to the search problem, a Grover iteration can be seen as a small rotation in the -dimensional subspace spanned by and
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 →