Curator's Take
This article shows that the long‑standing ancilla overhead in block‑encoding constructions can be sidestepped by working in an approximate regime, delivering a single‑ancilla encoding of any Hamiltonian given as a weighted sum of simple terms via generalized quantum signal processing. By coupling this idea with higher‑order Trotterization or multiproduct formulas, the authors achieve near‑optimal circuit depth while keeping qubit requirements dramatically lower than the standard LCU approach—a crucial advantage for early fault‑tolerant and even advanced NISQ devices. The result opens a practical pathway to more resource‑efficient quantum linear‑algebra and simulation algorithms, though the trade‑off between ancilla count and error‑scaling must be managed in concrete applications.
— Mark Eatherly
Summary
Block encodings are a central primitive in quantum algorithms, but standard constructions typically require logarithmic ancilla overhead and complicated controlled operations. Recent lower bounds further show that such ancilla overhead is unavoidable for exact constructions in broad circuit models. We show that this barrier can be bypassed in the approximate setting. Specifically, we present a simple single-ancilla construction that converts Hamiltonian evolution into a block encoding of the underlying Hamiltonian, via generalized quantum signal processing. For operators given by Hermitian decompositions $A=\sum_{j=1}^L α_j H_j$, we instantiate this block-encoding construction in two ways, which differ in how the required Hamiltonian evolution is implemented. Using higher-order Trotterization, we obtain an $\varepsilon$-approximate block encoding of $A$ with only one ancilla qubit and circuit depth $\widetilde O\big(L(α/\varepsilon)^{o(1)}\big),$ where $α=\sum_j α_j$. Using multiproduct formulas, we obtain circuit depth $\widetilde O(L)$, at the cost of $O(\log\log(1/\varepsilon))$ ancilla qubits. Our constructions provide alternatives to the standard LCU framework, with a focus on reducing the number of ancilla qubits while maintaining (near-)optimal circuit depth.