Many existing quantum algorithms require millions or billions of T gates to reach a scale that is classically hard to simulate. However, existing Clifford + T circuits seem hard even with 100 or so T gates, as far as the best simulators go (e.g. https://quantum-journal.org/papers/q-2019-09-02-181/).

Are there any quantum algorithms that require on the order of, say, 1000 T / Toffoli gates but could still be interesting for some application?

  • 1
    $\begingroup$ 1000 T gates is enough to do fault tolerant random circuit sampling that can't be simulated classically. That might count as interesting, but not an application. $\endgroup$ Apr 27, 2023 at 18:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.