Topics in Quantum Computing (CS6340)

Syllabus

• Introduction to Quantum Computing.
• Bounded-depth quantum circuits.
• Quantum algorithms using random walks, Hamiltonian Simulation and the HHL algorithm.
• Other advanced topics if time permits...

Evaluations

Textbook and References

• Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information.
• Phillip Kaye, Raymond Laflamme and Michele Mosca, An Introduction to Quantum Computing.
• Ronald de Wolf, Quantum Computing: Lecture Notes.
• Richard Feynman, Feynman Lectures on Computation (1996).
• Other quantum courses: Andrew Childs (University of Maryland), John Watrous (University of Waterloo), Rajat Mittal (IIT Kanpur), Ryan O'Donnell (CMU).

Papers/Articles

• C. Moore (1999). Quantum Circuits: Fanout, Parity and Counting. arXiv.
• F. Green, S. Homer, C. Moore, C. Pollett (2001). Counting, Fanout, and the Complexity of Quantum ACC. arXiv.
• P. Hoyer, R. Spalek (2002). Quantum Circuits with Unbounded Fan-out. arXiv.
• M. Fang, S. Fenner, F. Green, S. Homer, Y. Zhang (2003). Quantum Lower Bounds for Fanout. arXiv.
• S. Fenner, F. Green, S. Homer, Y. Zhang (2003). Bounds on the Power of Constant-Depth Quantum Circuits. arXiv.
• Y. Takahashi, Y. Kawano, M. Kitagawa (2003). On the computational power of constant-depth quantum circuits with gates for addition. Link.
• D. Bera, F. Green, S. Homer (2007). Small depth quantum circuits. Link.
• Y. Takahashi, S. Tani (2011). Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits. arXiv.
• D. Padé, S. Fenner, D. Grier, T. Thierauf (2020). Depth-2 QAC circuits cannot simulate quantum parity.arXiv.
• G. Rosenthal (2020). Bounds on the QAC⁰ Complexity of Approximating Parity. arXiv.
• S. Nadimpalli, N. Parham, F. Vasconcelos, H. Yeun (2023).On the Pauli Spectrum of QAC⁰.arXiv.
• J. Slote (2023). Parity vs. AC0 with simple quantum preprocessing. arXiv.
• A. Anshu, Y. Dong, F. Ou, P. Yao (2024). On the Computational Power of QAC⁰ with Barely Superlinear Ancillae.arXiv.
• A. B. Grilo, E. Kashefi, D. Markham, M. de Oliveira (2024). The Power of Shallow-depth Toffoli and Qudit Quantum Circuits. arXiv.
• J. Bao, F. Escudero-Gutiérrez (2024). Learning junta distributions, quantum junta states, and QAC⁰ circuits. arXiv.
• F. Vasconcelos, H-Y. Huang (2024). Learning shallow quantum circuits with many-qubit gates. arXiv.
• D. Grier, J. Morris (2024). Quantum Threshold is Powerful. arXiv.
• S. Fenner, D. Grier, D. Padé, T. Thierauf (2025). Tight bounds on depth-2 QAC-circuits computing parity. arXiv.
• B. Foxman, N. Parham, F. Vasconcelos, H. Yeun (2025). Random Unitaries in Constant (Quantum) Time. arXiv.
• N. Parham (2025). Quantum circuit lower bounds in the magic hierarchy. arXiv.
• Y. Dong, F. Ou, P. Yao (2025). Linear-Size QAC0 Channels: Learning, Testing and Hardness. arXiv.
• S. Grewal, D. Liang (2025). Efficient Learning of Structured Quantum Circuits via Pauli Dimensionality and Sparsity. arXiv.
• M. R. Joshi, A. Tal, F. Vasconcelos, J. Wright (2025). Improved Lower Bounds for QAC0. arXiv.
• D. Grier, J. Morris, K. Wu (2026). QAC⁰ Contains TC⁰ (with Many Copies of the Input). arXiv.
• M. R. Joshi, F. Vasconcelos (2026). Constant-Depth Unitary Preparation of Dicke States. arXiv.
• L. Gretta, M. Gupta, M. R. Joshi (2026). Parity ∉ QAC0 iff QAC0 is Fourier-Concentrated. arXiv.
• Y. Dong, F. Ou, P. Yao (2026). On the Computational Complexity of Geometrically Local QAC0 circuits. arXiv.
• L. Gretta, M. Gupta, M. R. Joshi (2026). Polylogarithmic-Weight Dicke States in QAC⁰ and Arbitrary Symmetric States in QAC⁰_f. arXiv.
• L. Gretta, M. R. Joshi (2026). Shor's algorithm requires Fanout. arXiv.

Lectures

1. Lecture 1: General Information.


2. Lectures 2-4: Razborov-Smolensky's AC⁰ lower bound proof. Notes.