CmpE 598 Sp.Tp. Quantum Algorithms  2014 Fall

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

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.  (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 (http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1457/3371, 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: https://cs.uwaterloo.ca/~watrous/Papers/QuantumClassicalStatesQFA.pdf). 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 https://cs.uwaterloo.ca/~watrous/Papers/QuantumComputationalComplexity.pdf). 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 http://arxiv.org/pdf/quant-ph/0505030v2.pdf)