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^7$, where $Q_L$ and $D_L$ are the number of logical qubits, and the logical depth of the algorithm.

Further informations

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. 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 the $T$-depth (which gives an idea of the total depth) is 54 million which is outside of the regime I am interested in.

  • 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).

  • 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
    Oct 13 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$
    – StarBucK
    Oct 13 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$ Oct 14 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$ Oct 18 at 8:43
  • 1
    $\begingroup$ It is easily tractable on a classical computer, there is no "quantum advantage" here, the work basically validate the implementation ("yes, it works as expected and it is implementable") and the theoretical scaling in practice ("yes, the number of gates follows the theoretical one, but the constant is XXX which is [low/normal/high]"). $\endgroup$ 2 days ago

Your Answer

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

Browse other questions tagged or ask your own question.