Sarah Meng Li

During my undergraduate study, I worked as a head teaching assistant for courses offered by Faculty of Computer Science and Department of Mathematics and Statistics.

• Network Computing: Fall 20’

• Design and Analysis of Algorithms I: Summer 20’, Fall 20’, Summer 21’

• First Year Interest Group: Patterns and Puzzles: Fall 19’, Fall 20’

• Software Engineering: Summer 20’, Winter 20’

• Introduction to Database Management System: Fall 17’, Winter 18’, Winter 20'

• Computer Organization with Assembly Language: Winter 19’

• Discrete Structures I: Fall 18', Fall 19'

• Discrete Math for CS: Winter 21’

• Data Structures and Algorithms: Fall 18', Winter 21’

• Computer Science I and II: Summer 18'

• Statistical Methods for Data Analysis and Inference: Summer 17'

• Introduction to Probability and Statistics: Summer 17'

• Introductory Statistics for Science and Health Sciences: Summer 17'

[1] Generators and Relations for the Group On(Z[1/2])

Joint work with Neil J. Ross and Peter Selinger.

We give a finite presentation by generators and relations for the group On(Z[1/2]) of n-dimensional orthogonal matrices with entries in Z[1/2]. We then obtain a similar presentation for the group of n-dimensional orthogonal matrices of the form (1/\sqrt{2})^k M, where k is a nonnegative integer and M is an integer matrix. Both groups arise in the study of quantum circuits. In particular, when the dimension is a power of 2 the elements of the latter group are precisely the matrices that can be represented by a quantum circuit over the universal gate set consisting of the Toffoli gate, the Hadamard gate, and the computational ancilla.

>>Paper

>> Slides

>> Video

[2] Reducing CNOT Count in Clifford+T Circuits for NISQ Architectures

Joint work with Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay.

We designed and implemented an algorithm that synthesizes a circuit over the universal fault-tolerant gate set {CNOT, T, T*, P, P*, X, Y, Z, H} while accounting for connectivity constraints of noisy intermediate-scale quantum computers. This algorithm significantly reduces the number of CNOT gates compared to the general SWAP template.

>> Paper

>> Slides

>> Video

[3] Improved Synthesis of Toffoli-Hadamard Circuits

Joint work with Matt Amy, Andrew Glaudell, and Neil J. Ross.

The matrices that can be exactly represented by a circuit over the Toffoli-Hadamard gate set are the orthogonal matrices of the form M/(root 2)^k, where M is an integer matrix and k is a nonnegative integer. The exact synthesis problem for this gate set is the problem of constructing a circuit for a given such matrix. Existing methods produce circuits consisting of O((2^n)log(n)k) gates, where n is the dimension of the matrix.

In this paper, we provide two improved synthesis methods. First, we show that a technique introduced by Kliuchnikov in 2013 for Clifford+T circuits can be straightforwardly adapted to Toffoli-Hadamard circuits, reducing the complexity of the synthesized circuit from O((2^n)log(n)k) to O((n^2)log(n)k). Then, we present an alternative synthesis method of similarly improved cost, but whose application is restricted to circuits on no more than three qubits. Our results also apply to orthogonal matrices over the dyadic fractions, which correspond to circuits using the 2-qubit gate H ⊗ H, rather than the usual single-qubit Hadamard gate H.

>> Paper

>> Poster

>> Slides

>> Video

[4] Dynamic Qubit Routing with CNOT Circuit Synthesis for Quantum Compilation

Joint work with Arianne Meijer - van de Griend

Many quantum computers have constraints regarding which two-qubit operations are locally allowed. To run a quantum circuit under those constraints, qubits need to be mapped to different quantum registers, and multi-qubit gates need to be routed accordingly. Recent developments have shown that compiling strategies based on Steiner tree provide a competitive tool to route CNOTs. However, these algorithms require the qubit map to be decided before routing. Moreover, the qubit map is fixed throughout the computation, i.e. the logical qubit will not be moved to a different physical qubit register. This is inefficient with respect to the CNOT count of the resulting circuit.

In this paper, we propose the algorithm PermRowCol for routing CNOTs in a quantum circuit. It dynamically remaps logical qubits during the computation, and thus results in fewer output CNOTs than the algorithms Steiner-Gauss and RowCol. Here we focus on circuits over CNOT only, but this method could be generalized to a routing and mapping strategy on Clifford+T circuits by slicing the quantum circuit into subcircuits composed of CNOTs and single-qubit gates. Additionally, PermRowCol can be used in place of Steiner-Gauss in the synthesis of phase polynomials as well as the extraction of quantum circuits from ZX-diagrams.

>> Paper

>> Slides

[5] Graphical CSS Code Transformation Using ZX Calculus

Joint work with Jiaxin Huang, Lia Yeh, Aleks Kissinger, Michele Mosca, and Michael Vasmer

In this work, we present a generic approach to transform CSS codes by building upon their equivalence to phase-free ZX diagrams. Using the ZX calculus, we demonstrate diagrammatic transformations between encoding maps associated with different codes. As a motivating example, we give explicit transformations between the Steane code and the quantum Reed-Muller code, since by switching between these two codes, one can obtain a fault-tolerant universal gate set. To this end, we propose a bidirectional rewrite rule to find a (not necessarily transversal) physical implementation for any logical ZX diagram in any CSS code.

Then we focus on two code transformation techniques: code morphing, a procedure that transforms a code while retaining its fault-tolerant gates, and gauge fixing, where complimentary codes (such as the Steane and quantum Reed-Muller codes) can be obtained from a common subsystem code. We provide explicit graphical derivations for these techniques and show how ZX and graphi >> Slides cal encoder maps relate several equivalent perspectives on these code transforming operations.

>> Paper

>> Poster

>> Slides

>> Thesis

[6] Improving the Fidelity of CNOT Circuits on NISQ Hardware

Joint work with Dohun Kim, Minyoung Kim, and Michele Mosca

We introduce an improved CNOT synthesis algorithm that considers nearest-neighbour interactions and CNOT gate error rates in noisy intermediate-scale quantum (NISQ) hardware. Compared to IBM's Qiskit compiler, it improves the fidelity of a synthesized CNOT circuit by about 2 times on average (up to 9 times). It lowers the synthesized CNOT count by a factor of 13 on average (up to a factor of 162).

Our contribution is twofold. First, we define a 𝖢𝗈𝗌𝗍 function by approximating the average gate fidelity Favg. According to the simulation results, 𝖢𝗈𝗌𝗍 fits the error probability of a noisy CNOT circuit, 𝖯𝗋𝗈𝖻=1−Favg, much tighter than the commonly used cost functions. On IBM's fake Nairobi backend, it matches 𝖯𝗋𝗈𝖻 to within 10^{−3}. On other backends, it fits 𝖯𝗋𝗈𝖻 to within 10^{−1}. 𝖢𝗈𝗌𝗍 accurately quantifies the dynamic error characteristics and shows remarkable scalability. Second, we propose a noise-aware CNOT routing algorithm, NAPermRowCol, by adapting the leading Steiner-tree-based connectivity-aware CNOT synthesis algorithms. A weighted edge is used to encode a CNOT gate error rate and 𝖢𝗈𝗌𝗍-instructed heuristics are applied to each reduction step. NAPermRowCol does not use ancillary qubits and is not restricted to certain initial qubit maps. Compared with algorithms that are noise-agnostic, it improves the fidelity of a synthesized CNOT circuit across varied NISQ hardware. Depending on the benchmark circuit and the IBM backend selected, it lowers the synthesized CNOT count up to 56.95% compared to ROWCOL and up to 21.62% compared to PermRowCol. It reduces the synthesis 𝖢𝗈𝗌𝗍 up to 25.71% compared to ROWCOL and up to 9.12% compared to PermRowCol. Our method can be extended to route a more general quantum circuit, giving a powerful new tool for compiling on NISQ devices.

>> Paper

>> Slides

>> Poster

I enjoy reading literatures on quantum circuit compiling. Here I share some reading notes for papers I’ve been reading and new things I’m learning.

Note: this page is currently under construction.

• Fault-tolerant Computing

  [1] Fault-tolerant conversion between the Steane and Reed-Muller quantum codes

• Quantum Circuit Optimization and Complexity Analysis
  [1] Asymptotically optimal synthesis of reversible circuits.

• Quantum circuit routing
  [1] Physical constraint-aware CNOT quantum circuit synthesis and optimization

I share some study notes from various classes in Computer Science, Mathematics, and Statistics.

Algorithms

Network Computing

At the Institute for Quantum Computing, I came across very interesting problems in quantum computing. I will share some discussions here. More info yet to come!

I love being part of STEM outreach! It is very satisfying to share what I’ve learned from classes and research with my community. I love helping students grow and navigate the STEM world.

Waterloo Math Circles, October - November 2023

• Complex numbers and quantum states

• Linear algebra and quantum circuits

• A peek into the Grover’s algorithm
  Slides & Handouts

Quetzal (A Quantum Computing Accelerator Program) - October 2023

• A Beginner’s Guide to Quantum Algorithms: The Grover’s Search

Institute for Quantum Computing, Quantum School for Young Students (IQC - QSYS), August 2023

• Quantum Error Correction: Slides & Handouts

• Grover’s Algorithm: Handouts

eSTEM Workshops with Renison University College, August 2023

• Picturing Quantum Processes

IQC Undergraduate School on Experimental Quantum Information Processing (USEQIP), June 2023

• Quantum Error Correction and Fault Tolerance: Surface Codes

K∩W - Intersections KW, October 2022

• A Beginner’s Guide to Quantum Algorithms: Grover’s Search Algorithm

Quantum Universal Education, September 2022

• A Beginner’s Guide to Quantum Error Correction

Waterloo Math Circles, October - November 2022

• A Beginner’s Guide to Quantum Computing: Deutch-Josza Algorithm

• Problem Solving with Euclidean Algorithm: Slides & Handouts

Insitute for Quantum Computing, Quantum School for Young Students (IQC - QSYS), June 2022

• Early Quantum Computing (The Deutsch-Josza Algorithm)

• A Beginner’s Guide to Quantum Error Correction

eSTEM Workshops with Renison University College, July - August 2022

• The Quantum Science of Lights

• Introduction to Quantum Computing

IQC Virtual Class Visits, 2021 - 2023

• A Spotlight on Quantum Physics

• Quantum Information Science Workshop at Ontario Science Center

Nova Scotia Math Circles, 2019 - 2023

• Problem-solving with Euclidean algorithm

• Probability Buffet: Slides

• Logic and Puzzles: Slides & Handouts

• Math and Coding

• Problem Solving with Algorithms

First Year Interest Group, 2019 - 2020

Canada Learning Code, 2018 - 2020

• Kids Learning Code - Gamemaking with Scratch and Makey Makey

• Ladies Learning Code - An Introduction to Artificial Intelligence and Machine Learning

• Teachers Learning Code - Making Art with Program

I enjoy problem solving, and here I share solutions and mindmaps to some algorithm practice on LeetCode.

Note: this page is currently under construction.

• Arrays & Strings

• Linked Lists

• Trees & Graphs

• Recursion

• Sorting & Searching

• Dynamic Programming

• Design Others