### 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. 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 https://arxiv.org/pdf/1406.4048.pdf)

3. Quantum nondeterminism beats classical nondeterminism. A succinctness example (see proof about the size of the minimal DFA for that promise problem in http://www.lu.lv/fileadmin/user_upload/lu_portal/projekti/datorzinatnes_...)

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. (http://arxiv.org/abs/0911.3266)

6. Succinctness of bounded-error real-time probabilistic and quantum finite automata (http://arxiv.org/abs/quant-ph/9802062)

7. Two-way DFA's. 2PFA’s can recognize some nonregular languages with bounded error (https://dmtcs.episciences.org/509/pdf, 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: https://cs.uwaterloo.ca/~watrous/Papers/QuantumClassicalStatesQFA.pdf).

9. A TM with a quantum tape (Figure 13 in https://cs.uwaterloo.ca/~watrous/Papers/QuantumComputationalComplexity.pdf). 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 http://arxiv.org/pdf/quant-ph/0505030v2.pdf)

### Grading:

Two midterms