CmpE 598 Sp.Tp. Quantum Algorithms  2014 Fall


Course Schedule: 

TTT 235 B3

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.


1. Probabilistic finite automata, zero error and bounded error.

2. Quantum machines: Definition, well-formedness. A succinctness example (see proof about the size of the minimal DFA for that promise problem in

3. Density matrices. Tracing a quantum program.

4. Quantum communication complexity. Real-time quantum automata with zero error cannot be smaller than DFA’s (Sections 4-6 of "On quantum and probabilistic communication: Las Vegas and one-way protocols", by Hartmut Klauck, reachable from within Boğaziçi)

5. Even quantum real-time automata recognize only the regular languages with bounded error.  (

6. Succinctness of bounded-error real-time probabilistic and quantum finite automata (

7. Two-way DFA's. 2PFA’s can recognize some nonregular languages with bounded error (, Section 6). But only in superpolynomial time. 2QFA’s (actually, 2PFA's with just one qubit) can recognize some nonregular languages with bounded error in polynomial time (the Ambainis-Watrous paper: 1QFA's with quantum heads can do it in linear time. Real numbers are sufficient for quantum programs. The QFT.

9. A TM with a quantum tape (Figure 13 in Tensor products. Grover’s algorithm.

10. Simon's algorithm

11. Reduction of factoring to order finding. Shor’s algorithm. (For a description of how the operations in Shor's algorithm can be implemented using a fixed set of quantum operations, see


Various, will be announced in class


Midterm 1: Oct.28 %30
Midterm 2: Dec. 2 %30
Final %40


Check your email, since I'm sending the second midterm questions now (November 28).

Updated lecture notes:


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