Abstract: In this work we present fast constructions for the quantum Fourier transform and quantum integer multiplication, using few ancilla qubits compared to the size of the input. For the approximate QFT we achieve depth O(log n) using only n + O(n / log n) total qubits, by applying a new technique we call "optimistic quantum circuits." To our knowledge this is the first circuit for the AQFT with space-time product O(n log n), matching a known lower bound. For multiplication, we construct circuits that use no ancilla qubits and only O(n^(1+eps)) gates (for arbitrary eps>0). With the use of O(n / log n) ancilla qubits, these gates can be arranged in the optimal depth of O(n^eps). Together these results yield a circuit for Shor's factoring algorithm with depth O(n^(1+eps)) using only 2n + O(n / log n) total qubits. In addition to these concrete results, we will discuss how optimistic quantum circuits may be used as a general technique for constructing efficient quantum circuits.
*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*