I was looking at the assumptions behind the Microsoft Azure resource estimator, which is mostly built on Litinsky's paper.

Calling $Q_{\text{Alg}}$ the number of logical qubits required by the end-user algorithm, they claim that the total number of logical qubits (more specifically "tiles") required by the algorithm is (Eq (D1) on page 29):

$$Q = 2 Q_{\text{Alg}}+\sqrt{8 Q_{\text{Alg}}}+1$$

It comes from the "fast block" scheme of Litinsky, shown below. This number excludes all the distillation part of the computer used to distill the magic states (they are acknowledged with another equation which I won't discuss).

My question: Am I correct by saying that this number neglects the count of the purified magic-state used in the computation, as it will occupy one of the tiles below. I insist on the fact I talk about the purified magic-state that we get at the end of the distillation process, I am not talking about the distillation factory.

In practice, if we inject one $T$-gate per clock cycle, it would be negligible in the total count, but "conceptually" the total number of tiles we need should then be written as:

$$Q = 2 (Q_{\text{Alg}}+\color{red}1)+\sqrt{8 (Q_{\text{Alg}}+\color{red}1)}+1$$

However, if I wanted to do more than one state injection per timestep (if some $T$-gates layer commute for instance), I should write

$$Q = 2 (Q_{\text{Alg}}+\color{red}N_{\parallel})+\sqrt{8 (Q_{\text{Alg}}+\color{red}N_{\parallel})}+1$$

where $N_{\parallel}$ is the maximum number of parallel $T$-gate implemented in the algorithm (and in this case it might not necessarily be negligible).

If the answer is "it doesn't matter, it is negligible", I would like to understand why in the case of $N_{\parallel}>1$, but overall I would like to check that my conceptual understanding is correct, i.e. that I am correct about the "exact" formulas (this is the most important point of my question).

Would you agree with me or I am missing something??

enter image description here


1 Answer 1


There isn't a hard yes or no answer to this question. You have to count the hardware time consumed by the output state somewhere, but there's nothing that intrinsically requires you to consider it part of the factory.

You could also count it part of the routing, or part of the gate teleportation fixup used to consume the magic state, or part of a buffer region that keeps a reserve of magic states to smooth out stalls, or etc.

  • $\begingroup$ I agree that we could imagine many different ways to compile on the hardware. But if I follow the logic of Litinsky (the way he uses the fast block), am I correct that the purified magic state needed to implement a $T$ gate must occupy one of the 2-qubit patches? If the answer is yes it might mean Azure thinks in different terms of how the computation is compiled (and I need to understand how). If the answer is no: then I didn't understand the logic of Litinsky and I would be interested by a clarification. $\endgroup$ Nov 30, 2023 at 9:23
  • $\begingroup$ @MarcoFellous-Asiani The magic state can probably sit in the hallway since it's the thing that need to travel down the hallway. In any case this is a negligible cost compared to the size of the factory and to the number of logical qubits that need to be stored by the algorithm. $\endgroup$ Nov 30, 2023 at 10:50

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.