Bilkent Quantum Computing

This is the homepage1 of Bilkent Math Graduate Seminars. For the Zoom link visit


go to last talk

Spring 2023 - Classical Simulation of quantum computations

Among the central problems in the foundations of quantum computation, one is to identify the minimal resources necessary for a quantum speedup. A fruitful approach for the study of this question is to characterize the extent to which quantum computers can be efficiently simulated using classical methods, and to quantify the domain in which classical simulation becomes inefficient; i.e., a quantum speedup. In this seminar series we focus on two key approaches for studying classical simulability. The first is based on the so-called stabilizer formalism introduced by Gottesman (arXiv:quant-ph/9807006), which forms a proper sub-theory of quantum mechanics. In this seminar series we will show (Gottesman-Knill theorem) that quantum circuits consisting only of stabilizer states, Clifford unitaries, and Pauli measurements (called stabilizer circuits) are efficiently classically simulable, thus not universal for quantum computation. However, such Clifford circuits, nevertheless, provide a useful theoretical tool for analyzing the complexity of classically simulating generic quantum circuits. The other method is based on sampling from so-called quasiprobability distributions, which generalize standard probability distributions by taking on negative values; e.g., the Wigner function, familiar from quantum optics. In this latter approach there is a marked distinction between even and odd dimensional quantum systems. Resolving this tension leads to the classical simulation algorithm of Zurel, et al. (arXiv:2004.01992).

Tentative schedule

Part I: Stabilizer simulation: