CmpE 598 Sp.Tp. Quantum Algorithms  2019 Spring

Instructor: 

Course Schedule: 

TTT 235 BM A6 | BM A6 | BM A6

Course Program: 

 

The field of quantum computation is based on the usage of the non-classical features of quantum systems to obtain efficient solutions for difficult computational problems. There have been some significant advances in this regard, Shor's polynomial time factorization algorithm (with its important implications for cryptography) being the most notable one. This course is aimed at computer scientists and engineers who need not have had a deep education about quantum physics. We will be focusing on the "software" of quantum computation, and any prerequisite material (mostly, a warmup of linear algebra) will be covered as we go along.

Topics:

1. Deterministic and probabilistic finite automata, zero error, one-sided error and bounded error. Introduction to quantum states. A QFA that recognizes a nonregular language with one-sided error. Homework: Prove that the angle in that QFA works.

​2. Formal definition of quantum finite automata. Density matrices. Quantum automata can simulate classical ones. Tensor products.

3.  The Myhill-Nerode theorem. Even quantum real-time automata recognize only the regular languages with bounded error. Two-way DFA's cannot recognize nonregular languages. 2PFA’s can recognize some nonregular languages with bounded error (https://dmtcs.episciences.org/509/pdf, Section 6). But only in superpolynomial time.

4. 2QFA’s (actually, 2PFA's with just one qubit) can recognize some nonregular languages with bounded error in polynomial time (the Ambainis-Watrous paper: https://cs.uwaterloo.ca/~watrous/Papers/QuantumClassicalStatesQFA.pdf). (For more on the relationship of the operation elements in our model and unitary transformations, see https://arxiv.org/pdf/1406.4048.pdf)

​5. Hadamard and CNOT gates. Quantum circuits. Error correction issues. The no-cloning theorem. One-time pads. Quantum key distribution: the BB84 protocol. Bell states and entanglement.

6. Superdense coding. Teleportation. The Toffoli gate is sufficient for classical universality. The Deutsch-Jozsa algorithm.

7. Grover’s algorithm.

8. The fast Fourier transform. The Fourier transform of a periodic vector. Introduction to quantum Fourier sampling.

9. Implementation of the QFT. (For a description of how the operations in Shor's algorithm can be implemented using a fixed set of quantum operations, see http://arxiv.org/pdf/quant-ph/0505030v2.pdfReduction of factorization to order finding.

10. Shor’s algorithm. 

Bize Ulaşın

Bilgisayar Mühendisliği Bölümü, Boğaziçi Üniversitesi,
34342 Bebek, İstanbul, Türkiye

  • Telefon: +90 212 359 45 23/24
  • Faks: +90 212 2872461
 

Bizi takip edin

Sosyal Medya hesaplarımızı izleyerek bölümdeki gelişmeleri takip edebilirsiniz