An introduction to quantum computing and resource estimation

The field of quantum computing has grown rapidly over the last decade. Physical systems with high double-digit numbers of qubits are expected within the coming year. As the machines continue to grow in size, they will be able to run increasingly sophisticated quantum algorithms. Some of these algorithms, such as Shor's factoring algorithm, will have serious repercussions on parts of our cryptographic infrastructure. This leads to an important question: how big of a quantum computer do we need to run an algorithm? To do so fault-tolerantly? Moreover, how long will it take?

I will begin by giving an overview of the key ideas and developments in quantum computing, as well as highlight the recent progress in physical implementations. I will then introduce ideas and techniques used for physical resource estimation of quantum algorithms. I will describe all parts of the pipeline, from the high-level algorithm description, to quantum circuit optimization, down to counting single-qubit gates and error-correcting code cycles. I will motivate the ideas using two examples studied by our research group: searching for pre-images in a cryptographic hash function, and building a quantum RAM.