CmpE 598 Sp.Tp. Quantum Algorithms  2018 Spring

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)