We are excited to have Greg Kahanamoku-Meyer from Lawrence Berkeley National Laboratory at the Harvard Quantum Information Seminar on
October 19th at Jefferson Hall 250. The talk will start at 4:30 pm.
Title - Quantum
circuits for fast multiplication with few ancillas
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 is practical for realistic problem sizes.