CMSC 858O On the Foundation of End-to-End Quantum Applications, Fall 2021

Lecture Note Scribing (20% of the grade)

Each student should scribe (at least) one lecture in one topic. This is an interactive procedure. The student should prepare a draft lecture note within 3 weeks from the given lecture. The instructor will work with the student to further polish the lecture note. It is expected that the final lecture notes will be available to the public. Note that lectures will be recorded and handwritten notes will be shared at ELMS.

We provide a latex typesetting template for your convenience. There is also a latex macro for some basic notations in quantum information. Check here for a sample tex file. Please use Qcircuit for drawing quantum circuits.

Milestones:

• Please submit your preference in lecture note scribing by 09/08/21 at ELMS.

• Please submit your draft lecture note within 3 weeks from your assigned lecture.

Paper Presentation (30% of the grade)

Each student is expected to present one paper (or a few papers about one specific topic) during the weeks of paper presentation. Students will bid for the paper to present (no more than 2 students for the same paper). The length of the presentation ranges from a half lecture to a full lecture depending on the nature of content. Students could use whiteboards, slides, or so for the presentation as long as it is clear for the audience. The presentation will also be recorded and shared at ELMS. In addition to the presentation, you should also prepare a lecture note (at least 2.5 pages) covering the fundamentals of your presentation, which should be shared with the instructor at least 3 days before your presentation.

Here are some general suggestions on how to read/understand/present a new research paper:

• A good way to understand a new paper is to imagine yourself as a reviewer for the paper and follow the suggestion here:e.g., The task of the Referee. The lecture note of your presentation could be a review of the paper following the above principles.

• Some other general principles: e.g., Principles of Effective Research, Six Rules for Rewriting, How to Read a Paper.

Milestones:

• Please bid for your paper and time slots by 09/17/21 at ELMS.

• Please share your lecture note at least 3 days before your presentation.

Tentative Paper List (subject to frequent updates)

Here are some suggested references to present for the course. This list should be considered as suggestions. Reasonable references outside the list are welcome, which should be submitted in your bid and approved by the instructor.

If you have any trouble identifying papers to present, please contact the instructor as soon as possible.

• Quantum Algorithms

  • Optimization (Provable Guarantees)

    • Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving. arXiv:1911.07306

    • Quantum algorithms and lower bounds for convex optimization. arXiv:1809.01731

    • Convex optimization using quantum oracles. arXiv:1809.00643

    • Quantum algorithms for escaping from saddle points. arXiv:2007.10253

    • A Quantum Interior Point Method for LPs and SDPs. doi:/10.1145/3406306

    • Quantum algorithms for matrix scaling and matrix balancing. arXiv:2011.12823

  • Exponential-time Algorithms

    • Dynamic Programming Speedup for TSP and other problems. arxiv:1807.05209

    • Quantum speedup of backtracking. abs:1509.02374

    • Quantum Tree Size Estimation (can be used to improve the previous algorithm among other applications). arXiv:1704.06774

    • Quantum Branch and Bound (applicable to integer programming). arXiv:1906.10375

  • Quantum Singular Value Transformation

    • Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv:1806.01838

    • A Grand Unification of Quantum Algorithms. arXiv:2105.02859

  • Algorithms for Quantum Machine Learning

    • Quantum Recommendation Systems. arXiv:1603.08675

    • A quantum-inspired classical algorithm for recommendation systems. arXiv:1807.04271

    • q-means: A quantum algorithm for unsupervised machine learning. arXiv:1812.03584.

    • Quantum Expectation-Maximization for Gaussian Mixture Models. arXiv:1908.06657

    • Quantum exploration algorithms for multi-armed bandits. arXiv:2007.07049

    • Quantum Boosting. arXiv:2002.05056

  • Sample Complexity of Learning Quantum States

    • Sample-optimal tomography of quantum states. arXiv:1508.01797

    • Efficient quantum tomography. arXiv:1508.01907

    • Shadow Tomography of Quantum States. arXiv:1711.01053

    • Sample-efficient learning of quantum many-body systems. arXiv:2004.07266

  • More conventional quantum algorithms

• Variational Quantum Methods

  • Constructions

    • A variational eigenvalue solver on a quantum processor. arXiv:1304.3061

    • A Quantum Approximate Optimization Algorithm. arXiv:1411.4028

    • Classification with Quantum Neural Networks on Near Term Processors. arXiv:1802.06002

    • Quantum Graph Neural Networks. arXiv:1909.12264

    • Quantum Recurrent Neural Networks. arXiv:2006.14619

    • Quantum Imaginary Time Evolution. arXiv:1901.07653

    • Quantum Convolutional Neural Networks. arXiv:1810.03787

    • Quantum generative adversarial learning. arXiv:1804.09139

  • Theory

    • Quantum embeddings for machine learning. arXiv:2001.03622

    • Learning Unitaries by Gradient Descent. arXiv:2001.11897.

    • Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature Communications, 2021.

    • Quantum Optimally Controlled Transition Landscapes. Science 303, 1998 (2004).

• Quantum Programming Languages

  • M. Ying. Foundations of Quantum Programming, Morgan Kaufmann, 2016.

  • Floyd–Hoare logic for quantum programs. ACM Transactions on Programming Languages and Systems (TOPLAS), 2012.

  • Projection-Based Runtime Assertions for Testing and Debugging Quantum Programs. OOPLSA 2020.

  • Relational Proofs for Quantum Programs. POPL 2020.

  • Quantum Abstract Interpretation. PLDI 2021.

  • FYI, you can also present papers from my group.

• Quantum Architecture

  • Logical abstractions for noisy variational Quantum algorithm simulation. ASPLOS 2021.

  • CutQC: using small Quantum computers for large Quantum circuit evaluations. ASPLOS 2021.

  • Exploiting Long-Distance Interactions and Tolerating Atom Loss in Neutral Atom Quantum Architectures. ISCA 2021.

  • Optimal Mapping for Near-Term Quantum Architectures based on Rydberg Atoms. ICCAD 2021. arXiv: 2109.04179

  • Architecting Noisy Intermediate-Scale Trapped Ion Quantum Computers. ISCA 2020.

  • Systematic Crosstalk Mitigation for Superconducting Qubits via Frequency-Aware Compilation. MICRO 2020.

  • Resource-Efficient Quantum Computing by Breaking Abstractions. In Proceedings of the IEEE, Jun 2020.

  • Optimized Quantum Compilation for Near-Term Algorithms with OpenPulse. MICRO 2020.

• Quantum Security/Cryptography

  • How to Record Quantum Queries, and Applications to Quantum Indifferentiability. CRYPTO 2019.

  • On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work. Eurocrypt 2021.

  • Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering. https://eprint.iacr.org/2021/1093

  • Tight Quantum Time-Space Tradeoffs for Function Inversion. FOCS 2020.

  • Oblivious Transfer is in MiniQCrypt. Eurocrypt 2021.

• Quantum Network/Communication

  • Concurrent Entanglement Routing for Quantum Networks: Model and Designs. SIGCOMM 2020.

  • A link layer protocol for quantum networks. SIGCOMM 2019.

  • Optimal Protocols for Entanglement Swapping and Distribution. International Conference on Computing, Networking and Communications 2020.