First of all, I would like to thank my mentor Roger Luo and Jinguo Liu for supervising me during Google Summer of Code 2020. In this GSoC project, I will develop a new Julia package ZXCalculus.jl
which implements ZXcalculus, and integrate it as a circuit simplification engine with YaoLang.jl
, the next DSL (domainspecific language) for Yao.jl
and quantum programs. Yao.jl
has achieved a stateofart quantum simulator with many advanced features such as automatic differentiation and symbolic computation. As a user of Yao.jl
, I’m so glad to have the opportunity to make contributions to it. In this blog post, I will summarize what we have done before the first evaluation.
Quantum circuits and ZXcalculus
Quantum computing uses the principles of quantum mechanics for computing. To describe quantum algorithms, we often use the quantum circuit model which is the analog of the classical logic circuit model. Quantum circuits are consist of a set of basic quantum gates such as Pauli X, Y, Z gate, Hadamard gate, T gate, CNOT gate.
In general, there will be lots of equivalent quantum circuits representing the same operation. At the viewpoint of quantum hardware, one wishes to find the circuit that minimizing the usage of hardware resources. Unfortunately, finding the most desired circuit is a very hard problem in computational complexity, as checking the equivalence between two quantum circuits is coQMAhard (quantum analog of coNP) ^{1},^{2}. Despite this, we still have some heuristic efficient algorithms for quantum circuit simplification. In this blog post, I will introduce a powerful tool for this problem, ZXcalculus.
A quantum circuit is a graph representing tensor products and matrices products. For example, this is the circuits representing \(\mathrm{CNOT}(2,3)\cdot\mathrm{CNOT}(1,2)\cdot(H\otimes I\otimes I).\)
Also, quantum circuits can be regarded as a special type of tensor network. In ZXcalculus, we introduce two kinds of tensors, Zspiders, and Xspiders. Tensor networks that consist of these tensors are called ZXdiagrams. As all basic quantum gates can be represented by ZXdiagrams, we can transform all quantum circuits to ZXdiagrams. Moreover, by the definition of Zspiders and Xspiders, there are basic equivalent rules with which one can simplify ZXdiagrams. After simplifying ZXdiagrams, we should transform them back to circuits. In the paper ^{3}, they developed algorithms for the above scheme.
During GSoC 2020, I’m going to achieve a Julia implementation of ZXcalculus. In the following sections, I will explain the reasons and methods briefly for this project.
Proposal for this GSoC project
The main proposal of this project is to implement ZXcalculus and its related algorithm in Julia language. And we will release a Julia package ZXCalculus.jl
. There exists a Python implementation of ZXcalculus, PyZX
. Like PyZX
, ZXCalculus.jl
will provide APIs for rewriting ZXdiagrams, extracting circuits from ZXdiagrams, simplifying circuits. Visualization of ZXdiagrams will be available in ZXCalculus.jl
too. Most functions of PyZX
will be implemented in ZXCalculus.jl
. Besides these, we will integrate ZXCalculus.jl
in the quantum compiler YaoLang.jl
and implement a compilationlevel circuit simplification engine.
In YaoLang.jl
, one can define hybrid quantum programs with classical information (e.g. classical parameters, classical control flows). These quantum programs will be transformed into an intermediate representation (the Yao IR), which contains quantum circuits along with SSA (static single assignment) form of the classical program. These circuits will be simplified with ZXCalculus.jl
. Then YaoIR
s will be compiled to backend instructions, like QASM or the simulator instructions of Yao.
To achieve the best performance in the compilation and enable further customization of the simplification procedure, a pure Julia implementation of ZXcalculus is necessary.
Methods
The circuits extraction method is a canonical method of ZXcalculus based circuit simplification algorithms. I will mainly discuss how I implement this method.
Data structures
To implement these algorithms, we need to implement data structures for storing ZXdiagrams and rules on how ZXdiagrams change. A ZXdiagram can be regarded as a multigraph with extra information on its vertices. Each vertex is one of Zspider, Xspider, or Hbox. In the original ZXdiagrams, open edges are allowed. For simplicity, we added 2 special kinds of vertices, input boundary, and output boundary, for recording these edges. We use the adjacency list representation for storing multigraphs. An adjacency list is stored as Dict
whose keys are the ids of vertices.
1 

Because we need to rewrite multigraphs with ZXcalculus rules, it will be more convenient to fix vertices ids. So we use Dict
instead of Array
. There are phases for Zspiders and Xspiders. We need another Dict for storing these phases. The data struct of ZXdiagram is similar to follow:
1 

In the paper, they proposed graphlike ZXdiagrams. Graphlike ZXdiagrams have only Zspiders and have different types of edges, Hadamard edges, and nonHadamard edges. We can also use multigraphs for representing graphlike ZXdiagrams. We can use different edge multiplicities for representing different edge types. We define ZXGraph
for graphlike ZXdiagrams:
1 

From now, we have built up data structs we need.
Rewriting rules
To simplify ZXdiagrams, we need to implement rewriting rules in ZXcalculus. There are two steps, matching rules and rewriting ZXdiagrams with corresponding rules. We used the holy traits tricks for Julia multiple dispatch for matching and rewriting. The APIs are like these:
1 

Here match
will return all matched vertices which will be stored in the struct
1 

And rewrite!
will try to use a rule to rewrite a ZXdiagram on the all matched vertices. Since some matched vertices may become unsatisfied with the corresponding rule after rewriting some vertices. We need to check whether a rule is still available on matched vertices.
1 

For simpilifying ZXdiagram with a rule, we defined simplify!
which is like
1 

In the simplification scheme of ^{3}, we need to convert a ZXdiagram to a graphlike ZXdiagram with rules i1, i2, h, and f. Then simplify the graphlike ZXdiagram with local complementary rule and pivoting rule. We can accomplish these steps with the above functions. Simplified graphlike ZXdiagrams will be only small skeletons comparing to original large circuits. The only thing remained is extracting circuits from ZXdiagrams.
Circuit extraction
This is the most complicated part of the simplification scheme. For more detail, one can read the original paper. I will only explain the circuit extraction algorithm briefly.
There is a property for any ZXdiagram of a quantum circuit. That is we can define a gflow on it. With a gflow, we can know the order of all spiders. The rules we used for simplifying the ZXdiagram will preserve this good property. It gives us the possibility to extracting circuits from simplified ZXdiagrams.
Moreover, any graphlike ZXdiagrams are CNOT + H circuits locally. We can extract these CNOT circuits with Gaussian elimination over $F_2$. Together with the remaining H gates, CZ gates, and Zrotations, we get a circuit equivalent to the original one.
Demo
The demo circuit is from the appendix of the paper ^{3}. All the codes can be found in examples\ex1.jl
of ZXCalculus.jl
.
1 

1 

1 

1 

1 

1 

Finally we got the simplified circuit.
What I have done
In the past phases during GSoC 2020, I have built up the main part of ZXCalculus.jl
, including
 data structures for representing ZXdiagrams,
 rewriting rules,
 circuit simplification algorithms ^{3},^{4},
 APIs for constructing ZXdiagrams from quantum gates,
 basic visualization of ZXdiagrams.
With the above functions, one can construct a circuit and simplify it. This is our main goal before the first evaluation. In the next phase, we will focus on the integration of ZXCalculus.jl
and YaoLang.jl
.