Designs from Magic-Augmented Clifford Circuits

We introduce magic-augmented Clifford circuits—architectures in which Clifford circuits are preceded and/or followed by constant-depth circuits of non-Clifford (“magic”) gates—as a resource-efficient way to realize approximate <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mi>k</a:mi> </a:math> -designs, with reduced circuit depth and usage of magic. We prove that shallow-Clifford circuits, when augmented with constant-depth circuits of magic gates, can generate approximate unitary and state <c:math xmlns:c="http://www.w3.org/1998/Math/MathML" display="inline"> <c:mi>k</c:mi> </c:math> -designs with <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"> <e:mi>ε</e:mi> </e:math> relative error. The total circuit depth for these constructions on <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"> <g:mi>N</g:mi> </g:math> qubits is <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline"> <i:mi>O</i:mi> <i:mo stretchy="false">(</i:mo> <i:mi>log</i:mi> <i:mo></i:mo> <i:mo stretchy="false">(</i:mo> <i:mi>N</i:mi> <i:mo>/</i:mo> <i:mi>ε</i:mi> <i:mo stretchy="false">)</i:mo> <i:mo stretchy="false">)</i:mo> <i:mo>+</i:mo> <i:msup> <i:mn>2</i:mn> <i:mrow> <i:mi>O</i:mi> <i:mo stretchy="false">(</i:mo> <i:mi>k</i:mi> <i:mi>log</i:mi> <i:mo></i:mo> <i:mi>k</i:mi> <i:mo stretchy="false">)</i:mo> </i:mrow> </i:msup> </i:math> in one dimension and <q:math xmlns:q="http://www.w3.org/1998/Math/MathML" display="inline"> <q:mi>O</q:mi> <q:mo stretchy="false">(</q:mo> <q:mi>log</q:mi> <q:mo></q:mo> <q:mi>log</q:mi> <q:mo></q:mo> <q:mo stretchy="false">(</q:mo> <q:mi>N</q:mi> <q:mo>/</q:mo> <q:mi>ε</q:mi> <q:mo stretchy="false">)</q:mo> <q:mo stretchy="false">)</q:mo> <q:mo>+</q:mo> <q:msup> <q:mn>2</q:mn> <q:mrow> <q:mi>O</q:mi> <q:mo stretchy="false">(</q:mo> <q:mi>k</q:mi> <q:mi>log</q:mi> <q:mo></q:mo> <q:mi>k</q:mi> <q:mo stretchy="false">)</q:mo> </q:mrow> </q:msup> </q:math> in all-to-all circuits using ancillas, which improves upon previous results for small <y:math xmlns:y="http://www.w3.org/1998/Math/MathML" display="inline"> <y:mi>k</y:mi> <y:mo>≥</y:mo> <y:mn>4</y:mn> </y:math> . Furthermore, our construction of relative-error state <ab:math xmlns:ab="http://www.w3.org/1998/Math/MathML" display="inline"> <ab:mi>k</ab:mi> </ab:math> -designs only involves states with strictly local magic. The required number of magic gates is parametrically reduced when considering <cb:math xmlns:cb="http://www.w3.org/1998/Math/MathML" display="inline"> <cb:mi>k</cb:mi> </cb:math> -designs with bounded additive error. As an example, we show that shallow-Clifford circuits followed by <eb:math xmlns:eb="http://www.w3.org/1998/Math/MathML" display="inline"> <eb:mi>O</eb:mi> <eb:mo stretchy="false">(</eb:mo> <eb:msup> <eb:mi>k</eb:mi> <eb:mn>2</eb:mn> </eb:msup> <eb:mo stretchy="false">)</eb:mo> </eb:math> single-qubit magic gates, independent of system size, can generate an additive-error state <ib:math xmlns:ib="http://www.w3.org/1998/Math/MathML" display="inline"> <ib:mi>k</ib:mi> </ib:math> -design. We develop a classical statistical mechanics description of our random circuit architectures, which provides a quantitative understanding of the required depth and number of magic gates for additive-error state <kb:math xmlns:kb="http://www.w3.org/1998/Math/MathML" display="inline"> <kb:mi>k</kb:mi> </kb:math> -designs. We also prove no-go theorems for various architectures to generate designs with bounded relative error.