Quantum Signal Processing for Polynomial Matrix Transformations

Hello! Let's dive into our next lesson.

Introduction

In our last session, we developed a concrete method for constructing a block encoding: a unitary circuit $U_A$ that embeds a sparse Hamiltonian $A$ into one of its blocks. This was a crucial step in moving from abstract concepts to practical circuit engineering. We now have a unitary $U_A$ that "contains" our Hamiltonian, but the key question remains: how do we use this unitary to perform useful computations, like simulating the evolution $e^{-iAt}$?

This lesson addresses that question by introducing one of the most powerful and unifying frameworks in modern quantum algorithms: Quantum Signal Processing (QSP). Our goal is to analyze the principles of QSP for applying polynomial transformations to a block-encoded matrix.

We will see that QSP provides a remarkably efficient way to transform a block encoding of a matrix $A$ into a block encoding of any (well-behaved) polynomial of that matrix, $P(A)$. This capability is the foundation for optimal algorithms in Hamiltonian simulation, quantum linear systems, and more.

Our journey will cover three main points:

1. The Core Mechanism: We'll start with the simplest case of a single qubit to understand how a sequence of rotations can "process" a scalar value $x$ to produce a polynomial $P(x)$.
2. Scaling to Matrices: We will then see how this single-qubit "game" is lifted to process a block-encoded matrix $A$, effectively applying the polynomial transformation to its eigenvalues.
3. Polynomials and Phases: Finally, we'll discuss which polynomials can be implemented and how the necessary rotation angles (phases) are determined.

This lesson builds directly on your knowledge of block encoding and will provide the theoretical foundation for our next topic: using QSP to construct an optimal Hamiltonian simulation circuit.

1. The Core Idea: The QSP "Game"

At its heart, QSP is a method for constructing a unitary matrix whose entries are specific polynomials. The simplest way to understand this is through a "game" played with 2x2 unitary matrices.

As the video explains, the game involves two key operations on a single qubit:

1. The Signal Unitary: A rotation around the ${\sigma }_x$ axis, whose angle depends on a scalar "signal" $x\in [-1,1]$. We define $x=\cos \theta$. The operator is:

   $$W(x)=e^{-i\theta {\sigma }_x}=e^{-i\arccos (x){\sigma }_x}=\left(\begin{array}{cc}x& -i\sqrt{1-x^2}\\ -i\sqrt{1-x^2}& x\end{array}\right)$$

   Note that the video uses a slightly different convention for $W(x)$ which is equivalent up to a global phase and basis change, but the principle is identical. The crucial part is that $⟨0|W(x)|0⟩=x$, so this unitary "encodes" the signal $x$.

2. The Processing Unitary: A rotation around the ${\sigma }_z$ axis by a controllable angle $\varphi$.

   $$R_z(\varphi )=e^{-i\varphi {\sigma }_z/2}=\left(\begin{array}{cc}{e}^{-i\varphi /2}& 0\\ 0& e^{i\varphi /2}\end{array}\right)$$

The QSP protocol constructs a sequence of these operations. For a target polynomial of degree $d$, we need a sequence of $d+1$ angles $\Phi =({\varphi }_0,{\varphi }_1,\dots ,{\varphi }_d)$. The total unitary is:

$$U_{\Phi }(x)=R_z({\varphi }_0)W(x)R_z({\varphi }_1)W(x)\dots W(x)R_z({\varphi }_d)$$

A remarkable result, which is the cornerstone of QSP, is that for a suitable choice of angles $\Phi$, the top-left entry of this unitary matrix is a degree-$d$ polynomial in $x$:

$$U_{\Phi }(x)=\left(\begin{array}{cc}P(x)& \cdot \\ \cdot & \cdot \end{array}\right)$$

where $P(x)=⟨0|U_{\Phi }(x)|0⟩$. This gives us a way to implement a (non-unitary) polynomial function by embedding it within a larger (unitary) matrix, a concept that should feel familiar from our work on block encoding.

2. From Scalar to Matrix: Processing a Block-Encoded Operator

The single-qubit game is powerful, but our goal is to apply a polynomial $P(A)$ to a matrix $A$. The bridge between the scalar case and the matrix case is the block encoding we constructed in the previous lesson.

The key idea is to use the block-encoding unitary $U_A$ to construct a new operator that acts on a small, invariant subspace for each eigenvector of $A$, and within that subspace, it behaves exactly like the signal unitary $W(\lambda )$ for the corresponding eigenvalue $\lambda$.

Let's break down the logic from the paper.

1. Start with a Block Encoding: We assume we have a block encoding $U_A$ of a Hermitian matrix $A$ such that $⟨0\dots 0|U_A|0\dots 0⟩=A$. For simplicity, let's assume $U_A$ is also Hermitian ($U_A^2=I$), a property that can be achieved with a specific circuit construction as we briefly noted last time.

2. Construct the Signal Operator W: We define a "qubitized" operator $W=(2|0⟩⟨0|-I)\otimes U_A$. This operator acts on the joint space of the ancilla and the system. If $|\lambda ⟩$ is an eigenvector of $A$ with eigenvalue $\lambda$, then $W$ has a 2D invariant subspace spanned by $|0⟩|\lambda ⟩$ and a related state. Within this subspace, $W$ acts as:

   $$W\cong \left(\begin{array}{cc}\lambda & \sqrt{1-{\lambda }^2}\\ \sqrt{1-{\lambda }^2}& -\lambda \end{array}\right)$$

   This is almost identical to our single-qubit signal unitary $W(\lambda )$! This is the crucial connection.

3. Process with an Ancilla: We introduce one more ancilla qubit (the "QSP ancilla" or "exit ancilla"). The QSP circuit now alternates between two operations:

   • Processing: Apply a single-qubit rotation $R_z({\varphi }_j)$ to the QSP ancilla.
   • Signal: Apply the operator $W$, controlled by the QSP ancilla.

The full sequence looks like this, where all rotations act on the QSP ancilla:

$$\text{Circuit}=R_z({\varphi }_0)\cdot \text{Controlled-}W\cdot R_z({\varphi }_1)\cdot \text{Controlled-}W\dots$$

Because the controlled-$W$ operation effectively applies $W(\lambda )$ for each eigenvalue $\lambda$, the entire sequence performs the single-qubit QSP protocol in parallel for all eigenvalues.

The final result is a unitary whose top-left block, when measured in the appropriate basis, corresponds to the operator $P(A)$. We have successfully applied a polynomial transformation to our block-encoded matrix.

3. Representable Polynomials and Finding the Phases

We've established that QSP can implement a polynomial transformation $P(A)$. But two questions naturally arise:

1. What are the constraints on the polynomial $P(x)$?
2. For a given $P(x)$, how do we find the phase angles $\Phi =({\varphi }_0,\dots ,{\varphi }_d)$?

This classical pre-processing step is known as "QSP-processing" or "phase-finding."

Properties of Representable Polynomials

As the paper and the initial video mention, not every polynomial can be directly implemented as the $⟨0|\dots |0⟩$ component. For the standard "Angle-QSP" convention we've been using, a degree-$d$ polynomial $P(x)$ must satisfy two main conditions:

1. Magnitude Bound: $|P(x)|\le 1$ for all $x\in [-1,1]$. This is intuitive, as $P(x)$ is an entry in a unitary matrix, whose elements cannot have a magnitude greater than 1.
2. Parity: $P(x)$ must have a definite parity, and this parity must match the degree $d$. That is, if $d$ is even, $P(x)$ must be an even function ($P(-x)=P(x)$), and if $d$ is odd, $P(x)$ must be an odd function ($P(-x)=-P(x)$).

What if we want to implement a polynomial without a definite parity, like $P(x)=x+x^2$? QSP can handle this by implementing the even and odd parts separately and then combining them using the Linear Combination of Unitaries (LCU) technique, which adds some overhead. More advanced conventions like Generalized-QSP (G-QSP) can implement arbitrary polynomials directly.

Finding the Phase Factors

The problem of finding the angles $\Phi$ for a given target polynomial $P(x)$ is a non-trivial classical computation. There is a rich literature on this, and several methods exist.

As the video and the "Hitchhiker's Guide" (Section 5) describe, the main approaches to finding the phases include:

• Direct Methods: These methods rely on analytical properties of the polynomials. One approach involves finding the roots of a related polynomial, which can be numerically unstable for high degrees. More recent, stable methods (like the BerSün method mentioned in 841de) use techniques based on Fourier transforms and contour integration.
• Optimization Methods: These methods frame the problem as finding the angles $\Phi$ that minimize the difference between the resulting QSP polynomial and the target polynomial. While the optimization landscape is complex with many local minima, clever initial guesses and algorithms (like fixed-point iteration or Newton's method) have been developed that are extremely effective in practice.

For our purposes, the crucial point is that finding the QSP phases is a solvable classical problem. Efficient and robust algorithms exist that, given a target polynomial $P(x)$, can compute the required angles $\Phi$ to high precision.

Conclusion

In this lesson, we have unpacked the core principles of Quantum Signal Processing, a cornerstone of modern quantum algorithm design.

Key Takeaways:

• QSP's Core Function: QSP provides a method to construct a unitary operator $U_{\Phi }$ whose entries are polynomials of a variable $x$. This is achieved by alternating a "signal" unitary $W(x)$ with "processing" single-qubit rotations $R_z({\varphi }_j)$.
• Processing Block-Encoded Matrices: The real power of QSP comes from its ability to process matrices. By using a block-encoding $U_A$ of a matrix $A$, we can construct a controlled signal operator that allows us to apply the QSP protocol to the eigenvalues of $A$, resulting in a block encoding of the polynomial operator $P(A)$.
• Polynomial Properties and Phase Finding: The simplest QSP conventions require the target polynomial to have a fixed parity and be bounded by 1. The classical problem of finding the required rotation angles for a given polynomial is well-studied and can be solved efficiently with various numerical methods.

Preview of the Next Lesson

We have established a powerful, general-purpose tool: if we can block-encode $A$, we can use QSP to generate a block encoding of $P(A)$ for essentially any polynomial $P$.

In our next lesson, Apply the QSP framework to construct a circuit for Hamiltonian simulation, approximating the time-evolution operator $e^{-iHt}$, we will put this tool to work. We will choose a specific polynomial—a truncated Jacobi-Anger expansion—that provides a very high-quality approximation to the function $f(x)=e^{-ixt}$. By finding the QSP phases for this polynomial, we will construct a near-optimal quantum circuit for Hamiltonian simulation.