Dear all,
We are excited to have Greg Kahanamoku-Meyer from Lawrence Berkeley National Laboratory at
the Harvard Quantum Information Seminar today 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.
Hope to see you all there.
Sincerely,
Jordan Cotler
Show replies by date