Q3L11d.txt

#
# File:   content-mit-8371x-subtitles/Q3L11d.txt
#
# Captions for 8.421x module
#
# This file has 52 caption lines.
#
# Do not add or delete any lines.  If there is text missing at the end, please add it to the last line.
#
#----------------------------------------

An important problem in quantum simulation
is eigenvalue sampling of energy spectra.
Specifically, for example, you are given a Hamiltonian
and asked to produce samples of its energy eigenvalues.
A specific common instance of this problem
is to estimate the energy gap between the ground state
and first excited state of a Hamiltonian.
Here we focus on a variant of this problem
where you are giving a controlled u to the j, where
j is a control, and in addition a state
v which is a superposition of eigenstates of u.
phi sub k here denotes an eigenstate of eigenvalue phi sub
k.
The goal of the problem is to produce
sample values of phi sub k.
Here is how the sampling algorithm works.
One starts with 0 v and applies a Hadamard
to the first register of qubits producing
an equal superposition and then v. A controlled u to the j
is then applied with a first register as the control,
with the u acting on v. This results in a superposition.
The u to the j produces phi sub k to the j-th power
acting on ket phi k.
These eigenvalues are roots of unity and thus
it's helpful to write the phase as lambda sub k.
Let us gather the terms that depend on j.
We find that this is a sum over e
to the 2 pi i lambda sub k j times ket j.
Recall, this is the form of the output
of the quantum Fourier transform,
and thus, in our next step when we apply the inverse quantum
Fourier transform we obtain a state which
is the sum over k with c sub k, lambda sub k, phi sub k.
Lambda sub k here is the phase of the eigenvalue.
And thus when we measure we obtain this value from which
we may compute phi sub k and the k-th eigenvalue
is obtained with probability c sub k squared.
In the initial state, if the vector v
is a superposition of the ground and excited states
with some epsilon fraction of the excited state,
then we may estimate epsilon using this algorithm.
The catch is that controlled u to the j is a lot to ask for,
and is not often available naturally.
If u is the quantum simulated evolution under H sys
using some Trotterization scheme, then controlled u to the j
will in general require exponential resources
to accomplish.
Such exponential time duration simulation
may be possible for some Hamiltonians.
Finding out when and for what is one
of the major goals of the study of quantum simulation.