CMPT 409/981 readings list

Here is a list of selected papers on various topics in quantum circuits and compilation.

Circuit compilation

• Linear reversible circuits
• Ketan Patel, Igor Markov. John Hayes. Optimal synthesis of linear reversible circuits. QIC 2008
• Timothée Goubault de Brugière et al. Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits. ACM TQC 2021
• General reversible circuits
• Mathias Soeken et al. LUT-Based Hierarchical Reversible Logic Synthesis. IEEE TCAD 2018
• Giulia Meuli et al. The role of multiplicative complexity in compiling low T-count oracle circuits. ICCAD 2019
• Relative phase circuits
• Dmitri Maslov. On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization. PRA 2016
• Mehdi Craig Gidney. Halving the cost of quantum addition. Quantum 2018.
• M. Amy, Neil J. Ross. The phase/state duality in reversible circuit design. PRA 2021
• T-count lower bounds
• M. Amy, Michele Mosca. T-count optimization and Reed-Muller codes. IEEE TIT 2019
• Michael Beverland et al. Lower bounds on the non-Clifford resources for quantum computations. QST 2020
• Jiaqing Jiang, Xin Wang. Lower bound the T-count via unitary stabilizer nullity. arXiv 2021
• Algorithm-specific
• Scherer et al. Concrete resource analysis of the quantum linear system algorithm used to compute the electromagnetic scattering cross section of a 2D target QIP (not the conference) 2017
• Andrew Childs et al. Toward the first quantum simulation with quantum speedup. PNAS 2018
• Craig Gidney, Martin Ekerå. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum 2021
• Luis Madhav Krishnan Vijayan et al. Compilation of algorithm-specific graph states for quantum circuits. arXiv 2022

Circuit optimization

• Phase polynomial optimizations
• M. Amy, Dmitri Maslov, Michele Mosca. Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning. IEEE TCAD 2014
• Luke Heyfron, Earl Campbell. An Efficient Quantum Compiler that reduces T count. QST 2018
• Aleks Kissinger, John van de Wetering. Reducing T-count with the ZX-calculus. PRA 2020
• Niel de Beaudrap, Xiaoning Bian, Quanlong Wang. Fast and effective techniques for T-count reduction via spider nest identities. TQC 2020
• Template-based
  • Sergey Bravyi et al. Clifford Circuit Optimization with Templates and Symbolic Pauli Gates. Quantum 2021
  • Kesha Hietala et al. A verified optimizer for Quantum circuits. POPL 2021
  • Mingkuan Xu et al. Quartz: Superoptimization of Quantum Circuits. PLDI 2022 (do the non-extended version)
• Compiler optimization
  • Shishir David Ittah et al. Enabling Dataflow Optimization for Quantum Programs. ACM TQC 2021

Surface code compilation & optimization

• Braided surface code
• Ming Adam Paetznick, Austin G. Fowler. Quantum circuit optimization by topological compaction in the surface code. arXiv 2013.
• Kota Asai, Shigeru Yamashita. Compaction of Topological Quantum Circuits by Modularization. IEICE FECCS 2019.
• Chen-Hao Hsu et al. A Bridge-based Compression Algorithm for Topological Quantum Circuits. DAC 2021.
• Lattice surgery
  • Camille Daniel Litinski. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum 2019.
  • Niel de Beaudrap, Dominic Horsman. The ZX calculus is a language for surface code lattice surgery. Quantum 2020.

Circuit theory

• Ken Matsumoto, Kazuyuki Amano. Representation of Quantum Circuits with Clifford and π/8 Gates. arXiv 2008
• Peter Selinger. Generators and relations for n-qubit Clifford operators. LMCS 2015
• M. Amy, Jianxin Chen, Neil J. Ross. A Finite Presentation of CNOT-Dihedral Operators. QPL 2017
• Xiaoning Bian, Peter Selinger. Generators and relations for 2-qubit Clifford+T operators. QPL 2022 (Famously presented around 2016 and existed only in slide form since then. They finally completed the computer-aided verification of the result just this past year.)
• Jonas Alexandre Clément et al. A Complete Equational Theory for Quantum Circuits. arXiv 2022 (Big result that just came out)

Circuit representations (Mix of theory, compilation, and verification/simulation)

• ZX-calculus
• John van de Wetering. ZX-calculus for the working quantum computer scientist. arXiv 2021 (Broad overview, don't read the whole thing)
• Lucas Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. njp 2014
• Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart. A Complete Axiomatisation of the ZX-Calculus for Clifford+T Quantum Mechanics. LICS 2018
• Miriam Backens, Aleks Kissinger. ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity. QPL 2018
• Ross Duncan et al. Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus. Quantum 2020
• Niel de Beaudrap, Aleks Kissinger, John van de Wetering. Circuit Extraction for ZX-diagrams can be #P-hard. ICALP 2022
• Quantum decision diagrams
• Philipp Niemann et al. QMDDs: Efficient Quantum Function Representation and Manipulation. IEEE TCAD 2015
• Robert Wille, Stefan Hillmich, Lukas Burgholzer. Tools for Quantum Computing Based on Decision Diagrams. ACM TQC 2021
• Alwin Zulehner, Robert Wille. Approximating Decision Diagrams for Quantum Circuit Simulation. ACM TQC 2022
• The sum-over-paths
• M. Amy. Towards Large-scale Functional Verification of Universal Quantum Circuits. QPL 2018
• Ashish M. Amy, Owen Bennett-Gibbs, Neil J. Ross. Symbolic synthesis of Clifford circuits and beyond. QPL 2022
• Renaud Vilmart. Completeness of Sum-Over-Paths for Toffoli-Hadamard and the Clifford Hierarchy. arXiv 2022

Circuit routing/mapping

• Alwin Zulehner, Alexandru Paler, Robert Wille. An Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures. IEEE TCAD 2019
• Gushu Li, Yufei Ding, Yuan Xie. Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices. ASPLOS 2019
• Aleks Kissinger, Arianne Meijer-van de Griend. CNOT circuit extraction for topologically-constrained quantum memories. QIC 2020
• Aniruddha Bapat et al. Quantum routing with fast reversals. Quantum 2021

Quantum programming languages

• Alexander Green et al. Quipper: A Scalable Quantum Programming Language. PLDI 2013
• Krysta Svore et al. Q#: Enabling scalable quantum computing and development with a high-level domain-specific language. RWDSL 2018
• Andrew Cross et al. OpenQASM 3: A broader and deeper quantum assembly language. ACM TQC 2022
• Charles Yuan, Christopher McNally, Michael Carbin. Twist: sound reasoning for purity and entanglement in Quantum programs. POPL 2022