QLunch: Quantum advantage of unitary Clifford circuits with magic state inputs

Speaker: Richard Jozsa, DAMTP, University of Cambridge UK 

Title: Quantum advantage of unitary Clifford circuits with magic state inputs

Abstract: 

We study the computational power of unitary Clifford circuits with solely magic state inputs and only final Z basis measurements (called CM circuits), supplemented by classical efficient computation. We will begin by reviewing the so-called Pauli Based Computation model of Bravyi, Smith and Smolin, and show how this formalism leads to an extension of the Gottesman-Knill theorem, that applies to universal computation: for (generally adaptive) Clifford circuits with joint stabiliser and non-stabiliser inputs, the stabiliser part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabiliser part, from whose outputs (with classical post-processing) the original circuit can be sampled. 

Using this result, we show that CM circuits together with postselection can simulate arbitrary postselected quantum circuits, and deduce that CM circuit outputs are hard to classically simulate up to additive error under plausible average case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply, any one of which suffices to imply hardness of classical simulation for CM circuits. 

This is joint work with Mithuna Yoganathan and Sergii Strelchuk.