10
$\begingroup$

I want to simulate large stabilizer circuits (H/S/CNOT/MEASURE/feedforward) with a small number of T gates mixed in. How can I do this in a way that scales exponentially only in the number of T gates? Are there existing implementations?

$\endgroup$
  • $\begingroup$ Can you separate the Clifford and non-Clifford gates? I.e. you would have a Clifford circuit, then some Ts, then another Clifford circuit, Ts again etc. If you could, I guess it should be then straightforward to have the scaling you wanted? $\endgroup$ – Kiro Apr 17 '18 at 5:30
  • $\begingroup$ @Kiro By using gate teleportation, all of the T gates can be moved to a single layer at the start (at the cost of having one spare qubit per T gate). $\endgroup$ – Craig Gidney Apr 17 '18 at 7:28
7
$\begingroup$

Taking your comment to Kiro to its logical conclusion, the answer is 'yes'. The basic idea is to decompose the T gate 'magic' state $\tfrac{1}{\sqrt 2}\bigl(\lvert 0 \rangle + \mathrm{e}^{i \pi / 4} \lvert 1 \rangle \bigr)$ as a linear combination of stabiliser states. (If you do this for several magic states, this produces an exponentially large linear combination.) Representing the T-gate states involved as density operators, together with any other stabiliser states introduced as inputs or as auxiliary work-space, we can use this expansion to compute the probability of any particular Pauli measurement outcome, such as a standard basis measurement on a single qubit, after performing a stabiliser circuit and gate teleportations of the T gates.

The basic idea behind this can be improved by noting that there is more than one way to expand the T-gate state as a linear combination — particularly if you consider decompositions of several T-gate states at once, rather than expanding each T-gate state independently, and if furthermore you are happy with an approximate simulation rather than an exact one (see e.g. [Bravyi+Gossett 2016] and [Campbell+Howard 2017]).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.