Hybrid Quantum-Classical Algorithm for Hamiltonian Simulation

1. Problem Statement

The paper addresses the problem of Hamiltonian simulation, specifically simulating the time evolution operator $e^{-iHt}$ for a quantum system. The authors focus on a specific class of Hamiltonians with a tensor product structure:
$$H = \sum_{i=1}^K H_i = \sum_{i=1}^K H_{i1} \otimes H_{i2} \otimes \dots \otimes H_{iM}$$
where each $H_{ij}$ is a small $d \times d$ Hermitian matrix.

Key Distinction from Existing Work:
Most existing quantum simulation algorithms (e.g., Sparse-Access models, Linear Combination of Unitaries (LCU)) rely on quantum oracles that provide access to matrix entries or assume the Hamiltonian is already a known linear combination of implementable unitaries.

• The Gap: It is often unclear if such oracles can be efficiently realized for arbitrary physical Hamiltonians.
• The Proposed Input: This paper assumes classical knowledge of the entries of the small constituent matrices $\{H_{ij}\}$. The goal is to leverage this classical data to construct a quantum simulation algorithm without requiring complex oracle access.

2. Methodology

The authors propose a Hybrid Classical-Quantum Algorithm. The workflow consists of three main stages:

A. Classical Pre-processing (Diagonalization)

Since the entries of the small matrices $H_{ij}$ are known classically, the algorithm first uses standard classical diagonalization algorithms to compute the eigenvalues ($\lambda_{ij}$) and eigenvectors ($|\lambda_{ij}\rangle$) for each $H_{ij}$.

• The spectrum of the full term $H_i = \bigotimes_j H_{ij}$ is constructed from the tensor product of the individual spectra.
• Optimization: If $H_i$ contains many identity terms (common in lattice systems), the algorithm identifies the set of non-trivial terms $R_i$ and only diagonalizes those, significantly reducing classical overhead.

B. Quantum Block-Encoding Construction

The core of the quantum algorithm is to construct a block-encoding of the Hamiltonian $H$. A unitary $U$ is a block-encoding of $A$ if $U = \begin{pmatrix} A & \cdot \\ \cdot & \cdot \end{pmatrix}$. The paper presents three distinct approaches to achieve this:

1. Approach 1 (Deterministic Linear Combination):

   • Prepare the eigenstates $|\lambda_{i1}\rangle \otimes \dots \otimes |\lambda_{iM}\rangle$ using quantum state preparation circuits.
   • Use Lemma III.2 to block-encode the density operators of these eigenstates.
   • Use Linear Combination of Unitaries (LCU) techniques to combine these block-encodings with coefficients derived from the eigenvalues to form the block-encoding of $H_i/\gamma_i$ (where $\gamma_i$ is a normalization factor).
   • Finally, combine all $H_i$ terms to block-encode $H$.

2. Approach 2 (Probabilistic Sampling / Central Limit Theorem):

   • Instead of deterministically combining all eigenstates, this approach samples a set of pure states based on a probability distribution defined by the absolute values of the eigenvalues.
   • It block-encodes these sampled states and averages them.
   • By the Central Limit Theorem, averaging $N = O(1/\epsilon^2)$ samples yields an $\epsilon$-approximate block-encoding of the target operator. This approach trades classical sampling time for potentially simpler quantum circuit structures but introduces a dependence on the sparsity of the eigenstates.

3. Approach 3 (Randomized Truncation for Dense States):

   • This approach utilizes a recent technique by Harrow, Lowe, and Witteveen (Ref. [36]) called Randomized Truncation.
   • It decomposes the potentially dense eigenstates into an ensemble of sparse states.
   • This allows for efficient state preparation even when the original eigenstates are not sparse, leveraging classical resources to handle the complexity of dense vectors while keeping the quantum circuit depth low.

C. Evolution Operator via QSVT

Once the block-encoding of $H$ is obtained, the algorithm applies Quantum Singular Value Transformation (QSVT) (specifically using the Jacobi-Anger expansion) to transform the block-encoding of $H$ into the block-encoding of the evolution operator $e^{-iHt}$.

D. Extension to Time-Dependent Hamiltonians

The method is extended to time-dependent Hamiltonians of the form $H(t) = \sum \alpha_i(t) H_i$, provided that all $H_i$ commute pairwise.

• Because the terms commute, the time-ordered exponential simplifies to $e^{-i \int H(s) ds}$.
• The algorithm computes the integral of the coefficients $\beta_i(t) = \int \alpha_i(s) ds$ classically and uses polynomial transformations (QSVT) to apply these time-dependent weights to the block-encoded $H_i$ terms.

3. Key Contributions

1. New Input Model: The paper establishes a simulation framework based on classical knowledge of tensor components rather than quantum oracles. This makes the algorithm applicable to physical lattice models (e.g., Transverse-Field Ising, Heisenberg) where the local terms are known but global oracles are not.
2. Three Hybrid Variants: It provides three algorithmic pathways (Deterministic, Probabilistic, Randomized Truncation) offering trade-offs between classical preprocessing time, quantum circuit depth, and ancilla qubit requirements.
3. Efficiency in Lattice Systems: The algorithm is shown to be highly efficient for systems where the non-trivial part of the Hamiltonian has small support (i.e., $|R_i| \ll M$). In such cases, the complexity scales polynomially with the number of non-trivial terms rather than the total system size.
4. Application to State Preparation: As a side contribution, the paper demonstrates how the "Randomized Truncation" technique can enhance quantum state preparation for dense states, reducing the required circuit depth and ancilla count compared to universal state preparation methods.

4. Results and Complexity Analysis

The paper provides detailed complexity bounds for the three approaches (summarized in Table I of the paper). Let $K$ be the number of terms, $d$ the dimension of local matrices, $M$ the number of tensor factors, and $|R|$ the maximum number of non-trivial terms in any $H_i$.

• Classical Complexity: Dominated by diagonalizing small matrices, roughly $O(K d^3)$ or $O(K |R| d^3)$.
• Quantum Complexity (Approach 1):
  $$O\left( K^2 d^{|R|} |R| \log(d) t \log(1/\delta) \right)$$
  Note: The complexity depends exponentially on $|R|$, making it optimal when $|R| = O(1)$ (e.g., nearest-neighbor interactions).
• Quantum Complexity (Approach 2):
  $$O\left( K^2 |R| \log(d) d^{4|R|} \delta^{-2} t^3 \log(1/\delta) \right)$$
  Higher dependence on error $\delta$ and time $t$, but avoids some classical diagonalization overhead.
• Quantum Complexity (Approach 3):
  $$O\left( t K^2 d^{|R|} |R| \log(Lsd) \log(1/\sqrt{\Delta}) \right)$$
  Efficient for dense states by leveraging classical sparsification.

Comparison with Existing Works:

• Unlike Sparse-Access models (Ref. [18, 28, 29]), this method does not require oracle construction.
• Unlike LCU models (Ref. [22]), it does not require the Hamiltonian to be a pre-defined sum of unitaries; it constructs the block-encoding from the tensor structure.
• For lattice simulations with nearest-neighbor interactions ($|R|=O(1)$), the proposed method achieves logarithmic scaling in $1/\delta$, offering an exponential speedup over product formula methods (Ref. [24, 25]) which scale polynomially in $1/\delta$.

5. Significance

• Complementarity: The authors argue that this hybrid framework does not compete with existing oracle-based methods but complements them. It fills a gap for Hamiltonians where the tensor structure is known classically but oracle access is difficult to implement.
• Near-Term Applicability: By offloading the diagonalization and state preparation logic to classical computers (or hybrid steps), the quantum circuit requirements are tailored for near-term devices, particularly for systems with local interactions.
• Generalization: The ability to handle time-dependent commuting Hamiltonians extends the utility of the method to dynamic physical systems.
• State Preparation: The application of randomized truncation to state preparation offers a practical route to preparing dense quantum states, a common bottleneck in quantum algorithms.

In conclusion, this work proposes a robust, hybrid strategy for Hamiltonian simulation that leverages classical computational power to overcome the limitations of current quantum simulation models, specifically targeting physically relevant lattice systems with local interactions.