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.


List of talks



List of presentation slides



Bibliography
1. Christian Schröder de Witt & Vladimir Zamdzhiev (2014): The ZX-calculus is incomplete for quantum mechanics. In: Proceedings 11th International Workshop on Quantum Physics and Logic, Kyoto, Japan June 4-6, 2014. Available at http://arxiv.org/abs/1404.3633
2. Miriam Backens (2014): The ZX-calculus is complete for stabilizer quantum mechanics. In New Journal of Physics. Vol. 16. No. 9. Pages 093021. September, 2014. doi:10.1088/1367-2630/16/9/093021
3. Miriam Backens (2012): The ZX-calculus is complete for stabilizer quantum mechanics. In: Proceedings 9th International Workshop on Quantum Physics and Logic, Brussels, Belguim October 10-12, 2012. Available at http://arxiv.org/abs/1307.7025.
4. Miriam Backens (2014): The ZX-calculus is complete for the single-qubit Clifford+T group. In: Proceedings 11th International Workshop on Quantum Physics and Logic, Kyoto, Japan June 4-6, 2014. Available at http://www.cs.ox.ac.uk/people/miriam.backens/Clifford_T.pdf