**Physics definition**: descriptions of the interactions governing a quantum system, and the energy assigned to the state of a system.

**Computer science definition**: quantum analogue of a constraint satisfaction problem (CSP).

**Mathematical definition**: A Hermitian matrix.

The Hamiltonian of a quantum system describes how it will evolve over time, via the **Schrodinger Equation**.

where $\ket{\psi(t)}$ denotes state of $n$ qubits at time $t \in \R$.

**differential equation**. The way the state changes in the next time step depends on the current state.

We can solve the Schrodinger equation to get:

$$ \ket{\psi(t)} = e^{-i H t} \ket{\psi(0)}. $$The matrix $e^{-i Ht}$ is the function $f(x) = e^{-ixt}$ applied to $H$:

$$ e^{-iHt} = \sum_j e^{-i E_j t} \ketbra{v_j}{v_j} $$where $E_j$ are energies and $\ket{v_j}$ are the eigenstates of $H$.

**Claim**: $e^{-iHt}$ is a **unitary matrix**.

Schrodinger Equation thus describes the unitary evolution of a quantum system in isolation.

**Proof**: Let $U = e^{-iHt}$. Then

$ UU^\dagger = \Big( \sum_j e^{-i E_j t} \ketbra{v_j}{v_j} \Big) \Big( \sum_j e^{+i E_j t} \ketbra{v_j}{v_j} \Big)$

$ \qquad = \sum_j e^{-i E_j t} e^{+i E_j t} \ketbra{v_j}{v_j} = \sum_j \ketbra{v_j}{v_j} = I$

**Input**:

- A description of a $k$-local Hamiltonian $H = H_1 + H_2 + \cdots + H_m$ on $n$ qubits.
- Time $t \in R$.
- Precision $\epsilon$.
- Initial quantum state $\ket{\psi(0)}$ (in quantum form).

**Goal**: Output a quantum state $\ket{\theta}$ such that

Even though the overall Hamiltonian $H$ is a large matrix ($2^n \times 2^n$), it can be specified very succinctly.

Each $k$-local term $H_j$ is equal to a $k$-qubit matrix $h_j$ tensored with the identity, so just need to describe $h_j$ ($2^k \times 2^k$ matrix) and the qubits it acts on.

Suppose $H$ consists of a single term $H_1 = h \otimes I_{n-k}$ that acts nontrivially on the first $k$ qubits.

Then $e^{-i H t} = e^{-i h t} \otimes I_{n-k}$.

**some** $k$-qubit gate. This can be decomposed into at most $2^{O(k)}$ single- and two-qubit gates, which for $k = O(1)$ is constant.

Suppose $H = H_1 + H_2$.

**Temptation**: $ e^{-iHt} = e^{-i(H_1 +H_2) t} = e^{-iH_1 t} \, e^{-iH_2t}$.

This is true for **numbers**, but not for matrices!

$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, $Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$. Note that $XZ \neq ZX$.

$$
e^{X+Z} \neq e^{X} \, e^{Z}
$$

**Exercise**: verify this!

If $A,B$ are square matrices, then

$$ e^{A + B} = e^{A} e^{B} $$**if and only if** $AB = BA$.

For all matrices $A,B$:

$$ e^{A + B} = \lim_{r \to \infty} \Big( e^{A/r} e^{B/r} \Big)^r $$In the context of Hamiltonians:

$$ e^{-i(H_1 + H_2)t} = \lim_{r \to \infty} \Big( e^{-iH_1 \frac{t}{r}} \, e^{-iH_2 \frac{t}{r}} \Big)^r $$Time-evolving a sum of terms is same as a sequence of infinitesimal time evolutions of the terms.

More generally,

$$ \Big \| e^{A_1 + \cdots + A_m} - \Big( e^{A_1/r} \cdots e^{A_m/r} \Big)^r \Big \| \leq \epsilon $$provided that

$$ r \gg \frac{m^2 L^2}{\epsilon} $$where $L = \max_i \| A_i \|$ the maximum of the spectral norms of each $A_i$ (i.e. the largest singular value of $A_i$).

**Input**: $k$-local Hamiltonian $H = H_1 + \cdots + H_m$, time $t \in R$, precision $\epsilon$, initial state $\ket{\psi(0)}$.

- Choose $r \gg m^2 t^2 \Big( \max_i \| H_i \|^2 \Big)/\epsilon$
- Apply $e^{-i H_1 t/r}, e^{-i H_2 t/r}, \ldots, e^{-i H_m t/r}$ in sequence $r$ times to the current state.

Number of qubits needed: $n$.

Number of gates: $2^{O(k)} \cdot m \cdot r = \mathrm{poly} \Big (2^k, m, t, \max \| H_i \|, \frac{1}{\epsilon} \Big)$.

The development of Hamiltonian simulation algorithms is an active area of quantum algorithms research.

- More efficient algorithms?
- Faster simulation algorithms for special types of Hamiltonians?
- Nonlocal interactions?

**Input**: Local Hamiltonian $H = \sum_i H_i$ and a state $\ket{\psi}$.

**Goal**: An estimate of the energy $\bra{\psi} H \ket{\psi}$.

**Solution**: Hamiltonian simulation + phase estimation.

Assume without loss of generality that $\| H \| \leq 1$. This means all energies $\{ E_j\}$ have magnitude at most $1$.

The unitary $U = e^{-i H}$ has spectral decomposition

$$ U = \sum_j e^{-i E_j} \ketbra{v_j}{v_j}. $$Phase estimation requires running (controlled versions of) $U, U^2, \ldots,U^{2^k}$.

Note that $U^{t} = e^{-i H t}$, which we can implement using Hamiltonian simulation algorithms!

Given a general state $\ket{\psi} = \sum_j \alpha_j \ket{v_j}$, running phase estimation yields a state close to

$$ \sum_j \alpha_j \ket{v_j} \otimes \ket{\tilde{E_j}}. $$Measuring the second register yields energy estimate $\tilde{E}_j$ with probability $|\alpha_j|^2$.

The expected value of the output is

$$ \sum_j |\alpha_j|^2 \tilde{E}_j \approx \sum_j |\alpha_j|^2 E_j = \bra{\psi} H \ket{\psi}. $$Repeating this procedure several times and taking empirical average yield a good estimate of $\bra{\psi} H \ket{\psi}$.

In his explorations of quantum computing, Feynman was motivated by the apparent difficulty of classically simulating quantum systems.

Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy.

** the** primary application of quantum computers, if and when we build them.

Scientific simulation occupies a significant fraction of the world's supercomputing resources today. They are used for:

- Weather simulations
- Simulating nuclear weapons
- Simulating complex fluid dynamics
- Materials design
- Protein folding

and much, much more!

We often hear about the glorious applications of quantum simulations to:

- Quantum chemistry
- Pharmaceuticals
- Materials design
- Catalyst design
- Understanding superconductivity

and much, much more!

Currently, there are not many proposals for ** specific** problems that

- Known classical methods do not give good answers
- Quantum computers will
give good answers*provably* - Have practical or scientific importance

There is a large emphasis on using quantum computers to solve quantum chemistry problems.

An oft-repeated example is the goal of better understanding **nitrogen fixation** in the **Haber process**, which is used to produce fertilizer (and explosives). This process consumes about 1% of world's yearly energy output.

It would be great to use quantum computers to optimize this process even by a little bit!

**ground state problems**, rather than **dynamics problems** (i.e. time-evolving a state).

**NP-hard** in general -- and we don't expect a generic quantum algorithm for these!

**case-by-case** basis via experimentation.

**Quantum dynamics problems** are more surefire candidates for quantum advantage. Examples of these include:

- Simulating quantum systems where particles are strongly correlated and highly entangled (superconductivity)
- Exploring chaotic quantum systems
- Exploring equilibration properties of quantum systems
- Simulating particle collisions in colliders

These problems are interesting and important from a fundamental science angle, rather than from engineering/pratical angle.

**Main takeaway**: The prospects of using quantum computers to solve important quantum chemistry/physics problems are tantalizing, but we can't point to specific, slam-dunk practical applications of quantum computers at the moment (except for breaking RSA, maybe).

However, we didn't forsee all the applications of digital computers back in the 40's and 50's.

Once we have large scale quantum computers to play with (and maybe before then), we are certainly going to find exciting uses of them that we can't even imagine at the moment.

Mixed states and noise.

In [ ]:

```
```