- Pset3 out, due November 2
- Henry, please record the lecture!

In quantum physics, **Hamiltonians** describe the laws of nature of a quantum system. In principle, they encode all information about how a collection of particles (in isolation) interact with each other over time.

**killer app** of quantum computing is **Hamiltonian simulation**, which is to evolve a quantum state over a time according to a Hamiltonian.

- Spectral theorem
- Functions of Hermitian matrices

Let $A \in \C^{d \times d}$ be a Hermitian matrix. It can always be **diagonalized**.

There exists an **orthonormal basis** $\{ \ket{v_1},\ldots,\ket{v_d} \}$ for $\C^d$ and **real eigenvalues** $\lambda_1,\ldots,\lambda_d$ such that

This is called a **spectral decomposition** of $A$.

In other words, $A$ looks like

$$ A = V \begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_d \end{pmatrix} V^\dagger $$where $V$ is a **unitary matrix** with $\ket{v_j}$ as its columns.

The vector $\ket{v_k}$ has eigenvalue $\lambda_k$ with respect to $A$.

**Proof**:
$ A \ket{v_k} = \Big( \sum_j \lambda_j \ketbra{v_j}{v_j} \Big) \ket{v_j} $

$ \quad = \sum_j \lambda_j \ket{v_j} \, \langle v_j \mid v_k \rangle $

Let $f: \R \to \C$ denote a function. Then for all Hermitian matrices $A$ with spectral decomposition $\sum_j \lambda_j \ketbra{v_j}{v_j}$, we define

$$ f(A) = \sum_j f(\lambda_j) \, \ketbra{v_j}{v_j}. $$In other words, $f$ just changes the **eigenvalues** of $A$, and leaves the eigenvectors unchanged.

**Example**: let $f(x) = x^2$. Then

$ f(A) = \sum_j \lambda_j^2 \ketbra{v_j}{v_j}. $

This matches

$ A^2 = \Big( \sum_j \lambda_j \ketbra{v_j}{v_j} \Big) \Big( \sum_k \lambda_k \ketbra{v_k}{v_k} \Big) = \sum_{j,k} \lambda_j \lambda_k \ket{v_j} \, \langle v_j \mid v_k \rangle \, \bra{v_k}$

$ \quad = \sum_j \lambda_j^2 \ketbra{v_j}{v_j}$

**Example**: let $f(x) = \sin(x)$. Then

$ f(A) = \sum_j \sin(\lambda_j) \, \ketbra{v_j}{v_j}. $

Before we dive into the physics, let's first see how computer scientists think about Hamiltonians.

**CS view of Hamiltonians**: Hamiltonians are **quantum analogues** of constraint satisfaction problems (CSPs).

An instance of a **$k$-local CSP** consists of:

**variables**$x_1,\ldots,x_n$ that can take boolean values**constraints**$C_1,\ldots,C_m$ where each $C_j$ indicates the allowed values for a subset $S_j$ of variables.

**Example**: **3SAT** is a $3$-local CSP where each of the constraints $C_j$ are of the form

The important questions: given a CSP,

- Is it
**satisfiable**? - What is the maximum number of constraints that can be simultaneously satisfied?

These questions generally correspond to **NP-complete problems**.

Given a graph $G = (V,E)$, find a partition of vertices that maximizes number of cut edges.

Equivalently, a $2$-local CSP:

- For every vertex $v \in V$, a variable $x_v$.
- For every edge $e = (u,v) \in E$, a constraint $x_u \neq x_v$.

NP-hard to find the optimal cut.

**approximately optimal cut** in polynomial time. The Goemans-Williamson algorithm can find a cut that achieves $87.8\%$ of the maximum possible.

**Open question**: is there a polynomial-time algorithm that achieves a better approximation of Max-Cut?

Mathematically, a **$n$-qubit Hamiltonian** $H$ is a **Hermitian** $n$-qubit matrix. It has dimension $2^n \times 2^n$.

By the spectral theorem, we can diagonalize $H = \sum_j E_j \, \ketbra{v_j}{v_j}.$

**energy levels** of $H$. The vector $\ket{v_j}$ is an **energy eigenstate** with energy $E_j$.

The physical interpretation of a Hamiltonian $H$: it assigns an **average energy** to every $n$-qubit state $\ket{\psi}$. Energy of $\ket{\psi}$ with respect to $H$: $\bra{\psi} H \ket{\psi}$

Since energy eigenstates form a basis, we can write $\ket{\psi} = \sum_j \alpha_j \ket{v_j}$.

Thus energy of $\ket{\psi} = \bra{\psi} \Big( \sum_j E_j \ketbra{v_j}{v_j} \Big) \ket{\psi}$

$ \quad = \sum_j E_j \, |\langle \psi \mid v_j \rangle |^2 = \sum_j E_j |\alpha_j|^2$.

The states $\ket{\psi}$ with **minimum energy** with respect to $H$ are called **ground states**. The minimum energy is called **ground energy**.

$E_{ground} = \min_{\ket{\psi}} \bra{\psi} H \ket{\psi}$.

**Exercise**: The ground energy of $H$ is equal to the **minimum eigenvalue** of $H$, and all ground states are eigenvectors of $H$.

Physics focuses on **local Hamiltonians**, which means

where each $H_j$ is a **local Hamiltonian term**, acting nontrivially on a small set of qubits.

**local gates** acting on one or two qubits at a time, the interesting Hamiltonians in physics are built out of local terms.

**Example**: a line of interacting particles.

Each vertex corresponds to a qubit. Qubits only interact with neighboring qubits.

For every pair of neighbors $(j,j+1)$, there is a Hamiltonian term

$$ H_{j,j+1} = I_{j-1} \otimes h_{j,j+1} \otimes I_{n-{j-1}} $$where $h_{j,j+1}$ is a $4 \times 4$ Hermitian matrix.

**Example**: a line of interacting particles.

The overall Hamiltonian is

$$ H = \sum_{j} H_{j,j+1} $$Note that $H$ is a **gigantic matrix** ($2^n \times 2^n$), but it is built out of a small number of local matrices $h_{j,j+1}$. Just like how an $n$-qubit quantum unitary can be built out of a small number of local unitary gates.

Local Hamiltonians are prevalent in physics because the laws of nature are inherently local: particles interact with nearby ones.

Depending on what kind of physical phenomena is being investigated, physicists will write down different local Hamiltonians.

For example, electric field, magnetic field, nuclear forces, etc...

An important model of magnetism in physics.

Each particle is a magnet that points up ($\ket{0}$) or points down ($\ket{1}$). Neighboring magnets want to **anti-align**.

There is also a **global magnetic field** that encourages all magnets to point in a specific direction.

The **1D Ising Model** is

where $\mu$ = magnetic field strength parameter.

**Note**: $Z_i \otimes Z_{i+1}$ and $Z_i$ are implicitly tensored with identity operators on all the other qubits. Each term is a $2^n \times 2^n$ matrix!

Why does $\mu Z_i$ capture the "global magnetic field" on the $i$'th qubit?

Thus $\mu Z_i$ has energy $\mu$ for any state where $i$'th qubit is in state $\ket{0}$, and $-\mu$ where $i$'th qubit is in state $\ket{1}$.

If $\mu > 0$, then $i$'th qubit "prefers" to be in state $\ket{1}$ (because that's lower energy); otherwise it prefers $\ket{0}$.

Its spectral decomposition:

$Z_i \otimes Z_j = \Big (\ketbra{0}{0}_i - \ketbra{1}{1}_i \Big ) \otimes \Big (\ketbra{0}{0}_{i+1} - \ketbra{1}{1}_{i+1} \Big) $

$ \qquad = \ketbra{00}{00}_{i,i+1} + \ketbra{11}{11}_{i,i+1} - \ketbra{01}{01}_{i,i+1} - \ketbra{10}{10}_{i,i+1}$

The lower energy configurations are where qubits $i$ and $i+1$ point in opposite directions!

The energy of a state $\ket{\psi}$ in the Ising model is

$$ \bra{\psi} H \ket{\psi} = \sum_{i=1}^{n-1} \bra{\psi} Z_i \otimes Z_{i+1} \ket{\psi} + \mu \sum_{i=1}^n \bra{\psi} Z_i \ket{\psi} $$The "anti-alignment" and "global magnetic field" terms **compete** with each other!

**Exercise**: what are the minimum energy configurations, depending on $\mu$?

**classical Hamiltonian**, because it is diagonal in the standard basis. In particular, ground states are all classical basis states.

An example of a **quantum Hamiltonian** is the **Transverse Field Ising Model**:

where $X = \begin{pmatrix} 0 & 1 \\ 0 & 1 \end{pmatrix}$.

The ground states of this Hamiltonian are generally **entangled and non-classical**.

The important questions: given a (local) Hamiltonian $H$,

- What is its ground energy?
- What are its ground states?
- How does a quantum system, governed by $H$, evolve over time?

Ground states are interesting because they represent quantum systems at **low temperatures** (e.g. near absolute zero). Ground states of quantum Hamiltonians tend to exhibit bizarre quantum effects.

Computing ground states and ground energies of Hamiltonians is not easy!

In fact, it is generally an **NP-hard** problem.

Finding ground states of local Hamiltonians is analogous to finding optimal solutions of CSPs.

Time evolution under a Hamiltonian, and simulating it.

In [ ]:

```
```