Source-linked AI summary
Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost
Dong An, Jin-Peng Liu, Lin Lin
TL;DR
The paper addresses estimating quantities associated with possibly unnormalized non-unitary dynamics and develops a linear-combination approach using block-encoded operators and Hamiltonian-simulation circuits. The resulting procedures provide precision- and confidence-controlled estimators, while their costs depend on implementing the approximating simulation circuits and may require additional normalization estimation.
Problem
Estimating observables for non-unitary dynamics can involve possibly unnormalized solutions, while normalized-state estimates require tighter error tolerances and may require estimating the solution norm.
Method
The approach uses linear combinations of unitaries, block encodings, state-preparation oracles, and Hamiltonian-simulation circuits approximating the required evolution operators.
Results
The estimators achieve precision ϵ with probability at least 1−δ under specified block-encoding and Hamiltonian-simulation error conditions.
Takeaways & Limitations
The framework supplies observable-estimation procedures whose query costs are expressed in terms of state preparation, block encodings, and approximating Hamiltonian-simulation circuits.
Takeaways & Limitations
The final complexity depends on implementing the approximating Hamiltonian-simulation circuits, with low-order methods potentially introducing extra overhead.
Abstract
from arXiv · showhide
We propose a simple method for simulating a general class of non-unitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving non-unitary processes, such as the quantum singular value transformation (QSVT). The LCHS method can achieve optimal cost in terms of state preparation. We also demonstrate an application for open quantum dynamics simulation using the complex absorbing potential method with near-optimal dependence on all parameters.
Supplemental Material for Linear combination of Hamiltonian simulation for non-unitary dynamics with optimal
The supplemental material is authored by Dong An, Jin-Peng Liu, and Lin Lin.
- Dong An, Jin-Peng Liu, and Lin Lin are listed as authors of the supplemental material.
I. PROOF OF Theorem 1
The proof establishes the LCHS representation using analytic matrix-function arguments and numerical integration, with complexity controlled by simulation steps and state-preparation success.
- The proof of Theorem 1 uses a Cauchy-theorem argument for matrix functions without relying on spectral mapping.
- The contour proof deforms an imaginary-axis integral onto a right-half-plane semicircle and analyzes its limiting contributions.
- The representation is verified by showing that the constructed expression satisfies the same differential equation and initial condition as the target evolution.
- The numerical integration analysis truncates the integral and applies trapezoidal rules, with truncation error O(ϵ) when K is chosen proportional to 1/ϵ.
- The LCU primitive succeeds with probability (∥T |ψ⟩∥/∥α∥1)^2 and uses amplitude amplification to reach constant success probability.
IV. HYBRID IMPLEMENTATION OF THE LCHS METHOD
The hybrid implementation evaluates quantum expectation values for sampled LCHS terms and performs the remaining summation through classical Monte Carlo sampling.
- The hybrid approach evaluates ⟨u0|U†_k(t) O U_k′(t)|u0⟩ using a non-unitary Hadamard test and amplitude estimation.
- The sampled expectation values are combined through classical Monte Carlo summation.
- The analysis treats estimation for a fixed pair of LCHS indices before accounting for classical sampling complexity.
IV.1. Estimating observables via non-unitary Hadamard test
The non-unitary Hadamard test estimates observables by replacing controlled unitaries with controlled block-encodings, with query complexity scaling inversely with precision.
- The non-unitary Hadamard test replaces the controlled unitary with a controlled block-encoding of the observable.
- ⟨ϕ|G|ϕ⟩ can be estimated to precision ϵ with probability at least 1−δ using O((αG/ϵ) log(αG/ϵ) log(1/δ)) queries.
- For the target LCHS expectation, setting ϵHS = ϵ/(4∥O∥) yields the same O((αO/ϵ) log(αO/ϵ) log(1/δ)) query scaling.
- The observable block-encoding and approximate Hamiltonian-simulation circuits are composed to form a block-encoding of the full non-unitary operator product.
IV.2. Linear combination via classical Monte Carlo sampling
The section estimates observables of the non-unitary solution by Monte Carlo sampling over pairs of Hamiltonian-simulation indices and combining non-unitary Hadamard-test outcomes. The analysis accounts for sampling and implementation errors, while highlighting worst-case and average-case query behavior.
- Estimator construction: With exact implementations, the expected estimator equals u(t)∗Ou(t).
- Guarantee: Theorem 9 estimates u(t)∗Ou(t) to precision ϵ with probability at least 1−δ when each Hamiltonian-simulation circuit has error ϵ_HS=O(ϵ/∥O∥).
- Guarantee: The analysis separately bounds non-unitary Hadamard-test errors and sampling errors, allocating each half of the total error and failure budget.
- Query behavior: In the worst case, circuit query complexity has almost linear dependence on K, while average-case sampling suppresses large indices with probability proportional to 1/(k^2k′^2).
- Scope: Estimating normalized-state expectations requires division by ∥u(t)∥^2 and may require an additional procedure when the norm is unknown.
V. IMPLEMENTATION OF THE INHOMOGENEOUS TERM
The inhomogeneous term is implemented by discretizing its time and Fourier integrals and encoding the resulting coefficients, source values, and controlled evolution in LCU ancilla registers. The resulting postselected state approximates the integral contribution from the source term.
- Discretization: The inhomogeneous integral is discretized over k and s using trapezoidal rules.
- Oracle construction: The coherent input model supplies time-dependent matrix data and source-state data through coefficient and source-term oracles.
- LCU implementation: The LCU procedure prepares time and space indices, encodes b(t), applies a select oracle for controlled evolution, and uncomputes the coefficient superposition.
- Output: The first subspace of the resulting state approximately encodes the source contribution ∫_0^T e^{-A(T−s)}b(s) ds.
VI. PROOFS OF THE COMPLEXITY ESTIMATES
The complexity proofs reduce controlled combinations of related unitaries to logarithmic-cost select oracles. They then apply this construction to the time- and frequency-indexed evolution operators used by LCHS.
- Select-oracle construction: A select oracle combining J related unitaries can be constructed with ⌈log(J)⌉ controlled-unitary queries.
- Select-oracle construction: Binary decomposition implements U_j by applying circuits for powers U^{2^l}, rather than repeating U_0 2^l times.
- Application to LCHS: For the trapezoidal frequency grid, the select oracle combines the required evolution operators using O(log(M)) cost.
- Application to LCHS: The same logarithmic-cost construction applies to the time-dependent operator L(s,τ), so total complexity is obtained by multiplying select-oracle estimates by log(M).
VI.2. Homogeneous term
The homogeneous-term analysis constructs a block-encoding of the LCHS representation and uses it with state preparation and postselection to prepare the evolved state. The resulting complexity separates matrix-input queries from state-preparation and success-amplification costs.
- Error analysis: The overall proof combines select-oracle, block-encoding, state-preparation, and error-normalization estimates.
- Block-encoding: Lemma 11 constructs a (∥c∥1, log(M), ϵ)-block-encoding of the LCHS evolution operator.
- Approximation: The LCU construction yields a block-encoding of the discretized evolution operator, with truncation and discretization accuracy controlled by sufficiently large K, M, and r.
- State preparation: Theorem 12 prepares an ϵ-approximation of the homogeneous evolved state with Ω(1) success probability and a success flag.
- Query complexity: The block-encoding uses O(1) queries to the state-preparation oracle, while matrix-input queries account for the remaining per-run cost.
- State preparation: After amplitude amplification, the expected repetition cost is governed by the inverse success amplitude rather than by the per-run complexity alone.
VI.3. Inhomogeneous term
The inhomogeneous term is encoded through an LCU construction, with its error controlled by quadrature and simulation choices. The resulting matrix-input query complexity is O(r log(M)).
- The construction encodes the inhomogeneous term using an LCU procedure.
- The approximation error is controlled by choosing parameters so the total error is at most ϵ.
- O(r log(M)) matrix-input queries suffice for the overall construction.
VI.4. Linear combination of homogeneous and inhomogeneous terms
The homogeneous and inhomogeneous contributions are combined as a linear combination of two block-encoded states. A constant-cost run followed by amplitude amplification yields the overall success complexity.
- Lemma 14 combines two possibly unnormalized block-encoded vectors into an approximation of their weighted sum.
- The combination uses two input unitaries, one extra ancilla qubit, and controlled one-qubit operations.
- The state-combination error is controlled by bounding the weighted approximation error relative to the norm of the target sum.
- Since each run costs O(1), amplitude amplification determines the number of repetitions needed for successful state preparation.
VI.5. Proof of Theorem 2
Theorem 2 is proved by combining the encoded homogeneous and inhomogeneous terms, with query costs determined by Hamiltonian simulation, coefficient preparation, and state preparation. The time-independent case admits simpler oracle constructions and improved product-formula bounds.
- The proof combines the homogeneous contribution with the encoded inhomogeneous term to construct an approximation of |u(T)⟩.
- The inhomogeneous encoding has coefficient norm O(∥b∥L1), while the homogeneous coefficient norm remains O(1).
- The resulting query counts include matrix-input queries and separate queries to state-preparation, inhomogeneity, and coefficient oracles.
- Assumption: Theorem 2 assumes p-th-order continuous differentiability of A(t), although truncated Dyson methods can reduce this requirement to first-order differentiability.
- Time-independent matrix A: For time-independent A, coherent time-evolution and select oracles can be built using O(log(M) log(Mt)) queries to the Hamiltonian-simulation oracles.
- Time-independent matrix A: The time-independent product formula replaces Γ_p by Λ_p and lowers the Trotter-error order parameter K by 1.
- Time-independent matrix A: Theorem 15 and Theorem 16 provide constant-success algorithms for preparing |e^-AT u0⟩ and |u(T)⟩, respectively.
VIII. PROOF OF Theorem 3
The open-system application constructs interaction-picture Hamiltonian-simulation oracles from diagonal and sparse-potential input oracles. LCU, truncated Dyson simulation, and amplitude amplification then determine the final query complexity and success overhead.
- The diagonal potential oracle constructs the free Hamiltonian-simulation oracle with one use for any evolution time.
- The select oracle for the free evolution uses O(log(M)) queries to the diagonal-potential oracle.
- The sparse potential is represented by an oracle, while the discretized Laplacian contributes a tridiagonal matrix to the Hamiltonian model.
- The interaction-picture Hamiltonian oracle is assembled using select-oracle constructions requiring O(log(MH) log(M)) queries to the input oracles.
- The truncated Dyson series method supplies the Hamiltonian-time oracle used in the LCU step.
- The LCU output encodes the homogeneous state, while quadrature and simulation errors are combined to set the approximation parameters.
- Amplitude amplification requires O(∥u0∥/∥u(T)∥) repetitions to obtain a successful preparation.