PaperlayerView exact revision on arXiv

Source-linked AI summary

Black-box Hamiltonian simulation and unitary implementation

Dominic W. Berry, Andrew M. Childs

arXiv:0910.4157v4quant-ph

TL;DR

The paper asks how black-box Hamiltonians and unitaries can be simulated or implemented efficiently in an oracle model. It uses quantum walks and related techniques to improve sparse-Hamiltonian simulation and obtain subquadratic black-box unitary implementation, while noting boundaries for the strongest scalings.

  • Problem

    The query complexity of implementing general black-box unitaries had not previously been studied, alongside the need for improved simulation of sparse and non-sparse black-box Hamiltonians.

  • Method

    The paper completes a quantum-walk approach to black-box Hamiltonian simulation using state preparation, phase estimation, and magnitude-dependent Hamiltonian decomposition.

  • Results

    ˜O(N^2/3/δ^1/3) matrix-element queries implement an arbitrary N × N unitary with trace-distance error at most δ, while sparse-Hamiltonian simulation scales linearly in ∥H∥t and at worst linearly in D.

  • Takeaways & Limitations

    Quantum walks provide a unified route to improved black-box Hamiltonian simulation and unitary implementation, including the best known constant-precision sparse-Hamiltonian simulation.

Abstract

from arXiv · show

We present general methods for simulating black-box Hamiltonians using quantum walks. These techniques have two main applications: simulating sparse Hamiltonians and implementing black-box unitary operations. In particular, we give the best known simulation of sparse Hamiltonians with constant precision. Our method has complexity linear in both the sparseness D (the maximum number of nonzero elements in a column) and the evolution time t, whereas previous methods had complexity scaling as D^4 and were superlinear in t. We also consider the task of implementing an arbitrary unitary operation given a black-box description of its matrix elements. Whereas standard methods for performing an explicitly specified N x N unitary operation use O(N^2) elementary gates, we show that a black-box unitary can be performed with bounded error using O(N^{2/3} (log log N)^{4/3}) queries to its matrix elements. In fact, except for pathological cases, it appears that most unitaries can be performed with only O(sqrt{N}) queries, which is optimal.

I. INTRODUCTION

The paper develops quantum-walk methods for black-box Hamiltonian simulation, targeting both sparse Hamiltonians and black-box unitary implementation. It completes the general quantum-walk procedure and combines state preparation, phase estimation, and Hamiltonian decomposition techniques to improve query complexity.

  • Hamiltonian simulation is motivated by simulating quantum systems and supporting quantum algorithms.
  • The authors formulate simulation and unitary implementation in an oracle model where matrix elements are supplied by black boxes.
  • Quantum walks replace Lie-Trotter-Suzuki methods, achieving strictly linear scaling in evolution time t and linear scaling in sparse Hamiltonian parameter D.Previous approaches had superlinear t dependence and scaling as ˜O(D^4), later improved to ˜O(D^3).
  • The paper completes general quantum-walk implementation using phase estimation, amplitude amplification, an ancilla-assisted orthogonality condition, and Lie-Trotter-Suzuki recombination.The ancilla modification enables O(1)-query state preparation in the sparse case, while magnitude-dependent decomposition improves the non-sparse case.
  • ˜O(N^2/3) queries suffice to implement a general non-sparse N × N unitary, compared with Ω(N^2) elementary gates for an explicitly described unitary.The black-box query model avoids the counting limitation applying to explicit implementations.
  • Numerical evidence suggests typical unitaries require only ˜O(sqrt(N)) queries, while an open question remains whether this scaling holds for all black-box unitaries.The text notes that pathological unitaries may require more queries and frames the general O(sqrt(N)) bound as unresolved.

B. Results

The paper develops quantum-walk methods for black-box Hamiltonian simulation, with separate bounds optimized for sparse and non-sparse Hamiltonians. It also derives black-box unitary implementation from the Hamiltonian-simulation framework.

  • Sparse Hamiltonian simulation: O(D) scaling in sparseness and linear scaling in ∥H∥t characterize the first main simulation result for sparse Hamiltonians.The theorem uses oracles for Hamiltonian elements and sparsity structure.
  • Non-sparse Hamiltonian simulation: The second simulation result improves scaling in D at the expense of worse scaling in ∥H∥t, making it preferable for non-sparse Hamiltonians.The paper explicitly distinguishes this result from the sparse-Hamiltonian bound.
  • Black-box unitary implementation: A black-box unitary operation can be implemented using the Hamiltonian-simulation correspondence and a restricted-eigenvalue advantage.The unitary oracle directly supplies the Hamiltonian oracle, while the unitary case permits additional exploitation of eigenvalue restrictions.
  • Quantum-walk framework: The quantum walk constructs simulation dynamics whose eigenvalues and eigenvectors are related to those of H, enabling phase-estimation-based evolution.The walk applies phases corresponding to Hamiltonian eigenvalues and then uncomputes the walk embedding.
  • Implementation details: Negative real Hamiltonian entries require sign choices for square roots, while negative diagonal entries are handled by an identity shift that changes evolution only by a global phase.The identity shift increases relevant norms by at most a factor of 2.
  • Quantum-walk framework: The walk-based approach achieves linear dependence on t, unlike Lie-Trotter-Suzuki methods whose many short time steps produce superlinear t dependence.The paper identifies linear t scaling as optimal.

IV. SPARSE HAMILTONIAN SIMULATION

The sparse-simulation method implements quantum-walk reflections through oracle-based state preparation and combines them with a lazy walk and phase estimation. This yields improved query scaling, especially in sparseness and evolution time, relative to earlier methods.

  • Quantum-walk implementation: Quantum-walk simulation requires implementing the reflection about |ϕj⟩ conditional on the first-register index j.The reflection is realized by state preparation, reflection about |0⟩, and inverse state preparation.
  • State preparation: O(1) oracle queries suffice to prepare |φj⟩ when ε ∈ (0, Λ1/DΛmax].The construction uses the Hamiltonian and sparsity oracles under the stated parameter condition.
  • State preparation: The state-preparation construction queries sparsity information to form amplitudes associated with nonzero matrix elements, with controlled rotations generated from Hamiltonian entries.The parameter X is chosen so that X ≥ Λmax.
  • Error reduction: Combining lazy quantum walks with phase estimation gives O(Λ1t/ε) walk steps and reduces error relative to the earlier quantum-walk method for small ε.The method estimates eigenvalue signs and corrects the difference between ˜λ and arcsin ˜λ.
  • Sparse-simulation bound: Theorem 1 follows by combining constant-query state preparation with the improved walk simulation, producing total oracle complexity O(XDt).The selected ε makes Λ1t/ε = XDt an integer and preserves the state-preparation condition.
  • Comparison with prior methods: Compared with high-order integrators, the sparse method is better in all listed parameters except δ, with linear rather than D4 dependence and linear rather than slightly superlinear dependence on ∥H∥t.For δ = O(1/D2), there is no further explicit dependence on D.
  • Comparison with prior methods: Theorem 1 improves over naive black-box preparation and the earlier walk method, which require O(D∥H∥1t/δ) and O(∥H∥1t/δ) queries, respectively.The paper attributes the improvement to both norm dependence and improved δ scaling.

1. At the beginning, to map the initial state from CM

The construction implements the quantum-walk isometry by preparing auxiliary states and carefully defining its action on an added ancilla qubit. The final map approximately removes the prepared auxiliary register.

  • The initial implementation prepares |φj⟩ in an additional register controlled by the index state |j⟩.
  • The isometry must specify the extra ancilla’s action so the required eigenvalue and eigenvector relations hold.The construction uses states |Ωj⟩ on the expanded space and enforces an orthogonality condition.
  • Choosing |Ωj⟩=|Ω,1⟩ removes an unwanted term, but the walk operator must still act correctly when the ancilla is |1⟩.The eigenstates of the walk operator can contain |1⟩-ancilla components even when the individual prepared states use |0⟩.
  • The final inverse state-preparation step maps |j,0⟩|φj⟩ back toward |j,0⟩ only approximately.An ancilla state |1⟩ is treated as a failure component, while the |0⟩ branch undergoes inverse state preparation.

V. IMPROVED STATE PREPARATION

This section improves quantum-walk state preparation using amplitude amplification, combining it with earlier preparation methods to improve efficiency. The resulting preparation error produces a controlled simulation error.

  • Amplitude amplification is introduced to improve state preparation, particularly for the non-sparse case.The technique draws on black-box state preparation and Grover-style reflections.
  • Black-box preparation of an M-dimensional state requires M queries directly, while the presented state-preparation scheme is optimal under the search lower bound.
  • Combining the earlier preparation method with Grover’s technique improves both approaches and is favorable when D is large.
  • The approximate preparation has relative error O(ε) in the first-term weighting.
  • The resulting Hamiltonian-simulation error is O(∥H∥tε).The bound follows from the deviation between the actual and intended simulated Hamiltonians during evolution time t.

VI. NON-SPARSE HAMILTONIANS

The non-sparse simulation analysis combines quantum-walk steps with improved state preparation and derives improved performance for large D. Its behavior depends on matrix-element magnitude distributions and related norm conditions.

  • The overall query complexity is obtained by multiplying the quantum-walk step count by the oracle queries needed for each prepared step.
  • The non-sparse result provides improved performance when D is large, including the possibility D=M.
  • The simulation error contributions from imperfect state preparation and the quantum-walk procedure are each bounded by O(δ) under the stated parameter restrictions.
  • The worst case can arise from two different factors, including a sharp concentration of matrix-element weight in one row.
  • If nonzero matrix elements have relatively even magnitudes, the maximum-entry norm can scale more favorably relative to the Hamiltonian norm.

VII. BREAKING UP THE HAMILTONIAN

The Hamiltonian is decomposed into terms whose matrix elements have similar magnitudes, then their evolutions are recombined using Lie-Trotter-Suzuki formulas. The approach targets improved non-sparse scaling but must handle potentially large component norms.

  • The Hamiltonian is split into terms whose matrix elements have similar magnitudes before their evolutions are recombined.
  • A general method uses a number of queries roughly proportional to D^2/3 even when the individual component norms are large.

A. Small norms

When splitting a Hamiltonian into magnitude bands whose component norms remain controlled, quantum-walk simulation achieves favorable query scaling, including linear dependence on evolution time and improved dependence on sparsity.

  • Result: If break(H) is bounded by a constant, the resulting simulation has scaling close to the favorable small-norm regime.The analysis defines break(H) as the norm increase caused by decomposing H into parts.
  • Decomposition: The Hamiltonian is split into L components containing matrix elements grouped by decreasing magnitude using cutoff values A_ℓ.H_ℓ contains elements between successive cutoffs, with the final component containing the smallest elements.
  • Error control: The simulation combines component evolutions with a Lie-Trotter-Suzuki integrator while separately controlling individual-simulation and Trotter errors.The construction uses K = 1 in the main proof and allocates component error so the total remains O(δ).
  • Result: The theorem also covers the worst case where component norms are not small, yielding D^3/4 scaling when Υ = D.When splitting does not significantly increase the norm, the analysis gives a better scaling than this worst case.

B. Norms of components

Numerical tests indicate that component norms usually remain controlled: break(H) is near one for random Hermitian matrices and no larger than 1.5 for tested random-unitary-derived Hamiltonians, while tailored perturbations can be pathological.

  • Random Hamiltonians: For random Hermitian matrices, break(H) never exceeded 1.2 and approached 1 as dimension increased.The test used randomly generated Hermitian matrices with normally distributed elements.
  • Random Hamiltonians: For Hamiltonians composed from Haar-random unitaries, break(H) was larger than for random Hamiltonians but no larger than 1.5.The unitary-derived cases were tested because unitaries can have a large spectral-norm versus 1-norm difference.
  • Pathological example: A 0.01% perturbation of the quantum Fourier transform produced a break(H) value proportional to M for one splitting.Changing the threshold or smoothing the transition between components can make other splittings better behaved.
  • Pathological example: The authors suspect that every particular splitting admits examples with large component norms.Thus, small break(H) is supported numerically for typical tested matrices rather than universally.

C. Large norms

For Hamiltonians whose component norms may be large, the paper uses nonuniform magnitude cutoffs and a two-stage integration strategy to retain improved query scaling without assuming small break(H).

  • Conclusion: The resulting construction establishes the claimed improved simulation query bound without assuming that component spectral norms remain small.The proof carefully chooses time intervals to satisfy both quantum-walk and Trotter-error constraints.
  • C. Large norms: The large-norm method partitions H by matrix-element magnitude but chooses nonconstant cutoff ratios tailored to component-query costs.The cutoffs are selected so the relevant ratio scales roughly as D^1/3, minimizing the total query count.
  • Integration strategy: The smallest component H_L is simulated with Theorem 1 rather than Lemma 8 to avoid losing the improved scaling.The comparison between H_L and H_L−1 determines the final cutoff choice.
  • C. Large norms: The approach yields roughly D^2/3 queries per component before choosing ξ proportional to 1/log D to make D^ξ = O(1).The number of components varies doubly logarithmically with D, producing a double-logarithmic factor.
  • Integration strategy: The proof uses separate treatment for H_1 and the remaining components because H_1 needs larger time steps while the others have larger norms.A two-step Trotter process combines H_1 with the remaining sum and then combines the remaining components.

VIII. IMPLEMENTATION OF UNITARIES

The paper reduces black-box unitary implementation to Hamiltonian simulation through an associated Hamiltonian and quantum walk, obtaining exact or bounded-error query bounds depending on the chosen simulation result.

  • Reduction: A black-box unitary U is converted into a related Hamiltonian whose evolution for time π/2 implements U on the target state.The associated Hamiltonian has dimension twice that of U and can be queried using the unitary oracle.
  • Exact implementation: O(NΛ_max) queries implement a black-box unitary exactly when Λ_max bounds the maximum matrix-element magnitude.The construction uses exact Hamiltonian simulation for a Hamiltonian with eigenvalues ±1.
  • Exact implementation: Each quantum-walk step uses O(1) unitary-oracle queries, yielding the exact implementation bound from the walk length.For the associated Hamiltonian, the sparsity parameter can be taken as D = N.
  • Bounded-error implementation: For general unitaries, bounded-error implementation follows by applying the paper’s Hamiltonian-simulation corollaries with t = π/2, ∥H∥ = 1, and D = N.The construction uses the matrix-element oracle and, where needed, an additional oracle for locating nonzero entries.
  • Query complexity: The general bound is ˜O(N^2/3δ^−1/3) queries, while favorable structure can give ˜O(√(N/δ)) scaling.The favorable cases include similar-magnitude nonzero elements or decompositions with break(U) = O(1).

IX. EXAMPLES

The examples show that black-box unitary implementation ranges from optimal search-like cases to more demanding unitaries whose complexity depends on matrix-element structure. A spin-rotation example illustrates an intermediate scaling, while permutation matrices can be implemented with O(N) queries.

  • Search unitary: Ω(√N) queries are required for the search-encoding unitary, since applying it to |0⟩ produces the unique marked state.The corresponding isometry is equivalent to standard Grover search.
  • Permutation matrices: O(N) queries suffice for permutation matrices, and these implementations can be exact.The construction uses known parameters so the quantum-walk steps introduce no approximation error.
  • Other examples: The examples include the quantum Fourier transform as another simple unitary considered by the implementation methods.
  • Spin-rotation unitary: O(N^5/8/δ^1/2) queries result for the spin-rotation example under Corollary 12.The first column has a relatively narrow peak, while middle columns have more spread-out elements.
  • Spin-rotation unitary: Fig. 3 compares matrix-element magnitudes for the first and last columns of exp(−iπJx/2) when J = 100.Separate points represent |⟨j|U|0⟩|, while the solid curve represents |⟨j|U|J⟩|.
  • Spin-rotation unitary: Corollary 12 can perform worse than O(√N) when a sharp peak coexists with a broad distribution of remaining matrix elements.Numerical testing suggests that decomposing this unitary into components may recover O(√N) scaling, although calculating its matrix elements is nontrivial.

X. CONCLUSION

The paper develops quantum-walk methods for black-box Hamiltonian simulation and applies them to sparse Hamiltonian simulation and arbitrary unitary implementation. It achieves improved sparse-Hamiltonian scaling and a subquadratic query bound for black-box unitaries, while leaving the optimal general unitary complexity open.

  • ˜O(N^2/3/δ^1/3) queries implement an arbitrary N × N unitary with trace-distance error at most δ.
  • The approach combines discrete-time quantum-walk simulation, amplitude-amplification state preparation, and integrators that decompose the Hamiltonian.
  • ˜O(√N/δ) black-box calls are achievable in many cases, except when decomposition produces components with large spectral norms.Numerical testing suggests such cases are rare.
  • Sparse-Hamiltonian simulation has query complexity linear in ∥H∥t and at worst linear in D, improving on superlinear-time and O(D^4) scaling.
  • Ω(√N) is the known lower bound for black-box unitary implementation, and whether general implementation can achieve O(√N) remains open.
  • The tradeoff among D, ∥Ht∥, ∥Ht∥1, ∥Ht∥max, and δ for general black-box Hamiltonian simulation remains poorly understood.
Loading 0910.4157v4…