Skip to main content

Achieving low circuit depth with few qubits, for arithmetic and the QFT

QuICS_04152015_9614_11.JPG

Speaker

Greg Kahanamoku-Meyer (MIT)

Event Type

QuICS seminar

Related Groups

JQI

Date & Time

September 11, 2024, 11:00am

Where to Attend

ATL 3100A and Virtual Via Zoom

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.*