Quantum advantage of unitary Clifford circuits with magic state inputs

Authors:
Top Cited Papers
Open Access
Publisher website
Google Scholar
Abstract
We study the computational power of unitary Clifford circuits with solely magic state inputs (CM circuits), supplemented by classical efficient computation. We show that CM circuits are hard to classically simulate up to multiplicative error (assuming polynomial hierarchy non-collapse), and also up to additive error under plausible average-case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply. Along the way, we give an extension of the Gottesman–Knill theorem that applies to universal computation, showing that for Clifford circuits with joint stabilizer and non-stabilizer inputs, the stabilizer part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabilizer part. Finally, we discuss implementational advantages of CM circuits.
Funding Information
  • European Union's Horizon 2020
  • Engineering and Physical Sciences Research Council (EP/R043957/1)
  • Leverhulme Early Career Fellowship

This publication has 17 references indexed in Scilit: