Source-linked AI summary
Optimal Hamiltonian Simulation by Quantum Signal Processing
Guang Hao Low, Isaac L. Chuang
TL;DR
Hamiltonian simulation algorithms have often been abstract and unintuitive, motivating simpler physically inspired methods. The paper uses single-ancilla quantum signal processing to achieve additive optimality, matching lower bounds while reducing ancilla overhead.
Problem
Hamiltonian simulation algorithms have often become increasingly abstract and mathematically sophisticated, leaving open whether an additively optimal algorithm exists.
Method
The paper applies quantum signal processing: single-qubit rotations transform encoded eigenvalue information using an optimal-length sequence, followed by projection with near-unity success probability.
Results
The algorithm matches the additive lower bound and achieves the optimal time-error trade-off, while reducing extra ancilla overhead to one qubit.
Takeaways & Limitations
Quantum signal processing provides a simple, rigorous framework for optimal Hamiltonian simulation and connects quantum algorithm design with function approximation and quantum control.
Takeaways & Limitations
The construction restricts h(θ) to a symmetry compatible with the parity and periodicity of A(θ) and C(θ).
Abstract
from arXiv · showhide
The physics of quantum mechanics is the inspiration for, and underlies, quantum computation. As such, one expects physical intuition to be highly influential in the understanding and design of many quantum algorithms, particularly simulation of physical systems. Surprisingly, this has been challenging, with current Hamiltonian simulation algorithms remaining abstract and often the result of sophisticated but unintuitive constructions. We contend that physical intuition can lead to optimal simulation methods by showing that a focus on simple single-qubit rotations elegantly furnishes an optimal algorithm for Hamiltonian simulation, a universal problem that encapsulates all the power of quantum computation. Specifically, we show that the query complexity of implementing time evolution by a $d$-sparse Hamiltonian $\hat{H}$ for time-interval $t$ with error $ε$ is $\mathcal{O}(td\|\hat{H}\|_{\text{max}}+\frac{\log{(1/ε)}}{\log{\log{(1/ε)}}})$, which matches lower bounds in all parameters. This connection is made through general three-step "quantum signal processing" methodology, comprised of (1) transducing eigenvalues of $\hat{H}$ into a single ancilla qubit, (2) transforming these eigenvalues through an optimal-length sequence of single-qubit rotations, and (3) projecting this ancilla with near unity success probability.