Topic outline
Mach-Zehnder interferometer
Two historically important papers. The paper of Einstein, Podolski and Rosen gave rise to the term "EPR pair"
A prominent mathematician and logician (and philosopher) reflects on the status of the quantum mechanics
Basics of Complex Linear Algebra
For last dozen of minutes the whiteboard is not visible. My apology. You can at least follow the commentary with the whiteboard open as the pdf below.
Reflection on the Dirac notation for a mathematical purist.
Deutsch-Jozsa algorithm
Left board
Right board
Left board
Right board
Universal set of gates
Lecture notes implicitly invite the following tasks:
- Verify the function of the circuit ABC for the one-qubit controlled operator
- Verify the equivalence of two distinct ways of multiplication by e^{i\alpha}
- Verify the function of two-controlled operator
- Verify the equivalence of the two-controlled gate and the one-controlled gate with the CNOT
- Verify the ``control by zero'' with help of two X-gates
- Try all square roots of negation
- (You can also try other functions applied to an operator. For instance, what e^{i A}, where A is a normal operator looks like?)
- Verify the function of the two-level operator U and its equivalence with the uncontrolled operator M
- Make sure you understand the transformation of the complicated two-level operator to the simple one
- Make sure you understand the ``unitary Gaussian elimination''.
Additional explanation
Shor's algorithm
At the moment we can theoretically build a circuit composed of basic small gates (single cubic and CNOT) for any matrix. (Except for the as yet unproven theorem ABC necessary for the construction of a single-cubic controlled operator.) We can therefore return to the question of for which matrices there is a "small" circuit.
To obtain sufficient motivation for some of the following theoretical passages (especially for the quantum Fourier transform), we will now look at the most important algorithm: Shor's algorithm for factorization.
A note on Fermat's factorization
- Try to decompose some composite number by Fermat's test. E.g. 21. We look for two squares equivalent modulo 21. We can succesively add squares to 21 and see when we get another square. We have 21 + 22 = 52. Hence 21 = (5 + 2) (5-2).
- Order of 2 mod 21 is 6. Thus (23 + 1) (23-1) = 9x7 = 63 = 0 mod 21. Nine is not a divisor, but it is a factor of the factorized number. The divisor 3 is thus found by Euclid's algorithm.
Think carefully about what the operator W looks like and how its construction is related to the reversible implementation of a classical algorithm.
- Is it really a permutation of basis elements?
- How big is the circuit for W (what number of elementary gates do we need)? Is it (measured as a function of m and n) polynomial? Quadratic? Or even linear?
You can skip success estimates when reading the lecture notes. Try to imagine an algorithm for factorization of 15. The group of invertible elements modulo 15 has order 8, so all elements have the order of the power of two. For M = 16, therefore, there is an equality in the approximation (*) in this case.
- in Czech
- from the lecture Number Theory and RSA
- the relevant example is translated in the above chapter about Shor's algorithm
Discrete Fourier transform and its quantum decomposition
The complexity of Shor's algorithm crucially depends on the circuit for the Fourier transform.
We could accept the matrix of the Fourier transform as given, but we will use the opportunity to explain the principle of the discrete Fourier transform as a decomposition of a complex function (mapping) over a group into the base of periodic functions (or the base of characters, or the Fourier base).
Linear algebraic definition of the basis of characters, or the Fourier basis.
Complex projective line representations
video lecture
Annotated lecture notes
Notes
Optional additional material on the Hopf fibration, which is way of representation of the three dimensional real sphere 𝕊3 (that is, the surface of the four-dimensional ball) in three dimensions.
An impressive visualization of the Hopf fibration
Unitary operators as rotations
(video lecture)
Note a mistake: "= ijk" is missing in the defining relation of quaternion units.
Action of unitary operators on qubits can be understood as rotations of the Bloch sphere representing qubits.
A basic tool in the above representation are properties of quaternions.
The inscription on the Broom Bridge in Dublin where quaternions were born.
Niles Johnson's lecture on the stereographic projection (slightly different from ours), Hopf fibration and quaternions.
Remarkable interactive visualization of quaternions and the stereographic projection
Extended Euler's formula and the AXBXC decomposition
The theorem about the AXBXC decomposition completes the construction of a circuit for a general unitary matrix using only CNOT and single qubit operators.
Quantum Key Sharing principle
The famous protocol BB84 (named after a paper by Charles Bennett and Gilles Brassard from 1984) can serve as a motivation for the concept of quantum entropy and for more advanced parts of the quantum information theory.
The protocol allows quantum key sharing whose security is based solely on principles of quantum mechanics, unlike classical protocols which depend on complexity assumptions like P ≠ NP. The above mentioned theory is needed for the proof of the security claim.
Lecture slides
Notes
Quantum entropy
A scientific paper by Peter Shor and John Preskill, proving security of BB84.
Tutorial examples
Here, the examples from the tutorials will be published.
If you would like to play with the quantum circuits a bit more, you may find the following links useful:
- https://algassert.com/quirk - a quantum circuit simulator, you may play with some predefined examples, and some very nontrivial operations are implemented there as basic gates
- https://quantum-computing.ibm.com/ - after registering, you may use IBM's quantum computers (real quantum hardware and there is a free tier), as such you can see the problems of contemporary quantum computers, not as powerful as quirk, however, may still be useful
- there are many more (both simulators and quantum computers) e.g. http://www.quantumplayground.net/#/home https://www.rigetti.com/ however, I do not have much experience with those
List of topics
The topic will be chosen at random, and further specified if needed. The examination will be oral after preparation.