Block-Encoding Sparse Hamiltonians

Hello! Welcome to our next lesson on recent advances in quantum computing.

Introduction

In our previous lesson, we explored the Linear Combination of Unitaries (LCU) lemma. We saw that it provides a powerful, abstract framework for implementing an operator $X = \sum_{j} a_{j} U_{j}$ by block-encoding it into a larger unitary matrix. This method relies on the existence of two oracles, UPrep and USelect, but we didn't delve into how one might construct the full block-encoding unitary for a given non-unitary matrix $A$ .

Today, we bridge that gap. We will move from the abstract concept to the concrete engineering of a quantum circuit. Our focus will be on the learning outcome: Construct a block-encoding circuit for a simple sparse Hamiltonian.

This is a crucial skill, as many problems in physics, chemistry, and optimization involve sparse Hamiltonians. We will learn a general recipe for this construction and see how the structure of the matrix dictates the structure of the quantum circuit. Specifically, we will cover:

A general theorem for block-encoding any $s$ -sparse matrix.
The decomposition of the block-encoding circuit into two primary components: an oracle for the matrix's sparsity structure (Oc) and an oracle for its numerical values (OA).
A detailed construction of these oracles for a second-quantized Hamiltonian, a context that should be familiar from your background in physics.

This lesson builds directly on our understanding of block-encoding from LCU and sets the stage for our next topic, Quantum Signal Processing, which uses these block-encoding circuits as a fundamental building block.

1. The General Recipe for Block-Encoding Sparse Matrices

The core idea behind block-encoding a sparse matrix is to create a unitary circuit that can, in superposition, perform two tasks: (1) locate the non-zero elements of the matrix, and (2) embed their values into the amplitudes of an ancilla qubit.

A general and elegant method for achieving this is laid out in the following theorem.

explicit quantum circuits for block encodings of certain ...

Let's begin with the general strategy for block-encoding sparse matrices. The paper 'explicit quantum circuits for block encodings of certain ...' by Lin and Tong provides a clear theorem and circuit diagram for this.

Please read Section 4, 'Efficient quantum circuits for block encodings of s-sparse matrices', focusing on Theorem 4.1 and its proof (pages 6-7). Pay attention to the definitions of the oracles Oc (Eq. 4.2) and OA (Eq. 4.3), and the overall circuit structure in Fig. 5.

Let's summarize the key components from the reading. For an $s$ -sparse matrix $A$ (where we assume $s = 2^{m}$ for simplicity), we can construct a block encoding for $A / s$ using a circuit with $m + 1$ ancilla qubits. The circuit, shown in the paper's Figure 5, relies on two oracles:

Oc (Oracle for Columns/Structure): This unitary encodes the sparsity pattern of the matrix. It takes a column index $j$ and an integer $ℓ \in {0, \dots, s - 1}$ and computes the row index of the $ℓ$ -th non-zero entry in column $j$ .
$O_{c} ∣ ℓ ⟩ ∣ j ⟩ = ∣ ℓ ⟩ ∣ c (j, ℓ)⟩$
The function $c (j, ℓ)$ is a classical function that describes the locations of the non-zero entries.
OA (Oracle for Amplitudes/Values): This unitary encodes the value of the matrix element $A_{c (j, ℓ), j}$ into the state of a single ancilla qubit, typically via a controlled rotation.
$O_{A} ∣0 ⟩ ∣ ℓ ⟩ ∣ j ⟩ = (A_{c (j, ℓ), j} ∣0 ⟩ + 1 - ∣ A_{c (j, ℓ), j} ∣^{2} ∣1 ⟩) ∣ ℓ ⟩ ∣ j ⟩$
Note that for this to be a valid unitary operation, the matrix $A$ must be scaled such that all its elements have a magnitude less than or equal to 1.

The full block-encoding unitary $U_{A}$ is then constructed by sandwiching these oracles between diffusion operators $D_{s}$ (which are just layers of Hadamard gates on the ancilla register used for $ℓ$ ):

U_{A} = (I \otimes D_{s} \otimes I) (I \otimes O_{c}) O_{A} (I \otimes D_{s} \otimes I)

The $D_{s}$ operators create a uniform superposition over all possible non-zero indices $ℓ$ , the oracles act on this superposition, and the final $D_{s}$ interferes the paths to yield the desired matrix element in the final measurement.

2. Constructing the Oracles for a Sparse Hamiltonian

The general recipe is powerful, but its efficiency depends entirely on our ability to construct efficient circuits for Oc and OA. Let's see how this is done for a physically motivated example: a second-quantized pairing Hamiltonian.

Your background in physics and theoretical modeling will be helpful here. We'll be working with creation ( $c^{†}$ ) and annihilation ( $c$ ) operators acting on a Fock space, where basis states are represented by bitstrings indicating the occupation of single-particle states.

An Efficient Quantum Circuit for Block Encoding a Pairing ...

Now, let's apply this recipe to a second-quantized pairing Hamiltonian. The paper 'An Efficient Quantum Circuit for Block Encoding a Pairing ...' provides an excellent, detailed construction. It uses slightly different notation (OC and OH instead of Oc and OA), but the underlying principle is identical.

Please read Section 4, 'Block encoding circuit' (pages 6-13). Pay close attention to: Section 4.1: How the action of creation/annihilation operators defines the sparsity structure c(j, l) as a conditional bit-swap, and how this is implemented in the OC circuit (Fig. 5). Section 4.2: How the OH circuit uses controlled rotations to encode the matrix element values (Fig. 8 & 9). Section 4.3: How these components are assembled into the complete block-encoding circuit (Fig. 10) and the verification in Eq. (37).

Let's distill the core construction logic from the paper.

The Structure Oracle (`OC`)

The Hamiltonian is a sum of terms like $H = \sum_{p, q} h_{pq} c_{p}^{†} c_{q}$ . In the Fock basis (represented by bitstrings), the operator $c_{p}^{†} c_{q}$ has a very specific action:

It gives a non-zero result only if it acts on a basis state $∣ j ⟩$ where single-particle state $q$ is occupied ( $∣ j ⟩_{q} = 1$ ) and state $p$ is unoccupied ( $∣ j ⟩_{p} = 0$ ).
When this condition is met, the resulting state, $c_{p}^{†} c_{q} ∣ j ⟩$ , is the state where the occupations have been swapped: state $q$ becomes unoccupied and state $p$ becomes occupied.

This gives us a direct prescription for the function $c (j, ℓ)$ , where $ℓ$ now indexes the pair $(p, q)$ . The function $c (j, ℓ)$ is simply a conditional SWAP of the bits at positions $p$ and $q$ in the bitstring representation of state $∣ j ⟩$ .

As shown in Figure 6 of the paper, the OC circuit implements this logic using multi-controlled SWAP gates. The controls check two things simultaneously:

The ancilla qubits are in the state corresponding to the term $(p, q)$ .
The main register qubits for the state $∣ j ⟩$ satisfy the occupation condition ( $∣ j ⟩_{q} = 1$ and $∣ j ⟩_{p} = 0$ ).

The Value Oracle (`OH`)

The OH oracle's job is to encode the coefficient $h_{pq}$ associated with the term $c_{p}^{†} c_{q}$ . This is done using a controlled rotation.

The circuit applies a $R_{y} (θ_{pq})$ rotation to a fresh ancilla qubit.
The rotation is controlled by the ancilla qubits that select the term $(p, q)$ .
The angle $θ_{pq}$ is chosen such that the rotation produces the desired amplitude, e.g., $θ_{pq} = 2 arccos (h_{pq})$ if the matrix is appropriately scaled.

Figure 8 in the paper shows exactly this: a multi-controlled $R_{y}$ gate where the controls are on the "selection qubits" that encode $ℓ = (p, q)$ .

The Complete Circuit

As shown in the figure above (Fig. 10 from the paper), the full circuit assembles these pieces in the order prescribed by the general theorem: Ds, then OH (which is OA), then OC, and finally Ds again. The paper's verification in Eq. (37) confirms that the top-left block of this unitary is indeed $H / s$ , just as we expect.

A Note on Hermitian Block Encodings

The construction we just studied produces a valid block encoding, but the resulting unitary matrix $U_{A}$ is not, in general, Hermitian, even if the original matrix $A$ was. For some applications, like quantum walks or certain versions of QSP, it is advantageous to have a Hermitian block encoding.

This requires a slightly different, more symmetric circuit structure, as detailed in Section 8 of the paper "explicit quantum circuits for block encodings of certain..." (4e0ad). This alternative construction involves applying Oc, then a SWAP gate, then O $_{c}^{†}$ , which guarantees the final unitary is Hermitian. This is an important variation to be aware of, demonstrating that there can be multiple ways to block-encode a matrix, each with different properties.

Conclusion

In this lesson, we have moved from the abstract definition of block-encoding to a concrete, constructive procedure for sparse matrices, particularly for physically motivated Hamiltonians.

Key Takeaways:

Any $s$ -sparse matrix $A$ can be block-encoded using a circuit built from two oracles: Oc for the sparsity structure and OA for the element values.
For second-quantized Hamiltonians, the Oc oracle can be implemented with controlled-SWAP gates that mimic the action of creation/annihilation operators on the Fock basis.
The OA oracle is typically implemented with multi-controlled rotation gates that encode the Hamiltonian's coefficients into quantum amplitudes.
The complexity and feasibility of block-encoding a matrix are determined by the complexity of constructing these oracles, which is directly related to the matrix's structure.

Preview of the Next Lesson

We now have a powerful tool in our arsenal: a method to construct a unitary circuit $U_{A}$ that "contains" a Hamiltonian $A$ . But how do we use $U_{A}$ to perform a task like simulation, i.e., to implement $e^{- i A t}$ ?

Our next lesson, Analyze the principles of Quantum Signal Processing (QSP) for applying polynomial transformations to a block-encoded matrix, will answer this question. We will see how a clever sequence of single-qubit rotations applied to an ancilla qubit can transform $U_{A}$ into a block encoding of any polynomial of $A$ , providing a highly efficient and precise path to Hamiltonian simulation and other advanced algorithms.