Using the Q# resource estimator, I found out that my program, meant to do graph coloring using Grover's algorithm, could be decomposed into ~500-1000*x T gates, where x in the number of iterations, often ranging between 5 and 10. This means I am considering thousands of T gates.

I am considering T gates because they can be a universal gate when paired with the Clifford group which is easy to simulate.

I am interested to know the average time it would take for a quantum computer (any type) to execute one of these T gates, time which I would then multiply to estimate the runtime of my program.

Thanks for reading !

  • $\begingroup$ Even though there is a T-count, this often isn't necessarily a good approximation of runtime cost - notably, if you have a multiply controlled NOT gate, Q# will incur T-costs, but your architecture may be able to apply the CCNOT natively $\endgroup$
    – C. Kang
    Oct 25 '20 at 23:53
  • $\begingroup$ Is the question here more about just framing the time cost of your program? Because if so, it's safe to say the runtime will likely be within hours/minutes (rather than days/weeks) $\endgroup$
    – C. Kang
    Oct 25 '20 at 23:54
  • $\begingroup$ @C.Kang I was more interested about the difference between a simulation and a real quantum computer in 10 node graph situation $\endgroup$ Oct 26 '20 at 13:01
  • $\begingroup$ Ah, in that case the quantum computer will run almost certainly much faster than your simulation. Gates typically take on the order of ms / ns to apply $\endgroup$
    – C. Kang
    Oct 26 '20 at 15:55
  • $\begingroup$ @C.Kang what would a good runtime cost approximation be then ? I have to do this for a paper, since I tested graphs from size 1-8, I would like to generalize my results. I saw that there was a resource estimator built in, and I thought I was made for this kind thing. However, I have troubles evaluating what every character means (I am referring to the first comment) $\endgroup$ Oct 26 '20 at 18:42

In the surface code there are two major costs to T gates: the spacetime cost and the reaction time cost.

The spacetime cost is due to the need to perform magic state distillation of a T state for each T gate, which takes hundreds of operations. A T gate factory producing a T state every hundred microseconds can easily monopolize a hundred thousand qubits. This isn't technically a limitation on the time of the computation, because you can just add more and more factories until the T gates are coming at any rate you want, but it represents a large cost that forces hard tradeoffs between more space usage and longer runtime. See https://arxiv.org/abs/1812.01238 and https://arxiv.org/abs/1905.06903. For scale:

enter image description here

The reaction time cost has to do with the fact that when you teleport through a T gate, you instead apply its inverse 50% of the time. You realize that it happened, but it still has to be fixed before the computation can properly progress. Ultimately this means that if you have a series of T gates to apply, you are limited by how fast you can figure out if you did T or inverse T and then correct it. In fact this is the only part of a quantum computation that isn't embarrassingly parallel. There is a technique where this time is minimized by preparing a wordline for each possible correction, and teleporting through the one that matters. With that technique the T depth of your circuit times your control system's reaction time is a lower bound on how fast the computation can finish. See https://arxiv.org/abs/1210.4626 and https://arxiv.org/abs/1905.08916.

enter image description here


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.