QSP for Hamiltonian Simulation

Hello! Let's continue our exploration of advanced quantum algorithms.

Introduction

In our last lesson, we established the fundamental principles of Quantum Signal Processing (QSP), showing how it can apply a polynomial transformation $P (A)$ to a block-encoded matrix $A$ . This powerful tool allows us to engineer a wide range of non-unitary operations by embedding them within a larger unitary circuit.

Today, we will apply this framework to one of the most important problems in quantum computing: Hamiltonian simulation. Our learning outcome is to apply the QSP framework to construct a circuit for Hamiltonian simulation, approximating the time-evolution operator $e^{- i H t}$ .

The function we want to implement is $f (x) = e^{- i x t}$ , which is not a polynomial. More importantly, it lacks the definite parity (being neither purely even nor purely odd) that the standard QSP protocol we studied requires. We will investigate two sophisticated strategies to overcome this challenge:

The Conventional LCU Approach: We will first see how to decompose the complex exponential into its even ( $cos$ ) and odd ( $sin$ ) components, approximate each with a suitable polynomial, and then recombine them using the Linear Combination of Unitaries (LCU) technique.
The Coherent One-Shot Method: We will then explore a more advanced and efficient method that uses a clever "pre-transformation" of the Hamiltonian's spectrum. This allows us to approximate the time-evolution operator with a single, high-probability QSP sequence, making it a "fully-coherent" subroutine.

By the end of this lesson, you will understand how to translate the abstract theory of QSP into a concrete circuit for performing near-optimal Hamiltonian simulation.

1. The Conventional Approach: Decomposing and Recombining

The most direct way to handle a function without definite parity, like $e^{- i x t} = cos (x t) - i sin (x t)$ , is to tackle its even and odd parts separately.

The even part is $cos (x t)$ .
The odd part is $- i sin (x t)$ .

We can find polynomial approximations for both $cos (x t)$ and $sin (x t)$ and then use QSP to implement them. A standard method for this is the Jacobi-Anger expansion, which expresses these trigonometric functions as an infinite series of Chebyshev polynomials. Truncating this series gives a high-quality polynomial approximation.

With these two polynomial approximations, say $P_{c o s} (x)$ and $P_{s i n} (x)$ , we can use QSP to construct two different unitaries that block-encode $P_{c o s} (H)$ and $- i P_{s i n} (H)$ . The final step is to add them together. As we've seen before, the tool for adding unitary operators is the Linear Combination of Unitaries (LCU) circuit.

Efficient fully-coherent quantum signal processing algorithms ...

The paper 'Efficient fully-coherent quantum signal processing algorithms for real-time dynamics simulation' by Martyn et al. provides an excellent description of this conventional QSP-LCU method.

Please read Section II, 'CONVENTIONAL QSP-BASED HAMILTONIAN SIMULATION' (pages 2-4). Pay close attention to: The core idea of applying QET (Quantum Eigenvalue Transformation, a synonym for the matrix version of QSP) twice: once for an even polynomial approximating cos(xτ) and once for an odd polynomial approximating -i sin(xτ). Figure 1, which shows the LCU circuit used to sum the two resulting operators. The discussion of the success probability, which is close to 1/4, highlighting the need for amplitude amplification.

As the paper details, this QSP-LCU approach is a valid way to perform Hamiltonian simulation. However, it has a significant drawback: the LCU circuit succeeds only when its ancilla qubit is measured in the $∣0 ⟩$ state, and the QSP subroutines also have their own success conditions. The combined success probability is low (around 1/4). To boost this to near unity, one must use techniques like amplitude amplification, which increases the circuit complexity and gate count.

This probabilistic nature makes the QSP-LCU method less "coherent" and less ideal for use as a seamless subroutine within larger quantum algorithms, where errors and failures can cascade. This motivates the search for a better approach.

2. The Advanced Approach: Coherent One-Shot Simulation

Is it possible to construct the approximation of $e^{- i H t}$ with a single QSP sequence that succeeds with high probability, avoiding the need for LCU and amplitude amplification? The answer is yes, through a clever technique that we'll call "coherent one-shot" simulation.

The core insight is that the strict parity requirement for QSP polynomials stems from the need for the polynomial $P (x)$ to satisfy $∣ P (x) ∣^{2} \leq 1$ for all $x \in [- 1, 1]$ , and in particular, $∣ P (\pm 1) ∣ = 1$ . If we could guarantee that the eigenvalues $λ$ of our Hamiltonian of interest lie strictly within a sub-interval, say $[a, b] \subset (- 1, 1)$ , we wouldn't need to worry about the polynomial's behavior at the boundaries.

This leads to a three-step process.

Efficient fully-coherent quantum signal processing algorithms ...

The same paper by Martyn et al. introduces this novel method. It's a more advanced construction that achieves full coherence.

Please read Section III, 'COHERENT ONE-SHOT HAMILTONIAN SIMULATION' (pages 7-9). Focus on understanding the three key steps: Pre-transformation: How the Hamiltonian's spectrum is linearly rescaled into a smaller interval like [ (1-β)/2, (1+β)/2 ]. Target Polynomial: The introduction of the 'Even Extension of the Complex Exponential' (EECE), which has the required even parity. Probability of Success: Why this method naturally leads to a high success probability, making it 'coherent'.

Let's summarize the elegant logic from the paper.

Step 1: Pre-transformation

We start with our block-encoded, rescaled Hamiltonian $H / α$ , whose eigenvalues are in $[- 1, 1]$ . We then apply a linear transformation to create a new Hamiltonian $\tilde{H}$ whose eigenvalues are guaranteed to be in a smaller, positive interval, for instance $[a, b] \subset [0, 1]$ . A common choice is:
$\tilde{H} = \frac{1}{2} (I + β H / α) for some β < 1$
The eigenvalues $λ$ of $H / α$ are mapped to $\tilde{λ} = \frac{1}{2} (1 + β λ)$ , which lie in the interval $[\frac{1 - β}{2}, \frac{1 + β}{2}]$ . This pre-transformation can be implemented with a simple circuit using one or two extra ancilla qubits, as shown in the paper's Figs. 4 and 5.

Step 2: The Even Extension of the Complex Exponential (EECE)

Now that we only care about the polynomial's behavior on a positive interval, we can design a target function that is purely even but matches $e^{- i xτ}$ for $x > 0$ . This is the EECE:

EECE (x; τ) := cos (τx) - i sin (τ ∣ x ∣)

This function has even parity by construction. For any positive eigenvalue $\tilde{λ}$ of our pre-transformed Hamiltonian $\tilde{H}$ , we have $EECE (\tilde{λ}; τ) = e^{- i \tilde{λ} τ}$ . We can find a single even polynomial $P_{EECE} (x)$ that approximates this function.

Step 3: The "One-Shot" QSP Implementation

We can now use a single QSP sequence to implement $P_{EECE} (\tilde{H})$ . By choosing the effective time $τ$ correctly, we can ensure that this operator approximates the desired time evolution. For example, applying $P_{EECE} (\tilde{H})$ with $τ = 2 t α / β$ gives:

P_{EECE} (\tilde{H}) \approx e^{- i \tilde{H} τ} = e^{- i \frac{1}{2} (I + β H / α) \frac{2 t α}{β}} = e^{- i t α / β} e^{- i H t}

This is exactly the time-evolution operator $e^{- i H t}$ , up to an irrelevant global phase.

Because we are implementing a single polynomial that is bounded by 1, the resulting QSP unitary block-encodes our target operator with a magnitude close to 1. By unitarity, this means the probability of success (i.e., measuring the ancillas in the correct state) is very high, scaling as $1 - O (ϵ^{2})$ , where $ϵ$ is the approximation error. This is why the method is "coherent" and "one-shot."

3. Constructing the Final Circuit

We have the theoretical framework. Now, let's look at the concrete structure of the quantum circuit that implements this. The circuit is a direct application of the QSP protocol we studied previously, using the block-encoding of our (possibly pre-transformed) Hamiltonian as the "signal unitary."

Realization of quantum signal processing on a noisy ...

The paper 'Realization of quantum signal processing on a noisy quantum computer' by Y. Sahin et al. provides a clear, modern depiction of the QSP circuit for Hamiltonian simulation.

Please read the subsection 'Review of Hamiltonian simulation by quantum signal processing' (page 2) and the 'Processing' subsection (page 6). Focus on Equation (17), which gives the explicit form of the QSP unitary U_QSP for an even-degree polynomial. This is the circuit we are aiming to build.

As described in the paper, the QSP circuit for an even-degree polynomial $f (x)$ of degree $d$ is constructed as a sequence of $d /2$ blocks. The overall unitary is:

U_{QSP} := k = 1 \prod d /2 [S (ϕ_{2 k - 1}) W^{†} S (ϕ_{2 k}) W]

Let's break down the components of this circuit:

$W$ : This is the signal unitary, which is the block encoding of our rescaled Hamiltonian $\tilde{H}$ . In the previous lessons, we saw how to construct this using methods like LCU or by finding a sparse-access oracle.
$S (ϕ)$ : This is the processing unitary. It is a phase rotation applied to the QSP ancilla, conditioned on the block-encoding ancillas being in the all-zero state. It can be implemented as a single-qubit $R_{z}$ rotation on the QSP ancilla, controlled by all the ancillas used for the block encoding $W$ .
${ϕ_{k}}$ : These are the QSP phases, a set of classical angles that are pre-computed to make the resulting polynomial match our target (e.g., the EECE approximation).

The final circuit is an alternating sequence of the block-encoding unitary $W$ (and its inverse $W^{†}$ ) and controlled phase rotations $S (ϕ_{k})$ . When we prepare the ancillas in the correct initial state and apply $U_{QSP}$ , the state of our system register evolves under an operator that is an excellent approximation of $e^{- i H t}$ .

Conclusion

In this lesson, we have bridged the gap between the abstract theory of QSP and the practical construction of a circuit for Hamiltonian simulation. We have shown how to overcome the parity constraint of the target function $e^{- i x t}$ to build a near-optimal simulation algorithm.

Key Takeaways:

The Challenge: Simulating $e^{- i H t}$ with QSP is non-trivial because the function $e^{- i x t}$ lacks the definite parity required by simple QSP protocols.
Two Solutions:
1. The LCU method splits the function into even ( $cos$ ) and odd ( $sin$ ) parts, implements them with separate QSP sequences, and recombines them probabilistically.
2. The coherent one-shot method is more advanced. It first rescales the Hamiltonian's spectrum to a safe sub-interval, then uses a single, high-probability QSP sequence to implement an even-parity approximation of the complex exponential (the EECE).
Circuit Construction: The final quantum circuit consists of an alternating sequence of a signal unitary (the block encoding of the Hamiltonian) and processing unitaries (controlled phase rotations), whose angles are determined by a classical pre-computation step.

Preview of the Next Lesson

We have now assembled a complete, powerful, and near-optimal algorithm for a critical quantum task. This represents a high point in the "ideal" world of fault-tolerant quantum algorithm design. However, real-world quantum computers are far from ideal; they are plagued by noise.

In the next module, we will pivot to confront this reality. Our first lesson will be Derive the Kraus operator representation for standard single-qubit noise channels (bit-flip, phase-flip, depolarizing). We will begin to build the mathematical language needed to describe what happens when our perfect gates and qubits interact with their environment, setting the stage for understanding and eventually combating these errors.