A log-depth in-place quantum Fourier transform that rarely needs ancillas

Technical Summary: A Log-Depth In-Place Quantum Fourier Transform That Rarely Needs Ancillas

Problem Statement
Designing quantum circuits for specific unitaries often requires balancing resource constraints (depth, qubit count, locality) against approximation error. Traditional approaches demand that a circuit approximate a unitary with low error across all possible input states. However, achieving this "worst-case" guarantee often necessitates significant resources, such as large numbers of ancilla qubits, long-range gates, or deep circuits. For instance, prior logarithmic-depth Quantum Fourier Transform (QFT) constructions required $O(n)$ ancilla qubits, long-range connectivity, or measurement-based feedforward. The authors posit that for many applications within larger quantum algorithms, it is sufficient to achieve a good approximation on most inputs rather than all, provided the "bad" inputs (where error is high) are rare or can be handled via reduction.

Methodology
The paper introduces a framework for "optimistic quantum circuits" and applies it to the QFT, followed by a reduction technique to handle worst-case inputs.

1. Optimistic Quantum Circuits:
   The authors define an optimistic quantum circuit $C$ (inducing unitary $\tilde{U}$) for a target unitary $U$ as one where the average squared error over any orthonormal basis is bounded by $\epsilon$. Formally, $\frac{1}{\dim \mathcal{H}} \sum_i \|\tilde{U}|\phi_i\rangle - U|\phi_i\rangle\|^2 < \epsilon$. This definition is basis-independent and equivalent to bounding the Frobenius norm of the error operator. Crucially, this allows for a small subspace of "bad" inputs where the error is $O(1)$, provided this subspace occupies only an $O(\epsilon)$ fraction of the Hilbert space.

2. Optimistic QFT Construction:
   The authors construct an optimistic QFT ($\widetilde{\text{QFT}}$) for $n$ qubits with error parameter $\epsilon$.

   • Blockwise Approach: The input register is divided into blocks of size $m = O(\log(n/\epsilon))$.
   • Phase Estimation Trick: The circuit leverages the fact that applying an inverse QFT to a block approximates a phase estimation of the phase factor. By applying $\text{QFT}^\dagger$ to a block, the circuit estimates the phase contribution of neighboring blocks.
   • Commutation: The construction inserts identities of the form $\text{QFT}^\dagger \text{QFT}$ and moves commuting blocks past each other. This breaks the linear dependency chain of standard approximate QFTs.
   • Failure Mode: The phase estimation fails (wrapping around modulo $2^m$) only when the input state on a block is near $0$ or $2^m$ (i.e., a long string of 0s or 1s). These constitute the "bad" subspace.
   • Resources: The resulting circuit has depth $O(\log(n/\epsilon))$, uses exactly $n$ qubits (no ancillas), is local for 1D qubit arrangements (with range $O(\log(n/\epsilon))$), and is measurement-free.

3. Worst-to-Average Case Reduction:
   To address scenarios where inputs might concentrate in the "bad" subspace, the authors propose a reduction to transform optimistic circuits into general approximate circuits.

   • Randomized Reduction: Before applying the optimistic circuit, a random unitary $V$ from a unitary 1-design is applied. Afterward, $\hat{V}^\dagger = U V^\dagger U^\dagger$ is applied. This randomizes the input state, ensuring that the probability of landing in the high-error subspace is low.
   • Derandomized Reduction: The randomized process can be purified into a unitary operation by encoding the choice of $V$ into a control register.
   • Specific 1-Design: For the QFT, the authors utilize the Weyl-Heisenberg group (uniform sampling of Pauli-like shifts and phase gradients) as the 1-design. This choice ensures that the required randomization and un-randomization operations are efficient.

Key Contributions and Results

• Optimistic QFT: The paper presents the first QFT construction that simultaneously achieves:
  • Depth: $O(\log(n/\epsilon))$.
  • Qubit Count: $n$ (no ancillas).
  • Locality: $O(\log(n/\epsilon))$ range (local for 1D).
  • Measurement-free.
  • Error: Bounded by $\epsilon$ on all states except an $O(\epsilon)$ fraction of the Hilbert space.
• Optimistic Multiplication and Factoring: The authors demonstrate that the optimistic QFT can be used directly in Shor's algorithm for integer factorization. By integrating the optimistic QFT into recent QFT-based fast arithmetic constructions (specifically an optimistic multiplier), they achieve factoring circuits with depth $O(n^{1+\delta})$ (for tunable $\delta > 0$) using only $2n + O(n/\log n)$ total qubits. This represents a significant improvement in depth and qubit efficiency compared to previous methods that required $O(n)$ ancillas or deeper circuits.
• General Approximate QFT: By applying the reduction technique, the authors derive an approximate QFT that works with low error on arbitrary inputs.
  • Randomized Version: Achieves depth $O(\log(n/\epsilon))$ using $n + O(n/\log(n/\epsilon))$ total qubits (sublinear ancillas).
  • Derandomized (Unitary) Version: Achieves depth $O(\log(n/\epsilon))$ using $3n + O(n/\log(n/\epsilon))$ total qubits.
  • These are claimed to be the first constructions to achieve asymptotically optimal logarithmic depth with sublinear ancilla counts (randomized) or without measurements/feedforward (derandomized).

Significance
The paper claims that "optimistic quantum circuits" offer a practical paradigm shift for quantum algorithm design. By accepting rare failure modes that are statistically unlikely to occur in typical algorithmic contexts (like Shor's algorithm), one can drastically reduce resource overheads (depth and ancilla count). The specific construction of the optimistic QFT removes the bottleneck of QFTs in factoring circuits, enabling nearly linear-depth factoring with minimal qubit overhead. Furthermore, the provided reduction technique offers a general method to convert such optimistic circuits into robust, worst-case guarantees when necessary, bridging the gap between heuristic efficiency and rigorous correctness. The work suggests that as quantum hardware matures, the trade-off between space-time volume and depth will become critical, and these constructions provide a pathway to optimize both.