Section outline

  • General

    Collapse all Expand all

  • Interpretation of Quantum Mechanics

  • Mach-Zehnder interferometer

  • Basics of Complex Linear Algebra

  • Postulates of Quantum Mechanics

  • Introduction into tensor products

  • Deutsch-Jozsa algorithm

  • Reversible computation

  • Universal set of gates

    • Universal set of gates File

    • 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''.

  • 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.

    • Shor's factorization algorithm File

    • 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.

    • Continued fractions File
      • in Czech
      • from the lecture Number Theory and RSA
      • the relevant example is translated in the file above
    • Discussion Forum

  • 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).

    • The Discrete Fourier Transform File

      Linear algebraic definition of the basis of characters, or the Fourier basis.

    • Quantum decomposition of the DFT File
    • Examples of DFT File
    • Discussion Forum
    • DFT as phase estimation File

      An alternative point of view of Shor's algorithm

  • Complex projective line representations

    • Complex projective line File

    • 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.

    • The Hopf fibration File

    • An impressive visualization of the Hopf fibration

  • Unitary operators as rotations

    • Action of unitary operators on qubits can be understood as rotations of the Bloch sphere representing qubits.

    • Geometry of unitary operators File

    • A basic tool in the above representation are properties of quaternions.

    • Quaternions File

    • The inscription on the Broom Bridge in Dublin where quaternions were born.the-plaque-upon-the-bridge.jpg

    • 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

      https://eater.net/quaternions

  • 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.

    • Extended Euler's formula and the decomposition AXBXC File

  • Quantum Key Sharing principle

    • We conclude the course with a description of the famous protocol BB884 (named after a paper by Charlese Bennetta and Gilles Brassarda from 1984). 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.

      Full proof of security requires the concept of quantum entropy and more advanced parts of the quantum information theory.

    • Stopa a pozitivní operátory File
    • Description of the BB84 protocol File
    • Mixed states File
    • Quantum entropy File
    • Holevo bound File

  • Tutorial 2023 examples

  • Tutorial 2022 examples

  • Tasks for credit