Back to search

University of Waterloo

Clifford Simulation: Techniques and Applications

Abstract

dc:description.abstract

Despite 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 × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/17038

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Kerzner, Alexander. Clifford Simulation: Techniques and Applications. University of Waterloo, 2021. http://hdl.handle.net/10012/17038