CmpE 598 Sp.Tp. Quantum Algorithms  2018 Spring


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.


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

2. Quantum machines: Definition, well-formedness.  Density matrices. Tracing a quantum program. (For more on the relationship of the operation elements in our model and unitary transformations, see

3. Quantum nondeterminism beats classical nondeterminism. A succinctness example (see proof about the size of the minimal DFA for that promise problem in

4. The Myhill-Nerode theorem. 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. Tensor products. 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.

8. 2QFA’s (actually, 2PFA's with just one qubit) can recognize some nonregular languages with bounded error in polynomial time (the Ambainis-Watrous paper:

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

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


Two midterms

Contact us

Department of Computer Engineering, Boğaziçi University,
34342 Bebek, Istanbul, Turkey

  • Phone: +90 212 359 45 23/24
  • Fax: +90 212 2872461

Connect with us

We're on Social Networks. Follow us & get in touch.