Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing

This paper presents a polynomial-time algorithm that provides an exact, suboptimal solution for decomposing arbitrary two-body Hamiltonians into local unitary transformations of an Ising Hamiltonian, thereby enabling scalable digital-analog quantum simulation without the need for computationally expensive numerical optimization.

The Gist

Imagine you are trying to bake a very specific, complex cake (a Quantum Simulation). To do this, you have a kitchen with a very powerful, but slightly stubborn, oven (the Quantum Computer).

In the old way of doing things (Digital Quantum Computing), you would try to build the cake entirely out of tiny, individual Lego bricks. You'd have to snap thousands of tiny bricks together one by one to make the shape you want. It's precise, but it takes a long time to figure out exactly which bricks go where, and if you drop one, the whole thing might fall apart.

Digital-Analog Quantum Computing (DAQC) is a smarter way to bake. Instead of using only tiny bricks, you use the oven's natural heat and airflow (the Natural Hamiltonian) to do the heavy lifting. You just need to open and close the oven door at the right times and maybe rotate the cake pan slightly (the Single Qubit Gates) to get the perfect shape.

The Problem: The "Recipe" Nightmare

The problem with this "oven" method is that figuring out the perfect recipe is incredibly hard.

• If you want to simulate a specific chemical reaction or a new material, you need to tell the oven exactly how to move.
• Currently, finding the right sequence of door openings and rotations requires a supercomputer to run a massive, endless calculation. It's like trying to solve a puzzle with a billion pieces by guessing randomly. It takes too long, and often, the computer gives up before finding a good solution.

The Solution: A New "Magic Recipe"

This paper introduces a new, clever method to solve that puzzle quickly and exactly, without needing a supercomputer to guess.

Here is the analogy:

1. The Old Way (The Guessing Game):
Imagine you have a giant, messy pile of ingredients (the problem you want to solve). You want to arrange them into a specific pattern. The old method says, "Let's try moving every single ingredient one by one, checking if it fits, and if not, try again." This takes forever.

2. The New Way (The "Decomposition" Trick):
The authors found a mathematical shortcut. They realized that any complex pattern of ingredients can be broken down into a few simple, repeating layers.

• They treat the problem like a 3D sculpture.
• Instead of trying to carve the whole sculpture at once, they use a special tool (math called Eigendecomposition) to see the sculpture's "skeleton."
• This skeleton tells them exactly how to slice the problem into simple, manageable chunks.

The "Magic" Steps

The paper provides a step-by-step recipe that anyone (or any computer) can follow in a reasonable amount of time:

1. Look at the "Map": They take the complex problem and turn it into a giant grid of numbers (a matrix).
2. Find the "Spine": They use a mathematical trick to find the main "spine" or direction of this grid. This is like finding the main axis of a spinning top.
3. Slice and Dice: They break the problem down into about $N^2$ simple steps (where $N$ is the number of particles). Crucially, they prove that you don't need millions of steps; you only need a number of steps that grows slowly as the problem gets bigger.
4. The "Sandwich" Technique: For each step, they tell the quantum computer:
   • Step A: Rotate the ingredients slightly (Digital Gate).
   • Step B: Let the oven do its natural work for a specific time (Analog Evolution).
   • Step C: Rotate them back.
   • This "sandwich" changes the oven's natural behavior just enough to mimic the specific problem you wanted to solve.

Why is this a Big Deal?

• Speed: Before, finding the recipe took exponential time (if the problem got slightly bigger, the time to find the recipe doubled, then quadrupled, then exploded). Now, it takes polynomial time. If the problem gets twice as big, the time to find the recipe only goes up by a manageable factor (like 8 times). It's the difference between waiting a million years and waiting a few hours.
• No Guessing: You don't need a supercomputer to "optimize" or guess the best path. The paper gives you an exact formula. It's like having a GPS that gives you the route instantly, rather than a map where you have to draw the lines yourself.
• Scalability: Because the recipe is so efficient, we can now simulate much larger and more complex systems (like new drugs or materials) on quantum computers that we actually have today.

The Bottom Line

The authors have taken a problem that was considered "impossible to solve efficiently" and turned it into a straightforward, step-by-step instruction manual. They showed that by using the natural strengths of the quantum hardware (the "oven") and applying a clever mathematical trick to organize the instructions, we can simulate the universe's most complex systems without getting stuck in a computational traffic jam.

It's the difference between trying to build a cathedral by hand, one stone at a time, versus having a blueprint that tells you exactly how to use a crane to lift the heavy beams into place instantly.

Technical Summary

Here is a detailed technical summary of the paper "Hamiltonian simulation with explicit formulas for Digital-Analog Quantum Computing" by Mikel Garcia de Andoin, Thorge Müller, and Gonzalo Camacho.

1. Problem Statement

The paper addresses the challenge of Hamiltonian simulation within the Digital-Analog Quantum Computing (DAQC) paradigm.

• Context: DAQC combines digital single-qubit gates (SQGs) with the natural analog evolution of a system under a source Hamiltonian ($H_S$) to simulate a target problem Hamiltonian ($H_P$). This paradigm offers universality with improved noise resilience compared to purely digital approaches.
• The Bottleneck: Designing optimal DAQC circuits for arbitrary two-body Hamiltonians is an NP-Hard problem. Existing methods typically require:
  • Exponential classical computational time to find optimal gate sequences.
  • Numerical optimization over large parameter spaces (often involving Matrix Product States or heuristic searches) during the preprocessing stage.
  • These requirements hinder the scalability of DAQC to systems with a large number of qubits ($N$).
• Specific Goal: The authors aim to find a suboptimal but efficient solution that expresses an arbitrary two-body Hamiltonian as a sum of local unitary transformations of a fixed Ising (ZZ) Hamiltonian, solvable within polynomial computational time.

2. Methodology

The authors propose a constructive protocol that avoids numerical optimization by deriving exact analytical formulas.

A. Mathematical Formulation

The problem is framed as decomposing the target Hamiltonian $H_P$ into a sequence of analog blocks evolved under a source Hamiltonian $H_S$ (specifically a ZZ Hamiltonian), sandwiched by digital SQGs ($U_k$):
$$e^{-i T H_P} \approx \prod_k U_k e^{-i t_k H_S} U_k^\dagger$$
By equating the exponents (ignoring non-commutativity errors initially, which are handled via Trotterization), the problem reduces to solving a linear system for the analog block times $t_k$ and the rotation parameters of the SQGs.

The core equation relates the coupling matrix of the problem ($H_P$) to the source ($H_S$) via a transformation matrix $B$:
$$\sum_k t_k \gamma_{ik}^\mu \gamma_{jk}^\nu = T \frac{h_{ij}^P}{h_{ij}^S} = B_{ij}^{\mu\nu}$$
Here, $\gamma_{ik}$ represents the components of the rotation vector for qubit $i$ at step $k$, constrained to be normalized ($\|\gamma\|=1$).

B. The Constructive Protocol

The authors introduce a novel approach to solve this system without iterative optimization:

1. Matrix Construction: They construct a $3N \times 3N$real symmetric matrix$B$ representing the couplings of the problem Hamiltonian relative to the source.
2. Eigendecomposition: Instead of solving the non-linear optimization directly, they perform an eigendecomposition of $B$:
   $$B = U^\dagger \Lambda U$$
   where $\Lambda$ contains eigenvalues and $U$ contains eigenvectors.
3. Handling Constraints:
   • Positivity: Since analog times $t_k$ must be positive, the authors ensure $B$ is positive semi-definite by adjusting the indeterminate diagonal elements (which correspond to single-qubit terms not present in two-body interactions).
   • Normalization: The eigenvectors of $B$ do not naturally satisfy the specific normalization condition required for the SQG rotation vectors ($\|\gamma\|=1$ with specific block structures).
4. Divide and Conquer Decomposition: To satisfy the normalization constraint, the authors derive an explicit formula to decompose each eigenvector projector into a sum of valid rotation vectors.
   • For each eigenvalue $\lambda_k$ and eigenvector $\vec{v}_k$, they construct a decomposition involving $2N$ steps.
   • This involves introducing auxiliary perpendicular vectors ($\eta, \xi$) and specific rotation angles $\theta$ to ensure the resulting vectors $\vec{\gamma}$ are normalized and satisfy the orthogonality conditions required to cancel cross-terms.
5. Explicit Formulas: The paper provides closed-form expressions (Eq. 14-17) for the analog times $t_q$ and the rotation parameters $\vec{\gamma}$ based on the eigendecomposition of $B$.

3. Key Contributions

• Polynomial Time Complexity: The protocol reduces the classical computational cost of compiling DAQC circuits from exponential to $O(N^3)$, dominated by the eigendecomposition of the $3N \times 3N$ matrix.
• Exact Analytical Solution: It provides an exact solution for expressing arbitrary two-body Hamiltonians as a sum of local unitary transformations of a ZZ Hamiltonian, eliminating the need for numerical optimization or heuristic search.
• Circuit Complexity: The resulting circuit consists of at most **$12N^2$** digital-analog blocks. This is comparable to the worst-case complexity of previous algorithms ($9N(N-1)/2$) but achieved without the heavy computational overhead.
• Scalability: The method allows for the simulation of arbitrary two-body Hamiltonians on systems with large $N$ using minimal classical resources.

4. Results

The authors validated their protocol through numerical calculations:

• Scaling Analysis: They generated random problem matrices $B$ (normalized to unit magnitude) for system sizes up to $N=50$.
• Total Time ($t_A$): The total analog block time required ($t_A = \sum t_q$) was found to scale nearly constantly with system size $N$ for these random instances. This contrasts with theoretical upper bounds that suggest linear scaling with $N$.
• Dependence on Coupling Ratios: The total time scales linearly with the maximum ratio between the problem and source Hamiltonian couplings ($T \max |h^P/h^S|$), but is independent of $N$ when this ratio is bounded.
• Efficiency: The protocol successfully generates valid circuits for arbitrary two-body interactions, confirming that the "suboptimal" solution (in terms of total time) is highly efficient in terms of classical compilation resources.

5. Significance and Future Outlook

• Enabling Large-Scale DAQC: By removing the exponential classical bottleneck, this work makes DAQC a viable candidate for near-term quantum simulation on platforms like superconducting circuits, trapped ions, and neutral atoms.
• Resource Minimization: It minimizes the classical computational resources required for the "preprocessing" stage of quantum compilation, allowing for faster circuit generation and potential real-time adaptation.
• Generalizability: While the current protocol assumes a ZZ source Hamiltonian, the authors note it can be extended to symmetric Hamiltonians (XX, YY). For generic source Hamiltonians, a two-step mapping (Source $\to$ ZZ $\to$ Problem) is possible, though it may increase the block count.
• Impact on Quantum Simulation: This advancement supports the practical implementation of quantum simulations in chemistry and condensed matter physics, where simulating complex many-body interactions is crucial.

In summary, the paper bridges the gap between the theoretical universality of DAQC and its practical implementation by providing a mathematically rigorous, computationally efficient recipe for compiling Hamiltonian simulation circuits.