The most fundamental open problem related to the ZX-calculus is establishing its completeness properties for some of the calculus' variants and introducing additional rules where the zx-calculus is known to be incomplete.
Completeness Definition
The completeness of the calculus is with respect to the traditional Hilbert space formulation of quantum mechanics. Formally completeness can be stated as:
〚$D_1$〛 $=$ 〚$D_2$〛 $\ \Longrightarrow\ ZX \vdash \ D_1 = D_2$
In other words, given two diagrams in the ZX-calculus, if their Hilbert space interpretations are equal, then we should be able to prove that the two diagrams are equal under the axioms of the ZX-calculus.
Known Completeness Results
We list all the known completeness results for the ZX-calculus and two restrictions of the calculus which correspond to the set of operations that can be generated by Clifford group quantum operations and Clifford+T quantum operations.
(Unrestricted) ZX-calculus
The ZX-calculus without any restrictions on the admissible angles of its nodes is sound and universal for quantum computing, but it is not complete [1] . Moreover, it is not complete even for single qubits (which correspond to line diagrams in ZX, i.e. diagrams where each node has degree at most two).
ZX-calculus restricted to Clifford operations
If we restrict the admissible angles of the nodes in a ZX-diagram to those which are integer multiples of $\pi/2$ (that is, every angle is either $0,\ \pi/2,\ \pi\,\ -\pi/2$), then the set of ZX-calculus diagrams correspond exactly to the Clifford segment of quantum mechanics (also known as Stabilizer Quantum Mechanics). This variant of the calculus is complete for stabilizer quantum mechanics [2] [3].
ZX-calculus restricted to Clifford+T operations on single qubits
If we restrict the admissible angles of the nodes in a ZX-diagram to those which are integer multiples of $\pi/4$, then the set of ZX-calculus diagrams correspond exactly to the Clifford+T segment of quantum mechanics (the T gate is also known as the $\pi/8$ gate). This set of operations is approximately universal, meaning that these operations can be used to approximate any other quantum operation with arbitrary accuracy. If, in addition, we restrict ourselves to performing single-qubit operations, then the ZX-calculus is complete for this segment of quantum mechanics [4].
Open Problems
The two main open problems related to completeness are listed below.
Completeness for the Clifford+T case
Outside of the single-qubit case, it is not known whether the ZX-calculus is complete or not for the Clifford+T segment of quantum computing.
Extensions to the calculus
The unrestricted ZX-calculus is incomplete and therefore it should be extended with additional rules if we wish to be able to prove equalities which are currently not derivable within it.
In addition, if the open question about completeness for the Clifford+T segment is answered negatively, then extensions for that variant of the calculus should also be developed.
List of papers
A comprehensive list of related papers.
- The ZX-calculus is incomplete for quantum mechanics
- The ZX-calculus is complete for stabilizer quantum mechanics (2012, QPL)
- The ZX-calculus is complete for stabilizer quantum mechanics (2014, NJP, revised)
- The ZX-calculus is complete for the single-qubit Clifford+T group
List of talks
- Vladimir Zamdzhiev, The ZX-calculus is incomplete for quantum mechanics
- Miriam Backens, The ZX-calculus is approximately complete for single qubits
List of presentation slides
- Vladimir Zamdzhiev, The ZX-calculus is incomplete for quantum mechanics
- Miriam Backens, Completeness results for the ZX-calculus