This is the homepage1 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. 7: Topics in Stabilizer Quantum Computation (Mark Howard)
The central question in quantum information theory is to delineate the operational capabilities achievable under the rules of quantum mechanics but not achievable with classical physics. As such, it can be useful to tinker with hypothetical theories having different sets of allowed state preparations, transformations and measurements; different combinations can give us theories that are less powerful than, equal to, or more powerful than quantum mechanics. When we attempt to understand the computational power of circuits, so-called stabilizer circuits comprise a restricted class that are provably weaker than a general (“universal”) quantum computer. For stabilizer circuits, the description of the achievable states and their updates is efficient leading to a classical simulation algorithm that is polynomial in the number of qubits. Remarkably, it is easy to boost the power of stabilizer circuits to that of a universal quantum computer by adding access to non-stabilizer states or operations. When error-correction is used these additional states or operations are typically very costly. All of the above naturally suggests a few questions that I will address:
1) How should we classically simulate stabilizer circuits interspersed with a few non-stabilizer gates, and how does the runtime scale?
2) How can we minimize the use of costly non-stabilizer operations?
3) What quantum mechanical property is missing from stabilizer circuits but present in universal quantum computers?
Apr. 14: Trading classical and quantum resources (Selman Ipek)
The stabilizer rank of a pure quantum state is defined as the smallest integer such that can be expressed as a superposition of 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+ gates in terms of the stabilizer rank of the magic input state .
References: arXiv:1506.01396
May 12: Stabilizer simulation methods for mixed magic states and noisy channels (James Seddon)
It has been known since the early days of the stabilizer formalism that while Clifford circuits with stabilizer state inputs can be simulated efficiently in the number of qubits and operations, more general circuits can be simulated with an overhead growing exponentially with, for example, the number of T gates, or some other “magic” resource. Quantifiers of magic resource known as magic monotones formalize the notion that some states/operations are harder to simulate than others, and various classical simulation algorithms have been proposed where performance guarantees depend explicitly on some magic monotone. A sequence of works on stabilizer rank culminated in the powerful simulator of Ref. [1], which reduces runtime by replacing an exact stabilizer decomposition with a sparsified approximation, but is largely restricted to simulating pure state evolution. Meanwhile, a parallel avenue of research developed links between quasiprobability simulation methods and robustness-type monotones [2, 3], yielding the insight that noisier circuits can be easier to simulate. Simulators of this type admit mixed initial states and more general quantum channels, but tend to be slower than stabilizer rank-based methods. In this seminar I will outline how stabilizer rank methods can be extended to deal with mixed magic states [4] and noisy non-Clifford operations [5], in the process improving on the runtime bounds of Ref. [1]. I will also discuss how this method (and the others introduced in Ref. [4]) can be situated within a broader framework of simulators for general quantum circuits on qubits, each with an associated magic monotone, showing that stabilizer rank and quasiprobability methods are more closely related than they first appear.
References:
[1] Bravyi, Browne, Calpin, Campbell, Gosset & Howard (2019) arxiv:1808.00128
[2] Pashayan, Wallman & Bartlett (2015) arxiv:1503.07525
[3] Howard & Campbell (2017) arxiv:1609.07488
[4] Seddon, Regula, Pashayan, Ouyang and Campbell (2021) arxiv:2002.06181
[5] Seddon (2022) https://discovery.ucl.ac.uk/id/eprint/10146361/
May 22: Quasiprobability methods in classical simulation (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
May. 26: Classical simulation of quantum circuits (Hakop Pashayan)
I will give some background on classical simulation then I will present a general framework for simulating quantum circuits using quasiprobabilistic methods. Through examples, I will demonstrate the strengths of this approach in its runtime performance, flexibility and generality.