This is the homepage^{1} of Bilkent Math Graduate Seminars. For the Zoom link visit researchseminars.org.
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).
Mar. 3: Introduction to stabilizer formalism (Selman Ipek)
In the finite-dimensional regime certain pure quantum states can be completely characterized by maximal abelian (i.e., commuting) subgroups of the Pauli group. These are called stabilizer states and well-known examples include Bell as well as Greenberger, Horne, Zeilinger states. The stabilizer formalism is a subtheory of finite-dimensional quantum mechanics consisting of stabilizer states, Clifford unitaries (i.e., unitaries that map one Pauli operator to another), and measurement of Pauli observables. The ability to fully describe such quantum states in group theoretic terms makes their analysis extremely convenient and they play an important role in quantum information processing and also quantum error correction. A key result for our purposes in this seminar is the celebrated Gottesman-Knill theorem which establishes that any quantum circuit built out of stabilizer states, Clifford unitaries, and Pauli measurements (called stabilizer circuits) can be efficiently simulated on a classical computer.
References: arXiv:quant-ph/9807006
References: Nielsen/Chuang: QCQI (Ch. 10)
Mar. 17: Improved simulation of stabilizer circuits (Selman Ipek)
The Gottesman-Knill theorem establishes that stabilizer circuits (defined previously) can be simulated efficiently on a classical computer. In arXiv:quant-ph/0406196 Aaronson and Gottesman improve the efficiency of the classical simulation and demonstrate that stabilizer circuits are (most likely) not universal for classical computation. Circuits that are otherwise stabilizer with the exception of a small number of non-Clifford gates are also considered and the complexity of such circuits scales exponentially with the number of non-Clifford gates.
References: arXiv:quant-ph/0406196
Mar. 24: Universal Quantum Computation with ideal Clifford gates and noisy ancillas (Selman Ipek)
In studying the resources necessary to achieve a quantum speedup it is useful to distinguish between operations that are (a) free, or (b) costly. The fact that stabilizer circuits can be efficiently classically simulated suggests that stabilizer operations be designated as free. This begs the question of whether it is possible to augment the free stabilizer operations with an additional costly resource (to be consumed) which promotes stabilizer circuits to quantum universality. Bravyi and Kitaev (arXiv:quant-ph/0403025) demonstrate that there are certain quantum states (deemed “magic”) which achieve precisely this. They also detail a protocol for distilling such magic states from a collection of noisy ancilla states.
References: arXiv:quant-ph/0403025
Mar. 31: Quantum universality and magic state distillation (Selman Ipek)
Stabilizer circuits can be promoted to quantum universality via the injection of magic states. An open question is the determination of precisely which non-stabilizer quantum states can be considered “magic”. Following Reichardt, we discuss magic state distillation protocols that tighten the boundary between the classically efficiently simulatable regime and that of full universal quantum computation.
References: arXiv:0608085
References: https://core.ac.uk/download/pdf/44132852.pdf
Apr. 14: Trading classical and quantum resources (Selman Ipek)
The stabilizer rank of a pure quantum state $\psi$ is defined as the smallest integer $\chi$ such that $\psi$ can be expressed as a superposition of $\chi$ stabilizer states. Combined with the magic states introduced by Bravyi and Kitaev, such a notion becomes especially useful because one can analyze the complexity of circuits composed of Clifford+$T$ gates in terms of the stabilizer rank of the magic input state $| T \rangle \langle T |^{\otimes m}$.
References: arXiv:1506.01396
May. 5: Quasiprobability methods in classical simulation (I) (Selman Ipek)
Quasiprobability distributions generalize standard probability distributions by allowing for negative values. A well-known example of such distributions is the Wigner function, familiar from quantum optics; i.e., quasiprobability distribution for continuous variable systems. Gibbons, et al. (arXiv:quant-ph/0401155) identified a set of axioms that should be satisfied by any finite-dimensional Wigner function. Building off of this, Gross (arXiv:quant-ph/0602001) defines a Wigner function consistent with Gibbons, et al. and demonstrates for odd-dimensional quantum systems that only stabilizer states are represented non-negatively, and that Clifford unitaries preserve non-negativity of the Wigner function.
References: arXiv:1010.2701
References: arXiv:quant-ph/0602001