Curator's Take
AI Commentary
This article settles a long‑standing open problem by proving that any constant‑depth approximation of the Quantum Fourier Transform – the heart of Shor’s algorithm – inevitably requires an n‑qubit fanout gate, linking the two operations in the QAC⁰ circuit model. By showing that implementing QFT without fanout is as hard as adding fanout itself, the work clarifies why shallow NISQ circuits have struggled to realize full‑scale factoring and highlights fanout as a concrete hardware target for future quantum processors. The result reframes progress on Shor’s algorithm: advances in fast, low‑depth fanout primitives will directly translate into more practical implementations of integer factorisation.
— Mark Eatherly
Summary
Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). We resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation. Formally, let $\mathsf{QFT}_q$ be the gate acting on $n = \lceil \log q \rceil$ qubits that computes the QFT under modulus $q$. It is known that any $n$-qubit $\mathsf{QFT}_q$ can be implemented in constant depth using $\mathsf{FANOUT}_n$, i.e. $\mathsf{QFT}_q \in \mathsf{QAC}^0_f$. We prove the converse by using a $\mathsf{QFT}_q$ gate to construct a state of ``non-negligible felinity". Consequently, $\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$. In the case of $q = 2^n$, such as in Shor's, we approximate $\mathsf{FANOUT}_n$ using a single $\mathsf{QFT}_{2^n}$ gate and $O(1)$ two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.