Perdrix, Simon ;
Wang, Quanlong
Supplementarity is Necessary for Quantum Diagram Reasoning
Abstract
The ZXcalculus is a powerful diagrammatic language for quantum mechanics and quantum information processing. We prove that its pi/4fragment is not complete, in other words the ZXcalculus is not complete for the so called "Clifford+T quantum mechanics". The completeness of this fragment was one of the main open problems in categorical quantum mechanics, a programme initiated by Abramsky and Coecke. The ZXcalculus was known to be incomplete for quantum mechanics. On the other hand, its pi/2fragment is known to be complete, i.e. the ZXcalculus is complete for the so called "stabilizer quantum mechanics". Deciding whether its pi/4fragment is complete is a crucial step in the development of the ZXcalculus since this fragment is approximately universal for quantum mechanics, contrary to the pi/2fragment.
To establish our incompleteness result, we consider a fairly simple property of quantum states called supplementarity. We show that supplementarity can be derived in the ZXcalculus if and only if the angles involved in this equation are multiples of pi/2. In particular, the impossibility to derive supplementarity for pi/4 implies the incompleteness of the ZXcalculus for Clifford+T quantum mechanics. As a consequence, we propose to add the supplementarity to the set of rules of the ZXcalculus.
We also show that if a ZXdiagram involves antiphase twins, they can be merged when the ZXcalculus is augmented with the supplementarity rule. Merging antiphase twins makes diagrammatic reasoning much easier and provides a purely graphical meaning to the supplementarity rule.
BibTeX  Entry
@InProceedings{perdrix_et_al:LIPIcs:2016:6506,
author = {Simon Perdrix and Quanlong Wang},
title = {{Supplementarity is Necessary for Quantum Diagram Reasoning}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {76:176:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6506},
URN = {urn:nbn:de:0030drops65062},
doi = {10.4230/LIPIcs.MFCS.2016.76},
annote = {Keywords: quantum diagram reasoning, completeness, ZXcalculus, quantum computing, categorical quantum mechanics}
}
19.08.2016
Keywords: 

quantum diagram reasoning, completeness, ZXcalculus, quantum computing, categorical quantum mechanics 
Seminar: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Issue date: 

2016 
Date of publication: 

19.08.2016 