11
$\begingroup$

My question

I am looking for some review paper, or a list of different papers providing concrete numbers about the depth, number of qubits and number of $T$ gates required on the Clifford+T basis for usefull quantum algorithms (quantum Fourier transform, Grover, HHL, any other you can think of).

I am not looking for asymptotic behaviors as I would like to have an idea of the concrete numbers for typical problem sizes. This question is "simple" but I haven't found any paper summarizing it nicely so far, and there are some papers providing only half of the numbers required (for instance the number of qubits but not the depth).

I am in particular interested to find "powerfull algorithms" in the regime where: $Q_L N_L \leq 10^{11}$, where $Q_L$ and $D_L$ are the number of logical qubits, and the logical depth of the algorithm. Typically Shor algorithm applied for RSA 2048 is often given as an example of powerful quantum algorithm. But it requires quite a lot of resources, I am looking for usefull algorithms requiring less than Shor (more precisely in the regime I just provided).

Further information

As suggested in the comment, it may happen that for some algo, the answer will depend on some extra characteristics describing the problem. In such case, one specific example would be fine for me as long as it outperforms the best known classical algo dedicated to solve the same task. Again I just would like to have some rough idea of the number of $T$ gates, qubits and depth required for a quantum algorithm clearly outperforming the best known classical algorithm solving the same task.

The reason why I am looking for Clifford+T decomposition is because I want to know the values for fault-tolerant quantum computing. However ideally, I don't want the paper to already assume which scheme of fault-tolerance I use to implement those gates. I already know how I implement them on my side, I really just need to know the (logical) depth, number of qubits and $T$ gates strictly required by the algorithm assuming I know how to implement $T$ and Clifford. I don't need any restriction in connectivity neither (like nearest neighbor interactions).

As last comment: I know that some of the answer will say "it depends", for instance it depends on how accurate we want the decomposition of the algorithm on the gateset (we can only approximate unitaries with Clifford+T). But anyway in practice to solve a concrete task we can find a reasonably good approximation. I am looking for a kind of source that thought about all this already.

Some references I already found

  • Approximate QFT

This paper provides concrete numbers for everything but the algorithm depth that is lacking.

  • Derivative pricing

This paper given in the comments provides good numbers, but it is not really outperforming what is doable on classical computers (see comments).

  • Computing electromagnetic scattering cross section

This paper provides everything, but the depth is extremly high (typically $10^{20}$ way beyond the regime I am interested in).

Improve this question
$\endgroup$
13
  • 2
    $\begingroup$ One small note: Grover can be done exactly with your set of gates. It doesn't need approximating. But it still depends on what function your oracle is implementing for the search. This could easily massively outweigh the "basic" cost of the other gates that we know about explicitly. $\endgroup$
    – DaftWullie
    Commented Oct 13, 2021 at 7:39
  • 1
    $\begingroup$ @DaftWullie I am thinking about typical algorithm considered for the large scale. Such as Shor, Grover, etc. Sycamore is doing NISQ and it is not so clear about wether or not it outpeforms classical computer. I am interested in such values for those "famous" algorithms (Grover, Shor etc) in cases there is no doubt today that the best classical computer would not be able to solve it in a "reasonable" amount of time. $\endgroup$
    – Marco Fellous-Asiani
    Commented Oct 13, 2021 at 15:13
  • 2
    $\begingroup$ Shamelessly plugging in some work that I was a part of which computed the number of qubits, T-count and T-depth in order to implement Amplitude Estimation to price a financial derivative quantum-journal.org/papers/q-2021-06-01-463 $\endgroup$
    – sheesymcdeezy
    Commented Oct 14, 2021 at 15:58
  • 1
    $\begingroup$ Here are two more papers that address T-gate counts for QPE for quantum chemistry and Solving the 1-d wave equation using Hamiltonian simulation (disclaimer: I'm the main author of the second paper). $\endgroup$
    – Adrien Suau
    Commented Oct 18, 2021 at 8:43
  • 2
    $\begingroup$ ... we want this algorithm to be useful we need a quantum computer that can execute a T-depth of 10^8 with 8000 error corrected qubits in 1 second. Otherwise we can just use our current classical methods instead. This (1) gives the hardware people an interesting benchmark to aim for and (2) algorithm people motivation to try and find better tricks to reduce these requirements. (2/2) $\endgroup$
    – sheesymcdeezy
    Commented Jan 19, 2022 at 18:36

2 Answers 2

Reset to default
6
+500
$\begingroup$

Copying over from "Are circuits with more than 1000 gates common?". Note that a Toffoli gate is roughly as expensive as 2T gates or 4T gates, depending on your architecture.

According to Table III of https://arxiv.org/abs/2011.03494 , quantum chemistry algorithms looking at properties of the FeMoCo molecule use half a billion Toffoli gates.

enter image description here

According to Table 1 of https://arxiv.org/abs/1905.09749 , factoring 2048 bit numbers takes 3 billion Toffoli gates:

enter image description here

According to Table 1 of https://arxiv.org/abs/2001.09580 , 256 bit elliptic curve discrete logarithms take a few billion T gates:

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks a lot. The two first table are unfortunately a bit outside of my range of interest (but this is still very interesting info to keep in mind). In case you want to update your answer, I found a less demanding algo for ECC: tches.iacr.org/index.php/TCHES/article/view/8741/8341 it requires only one million in terms of depth (it's an upper bound) $\endgroup$
    – Marco Fellous-Asiani
    Commented Jan 18, 2022 at 19:36
  • $\begingroup$ The motivations behind my question are to find algorithm not "as demanding" as Shor for RSA 2048, but that would still provide interesting results (outperforming best classical algorithms ran on state of the art supercomputer). ECC is one good candidate. I am interested in other examples (for quantum chemistry for instance) $\endgroup$
    – Marco Fellous-Asiani
    Commented Jan 18, 2022 at 19:46
6
$\begingroup$

The most useful use-case I found for a big fault-tolerant quantum computer, besides Shor, is a simulation of molecules, which are too hard to simulate on classical computers + demand fault-tolerant computers.

Read this article

Generally speaking, you can see the following demand (depending on the accuracy you want): Table 1

The approximation that they are doing about the number of physical qubits, is ok that this is just approximation because it depends on noise and coding, which is ok to be talked separately not in this context when showing a new algorithm application.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you a lot for the ref! $\endgroup$
    – Marco Fellous-Asiani
    Commented Jan 19, 2022 at 19:01

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.