Approximate, universal quantum computation is most commonly described by circuits consisting of Clifford+T gates. The T gate, except being crucial for the universality, is the one which is, in real-world implementations, the most resource-intensive, and the least fault-tolerant of all operations. Because of that, a natural question emerges – how to reduce the number of T gates (or T-count) in a given circuit. The known methods used to reduce the T-count to an optimal value have an exponential running time [24, 2], which motivates the search for an efficient heuristic algorithm. The importance of this problem, along with proposed solutions were discussed in multiple publications including [6, 18, 16, 15, 7, 23]. Spider nest identities, introduced in [16], together with the decomposition of the circuit inspired by [18], were combined in [15] to provide an effective algorithm for T-count reduction. This approach was tested and compared with previous results, and, in some cases, it resulted in a significant improvement of the state of the art. Another advantage of this algorithm was, in contrast to the other results, a significant improvement of the execution time. In this dissertation, we discuss several modifications of the algorithm in order to gain partial outperformance without a significant increase of the running time, which include analysis of the influence of the order of applying the identities, efficient usage of identities generated from small and big spider nests, combining the results obtained in [25] with spider nest identities, and others. Some of these modifications improve or achieve the current state of the art for various circuits. We also provide a quantitative comparison of results, verified using [3] – a tool created alongside [4], on numerous benchmark circuits obtained from [9, 26, 3]. Moreover, we present abstract formulations of considered problem, pose a question of completeness of spider nest identities with respect to T-count reduction, and present different, possibly more elegant, way of phrasing the spider nest identities, as dense spider nest identities.
@mastersthesis{Domitrz2022Masters,
author = {Domitrz, Witalis},
title = {{On the Verge to Improve Technique of T-count Reduction via Spider Nest Identities}},
year = {2021},
school = {University of Oxford},
urldate = {2021-10-22},
link = {https://www.cs.ox.ac.uk/people/aleks.kissinger/theses/domitrz-thesis.pdf},
keywords = {ZX-Calculus, Optimisation, T-count, Clifford+T, Phase Gadgets, Applied, Master Thesis},
abstract = {Approximate, universal quantum computation is most commonly described by circuits consisting of Clifford+T gates. The T gate, except being crucial for the universality, is the one which is, in real-world implementations, the most resource-intensive, and the least fault-tolerant of all operations. Because of that, a natural question emerges – how to reduce the number of T gates (or T-count) in a given circuit. The known methods used to reduce the T-count to an optimal value have an exponential running time [24, 2], which motivates the search for an efficient heuristic algorithm. The importance of this problem, along with proposed solutions were discussed in multiple publications including [6, 18, 16, 15, 7, 23]. Spider nest identities, introduced in [16], together with the decomposition of the circuit inspired by [18], were combined in [15] to provide an effective algorithm for T-count reduction. This approach was tested and compared with previous results, and, in some cases, it resulted in a significant improvement of the state of the art. Another advantage of this algorithm was, in contrast to the other results, a significant improvement of the execution time. In this dissertation, we discuss several modifications of the algorithm in order to gain partial outperformance without a significant increase of the running time, which include analysis of the influence of the order of applying the identities, efficient usage of identities generated from small and big spider nests, combining the results obtained in [25] with spider nest identities, and others. Some of these modifications improve or achieve the current state of the art for various circuits. We also provide a quantitative comparison of results, verified using [3] – a tool created alongside [4], on numerous benchmark circuits obtained from [9, 26, 3]. Moreover, we present abstract formulations of considered problem, pose a question of completeness of spider nest identities with respect to T-count reduction, and present different, possibly more elegant, way of phrasing the spider nest identities, as dense spider nest identities.}
}
Copy to Clipboard