Hamiltonian Simulation by Uniform Spectral Amplification
read the original abstract
The exponential speedups promised by Hamiltonian simulation on a quantum computer depends crucially on structure in both the Hamiltonian $\hat{H}$, and the quantum circuit $\hat{U}$ that encodes its description. In the quest to better approximate time-evolution $e^{-i\hat{H}t}$ with error $\epsilon$, we motivate a systematic approach to understanding and exploiting structure, in a setting where Hamiltonians are encoded as measurement operators of unitary circuits $\hat{U}$ for generalized measurement. This allows us to define a \emph{uniform spectral amplification} problem on this framework for expanding the spectrum of encoded Hamiltonian with exponentially small distortion. We present general solutions to uniform spectral amplification in a hierarchy where factoring $\hat{U}$ into $n=1,2,3$ unitary oracles represents increasing structural knowledge of the encoding. Combined with structural knowledge of the Hamiltonian, specializing these results allow us simulate time-evolution by $d$-sparse Hamiltonians using $\mathcal{O}\left(t(d \|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2}\log{(t\|\hat{H}\|/\epsilon)}\right)$ queries, where $\|\hat H\|\le \|\hat H\|_1\le d\|\hat H\|_{\text{max}}$. Up to logarithmic factors, this is a polynomial improvement upon prior art using $\mathcal{O}\left(td\|\hat H\|_{\text{max}}+\frac{\log{(1/\epsilon)}}{\log\log{(1/\epsilon)}}\right)$ or $\mathcal{O}(t^{3/2}(d \|\hat H\|_{\text{max}}\|\hat H\|_{1}\|\hat H\|/\epsilon)^{1/2})$ queries. In the process, we also prove a matching lower bound of $\Omega(t(d\|\hat H\|_{\text{max}}\|\hat H\|_{1})^{1/2})$ queries, present a distortion-free generalization of spectral gap amplification, and an amplitude amplification algorithm that performs multiplication on unknown state amplitudes.
This paper has not been read by Pith yet.
Forward citations
Cited by 11 Pith papers
-
Quantum Simulation of Differential-Algebraic Equations with Applications to Unsteady Stokes Flow
Introduces a dilation framework for quantum simulation of linear DAEs, applied to structure-preserving discretizations of unsteady Stokes flow yielding simulation cost scaling as O(h^{-2} sqrt(t)).
-
Accelerating quantum Gibbs sampling without quantum walks
A factorization of the parent Hamiltonian into noncommutative first-order operators enables a walk-free QSVT algorithm with quadratic gap improvement for preparing purified Gibbs states under exact KMS detailed balance.
-
Quantum Solvers for Nonlinear Matrix Equations in Quantum Chemistry
Quantum algorithm block-encodes Riccati solutions for m-particle m-hole RPA using Riesz projectors and QSVT, claiming linear system-size scaling under sparsity and polynomial cost in excitation rank m.
-
Quantum Simulation of Differential-Algebraic Equations with Applications to Unsteady Stokes Flow
A new dilation embeds non-Hermitian DAE evolution into projected Hermitian quantum dynamics, enabling block encodings and QSVT for simulation of constrained systems like unsteady Stokes flow.
-
Quantum analog-encoding for correlated Gaussian vectors and their exponentiation with application to rough volatility
Quantum algorithms prepare states for normalized correlated Gaussians and their exponentials with gate complexities scaling as Õ(‖Σ‖_F/λ_max ⋅ κ^1.5), achieving subcubic scaling in N for fractional processes and enab...
-
A Unified Poisson Summation Framework for Generalized Quantum Matrix Transformations
A dual Fourier-PSF and contour-PSF framework resolves the smoothness-sparsity trade-off for efficient quantum simulation of singular and holomorphic matrix functions.
-
Accelerating Inference for Multilayer Neural Networks with Quantum Computers
Quantum circuits for coherent multilayer neural network inference achieve quadratic to polylogarithmic speedups over classical methods depending on quantum data access models for inputs and weights.
-
Exponential Lindbladian fast forwarding and exponential amplification of certain Gibbs state properties
Quantum algorithms achieve exponential fast-forwarding for structured Lindbladian dynamics and coherence-dependent exponential speedup in Gibbs state property estimation.
-
QKAN: quantum Kolmogorov-Arnold networks with applications in machine learning and multivariate state preparation
QKAN is a quantum algorithmic framework using block-encodings and QSVT to implement wide-and-shallow networks for quantum learning and compositional state preparation.
-
Quantum Simulation of Non-Unitary Dynamics via Amplitude-Phase Separation
Introduces Amplitude-Phase Separation (APS) decomposition for quantum simulation of non-unitary dynamics, with complementary error scaling advantages in time-independent cases and unification of prior methods like LCH...
-
A Quantum Linear Systems Pathway for Solving Differential Equations
A quantum algorithm pathway using block encoding and QSVT to solve differential equations, with demonstrations on heat and Burgers' equations plus hardware resource estimates.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.