Computational complexity perspective on graphical calculi for quantum computation

Mitosek, Piotr B. (2025). Computational complexity perspective on graphical calculi for quantum computation. University of Birmingham. Ph.D.

Preview

Mitosek2025PhD.pdf
Text - Accepted Version
Available under License Creative Commons Attribution.
Download (3MB) | Preview

Abstract

Diagrammatic reasoning via languages such as ZX Calculus is a powerful tool in theoretical quantum computing. However, physical quantum computers do not understand diagrams and require explicit quantum circuits as inputs. Finding a circuit equivalent to the given diagram is known as circuit extraction. Such problems in graphical calculi form a limitation preventing the wider adoption of diagrammatic reasoning.
Computational complexity theory formalises the difficulty of problems. For ZX diagrams, the circuit extraction problem is #P-hard and unlikely to have an efficient algorithm. Therefore, partial solutions are critical. Currently, efficient circuit extraction is only possible for diagrams containing a structure of so-called Pauli flow. This structure is necessary and sufficient for robust determinism in measurement-based quantum computation (MBQC) – a model of quantum computation, an alternative to circuits, where adaptive single-qubit measurements drive computation. Thus, Pauli flow links MBQC, ZX Calculus, and the circuit model. It is known how to find flow structures in polynomial time when they exist; nevertheless, their lengthy and complex definitions often hinder working with them.
In this thesis, I present contributions to two connected topics: the hardness of problems in graphical calculi and Pauli flow as a method for overcoming circuit extraction. First, I show that circuit extraction can be #P-hard for phase-free ZH diagrams, extending the previous result for ZX diagrams. I also establish a relation between phase-free ZH and NP #\(^P\) class. This involves weakening the oracle, crafting a complete problem, and encoding the problem into phase-free ZH.
My next contribution concerns Pauli flow. I simplify the Pauli flow definition by providing a new algebraic interpretation. This involves defining two matrices arising from the adjacency matrix of the underlying graph. Then, Pauli flow corresponds to the existence of a right-inverse of the first matrix, which, when multiplied by the second matrix, results in a matrix of a directed acyclic graph. Based on the newly defined algebraic interpretation, I obtain O(n\(^3\)) algorithms for finding Pauli flow, improving on the previous O(n\(^4\)) bounds. I also introduce a lower bound for Pauli flow-finding by linking it to linear algebra problems over F\(_2\). Finally, when given an unlabelled open graph, I show how to find measurement labelling resulting in Pauli flow.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):