I have seen circuits with 30 qubits and around 500 gates. Also circuits with 32 qubits and 6000 gates. Are circuits with more than 1000 gates common in quantum computing? Are there many quantum algorithms that require more than 1000 gates? How common are they?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
I'd say it's far more common for quantum algorithms to use billions of gates than thousands. And that's assuming you're ignoring Clifford gates as well as error correction overhead! If you want to count those, add in another factor of a million.
For example...
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.
According to Table 1 of https://arxiv.org/abs/1905.09749 , factoring 2048 bit numbers takes 3 billion Toffoli gates:
According to Table 1 of https://arxiv.org/abs/2001.09580 , 256 bit elliptic curve discrete logarithms take a few billion T gates:
answered May 31, 2021 at 21:14
-
$\begingroup$ Wow, that's sobering. And how many gates can currently be run on a real device? $\endgroup$ Jun 1, 2021 at 8:42
-
$\begingroup$ @WeatherReport I think Craig can give more reliable numbers than me. AFAIK, the number of gates is of the order of 100, depending on the platform. The problem is that the number of gates is limited by the gate fidelity since errors are accumulating and the outcomes eventually become white noise. You cannot increase the fidelity arbitrarily, that is why you need quantum error correction. Among others, this requires a notable overhead in the physical qubits. Current devices with 50-100 qubits can only provide a few (1-2) logical qubits with realistic codes, so you cannot do much. $\endgroup$ Jun 1, 2021 at 9:21
-
4$\begingroup$ @WeatherReport Off the top of my head, the quantum supremacy experiment that google did used roughly 1500 gates and had a signal-to-noise of roughly 0.1%. So you can do classically hard things with thousands of gates, but it's a big open question if you can do useful things (as in things industry would pay for) with that many gates. The closest I know of is Scott Aaronson's client certified randomness proposal, but it rides a fine line between too-hard and too-easy due to verification being harder than spoofing (except spoofing has a strict time limit). $\endgroup$ Jun 1, 2021 at 12:04
-
$\begingroup$ And to add a quantum finance example (that I am shamelessly a co-author of :P), from Table 1 in arxiv.org/abs/2012.03819, pricing commonly used non-trivial options (autocallables and TARFs) using Monte Carlo simulations on a quantum computer takes ~10 billion gates. $\endgroup$ Aug 1, 2021 at 8:11
-
$\begingroup$ In the last example, the lowest number of T gates that I see is more than 10^31. How is that a few billion? $\endgroup$ Sep 3 at 17:53