Abstract
dc:description.abstractDespite the widespread belief that quantum computers cannot be efficiently simulated classically, efficient simulation is known to be possible in certain restricted regimes. In particular, the Gottesman-Knill theorem states that Clifford circuits can be efficiently simulated. We begin this thesis by reviewing and comparing several known techniques for efficient simulation of Clifford circuits: the stabilizer formalism, CH form, affine form, and the graph state formalism. We describe each simulation method and give four different proofs of the Gottesman-Knill theorem. Next we review a recent work [15], which shows that restricting the geometry of Clifford circuits can lead to a further speedup. We give an algorithm for simulating Pauli basis measurements on a planar graph state in time \widetilde{O}(nω/2), where ω < 2.373 is the matrix multiplication exponent. This algorithm achieves a quadratic speedup over using Clifford simulation methods directly. As an application of this algorithm, we consider a depth-$d$ Clifford circuit whose two-qubit gates act along edges of a planar graph and describe how to sample from its output distribution or compute an output probability in time \widetilde{O}(nω/2d\omega). For $d= O(\log n)$, both of these results are quadratic speedups over using Clifford simulation methods directly. Finally, we extend these simulation algorithms to universal circuits by using stabilizer rank methods. We follow a previously known gadgetization procedure [9] to show that given a depth-$d$ Clifford+$T$ circuit with $t$ $T$ gates and whose two-qubit gates act along edges of a planar graph, we can sample from its output distribution in time \widetilde{O}(20.7926tn5/2t6 d3) and can compute output probabilities in time \widetilde{O}(20.3963tn3/2t6 d3). Previous work [9,6], applied to the case $d=O(\log n)$, gives algorithms for sampling in time O(20.3963t n6 t6) and computation of output probabilities in time O(20.3963tn3t3). Our sampling algorithm offers improved scaling in $n$ but poorer scaling in the exponential term, while our algorithm for computing output probabilities offers improved scaling in $n$ with identical scaling in the exponential term.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2021
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Kerzner, Alexander
- Advisor dc:contributor.advisor
-
- Gosset, David
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/17038