THEORETICAL COMPUTER SCIENCE, THE INTERSECTION OF COMPUTATIONAL COMPLEXITY AND ZX CALCULUS

Optimization of ZX Diagrams via Methods from Computational Complexity

Computational Complexity and Quantum Computation are two areas of Theoretical Computer Science. The first one is about how hard problems are and how many resources are needed to solve them. Quantum Complexity is the subarea of Computer Science that uses quantum mechanics, especially entanglement and superposition phenomena.

ZX Calculus is a graphical calculus for quantum computation, strongly connecting to quantum circuits. Quantum circuits are known to be equivalent to the most popular models of computation among quantum researchers. The ZX calculus consists of ZX diagrams, being open graphs, and transformation rules. I am interested in the optimization of ZX diagrams via methods from Computational Complexity and researching the intersection of ZX Calculus and Computational Complexity in general.

The ZX Calculus strongly connects to various areas of mathematics, like Graph Theory or Category Theory. The intersection of ZX and Computational Complexity has not been researched in detail, but it is becoming more popular.

One of the ideas is relating ZX optimization to reconfiguration problems, like graph recolouring. It could, for instance, involve a deep analysis of the cycle structure in the diagrams.

Ideally, the project would lead to the classification of minimal ZX diagrams among equivalence classes, relation to quantum circuits, establishing the complexity of known reductions in the field, and designing new optimization techniques.