Тематический план

  • Общее

    Свернуть всё Развернуть всё

  • 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

    • Файл icon
      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''.
    • Форум icon
      Discussion Форум

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

    • Файл icon
      Shor's factorization algorithm Файл

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

    • Файл icon
      Continued fractions Файл
      • in Czech
      • from the lecture Number Theory and RSA
      • the relevant example is translated in the file above
    • Форум icon
      Discussion Форум

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

    • Файл icon
      The Discrete Fourier Transform Файл

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

    • Файл icon
      Quantum decomposition of the DFT Файл
    • Файл icon
      Examples of DFT Файл
    • Форум icon
      Discussion Форум
    • Файл icon
      DFT as phase estimation Файл

      An alternative point of view of Shor's algorithm

  • Complex projective line representations

    • Файл icon
      Complex projective line Файл

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

    • Файл icon
      The Hopf fibration Файл

    • An impressive visualization of the Hopf fibration

    • Форум icon
      Discussion Форум

  • Unitary operators as rotations

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

    • Файл icon
      Geometry of unitary operators Файл

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

    • Файл icon
      Quaternions Файл

    • 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

    • Форум icon
      Discussion Форум

  • Extended Euler's formula and the AXBXC decomposition

  • Quantum Key Sharing principle

  • Tutorial 2023 examples

  • Tutorial 2022 examples

  • Tasks for credit