I'm trying to find an exact resource count for specific QFTs.

A QFT generally needs small power-of-two rotations. These can be constructed out of Clifford+T, but I'm wondering if one can inject them directly into a surface code and do some gate teleportation.

One approach for distillation is to copy the traditional T-gate distillation, and inject many noisy rotations of some angle, then use something like a $[[2^r-1,1,3]]$ quantum Reed-Muller to correct the logical surface code qubits, then continue. However, the error correction zoo says this is the smallest code with such transversal gates, but it needs $2^r-1$ qubits!

I found this paper, but I don't see anything in their methods that protects against an "overshooting" kind of error, where the physical rotations are a bit too far or too short.

Finally, once it's distilled, the usual T-gate teleportation method works, except that when we measure a "1", the phase clean-up to teleport a $\frac{\pi}{2^k}$ gate will be $\frac{\pi}{2^{k-1}}$. But we can always just repeat the process for that phase cleanup, and as soon as we measure 0 after the teleportation, the chain stops. So on average, a constant number of these rotation gates.

My question is: are there better method(s) for either distillation or teleportation of arbitrary and/or power-of-two rotation gates?


1 Answer 1


Generally speaking, you would never do a $\pi/2^{10}$ rotation by physical injection and distillation. It would be horrendously expensive. It's far cheaper to use a series of T and H gates to approximate the small rotation.

Even cheaper than that is to pay to create a series of states $Z^{2^{-0}}|+\rangle$, $Z^{2^{-1}}|+\rangle$,$Z^{2^{-2}}|+\rangle$,$Z^{2^{-3}}|+\rangle$,$Z^{2^{-4}}|+\rangle$, $\dots$ up to $Z^{2^{-10}}|+\rangle$ or up to some precision cutoff. You can then use catalysis (see figure 14 of arXiv:1812.01238) or phase gradient kickback via an adder (page 4 of arXiv:1709.06648) to apply the rotation very cheaply.

I'm trying to find an exact resource count for specific QFTs.

arXiv:1803.04933 explains how to do phase gradient kickback specifically for the QFT. In the QFT you can truncate rotations quite aggressively, down from $O(n^2)$ rotations to $O(n \lg \frac{1}{\epsilon})$ rotations. And because of the kickback using adders, each kept rotation ends up with a T cost of 4.

Note that, in many contexts, the QFT appears at the end of the circuit. When that happens, you can use qubit recycling to reduce the number of rotations to $O(n)$. In that context it's likely cheaper to synthesize each rotation from scratch rather than bother with a phase gradient state.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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