Qubitization
Turning a block-encoded Hamiltonian into a quantum walk whose eigenphases encode arccos of the Hamiltonian's spectrum, enabling optimal simulation.
The walk operator
Given a block-encoding of H / alpha via SELECT and PREPARE, qubitization (Low and Chuang, 2017) constructs a walk operator W = (reflection about the PREPARE state) times SELECT. The key result: within each two-dimensional invariant subspace tied to an eigenvalue E of H, W acts as a rotation by an angle theta with cos(theta) = E / alpha.
Why this is powerful
The eigenphases of W are +/- arccos(E / alpha). So the walk operator maps the entire spectrum of H onto phases of a single unitary, one two-by-two rotation block per eigenvalue. This is the discrete analog of the classical power method structured as reflections.
Simulating time evolution
To realize e^(-iHt) you must convert the arccos-phases of W into the desired e^(-iEt) phases. This is done with quantum signal processing: interspersing calls to W with single-qubit rotations applies a polynomial to cos(theta), and a well-chosen polynomial approximates e^(-i alpha t x) evaluated at x = E/alpha. The number of W calls needed is O(alpha t + log(1/epsilon)).
- Query complexity O(alpha t + log(1/epsilon)) is optimal, matching lower bounds.
- Additive, not multiplicative, dependence on precision: log(1/epsilon).
- No large-order Taylor truncation; the polynomial is applied directly.
- Requires ancillas for the block-encoding and one signal qubit.
Relation to other methods
Qubitization subsumes LCU and Taylor-series simulation as special cases and generalizes to arbitrary matrix functions through the quantum singular value transformation. It is the current standard for asymptotically optimal Hamiltonian simulation and for phase estimation, because the walk operator's clean eigenphase structure makes eigenvalue extraction efficient.
In resource estimates for chemistry and materials, qubitization-based phase estimation typically gives the lowest known gate counts, which is why it dominates rigorous forecasts of when quantum simulation will surpass classical methods.