CMPT 478/981 project

Project overview

For the course project you are asked to do your own independent research on a topic in quantum circuits and compilation. The only specific requirement for the project is a written report. You may work in groups of up to two (2)

Broadly speaking, the project may take one of a few forms:

Option 1: Coding

For a coding-style project, you should implement some non-trivial compilation/optimization/verification/etc. algorithm(s). They can be algorithm(s) we've seen in class or in papers, and they can be implemented inside existing compilers/software packages (listed below) or free-form. The main requirement here is that it is your own work, i.e. you are not simply copy and pasting some existing compilation code from Qiskit. If you do a coding style project, your report should detail your implementation, any challenges or issues that arose, and some experimental results. For example, you may choose to compare two different compilation algorithms, or compare your implementation against another existing implementation. Benchmark circuits can be found, for example, in the Feynman repository listed below.

Here is a (non-exhaustive) list of software packages which may be of use:

Qiskit - IBM's quantum software mega-suite
PyZX - Python compilation package for working with ZX diagrams
Quipper - Compiler for the Quipper DSL written in Haskell
newsynth - package that broke off from Quipper implementing number-theoretic synthesis
JKQ A collection of C++ tools for quantum circuits & compilation built around the quantum decision diagram representation
QuilC - Compiler for the Quil instruction set written in Lisp
Feynman - Haskell compilation package implementing the sum-over-paths. Also includes a useful suite of benchmark circuits in two formats.
staq - C++-based compiler/transpiler for openQASM 2
inQWIRE - Various compilers, libraries and languages for writing and compiling formally verified quantum code in coq
Strawberry Fields - Python based library for photonic quantum computation

Option 2: Theory

Select a topic and read one or more papers on it then write a report. A typical format would be to survey a few different methods for a particular problem in compilation, e.g. different optimization algorithms, and write a comparative analysis. Where does one method particularly shine? Are there any trade-offs or is one method clearly superior? Are they complementary in that their combination can be used to solve a larger problem? If you choose to do a report on a single paper, your report should clearly explain the details of the work and provide some new insight and criticism. In the end the depth of the analysis of each paper should roughly be inversely proportional to the number of papers you are reading.

Some samples (slightly out of the course scope) are provided here and here. This should be a more in depth report (around 10 pages) than if the project is largely coding based.

Option 3: Application

Apply compilation techniques to solve a problem, possibly related to your own research. An example could be to compile a non-trivial instance of a quantum algorithm down to Clifford+T --- e.g. simulation of the ground state energy of a particular molecule using phase estimation, or an instance of Grover's search applied to SAT solving. You will likely need to read papers to fill in gaps in your knowledge on the algorithmic side.

Milestones

Jan. 31st: Decide on your group, if any
Feb. 27th: Propose your project idea to the instructor
Apr. 11th: Deadline to hand in your project

Resources

Template for writing your report in LaTeX (not required but recommended)

Possible projects

Compilation algorithm implementation
Choose (1) optimization/compilation algorithm (e.g. from the reading list) and (1) software package that doesn't already implement that algorithm, then implement that algorithm in that software package. Examples include T-opt or Gridsynth in Qiskit. Bonus points for making a pull request at the end.
Linear reversible synthesis
On the complexity of matrix reduction over finite fields gives an algorithm for fast Gaussian elimination in finite fields such as $\mathbb{Z}_2$, which can be used to synthesize linear reversible (i.e. CNOT only) circuits. Implement and compare this to the Patel-Markov-Hayes algorithm ( Optimal synthesis of linear reversible circuits) and/or more recent work such as Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits.
Resource estimation
Compile an instance of some quantum algorithm applied to some specific problem (e.g. quantum algorithm for finding the optimal variable ordering in a binary decision diagram) to be executed on fault-tolerant hardware (i.e. compile to Clifford+T). Estimate the amount of space, circuit depth, number of each type of gate, etc. as a function of the input size.
Toy problem
Pick (1) NP complete problem and (1) quantum circuit toolkit (e.g. Qiskit) and implement a compilation routine to take an arbitrary instance of that NP complete problem and compile an instance of QAOA solving it. Run some experiments simulating the resulting circuit on some toy sizes. Bonus points for running on real quantum hardware. Note: there should not already be a compilation routine in the given toolkit for this problem. For example, Pennylane has an existing routine for compiling an QAOA instance solving Vertex Cover.
Compiler frontend
Write a compiler frontend for (a subset of) Q# or some other high-level quantum programming language and compile down to an intermediate representation such as openQASM 2/3 or QIR. As in the classical case, the use of languages like openQASM or QIR as intermediate representations allows developers to solve the "N-to-M" problem of writing a compiler for every combination of high-level language and individual hardware platform.
Template-based circuit optimizer
Implement a template-based circuit optimizer using a complete re-writing theory (e.g. A Complete Equational Theory for Quantum Circuits, Generators and relations for n-qubit Clifford operators, Generators and relations for 2-qubit Clifford+T operators). A complete re-writing theory means that whenever two circuits are equal as unitaries, one can be re-written to the other using only rules in the theory.
Verification
Use a circuit verification package (e.g. JKQ or Feynman) to write a static assertion checker for the Silq or Twist language.
Quantum arithmetic
Write an openQASM 3 library for reversible arithmetic (e.g. multipliers, adders, exponentiation) on qubit registers of arbitrary width. That is, program circuit families for arithmetic operations in the openQASM 3 circuit language. Note: this was impossible in openQASM 2 because qubit registers had statically fixed sizes.
Braided surface code compilation
Implement a braided surface code compiler using the modular presentation of surface code braiding from Compaction of Topological Quantum Circuits by Modularization.
Readings
Pick 2-4 papers in one topic (e.g. from the readings list) and write a report synthesizing and comparing them.

Please ask me to expand on any of these if you're interested but unsure of the details.