Product formulas for Hamiltonian simulation

[shangtai]

Had a discussion with @marekgluza and it is related to issue #1138

We intend to add a new method to symbolic hamiltonian where we can apply the product formula, mainly to implement eqs (1-2) here https://arxiv.org/abs/1901.00564

The idea is that given a symbolic Hamiltonian H, we find a corresponding circuit of primitive gates that approximates the evaluation to time t up to eps as arguments. This would help to explore use of fewer gates to achieve the approximation.

To make it general, I think we also need the ability to split the Hamiltonian into groups which contains commuting elements. It wonder if anyone has coded something like this?

Alternatively, we might have to assume that the given symbolic Hamiltonian has certain properties.

[marekgluza]

Hamiltonian simulation task

• cf abstract stage in #1138

  • [ ] Given a symbolically prescribed $H_0=\sum h_i$ get a circuit approximation of $e^{itH_0}$ via a product formula for example first order $(\prod_i e^{i t/N h_i})^N$

• More specific definitions we wish to approximate $$ U(t) = $e^{itH_0}$$ using parametrized gates $$U_i(s) = e^{i s h_i})$$ For this we define the first order formula $$L_N(t) = (\prod_i e^{i t/N h_i})^N$$ For any given $\epsilon >0$ we wish to find $N$ such $$||L_N(t) - U(t)||\le \epsilon$$ in operator norm.

Stage 1: Strategies for finding $dt$ to hit $\epsilon$ for the first order product formula

Scenario A: Classical simulation is possible.

This is the case where we can use the numpy backend to compute and store $U(t)$ This function defines $N$ by an exponential growth so that at some point the criterion above is fulfilled.

https://github.com/qiboteam/qibo/blob/0eb381d8644a74647501a196d2533d406c7b2d51/src/qibo/models/dbi/double_bracket_evolution_oracles.py#L81-L116

• [X] Task: find smallest needed $N$.
  • [X] implement binary search to extend the function above. Implemented by @shangtai https://github.com/qiboteam/qibo/blob/417bbfc8845b5ebd019d386db27f73bf43260727/src/qibo/models/dbi/double_bracket_evolution_oracles.py#L118

Scenario B: Classical simulation is not possible.

We may use the bound $$||Q(s) - U(s) || = \sum_{i=1}^N ||[hi,h{i+1}|| s^2 \le C_h s^2 N$$ where $C_h = max_i ||[hi,h{i+1}||$

Set $N = \epsilon / (C_h s^2)$

https://slides.com/marekgluza/tutorial-quantum-simulation#/1/6/3

[marekgluza]

Non-trivial benchmark example:

A hamiltonian of the form $$H_0 = \sum_i (Z_i + XiX{i+1} + Xi Z{i+1} X_{i+2})$$ can be simulated by free fermions for 10k sites. We can probe the performance there.

@shangtai

• [ ] verify that in the notation above $h_i = (Z_i + XiX{i+1} + Xi Z{i+1} X_{i+2})$. This is my question related to https://arxiv.org/abs/1901.00564 whether the notation there is useful for us or should we adapt it? In this example, can we use their higher order formula?

This Hamiltonian is interesting for physics (similar terms can generate symmetry-protected topologically ordered chains) and it is a nice toy example for non trivial Hamiltonian simulation because the parametrized gate $$e^{is Xi Z{i+1} X_{i+2}}$$ can be generated by a single group commutator because $$[ Xi Y{i+1}, X{i+1}X{i+2}] = 2 i Xi Z{i+1} X_{i+2}$$ Such two qubit interactions can be obtained from a single $e^{iZiZ{i+1}}$ parametrized gate via Hadamards or from 3 CNOTS (unfortunately I think $e^{is X \otimes Y} \notin SO(4)$ so not 2 CNOTS which suffice for any SO(4))

• [ ] compare the $N$ obtained for this model with the theoretical bound and with the ED allocation of $N$

[marekgluza]

How this connects to existing capabilities

See same function again: https://github.com/qiboteam/qibo/blob/0eb381d8644a74647501a196d2533d406c7b2d51/src/qibo/models/dbi/double_bracket_evolution_oracles.py#L81-L116

It assumes that we have a SymbolicHamiltonian for $H_0$ which can generate circuit. In the notation above, that circuit is exactly $Q(s)$ so the circuit method of SymbolicHamiltonian should be used only once and for a small step size. The rest should be by taking a concatenation of $N$ such circuits.

Stage 2 higher order formulas preparation

@shangtai Once the PR is in review I will spend more time on how to use Higher order formulas in this formalism but I believe it's just directly same as Childs and Su. In fact I formulated the above with parametrized gates (which we can obtain from a universal gate set by Solovay-Kitaev) and they just assume they have the exponentials $e^{it h_j}$. Then in terms of these parametrized gates the higher order formulas are formulated. No splitting into even and odd is needed here.

• [ ] explore the advantage of having an even - odd splitting of terms. Inside of each group all the terms are commuting and hence can be implemented in parallel. Does it matter for decoherence?
• [ ] prepare for higher order formulas and block this 3-qubit terms example in the even odd formalism to use the $L_2$ formula from the CS paper. What is the best way to do it?
• [ ] Can we generalize the product higher order formulas to more naturally treat this 3-local Hamiltonian?

[marekgluza]

Stage 2: higher order formulas for Hamiltonian simulation for SymbolicHamiltonian

To be expanded: Discussion how to use existing capabilities and integrate with the CS19 paper

[marekgluza]

Could be considered: https://arxiv.org/abs/2403.08729