LCU Lemma and Non-Unitary Matrix Simulation

Hello! Welcome to the next lesson in our deep dive into recent advances in quantum computing.

In our last few lessons, we explored variational quantum algorithms like VQE and QAOA, which are leading candidates for applications on near-term, noisy hardware. We saw how they use a hybrid quantum-classical approach to find solutions to optimization problems.

Today, we shift gears to a powerful and fundamental technique that underpins many of the most advanced quantum algorithms designed for fault-tolerant computers. The core challenge we'll address is this: quantum computers evolve states through unitary operations, but many crucial computational tasks—from solving linear systems to certain types of simulation—involve non-unitary matrices. How do we bridge this gap?

This lesson will answer that question by focusing on the learning outcome: Derive the Linear Combination of Unitaries (LCU) lemma and analyze its application for non-unitary matrix simulation.

We will cover:

The core concept of "block-encoding," where a non-unitary operator is embedded within a larger unitary one.
The derivation of the LCU lemma, which formalizes a circuit for applying an operator expressed as $X = \sum_{j} a_{j} U_{j}$ .
How to apply this framework to simulate non-unitary operations, such as matrix inversion and imaginary time evolution.

This topic is a cornerstone of modern quantum algorithm design and serves as the foundation for even more advanced methods like Quantum Signal Processing (QSP), which we'll touch upon briefly.

1. The Linear Combination of Unitaries (LCU) Lemma

The central idea of LCU is to apply an operator $X$ that can be expressed as a linear combination of unitary operators, $X = \sum_{j = 0}^{J - 1} a_{j} U_{j}$ , where $a_{j}$ are coefficients and $U_{j}$ are unitaries. Since $X$ itself is not necessarily unitary, we can't implement it directly as a gate. Instead, we devise a larger quantum circuit that applies $X$ probabilistically, and then use amplitude amplification to make the process efficient.

This is achieved by introducing an ancillary register and two special operations:

UPrep: A unitary that prepares a quantum state encoding the coefficients $a_{j}$ .
USelect: A controlled unitary that applies $U_{j}$ to the main register, conditional on the state $∣ j ⟩$ of the ancilla.

Let's dive into the formal derivation.

Quantum Algorithms with Applications to Simulating Physical ...

The PhD thesis 'Quantum Algorithms with Applications to Simulating Physical ...' by Anirban Chowdhury provides a clear and detailed derivation of the LCU framework. We will use this as our primary reference.

Please read Section 3.7, 'The LCU framework' (pages 48-51). Focus on understanding the definitions of USelect (Eq. 3.41) and UPrep (Eq. 3.42), the circuit in Fig. 3.2, and the derivation leading to Eq. 3.44, which shows how the desired state X|ψ〉 is produced. Finally, read Lemma 6, which is the formal statement of the LCU Lemma.

Let's break down the key steps from the reading:

State Preparation (UPrep): We start with the ancilla in the $∣0 ⟩$ state and apply UPrep to create a superposition weighted by the square roots of the coefficients:
$U_{Prep} ∣0 ⟩_{a} = \frac{1}{∥ a ∥ _{1}} j = 0 \sum J - 1 a_{j} ∣ j ⟩_{a}$
Here, we assume $a_{j} > 0$ and $∥ a ∥_{1} = \sum_{j} a_{j}$ . The subscript $a$ denotes the ancilla register.
Controlled Application (USelect): Next, the USelect operator acts on the combined system of the ancilla and the main state $∣ ψ ⟩_{s}$ .
$U_{Select} ((\frac{1}{∥ a ∥ _{1}} j \sum a_{j} ∣ j ⟩_{a}) \otimes ∣ ψ ⟩_{s}) = \frac{1}{∥ a ∥ _{1}} j \sum a_{j} ∣ j ⟩_{a} \otimes U_{j} ∣ ψ ⟩_{s}$
Uncomputing and Projecting: The circuit then applies $U_{Prep}^{†}$ . Let's see what happens to the component of the state where the ancilla is $∣0 ⟩_{a}$ . The projection onto $⟨ 0 ∣_{a}$ is:
$⟨ 0 ∣_{a} U_{Prep}^{†} (\frac{1}{∥ a ∥ _{1}} j \sum a_{j} ∣ j ⟩_{a} \otimes U_{j} ∣ ψ ⟩_{s})$
Since $⟨ 0 ∣_{a} U_{Prep}^{†} = (U_{Prep} ∣0 ⟩_{a})^{†} = \frac{1}{∥ a ∥ _{1}} \sum_{k} a_{k} ⟨ k ∣_{a}$ , this simplifies to:
$\frac{1}{∥ a ∥ _{1}} k, j \sum a_{k} a_{j} ⟨ k ∣ j ⟩_{a} \otimes U_{j} ∣ ψ ⟩_{s} = \frac{1}{∥ a ∥ _{1}} j \sum a_{j} U_{j} ∣ ψ ⟩_{s} = \frac{1}{∥ a ∥ _{1}} X ∣ ψ ⟩_{s}$
The full state after the circuit in Fig. 3.2 is therefore:
$∣ Ψ_{final} ⟩ = \frac{1}{∥ a ∥ _{1}} ∣0 ⟩_{a} \otimes (X ∣ ψ ⟩_{s}) + ∣ Φ^{⊥} ⟩$
where $∣ Φ^{⊥} ⟩$ is some state orthogonal to the $∣0 ⟩_{a}$ subspace.
Amplitude Amplification: Measuring the ancilla and post-selecting the $∣0 ⟩_{a}$ outcome successfully applies $X$ , but the success probability is $∥ X ∣ ψ ⟩ ∥^{2} /∥ a ∥_{1}^{2}$ , which can be very small. As stated in Lemma 6, we can use amplitude amplification to boost this success probability to be close to 1. The cost of this amplification, in terms of the number of uses of UPrep and USelect, scales as $O (∥ \veca ∥_{1} /∥ X ∣ ψ ⟩ ∥)$ .

This is the LCU Lemma. It provides a generic recipe for applying any operator that can be written as a linear combination of unitaries. The cost is determined by the 1-norm of the coefficients, $∥ a ∥_{1}$ .

2. Application: Simulating Non-Unitary Matrices

The power of the LCU lemma lies in its ability to simulate non-unitary matrices, provided we can find a suitable decomposition for them. Let's explore two key examples.

2.1 Hamiltonian Simulation via Taylor Series

A direct application is in Hamiltonian simulation. The time-evolution operator $U (t) = e^{- i H t}$ is unitary. However, some of the most advanced simulation algorithms work by first approximating $U (t)$ with its Taylor series:

e^{- i H t} \approx k = 0 \sum N \frac{( - i t ) ^{k}}{k !} H^{k}

If the Hamiltonian $H$ is itself a sum of unitaries, $H = \sum_{l} α_{l} h_{l}$ , then each power $H^{k}$ is a more complex linear combination of products of unitaries. The truncated Taylor series is therefore a large linear combination of unitaries, making it a perfect candidate for the LCU method.

tions Using a Linear Combination of Unitaries

The paper 'Simulating Hamiltonian dynamics with a truncated Taylor series' by Berry et al. is a foundational work on this topic. Let's look at how they formulate the problem.

Please read Section 2.1, 'Linear combination of unitaries' (pages 2-3). Focus on how the Hamiltonian in Eq. (1) and the Taylor series in Eq. (4) naturally lead to the LCU form in Eq. (5), UL = ∑ βj Vj. Also, note the definitions of the prepare (P) and select (S) operators in Eqs. (6) and (8), which are exactly the UPrep and USelect we just discussed.

This approach represents a significant departure from the Trotter-Suzuki methods we will discuss later. Instead of approximating the evolution as a product of short-time evolutions, it directly constructs a polynomial approximation to $e^{- i H t}$ and implements it with LCU. This often leads to much better scaling with the desired simulation accuracy.

2.2 Matrix Inversion and Imaginary Time Evolution

A more striking example is the application of genuinely non-unitary matrices. Consider the problem of solving a linear system of equations $A x = b$ , which requires applying $A^{- 1}$ . How can LCU help?

For a positive definite matrix $H$ , its inverse can be expressed via an integral representation:

H^{- 1} = \int_{0}^{\infty} e^{- H t} d t

This expresses the non-unitary $H^{- 1}$ as a "continuous" linear combination of other non-unitary operators: the imaginary time evolution operators $e^{- H t}$ .

Each of these can, in turn, be expressed as an LCU using a Gaussian integral identity known as the Hubbard-Stratonovich transformation:

e^{- H^{2} /2} = \frac{1}{2 π} \int_{- \infty}^{\infty} e^{- y^{2} /2} e^{- i yH} d y

This remarkable identity decomposes the non-unitary operator $e^{- H^{2} /2}$ into a linear combination of unitary operators of the form $e^{- i yH}$ (i.e., standard Hamiltonian evolution).

By discretizing these two integrals, one can construct an LCU representation for $H^{- 1}$ , which can then be implemented on a quantum computer.

Quantum Algorithms with Applications to Simulating Physical ...

Let's return to the thesis by Chowdhury to see these ideas in action. The text demonstrates how to construct LCU representations for both imaginary time evolution and matrix inversion.

Please skim Section 4.3.1, 'Imaginary time evolution as LCU' (pages 75-76), to see the Hubbard-Stratonovich transformation in Eq. (4.8) and its discrete approximation in Eq. (4.11). Then, skim Section 6.3.2, 'Matrix inversion as LCU' (page 127), to see how the integral for 1/H (Eq. 6.20) is combined with the previous technique to yield a full LCU decomposition (Eq. 6.21).

These examples show the versatility of the LCU framework. By finding the right mathematical transformation, we can express a wide range of non-unitary operations as linear combinations of unitaries, making them accessible to quantum computation.

3. The Bigger Picture: From LCU to QSP

LCU is the gateway to a class of even more powerful and unifying algorithmic frameworks, namely Quantum Signal Processing (QSP) and its generalization, Quantum Singular Value Transformation (QSVT).

While LCU allows us to implement a polynomial of a unitary $U$ by expanding it as $\sum a_{j} U^{j}$ , QSP provides a way to implement a polynomial transformation $P (U)$ with a circuit whose depth is only proportional to the degree of the polynomial, which is often far more efficient. It achieves this not by preparing a state with coefficients, but by a carefully constructed sequence of single-qubit rotations.

Quantum Signal Processing

To get a sense of this connection, let's watch the introduction to a seminar on Quantum Signal Processing by Prof. Lin Lin, a leading expert in the field. He frames the problem perfectly.

Please watch from 02:27 to 07:15. The speaker explains why representing non-unitary polynomial functions with unitary matrices is so crucial and introduces QSP and the 'Grand Unification of Quantum Algorithms' (QSVT) as the modern tools for this.

The video highlights that many, if not most, advanced quantum algorithms can be viewed through the lens of applying a non-unitary function $f (A)$ of some matrix $A$ to a vector. LCU, QSP, and QSVT provide a unified and highly efficient toolkit for achieving this.

Conclusion

In this lesson, we have unpacked the Linear Combination of Unitaries (LCU) lemma, a cornerstone of modern quantum algorithm design.

Key Takeaways:

The LCU lemma provides a constructive method for applying an operator $X = \sum_{j} a_{j} U_{j}$ on a quantum computer.
The method relies on block-encoding: embedding $X$ into a larger unitary circuit using UPrep and USelect operations on an ancilla register.
Amplitude amplification is used to convert the probabilistic post-selection process into a near-deterministic algorithm, with a cost scaling with the 1-norm of the coefficients, $∥ a ∥_{1}$ .
LCU is a powerful tool for simulating non-unitary matrices. By finding mathematical decompositions (e.g., Taylor series, integral transforms), we can express operators like $e^{- H t}$ and $H^{- 1}$ as LCUs and implement them.
LCU is a conceptual and practical stepping stone to more advanced techniques like QSP and QSVT, which represent the state-of-the-art in quantum simulation and algorithms.

Preview of the Next Lesson

We've just seen a very sophisticated approach to Hamiltonian simulation based on series expansions. In the next lesson, we will step back to study a more direct and historically fundamental technique: Implement Hamiltonian simulation using a first-order Trotter-Suzuki decomposition. This will give you a fuller picture of the different approaches to simulation, contrasting the simpler, product-formula-based methods with the advanced LCU-based techniques.