Joint IQIM/AWS Seminar Series

Abstract: Arithmetic on superpositions of numbers is a fundamental operation for many quantum algorithms. Multiplication in particular accounts for the vast majority of the cost of Shor's algorithm for factoring, as well as of recent protocols for efficiently-verifiable quantum advantage. The standard way of performing multiplication, both in the classical and quantum settings, requires O(n^2) gates, where n is the length of the inputs. Faster classical algorithms have been known for decades, but building quantum circuits based on them seems to require a large number of ancilla qubits. Here I present a technique for quantum multiplication which can achieve a sub-quadratic gate count using as few as just one ancilla qubit. I will discuss the algorithm itself and applications, showing to our knowledge the first implementation of Shor's algorithm that simultaneously uses fewer than O(n^3) gates and fewer than 3n total qubits. I will then discuss optimizations that can be applied in practice and present estimates of gate and qubit counts, showing that the algorithm performs well for realistic problem sizes.