Last time: Hamiltonians¶
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.
Time evolution of a quantum system¶
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$.
This is a differential equation. The way the state changes in the next time step depends on the current state.
Time evolution of a quantum system¶
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$
Hamiltonian simulation problem¶
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
$$ \Big \| \, \ket{\theta} - e^{-i H t} \ket{\psi(0)} \Big \| \leq \epsilon. $$Hamiltonian simulation problem¶
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.
Warmup¶
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}$.
The unitary $e^{-i h t}$ is like 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.
More interesting case¶
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!
Counterexample¶
$X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, $Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$. Note that $XZ \neq ZX$.
Exercise: verify this!
If $A,B$ are square matrices, then
$$ e^{A + B} = e^{A} e^{B} $$if and only if $AB = BA$.
Lie-Trotter-Suzuki formula¶
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.
Lie-Trotter-Suzuki formula¶
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$).
Hamiltonian simulation algorithm¶
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.
Each $e^{-i H_j t/r}$ is a $k$-local unitary that can be decomposed into $2^{O(k)}$ elementary gates.
Hamiltonian simulation algorithm¶
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?
The Lie-Suzuki-Trotter-based algorithms are conceptually simple, but the time complexity is not optimal. There are more sophisticated algorithms that achieve better performance theoretically, but are much more complicated.
Measuring the energy of a state¶
Input: Local Hamiltonian $H = \sum_i H_i$ and a state $\ket{\psi}$.
Goal: An estimate of the energy $\bra{\psi} H \ket{\psi}$.
This is an important subroutine for applications in quantum physics and chemistry. For example, you might want to find a state that minimizes the energy.
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}. $$Using phase estimation with unitary $U$ and eigenstate $\ket{v_j}$ with $k$ ancilla qubits, we get estimate $|\tilde{E}_j - E_j | \leq 2^{-k}$.
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!
In order for this to be efficient, we need $2^k \leq \mathrm{poly}(n)$, or $k = O(\log n)$ bits of precision.
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}$.
Perspectives on quantum simulation¶
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.
Today, quantum simulation is considered the primary application of quantum computers, if and when we build them.
Why simulate physics?¶
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!
Quantum simulations: the optimistic take¶
We often hear about the glorious applications of quantum simulations to:
- Quantum chemistry
- Pharmaceuticals
- Materials design
- Catalyst design
- Understanding superconductivity
and much, much more!
Quantum simulations: what we know¶
Currently, there are not many proposals for specific problems that
- Known classical methods do not give good answers
- Quantum computers will provably give good answers
- Have practical or scientific importance
Quantum simulations: what we know¶
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!
However, current proposals for using quantum computers to solve quantum chemistry problems (such as exploring the Haber process) involve solving ground state problems, rather than dynamics problems (i.e. time-evolving a state).
However ground state problems are NP-hard in general -- and we don't expect a generic quantum algorithm for these!
Quantum computers could still be useful for specific chemistry problems like nitrogen fixation, but we would only find out on a 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.
Next time¶
Mixed states and noise.