Abstract
In faulttolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and π/2phase rotations, together with T operations (π/4phase rotations). For many error correcting codes, faulttolerant realisations of Clifford operations are significantly less resourceintensive than those of T gates, which motivates finding ways to realise the same transformation involving Tcount (the number of T gates involved) which is as low as possible. Investigations into this problem [Matthew Amy et al., 2013; Gosset et al., 2014; Matthew Amy et al., 2014; Matthew Amy et al., 2018; Earl T. Campbell and Mark Howard, 2017; Matthew Amy and Michele Mosca, 2019] has led to observations that this problem is closely related to NPhard tensor decomposition problems [Luke E. Heyfron and Earl T. Campbell, 2018] and is tantamount to the difficult problem of decoding exponentially long ReedMuller codes [Matthew Amy and Michele Mosca, 2019]. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the Tcount, based on the effective application of "spider nest identities": easily recognised products of parityphase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the Tcounts of a number of circuits, in runtimes which are typically less than the time required to make a fresh cup of coffee.
BibTeX  Entry
@InProceedings{debeaudrap_et_al:LIPIcs:2020:12070,
author = {Niel de Beaudrap and Xiaoning Bian and Quanlong Wang},
title = {{Fast and Effective Techniques for TCount Reduction via Spider Nest Identities}},
booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
pages = {11:111:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771467},
ISSN = {18688969},
year = {2020},
volume = {158},
editor = {Steven T. Flammia},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12070},
URN = {urn:nbn:de:0030drops120705},
doi = {10.4230/LIPIcs.TQC.2020.11},
annote = {Keywords: Tcount, Parityphase operations, Phase gadgets, Clifford hierarchy, ZX calculus}
}
Keywords: 

Tcount, Parityphase operations, Phase gadgets, Clifford hierarchy, ZX calculus 
Collection: 

15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020) 
Issue Date: 

2020 
Date of publication: 

08.06.2020 
Supplementary Material: 

The software which produced our results may be found on GitHub, at https://github.com/njross/optimizer, commit 46b8ce0873ff09bf54cf704080b7daa252c48eba. 