PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamiltonian Simulation by Uniform Spectral Amplification

Guang Hao Low, Isaac L. Chuang

arXiv:1707.05391v1quant-ph

TL;DR

Hamiltonian-simulation speedups depend on structure in both the Hamiltonian and its circuit encoding. The paper develops uniform spectral amplification and applies it to sparse-Hamiltonian simulation, reporting a query upper bound and matching lower bound up to logarithmic factors.

  • Problem

    Hamiltonian-simulation speedups depend on the Hamiltonian's structure and how its description is made accessible, since encoding a classical list of O(n^2) matrix elements can itself take exponential time.

    Source: §1 · p. 2

  • Method

    Combining qubitization and quantum signal processing, the paper formulates uniform spectral amplification as low-distortion expansion of an encoded Hamiltonian's spectrum.

    Source: §1 · p. 3, §2 · p. 7, §7 · p. 24

  • Results

    O(t(dΛmaxΛ1)^1/2) queries excluding logarithmic factors, with a matching Ω(t(d||H||max||H||1)^1/2) lower bound for sparse-Hamiltonian simulation.

    Source: §7 · p. 24

  • Takeaways & Limitations

    When information about ||H||1 is unavailable, choosing Λ1=dΛmax=d||H||max recovers previous results.

    Source: §7 · p. 24

    The stated equivalence is limited to ||Ht||=O(1) and fails when time evolution can be approximated with o(t) queries.

    Source: §1.1.3 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

The section introduces uniform spectral amplification as a way to exploit structure in Hamiltonians and their encodings, developing methods based on amplitude multiplication and signal unitaries factored into multiple oracles. It connects measurement encodings and simulation circuits, including sparse-Hamiltonian simulation and its lower bound.

1 Introduction

  • Quantum-algorithm speedups depend on both Hamiltonian structure and how its description is made accessible, motivating query complexity as a measure of simulation cost.Uniform spectral amplification targets reduced normalization with exponentially small spectral distortion; standard amplitude amplification, oblivious amplitude amplification, and spectral gap amplification do not directly meet its uniformity or distortion requirements.Source: §1 · pp. 2–3

1.1.2 Uniform Spectral Amplification by Amplitude Multiplication

  • Amplitude multiplication scales unknown state amplitudes arithmetically with exponentially small error, independent of their values and without prior knowledge of them.Amplitude amplification instead has a highly nonlinear dependence on the initial overlap.Source: §1 · p. 4

1.1.1 Uniform Spectral Amplification by Quantum Signal Processing

  • With no assumptions on the signal unitary, quantum signal processing reduces the encoding normalization to 2Λ using O(α/Λ log(1/ϵ)) queries.This improves the success probability of generalized measurement but does not benefit Hamiltonian simulation.Source: §1.1.1 · p. 4
  • The low-energy extension amplifies a subspace with eigenvalues in [−α, −α(1−∆)] while preserving the relative energy spacing of relevant states.It generalizes spectral gap amplification and applies to Hamiltonians encoded in standard-form.Source: §1.1.1 · p. 4
  • Flexible quantum signal processing implements polynomial functions of the encoded Hamiltonian directly, avoiding Hamiltonian simulation as an intermediate step.The approach uses polynomials with desired properties and reduces space, query-complexity, and error overhead relative to linear-combination-of-unitaries.Source: §1.1.1 · p. 4

1.1.2 Uniform Spectral Amplification by Amplitude Multiplication

  • Factoring the signal unitary into two or three oracles enables uniform overlap multiplication and sparse-Hamiltonian simulation matching Claim 1 up to logarithmic factors, with a matching lower bound.Unlike prior amplitude amplification's nonlinear dependence on error, the method multiplies state overlaps uniformly.Source: §1.1.2 · p. 5

1.1.3 Universality of the Standard-Form

  • The reverse mapping from controlled time-evolution to a standard-form measurement encoding gives simulation and measurement circuits equivalent up to logarithmic time and constant space overhead, when ∥Ht∥=O(1).The mapping has an exponential precision improvement over standard phase estimation, but does not apply when evolution uses o(t) queries.Source: §1.1.3 · p. 6

1.2 Organization

  • Sec. 2 reviews quantum signal processing and proves a more useful variant, while Sec. 3 treats the signal unitary as a single oracle and solves uniform spectral amplification.The outline identifies Thm. 2 and Thm. 3 as the single-oracle solutions.Source: §1.2 · p. 7
  • Sec. 4 generalizes amplitude amplification and uses it for amplitude multiplication; Sec. 5 applies this to overlap-encoded Hamiltonians and sparse-matrix simulation matching a lower bound.The outline names Thm. 7 and Thm. 8 for amplitude amplification and multiplication, Lem. 7 for uniform spectral amplification, and Thm. 5 and Thm. 6 for sparse simulation and its lower bound.Source: §1.2 · p. 7
  • Sec. 6 establishes an equivalence between quantum circuits for simulation and measurement, yielding a simulation algorithm and a unifying perspective on simulation algorithms.The outline also states that this part proves a universality property of the standard form.Source: §1.2 · p. 7

2 Quantum Signal Processing Techniques

Quantum signal processing turns polynomial approximations of an encoded Hamiltonian into quantum circuits. The section reviews its prior-art constraints and presents a flexible version that removes them for implementing a single polynomial component.

2 Quantum Signal Processing Techniques

  • Quantum signal processing implements polynomial functions of an encoded Hamiltonian with optimal query complexity, constant ancilla overhead, and no approximation.The basic version has constraints on valid polynomials; the section introduces a generalization that drops them.Source: §2 · p. 7

2.1 Quantum Signal Processing in Prior Art

  • The prior-art construction encodes A[H′] + iB[H′] in standard form using polynomials meeting the achievable-(A, B) conditions.Its circuit uses O(N) queries and O(N log(d)) primitive gates.Source: §2.1 · p. 9

2.2 Flexible Quantum Signal Processing

  • Flexible quantum signal processing uses an extra ancilla to cancel the A[H′] component and encode B[H′] without the prior-art constraints.Any degree-N bounded matrix polynomial that vanishes at the origin can then be implemented exactly with O(N) queries, O(N) additional gates, and O(1) ancillas.Source: §2.2 · pp. 9–10

3 Uniform Spectral Amplification by Quantum Signal Processing

The section uses quantum signal processing to reduce the normalization of an encoded Hamiltonian, then identifies when this helps simulation. Its gap-amplification result applies uniformly to a low-energy band, with corresponding simulation for that subspace.

3 Uniform Spectral Amplification by Quantum Signal Processing

  • Theorem 2's normalization reduction is exactly balanced by increased query complexity, so it provides no advantage for Hamiltonian simulation.The result may still help measurement applications because it improves the success probability by a quadratic factor.Source: §3 · p. 11
  • A polynomial approximating a truncated linear function enables uniform amplification of a low-energy band, stretching gaps of width Δ by Δ^-1 with O(Δ^1/2) queries.This generalizes spectral gap amplification to standard-form encodings; full effect requires α = ||H||, as for frustration-free Hamiltonians.Source: §3 · p. 11
  • Combining gap amplification with qubitization gives Hamiltonian simulation on eigenstates in the low-energy interval [−1, −1 + Δ] with error ϵ.The paper identifies low-energy subspaces in quantum chemistry and adiabatic computation as relevant applications.Source: §3 · pp. 11–12
  • Because the amplification polynomial is odd, the same stretching also applies to high-energy eigenvalues in [1 − Δ, 1].The theorem's low-energy-subspace simulation corollary is stated for the negative-energy interval.Source: §3 · p. 12

4 Amplitude Amplification Techniques

The section develops amplitude amplification from reflection-based state preparation into polynomially programmable variants. Flexible amplitude amplification then supports multiplication of unknown target-state amplitudes with exponentially small multiplicative error.

4.1 Amplitude Amplification

  • O(1/θ) queries boost the target-state amplitude to O(1) using reflections about the start and target states.The start-state overlap is sin(θ), and the standard Grover iterate uses two reflection queries.Source: §4.1 · p. 12

4.2 Amplitude Amplification by Partial Reflections

  • N+1 queries implement target amplitudes iC(λ)+D(λ) when C and D are odd real polynomials of degree at most 2N+1 satisfying the stated bounds.The method resolves the difficulty of specifying partial-reflection phases for arbitrary functions; choosing C(y)=±T_{2N+1}(y) and D(y)=0 recovers standard amplitude amplification.Source: §4.2 · p. 13

4.3 Flexible Amplitude Amplification

  • An added ancilla cancels the C contribution, allowing flexible amplitude amplification to prepare target amplitudes determined only by D.The resulting achievable D functions are odd real polynomials bounded in magnitude by one on [-1,1].Source: §4.3 · pp. 14–15

4.4 Amplitude Multiplication

  • Amplitude multiplication divides every initial target amplitude by 2Γ with multiplicative error ε, given Γ as an upper bound on its magnitude and Γ≤1/2.The construction uses O(n) queries and O(n log(d)) primitive gates; its error can be exponentially small.Source: §4.4 · p. 15

5 Uniform Spectral Amplification by Amplitude Multiplication

This section uses accessible-oracle factorizations and amplitude multiplication to study uniform spectral amplification and sparse Hamiltonian simulation. It also constructs a PARITY composed with OR Hamiltonian to establish a simulation lower bound while allowing sparsity and 1-norm to vary independently.

5 Uniform Spectral Amplification by Amplitude Multiplication

  • Factoring the signal unitary into oracles supports a hierarchy of amplification results, including a sparse-simulation algorithm and a matching lower bound.The factorization interprets encoded Hamiltonians through overlaps between prepared states.Source: §5 · p. 16

5.1 Matrix Elements as State Overlaps

  • Hamiltonian matrix elements can be represented as overlaps of appropriately defined quantum states, even when the Hamiltonian is non-unitary.The overlap states may have dimension greater than the Hamiltonian.Source: §5.1 · p. 16

5.2 Amplitude Multiplication of Overlap States

  • Amplitude multiplication avoids amplitude amplification’s nonlinear distortion, boosting encoded-Hamiltonian normalization with exponentially small spectral distortion.The result applies when upper bounds on the state-preparation slowdown factors and a target error are supplied.Source: §5.2 · pp. 17–18

5.3 Reduction to Sparse Matrices

  • For sparse Hamiltonian simulation, when ∥Ĥ∥1=d∥Ĥ∥max and Λ=Λ1=dΛmax, Theorem 5 has query complexity O(tdΛmax) up to logarithmic factors, equal to prior art.In the best case, ∥Ĥ∥1=O(∥Ĥ∥max) leads to a quadratic improvement in sparsity.Source: §5.3 · p. 20

5.4 Lower Bound on Sparse Hamiltonian Simulation

  • A PARITY composed with OR construction gives a sparse-simulation lower bound of Ω(t(d||H||1)^1/2) queries.The passage also notes an additive error-dependent lower-bound term of Ω(log(1/ε)/log log(1/ε)).Source: §5.4 · p. 20
  • The PARITY∘OR extension allows sparsity and 1-norm to vary independently.It composes OR Hamiltonians for groups of m input bits in place of the NOT Hamiltonians used for PARITY.Source: §5.4 · p. 21
  • The OR Hamiltonian maps |j⟩output|u⟩o to |j ⊕ OR(x)⟩output|u⟩o, with sparsity 2m, max-norm Θ(1), and 1-norm Θ(1).Here |u⟩o is the uniform superposition over the m-bit input positions.Source: §5.4 · p. 22
  • At least Omega(n*sqrt(m)) queries are required to simulate the PARITY∘OR Hamiltonian at time t = nπ/(2s).The construction has sparsity d = 2sm, max-norm Θ(1), and 1-norm Θ(s).Source: §5.4 · p. 22

6 Universality of the Standard-Form

This section establishes a connection between Hamiltonian simulation and measurement in standard-form encodings. It uses that connection to treat sums of Hermitian components and to relate their controlled exponentials to Hamiltonian simulation.

6 Universality of the Standard-Form

  • Circuits for time-evolution and measurement operators can be interconverted with logarithmic query overhead in error and constant space overhead.The stated connection has an edge case when time-evolution can be simulated with o(t) queries.Source: §6 · pp. 22–23
  • Quantum phase estimation provides the converse construction, encoding a measurement operator with O(1/ϵ) queries and error O(ϵ).The phase estimate controls an ancilla rotation, after which the register is uncomputed.Source: §6 · pp. 22–23
  • O(log(1/ϵ)) quantum signal processing queries approximate the inverse-sine transformation when ∥Ht∥≤1/2, yielding a standard-form encoding with normalization 1.The construction approximates sin(Ht) using a polynomial approximation to sin^-1(x).Source: §6 · pp. 23–24
  • For a sum of Hermitian components, access to their controlled exponentials suffices for simulation without restricting component eigenvalues to ±1.The paper also describes this approach as simpler in concept and implementation than compressed fractional queries.Source: §6 · p. 24

7 Conclusions

The conclusions highlight a sparse-Hamiltonian simulation algorithm whose query cost uses both sparsity and the induced one-norm, with a matching lower-bound result. They identify reduced encoding normalization as a broader direction for exploiting structure.

7 Conclusions

  • O(t(dΛmaxΛ1)^1/2) queries, excluding logarithmic factors, give the sparse-Hamiltonian simulation scaling, while the worst case recovers prior-art scaling.The conclusion states that the lower bound is consistent with a stronger bound when spectral-norm information is available.Source: §7 · p. 24
  • The best-case O(t√d) scaling is essential to an optimal realization of quantum search.The paper notes that the earlier scaling is recovered when information on the induced one-norm is unavailable.Source: §7 · p. 24
  • Reducing the normalization constant of Hamiltonian encodings is proposed as a potentially broader route to improving algorithms.The conclusion presents this as a future direction rather than a demonstrated further improvement.Source: §7 · p. 24

A Polynomial Approximations to a Truncated Linear Function

The section constructs an odd polynomial approximation to a truncated linear function by building entire approximations to sign and rectangular functions, then multiplying by a linear factor. The resulting degree scales as O(Γ^-1 log(1/ϵ)).

A Polynomial Approximations to a Truncated Linear Function

  • n = O(Γ^-1 log(1/ϵ)) suffices for an odd polynomial approximating the truncated linear function when Γ ∈ [0, 1/2] and ϵ ∈ (0, O(Γ)].The polynomial is constructed by multiplying a rectangular-function approximation by x/(2Γ).Source: A Polynomial Approximations to a… · pp. 25, 29
  • The construction approximates sign with an entire error function, combines shifted error functions to approximate a rectangle, and multiplies by x/(2Γ) to obtain the truncated linear function.Shifted error-function polynomials are the basic ingredient used to construct the sign and rectangular approximations.Source: A Polynomial Approximations to a… · pp. 25, 28
  • For x ≥ 2Γ, the entire truncated-linear approximation is bounded in [−0.0011, 0.56], with the corresponding bounds for x ≤ −2Γ following from oddness.The stated bounds are independent of Γ and hold for all ϵ′ ∈ [0, 1].Source: A Polynomial Approximations to a… · p. 26
  • The direct Chebyshev truncation of the entire truncated-linear approximation has worst-case uniform error ϵ, so the construction instead truncates the rectangle approximation before multiplying by x/(2Γ).The truncation error must satisfy ϵ_rect ≤ 2Γ to keep the resulting polynomial bounded by 1 as required by quantum signal processing.Source: A Polynomial Approximations to a… · pp. 26, 29

B Polynomials for Low-Energy Uniform Spectral Amplification

This section constructs a polynomial approximation to the gapped linear function by approximating it with an entire function and truncating its Chebyshev expansion. The resulting degree scales as O(∆^-1/2 log^(3/2)(1/(∆ϵ))).

B Polynomials for Low-Energy Uniform Spectral Amplification

  • The construction first forms an entire approximation to the gapped linear function over x ∈ [−1, ∞], then truncates its Chebyshev expansion to obtain a polynomial.The section uses an entire sign-function approximation and intermediate error-function results to build the approximant.Source: B Polynomials for Low-Energy Uniform… · p. 29
  • On x ∈ [1−∆, 1], the entire gapped-linear approximant has magnitude at most ϵ/10.The construction also bounds the approximant on subintervals of its domain, including [−1 + 3∆/2, 1 − ∆], where it lies between 0 and 1/2.Source: B Polynomials for Low-Energy Uniform… · p. 30
  • n = O(∆^-1/2 log^(3/2)(1/(∆ϵ))) gives an odd polynomial approximation to the gapped linear function.The polynomial is obtained by Chebyshev truncation of an entire approximation.Source: B Polynomials for Low-Energy Uniform… · pp. 29–30
Loading 1707.05391v1…