Less than a million CNOTs should be enough to solve a classically intractable instance of a scientific problem with a quantum circuit*

The question I will try to answer in this talk is the following: what is the size of the smallest quantum computation capable of solving an instance of a scientifically interesting problem that is intractable for a classical computer? The problem I consider is Hamiltonian dynamics simulation, in the sense of the ability to sample probability distribution given by a state evolved under the target Hamiltonian for a specified time t and accurate to within a specified error epsilon. The core of the talk concerns the development and application of a range of algorithm design, circuit optimization, and hardware/software co-design techniques, the combination of which leads to the reduction in the quantum resource counts provided by pure algorithmic formulations by several orders of magnitude. Specifically, the best physical-level quantum circuit features under 650,000 CNOT gates, and the best fault-tolerant circuit features under 6.8x10^6 T gates. This illustrates that algorithmic and software-level optimizations will be indispensable for practical quantum computing.