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

Lecture Note Scribing (10% of the grade)

Each student should scribe (at least) one lecture. 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/22 at ELMS.

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

Paper Presentation (15% 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 the 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.

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/15/22 at ELMS.

Tentative Paper List (subject to frequent updates)

Here are some suggested references to present for the course. This list should be considered as a suggestion. 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 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

  • 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 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

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

    • Critical Points in Quantum Generative Models. ICLR 2021.

    • Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps. arXiv: 2205.05786.

    • Gaussian initializations help deep variational quantum circuits escape from the barren plateau. arXiv: 2203.09376.

• Classical ML for Quantum Problems.

  • Learning ground states of quantum Hamiltonians with graph networks. arXiv:2110.06390

  • Provably efficient machine learning for quantum many-body problems. QIP 2022.

• Quantum Architecture

  • Logical abstractions for noisy variational Quantum algorithm simulation. 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.

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

  • SupermarQ: A Scalable Quantum Benchmark Suite. HPCA 2022.

  • QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits. HPCA 2022.

• 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 Proofs of Deletion for Learning with Errors. QIP 2022.

  • Succinct Blind Quantum Computation Using a Random Oracle. STOC 2022.

• 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.

  • NetSquid, a NETwork Simulator for QUantum Information using Discrete events. Communications Physics volume 4, Article number: 164 (2021).

  • Advances in the Quantum Internet. Communications of the ACM, August 2022.