PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamiltonian Simulation by Qubitization

Guang Hao Low, Isaac L. Chuang

arXiv:1610.06546v3quant-ph

TL;DR

The paper addresses efficient simulation of Hamiltonians available through unitary and state-preparation oracles, and develops qubitization to encode them in invariant subspaces. Its quantum signal processor achieves optimal query complexity for Hamiltonian evolution and broader operator functions, while extending useful input models; the authors note that incorporating structural information remains an open challenge.

  • Problem

    Hamiltonian simulation must handle diverse oracle-access models, while repeated applications of a projected signal operator can suffer leakage because its subspace is not generally invariant.

  • Method

    Qubitization converts a Hermitian operator encoded as a flagged block of a unitary oracle into structured unitary dynamics, which quantum signal processing transforms into target functions f[H].

  • Results

    The framework provides optimal query complexity for Hamiltonian simulation and a large class of operator functions, while also covering purified density matrices and prior sparse or linear-combination models.

  • Takeaways & Limitations

    The standard-form encoding broadens the scope of Hamiltonian-simulation inputs and supports applications including quantum linear systems, Gibbs sampling, and quantum phase estimation.

  • Takeaways & Limitations

    The authors leave open when structural information can be incorporated into standard-form encodings, especially when naive decompositions use components with large spectral norms.

Abstract

from arXiv · show

We present the problem of approximating the time-evolution operator $e^{-i\hat{H}t}$ to error $ε$, where the Hamiltonian $\hat{H}=(\langle G|\otimes\hat{\mathcal{I}})\hat{U}(|G\rangle\otimes\hat{\mathcal{I}})$ is the projection of a unitary oracle $\hat{U}$ onto the state $|G\rangle$ created by another unitary oracle. Our algorithm solves this with a query complexity $\mathcal{O}\big(t+\log({1/ε})\big)$ to both oracles that is optimal with respect to all parameters in both the asymptotic and non-asymptotic regime, and also with low overhead, using at most two additional ancilla qubits. This approach to Hamiltonian simulation subsumes important prior art considering Hamiltonians which are $d$-sparse or a linear combination of unitaries, leading to significant improvements in space and gate complexity, such as a quadratic speed-up for precision simulations. It also motivates useful new instances, such as where $\hat{H}$ is a density matrix. A key technical result is `qubitization', which uses the controlled version of these oracles to embed any $\hat{H}$ in an invariant $\text{SU}(2)$ subspace. A large class of operator functions of $\hat{H}$ can then be computed with optimal query complexity, of which $e^{-i\hat{H}t}$ is a special case.

1 Introduction

The paper develops a general Hamiltonian-simulation framework for Hamiltonians encoded by unitary and state-preparation oracles. Qubitization combines optimal query complexity with low overhead and extends the approach to broader operator-function and input models.

  • Motivation: Hamiltonian simulation costs depend on system size, evolution time, target error, and the model used to access the Hamiltonian.Earlier approaches include sparse-Hamiltonian and linear-combination-of-unitaries models.
  • Motivation: The d-sparse model can be exponentially slower for high-weight terms, require difficult row-computable oracles, and double the system-qubit count.These limitations motivate a more flexible input model with simpler oracles and lower space overhead.
  • Qubitization: Qubitization embeds a Hermitian Hamiltonian projected from oracle U into an invariant SU(2) subspace using controlled state-preparation and signal oracles.This construction underlies the paper’s general quantum signal processor for computing operator functions f[H].
  • Main result: Theorem 1 simulates e^−iHt with optimal query complexity and at most two additional qubits beyond the registers needed for the signal encoding.The theorem specifies total space of ⌈log2(N)⌉ + ⌈log2(d)⌉ + 2 qubits and O(Q log(d)) additional two-qubit gates.

2 Overview of the Quantum Signal Processor

The quantum signal processor transforms a standard-form encoding of a Hermitian signal operator into target functions of that operator. Qubitization supplies invariant SU(2) subspaces, enabling optimal polynomial processing with constant ancilla overhead.

  • Signal-operator encoding: A standard-form signal oracle encodes H as the top-left block of a unitary U flagged by the ancilla state |G⟩.The encoding acts on the subspace |G⟩⊗H_s, while U's action outside that subspace is generally uncontrolled.
  • Signal-operator encoding: Repeated applications of the original oracle can leak outside eigenstate subspaces, preventing straightforward computation of higher moments such as H^2.The leakage depends on undefined components of U and must otherwise be analyzed case by case.
  • Qubitization: Qubitization constructs an iterate W that preserves disjoint two-dimensional SU(2) subspaces for each eigenvalue of H.The iterate is built from G, controlled-U, their inverses, one additional qubit, and O(log(dim(H_a))) gates.
  • Quantum signal processing: The quantum signal processor uses controlled iterates and ancilla controls to encode polynomial target operators A[H] + iB[H].The ancilla-free construction uses Q queries to W, zero additional qubits beyond W, and O(Q log(dim(H_a))) gates under stated polynomial conditions.
  • Quantum signal processing: A single-ancilla construction supports opposite-parity polynomial components and outputs A[H] + iC[H] using controlled-W queries.This extends the available polynomial basis by embedding W into another invariant SU(2) subspace.
  • Scope: The framework is agnostic to the underlying oracle model, allowing diverse Hamiltonian descriptions to be converted into standard form for target-operator processing.The paper presents this standard-form conversion as the basis for its Hamiltonian-simulation results across varied input models.

3 Explicit Encodings of ˆH = (⟨G| ⊗ˆI) ˆU(|G⟩⊗ˆI)

The standard-form encoding is instantiated for linear combinations of unitaries, d-sparse Hamiltonians, and purified density matrices. These constructions connect common input models to the signal-processing framework with explicit oracle and gate implementations.

  • Linear Combination of Unitaries: Linear-combination-of-unitaries encoding represents H as a sum of d unitary operators with coefficients whose L1 norm bounds the spectral norm.The coefficient state and selector oracle can be implemented using O(d) and O(dC) primitive gates, respectively, when each unitary uses O(C) gates.
  • Linear Combination of Unitaries: Lemma 5 formalizes standard-form encoding by preparing the coefficient-weighted ancilla state and applying a unitary selector.The construction provides a general route for encoding Hamiltonians specified as linear combinations of unitaries.
  • Linear Combination of Unitaries: The optimal LCU decomposition may be difficult to find or poorly matched to the model, although LCU establishes that an encoding is possible in principle.The passage identifies decomposition choice and model fit as practical limitations of this implementation route.
  • d-Sparse Hamiltonians: A d-sparse Hamiltonian is specified by an oracle returning matrix entries and another computing the column index of each nonzero element in a row.These are the value oracle O_H and the position oracle O_F.
  • d-Sparse Hamiltonians: The sparse-oracle construction encodes H/(d∥H∥max) in standard form using O(1) queries.The construction prepares row- and column-index-dependent states whose overlap reproduces the normalized matrix entries.
  • Purified Density Matrices: A purified density matrix ρ obtained by tracing out an ancilla can itself be encoded in standard form using a swap unitary.If G prepares the purification, swapping one ancilla register with the system yields ⟨G|U|G⟩ = ρ.

4 Qubitization in a Quantum Signal Processor

Qubitization converts a standard-form signal operator into an iterate with the same signal operator acting in an invariant SU(2) subspace. The construction remains available for arbitrary signal unitaries by adding one qubit and querying controlled U and controlled U† once.

  • General construction: The resulting construction requires no detailed information about |G⟩ beyond oracle access to its state-preparation unitary.Thus arbitrary G and U can be assumed qubitized without loss of generality, with minimal overhead.
  • Constructing the iterate: Qubitization seeks an iterate W with the same Hermitian signal operator and an SU(2)-invariant subspace containing |G⟩.The necessary and sufficient conditions require preserving the projected operator and making the squared transformed iterate project to the identity.
  • Constructing the iterate: The iterate is analyzed through eigenstates |λ⟩ and a complementary state |G⊥_λ⟩ generated by applying S U.For each eigenvalue, the invariant behavior follows by repeatedly applying the unitary and orthonormalizing the resulting two-dimensional subspace.
  • Special cases: For reflection oracles, a reflection about |G⟩ directly produces the required qubitized iterate.This special case uses S=I and implements the same signal operator in an SU(2)-invariant subspace.
  • General construction: For general signal unitaries, a one-qubit extension containing U and U† supplies a simple construction satisfying the qubitization conditions.The extended circuit preserves the signal operator and uses one query each to controlled U and controlled U†.

5 Operator Function Design on a Quantum Signal Processor

The quantum signal processor transforms a qubitized Hermitian signal operator into target functions using phased iterates whose action decomposes into SU(2) rotations. Polynomial and Fourier characterizations determine which functions are achievable and connect query complexity to best polynomial approximation.

  • Purpose and structure: The quantum signal processor transforms a signal operator H into a desired target operator f[H].Its framework provides a systematic procedure and connects query complexity with polynomial approximation theory.
  • Purpose and structure: Qubitization makes function design possible by generating Chebyshev polynomials of H within invariant subspaces.Phased iterates retain the invariant subspace while adding controllable parameters for operator transformations.
  • Implementation variants: Ancilla-free processing handles target operators whose real and imaginary parts have the same parity, while one ancilla enables opposite parity.The parity constraints arise from the polynomial characterization of achievable functions.
  • Signal processing sequence: A sequence of phased iterates acts as a product of single-qubit rotations, with phase choices determining polynomial coefficients in the signal operator.The ancilla-block output is expressed through functions such as A[H]+iB[H].
  • Approximation complexity: The query complexity for approximating a function is exactly the complexity of its best constrained polynomial approximation.This follows because polynomials form a complete basis on bounded real intervals.
  • Achievability conditions: Achievable A and C functions are bounded Fourier series with fixed parity, normalization, and a pointwise sum-of-squares constraint.Their implementing phase sequence can be computed classically in O(poly(Q)) time, and approximate inputs can be stabilized into achievable functions.

6 Application to Hamiltonian Simulation

Hamiltonian simulation follows by approximating e^-iHt with achievable polynomials in the qubitized signal operator. The resulting procedure gives optimal query scaling and transfers directly to sparse, linear-combination, and purified-density-matrix input models.

  • Hamiltonian simulation: The simulation proof approximates e^-iλt using a truncated Jacobi–Anger expansion and stabilizes the resulting polynomials into achievable functions.The truncation uses Bessel-function coefficients, while stability converts approximate feasibility into an implementable quantum signal processor.
  • Hamiltonian simulation: The implemented operator has error O(√ϵ) in spectral norm and failure probability O(ϵ).Solving for the polynomial degree yields the stated query complexity to the oracles encoding H.
  • Input models: O(dt∥H∥max + log(1/ϵ)) queries simulate a d-sparse Hermitian Hamiltonian.This sparse-model result follows by combining the general theorem with a standard-form encoding.
  • Optimality: The sparse-case query complexity exactly matches a lower bound valid for all parameter values, establishing optimality beyond asymptotic limits.The lower bound is based on simulating a Hamiltonian that solves PARITY with unbounded error.
  • Input models: O(αt + log(1/ϵ)) queries simulate a Hamiltonian given as a linear combination of unitaries.This is an immediate application of the standard-form encoding for that input model.
  • Input models: O(t + log(1/ϵ)) queries simulate time evolution by a purified density matrix.The density-matrix instance follows from its standard-form encoding.

7 Conclusion

The paper presents qubitization and quantum signal processing as a general framework for optimal Hamiltonian simulation from flagged signal-unitary encodings. It improves important input models while leaving the use of additional Hamiltonian structure as an open direction.

  • Conclusion: The framework covers Hamiltonians embedded in flagged subspaces and achieves optimal query complexity in all parameters with minimal overhead.It significantly improves d-sparse and linear-combination-of-unitaries models while extending the range of useful formulations.
  • Conclusion: For purified density matrices, the method gives a quadratic improvement in time and an exponential improvement in error over the sample-based model.The paper states that this result follows from a short proof.
  • Open directions: A linear-combination decomposition can incur a factor ∥α⃗∥1/∥H∥ slowdown when the Hamiltonian norm is much smaller than the coefficient sum.Finding a decomposition with ∥α⃗∥1=O(∥H∥) appears difficult in general.
  • Open directions: The standard-form approach instead seeks any suitable encoding of H rather than a decomposition constrained by component properties.Identifying when additional structural information can be incorporated remains an open challenge.
  • Broader framework: Quantum signal processing imposes structure on unitary processes implementing Hermitian signal operators and supports efficient transformations into desired functions.The paper relates the resulting optimal query complexity to fundamental polynomial and Fourier approximation bounds.
  • Broader framework: Subsequent developments extend the framework to singular-value transformations and exploit geometric locality, induced one-norm, spectral norm, and energy-scale structure.These later algorithms are described as optimal up to sub-polynomial factors with respect to their structural parameters.

A Qubitization of Normal Operators

The paper extends qubitization from Hermitian to normal operators by encoding their complex eigenvalues through alternating phased iterates. This construction connects special cases including oblivious amplitude amplification and Hermitian qubitization, while imposing an alternating-sequence constraint.

  • Normal-operator encoding: Normal operators are handled through a unitary oracle encoding whose polar components commute.The construction uses the unitary and positive-semidefinite parts of a normal matrix, with commuting factors.
  • Invariant subspaces: The iterates W_φ^± map between two related two-dimensional subspaces associated with each eigenstate.The alternating products preserve the relevant structure by switching between the subspaces generated by the ± iterates.
  • Invariant subspaces: Quantum signal processing is restricted to controlled blocks of even length because only alternating-sign products have invariant subspaces.Repeated application of iterates with the same sign does not generally preserve the subspace.
  • Special cases: The construction reduces to Hermitian qubitization when all phase parameters θ_λ vanish.When the unitary polar component has eigenvalues ±1, the operator becomes Hermitian.
  • Special cases: It reduces to oblivious amplitude amplification when all eigenvalues λ are identical and φ = π/2.

A.1 Minimal example

The minimal example constructs the invariant-subspace behavior of normal qubitization from alternating applications of R U and R U†. It shows how overlaps involving the encoded eigenvalue determine the resulting two-dimensional representations.

  • Setup: The example fixes φ = π/2, identifies |G⟩ with |0⟩, and uses R = 2|0⟩⟨0| − 1.
  • Basis construction: Gram–Schmidt orthogonalization supplies the basis needed to represent the alternating iterates within these subspaces.
  • Invariant subspaces: Alternating sequences preserve inputs to R U† in span{|0⟩, |1⟩} and inputs to R U in span{|0⟩, |2⟩}.The proof uses projectors onto the corresponding two-dimensional spans.
  • Overlap structure: The overlap between the encoded states satisfies |⟨1|R U|2⟩| = |λ|.The complementary overlap is given by ⟨0|R U|2⟩ = ⟨2|U†|0⟩* = √(1 − |λ|^2).
  • Phase implementation: Table 3 lists phase sequences implementing h(θ) = t sin(θ) with errors bounded by the stated simulation criterion.

B Practical Details for Implementing Hamiltonian Simulation

The implementation appendix details Fourier-based phase synthesis and compares query costs with BCCKS under a common signal-operator encoding. The paper’s approach approaches four queries per unit time asymptotically, while the BCCKS cost retains logarithmic factors.

  • Approximation and phases: The appendix uses a truncated Fourier approximation to e^{it sin(θ)} and provides phase data for implementing the target function.It includes error-scaling plots and phase tables for quantum signal processing.
  • Query accounting: The comparison counts queries to the signal operator U, including both U and U† when the oracle is not already qubitized.This adds a factor of two relative to the asymptotic controlled-iterate count.
  • Asymptotic comparison: 4 queries per unit simulation time is approached by this work as t → ∞.The BCCKS query rate instead scales as O(log(t/ϵ) log log(t/ϵ)).
  • BCCKS accounting: BCCKS uses 3Kr queries, with r = ⌈t/log(2)⌉ segments and three queries per segment for oblivious amplitude amplification.
  • Comparison caveat: The plotted BCCKS performance slightly overestimates its performance because the simulated-evolution error is a factor O(1) ≳ 2 larger than ϵ.
Loading 1610.06546v3…