cs191.html

<div><div class='wrapper'>
<p><a name='1'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Introduction -- January 17, 2012</h2>
<h2>Course Information</h2>
<ul>
<li>Announcements on website</li>
<li>Try Piazza for questions.</li>
<li>GSIs:</li>
<li>Dylan Gorman<ul>
<li>dgorman@berkeley.edu</li>
</ul>
</li>
<li>Seung Woo Shin<ul>
<li>lagnared@gmail.com</li>
</ul>
</li>
<li>Lecture notes on website. No textbook.</li>
<li>Prerequisites: Math 54, Physics 7A/B, 7C or CS 70.</li>
<li>Work and Grading:</li>
<li>Weekly homework<ul>
<li>Out Tue, due following Mon @ 5 in dropbox (second-floor Soda).</li>
</ul>
</li>
<li>2 Midterms: 14 Feb, 22 Mar.</li>
<li>Final Project</li>
<li>In-class quizzes</li>
<li>Academic integrity policy</li>
</ul>
<h2>Today</h2>
<ul>
<li>What is quantum computation?</li>
<li>What is this course?</li>
<li>Double-slit experiment</li>
</ul>
<h2>What is Quantum Computation?</h2>
<ul>
<li>
<p>Computers based on quantum mechanics can solve certain problems
  exponentially faster than classical computers, e.g. factoring
  (Shor's algorithm).</p>
</li>
<li>
<p>How to design quantum algorithms?</p>
</li>
<li>Requires different methodology than for classical algorithms</li>
<li>Are there limits to what quantum computers can do? (Probably. Is not
  known to automatically solve NP-complete problems. Also, halting
  problem.)</li>
<li>How to implement quantum computers in the laboratory (AQC, among
  other forms).</li>
<li>Can you design them so they're scalable?</li>
</ul>
<p>Quantum computation starts with this realization that if we were to
base our computers on QM rather than classical physics, then they can
be exponentially more powerful.</p>
<p>This was really a big deal because it was believed that it didn't
really matter how you implemented computers; all that you could do was
make each step faster.</p>
<p>The fact that there's something like quantum computers that can be
exponentially faster, this was really a big surprise. And really on
fundamental problems, like factoring.</p>
<p>What this course will focus on is several questions on quantum computers.</p>
<p>Where we are for quantum computers is sort of where computers were
60-70 years ago.</p>
<ul>
<li>Size -- room full of equipment</li>
<li>Reliability -- not very much so</li>
<li>Limited applications</li>
</ul>
<h2>Ion traps.</h2>
<p>Can trap a small handful of ions, small number of qubits. No
fundamental obstacle scaling to ~40 qubits over next two years.</p>
<h2>Entanglement</h2>
<p>Basic resource in quantum mechanics. Unique aspect of QM, and one
fundamental to quantum computing</p>
<h2>Quantum Teleportation</h2>
<p>Entanglement.</p>
<h2>Quantum Cryptography</h2>
<p>Ways to use QM to communicate securely (still safe even with Shor's).</p>
<h2>This course</h2>
<ul>
<li>Introduction to QM in the language of qubits and quantum gates.</li>
<li>Emphasis on paradoxes, entanglement.</li>
<li>Quantum algorithms.</li>
<li>Quantum cryptography.</li>
<li>Implementing qubits in the laboratory -- spin...</li>
</ul>
<p>There are certain difficulties you can sweep away by focusing on it in
this language. It also highlights certain aspects of QM. Interesting
to focus on these aspects because they lend an alternative
interpretation of QM.</p>
<h2>Aside:</h2>
<p>There will not be programming projects. There will be a couple of
guest lectures. (not clear it will happen) would try to set things up
so we could go and play with equipment in lab. This obviously depends
on whether it scales and is set up well enough. Might be in place by
the end of the semester.</p>
<p>One thing that has to be done is arrange discussion sections. (under
discussion. Looks like a tentative Wed 11-12 and Fri 1-2.)</p>
<p>INTERIM.</p>
<h2>Young's double-slit experiment.</h2>
<p>(particle-wave duality at quantum level. Physics completely
different. So different that it defies reason.)</p>
<p>There are two aspects of dealing with QM: understanding what those
rules are, and believing that nature works that way.</p>
<p>Hopefully you'll suspend your disbelief and just go with understanding
what the rules are.</p>
<p>(blah, more particle-wave duality)</p>
<p>(this basically boils down to interference.)</p>
<p>(tracking which slit each particle goes through leads to a collapse of
 the wavefunction, and we observe particles behaving like particles,
 not waves)</p>
<p>(talk about superposition of states; introduction of the wavefunction.
 Explained entirely by Schrödinger's cat.)</p>
<p>The thing that's most troubling about this from actual experience as
well as physics is that there has to be a mechanism. How did nature do
this? We are going to have a completely precise description. But it's
not going to be a mechanism unlike anything else.</p>
<p>Part of understanding QM is coming to terms psychologically with this
superposition of states, the existence in more than one state
simultaneously.</p>
<p><a name='2'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Qubits, Superposition, &amp; Measurement -- January 19, 2012</h2>
<h2>Quantization:</h2>
<ul>
<li>Atomic orbitals: Electrons within an atom exist in quantized energy
   levels. Qualitatively -- resonating standing waves. (We have Bohr to
   thank for this)</li>
<li>The important thing is that there is this quantization, and you can
     choose to think of the ground/excited state of an electron as encoding
     in binary. Or you can have a k-level system, where you have energy
     levels 0 through k-1. These are the things we'll be thinking about
     notationally.</li>
<li>There are other systems we can think of as a two-level system,
     e.g. photons (in terms of polarization, e.g.)<ul>
<li>spin (very roughly magnetic moment associated with the charge)</li>
</ul>
</li>
<li>These are very rough descriptions. For our purpose, you can think about
   k-level systems, where you have k discrete levels.</li>
</ul>
<h2>Superposition</h2>
<p>The first axiom of quantum mechanics is the superposition principle. It
says that if a system can exist in one of two states, then it can also
exist in a linear superposition of said states. Likewise, if it can exist
in k states, it can also exist in a superposition of all k states (trivial
to prove)</p>
<p>In other words, <mathjax>$\alpha_1\ket{0} + \alpha_1\ket{1} + ... +
\alpha_{k-1}\ket{k-1}$</mathjax></p>
<p>Our <mathjax>$\alpha _i$</mathjax> are actually probability amplitudes. These don't sum to
one; rather the magnitudes of their intensities sum to one.</p>
<p>(some talk about normalization in order to satisfy said property)</p>
<p>What does this superposition principle correspond to? We talked about the
double-slit experiment. Electron/photon going through one of two slits,
probability of which slit corresponds to these.</p>
<h2>Measurement</h2>
<p>The second axiom of quantum mechanics is the measurement axiom. The
superposition is the private world of this system. As long as you're not
looking at it, it's going to be in this linear superposition. But as soon
as you make a measurement, the outcome of the measurement is one of these
levels <mathjax>$\ket{j}$</mathjax> with probability <mathjax>$\abs{\alpha _j}^2$</mathjax> (i.e. you collapse
the wave function).</p>
<p>So if you go back to our last example, there we have a qubit (a quantum
bit) -- a two-level system is called a quantum bit because it's a quantum
analogue of a bit. So we had an example where we had a superposition of two
states. (demonstration of the probabilities)</p>
<p>[ talk about how attempting to detect which of the slits the particle went
  through actually constitutes a measurement, which changes the state of
  the system ]</p>
<p>standard basis measurement:
     checking exactly which state the system is in.</p>
<p>Another way of writing the state of a quantum system (as opposed to bra-ket
notation) is just saying that it's k complex numbers and presenting them as
a vector. Should be immediately intuitive. We still have the same condition
that the summation of <mathjax>$\alpha _i^2 = 1$</mathjax>. Our vector, therefore, must sit on
the unit k-sphere in k-space.</p>
<p>Ket notation: invented by Dirac. The reason we are going to be so enamored
by the ket notation is that it simultaneously expreses 1) the quantum state
is a vector in a vector space and 2) this quantum state encodes
information. The fact that we are labeling our states as <mathjax>$\ket{0}$</mathjax> and
<mathjax>$\ket{1}$</mathjax> is indicative in itself that we are encoding information.</p>
<p>Two ways of rephrasing the probability of landing in a particular state,
therefore is 1) the length of the projection onto said basis vector and 2)
<mathjax>$cos^2θ_j$</mathjax>.</p>
<p>Generalization of the notion of measurement: in general, when you do a
measurement, you don't need to pick the standard basis; you can pick any
orthonormal basis.</p>
<p>There is another useful basis called the sign basis: <mathjax>$\ket{+}$</mathjax> and
<mathjax>$\ket{-}$</mathjax>. If placed on the unit circle, we have <mathjax>$\ket{+}$</mathjax> located at
<mathjax>$\theta=\frac{\pi}{4}$</mathjax> and <mathjax>$\ket{-}$</mathjax> located at <mathjax>$\theta=-\frac{\pi}{4}$</mathjax>.</p>
<p>[ change of basis can be done using matrices or using substitution. ]</p>
<h2>Significance of sign basis</h2>
<p>The standard basis is going to correspond to a certain quantity. The sign
basis will correspond to a different quantity. By analogy, let's assume
that we're measuring the position or momentum of the system depending on
which basis we're using (might as well be -- Heisenberg's uncertainty
principle and all).</p>
<p>explanation of Heisenberg's uncertainty principle, except without actually
  attributing a name to it. basically, with two related quantities, the
  more accurately you know one, the less accurately you can know the other.</p>
<p>maximal uncertainty occurs with conjugate basis. measure of uncertainty:
  spread -- <mathjax>$\abs{\alpha_0} + \abs{\alpha_1}$</mathjax>. Corresponds to maximum
  uncertainty. Uncertainty ranges from 1 to <mathjax>$\sqrt{2}$</mathjax>.</p>
<p>Specifically, Heisenberg's uncertainty principle: <mathjax>$S(\alpha_0) + S(\beta_0)
\ge \sqrt{2}$</mathjax>. (<mathjax>$\alpha_0$</mathjax>, <mathjax>$\beta_0$</mathjax> correspond to a conjugate basis)</p>
<p><a name='3'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Multiple-qubit Systems -- January 24, 2012</h2>
<p>Snafu with the projections, so lecture will be on the whiteboard! Will
also stop early, unfortunately.</p>
<p>State of a single qubit is a superposition of various states
(<mathjax>$\cos\theta\ket{0} + \sin\theta\ket{1}$</mathjax>). measurement has effect of
collapsing the superposition.</p>
<p>(hydrogen atom: electron can be in ground state or excited state.)</p>
<p>Now we study two qubits!</p>
<h1>TWO QUBITS</h1>
<p>Now you have two such particles, and we want to describe their joint state,
what that state looks like. Classically, this can be one of four states. So
quantumly, it is in a superposition of these four states. Our <mathjax>$\ket{\psi}$</mathjax>,
then, is <mathjax>$\alpha_{00}\ket{00} + \alpha_{01}\ket{01} + \alpha_{10}\ket{10} +
\alpha_{11}\ket{11}$</mathjax>.  Collapse of the wavefunction occurs in exactly the
same manner.</p>
<p>Probability first qubit is 0: <mathjax>$\abs{\alpha_{00}}^2 + \abs{\alpha_{01}}
^2$</mathjax>. New state is a renormalization of the remaining states.</p>
<h1>ENTANGLEMENT</h1>
<p>First, let me show you what it means for two qubits not to be
entangled. Essentially, we have conditional independence.</p>
<p>Quantum mechanics tells us that this is a very rare event (i.e. it
almost never happens).</p>
<h2>Bell State</h2>
<p>You have two qubits in the state <mathjax>$\frac{1}{\sqrt{2}}\parens{\ket{00} +
\ket{11}}$</mathjax>. Impossible to factor (nontrivial tensor product), so we must
have some sort of dependence occurring. Neither of the two qubits has a
definite state. All you can say is that the two qubits together are in a
certain state.</p>
<p>Rotational invariants of Bell states -- maximally entangled in all
orthogonal bases.</p>
<p><a name='4'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Entanglement, EPR, Bell's Experiment -- January 26, 2012</h2>
<p>Ignore Q4 on HW2. Probably.</p>
<h1>Entanglement</h1>
<p>Last time, we saw a Bell state (a Bell basis state). This is a state
of two particles (i.e. two qubits), and the state of each of the
qubits is "entangled", so to speak, with the other of the qubits.</p>
<p>This state has a very curious property, as we saw last time: maximally
entangled qubits will remain maximally entangled regardless of the
choice of bases, as long as they are orthogonal. This is known as the
ROTATIONAL INVARIANCE OF BELL STATES.</p>
<p>For the bell basis state α₀₀|00〉 + α₁₁|11〉, we have rotational
invariance for <em>real</em> rotations only. Certain bell bases additionally
have rotational invariance over complex rotations.</p>
<p>FACT 1:</p>
<pre><code>You get the same outcome if measure both in the v, v⊥ basis.
</code></pre>
<p>FACT 2:</p>
<pre><code>Independent of separation between particles. It's not because
the particles are close to each other and talking to each
other; it's because of their state.
</code></pre>
<p>Einsten, Podolsky, &amp; Rosen '35:</p>
<pre><code>Imagine that you have a pair of particles that are emitted
(e.g. electron, positron) that are highly entangled. They are
emitted in opposite directions and travel far from each other. And
then you measure Particle 1 in bit (0/1) basis ⇒ knowledge of the
bit on the other particle. Also, measure Particle 2 in the sign
basis ⇒ knowledge of the sign on the first particle. Contradicts
uncertainty principle?

Not at all. { sign information destroyed, etc. } Sign information
measured in the second particle has nothing to do with that of the
first particle, since measuring the bit information destroyed the
sign information (i.e. is now entirely unknown). { more questions
regarding the Einstein/deterministic interpretation of quantum
mechanics. }
</code></pre>
<p>Bell '64:</p>
<pre><code>Take two entangled particles. Despite large separation distance,
they are quantumly connected. What you can do is start playing
with the notion of measuring the particles in arbitrary
bases.

Make one measurement with outcome u. You'd have |v〉 and |v⊥〉
with probabilities cos²θ and sin²θ.

Bell's idea was this: Surely, if you play with your choice of u
and v, you're going to get something good.

We have some input, 0 or 1, that tells us which basis to
pick. Suppose there are two experimentalists who have these
entangled pairs of qubits. At the last minute, Alice gets as input
some random bit; likewise, Bob gets some other random bit.

We want to know the two output bits.

Goal: maximize probability that r{a}r{b} = a + b (mod 2) = a ⊕ b

    If either of the inputs is a zero, they want to output the same
    bit. But if both of the inputs are one, they want to output
    opposite bits.

Fact: If you choose the correct angles, in the quantum world, you
get a success probability of cos²(π/8) ≈ 0.85.

Claim: no way to do better than 3/4, if you agree to say the same
thing in advance. (Local) hidden variable theory ≤ 0.75. Impossible
to do better.

However: Quantum mechanics gives us a success rate of ≈ 0.853, or
cos²(π/8).
</code></pre>
<p>Alice's protocol is as follows: if r{a} = 0, measure in basis rotated
↻ π/16.  if r{a} = 1, measure in basis rotated ↺ 3π/16.</p>
<p>Bob protocol is as follows: if r{b} = 0, measure in basis rotated
↺ π/16.  if r{b} = 1, measure in basis rotated ↻ 3π/16.</p>
<p>{ where did these angles come from? If you plot them on the number
  line, you get four points a₁, b₀, a₀, b₁. When either is zero, we
  have a distance of π/8, else we have a distance of 3π/8. }</p>
<p>For the cases where (a ⊕ b), we have probability cos²(π/8). for the
case where !(a ⊕ b), we have probability sin²(3π/8) = cos²(π/8).</p>
<p>Conclusively disproves Einstein's hidden-variable theory.</p>
<p>There's this remarkable aspect where over time you can refine these
concepts to the point that we can sit down in an hour and a half to
understand these concepts that Einstein would have given anything to
understand. Isn't this remarkable?</p>
<p>When you actually do these experiments, they turn out to refute the
entire plan Einstein had.</p>
<p><a name='5'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Quantum Gates -- January 31, 2012</h2>
<p>GATES, MORE GATES.</p>
<p><a name='6'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Revisiting Axioms of Quantum Mechanics -- Feb 2, 2012</h2>
<p>We're going to be revisiting, over the next few lectures, the axioms
of quantum mechanics and how to refine them further.</p>
<p>Today: first axiom: superposition principle. In general, if we're in a
system that has k distinguishable states, then in general it is in a
linear superposition of these states. Each state is a unit vector, and
the states of the system reside on the surface of the sphere.</p>
<h1>Addendum:</h1>
<p>What happens if we have two different subsystems? Take the first to be
k-dimensional, and the second to be l-dimensional. So now, in the
addendum, the question we are asking is "what happens if we take these
two subsystems and put them together and call this our new system?"
Take a tensor product of these two states. k × l distinguishable states.</p>
<p>So now, if you apply our superposition principle, what does it tell
us? We can be in any superposition of states. We are in a
superposition of basis vectors of (k ⊗ l).</p>
<p>Separately, we have k + l amount of storage space, but when we put
them together, we have k × l. These are the fundamental underpinnings
of quantum computing: this is where entanglement comes from; this is
where the exponential speedup comes from.</p>
<p>It's so very different from classical physics that if you chase it
out, you have consequences. One can just keep it at the level of
formalism, and then it's just notation; it's slightly weird. But then
you look at it and try to understand it, and it really has profound
consequences. So let's try to understand these consequences further.</p>
<p>[ calculating angles between states; inner product actually must be ]
[ equivalent to the product of the inner product of the components. ]</p>
<p>So now, let's back up for a moment and ask: we've said there's this
anomaly where we get a multiplicative effect instead of additive. Why?
They could be entangled. These states we are considering are product
states and are not entangled. In general, when you have a composite
system, you won't be able to decompose it into the tensor product of
two states, i.e. general state cannot be factored. For instance, Bell
states cannot be factored. You cannot say what the first particle must
be, and what the second state must be. All you can say is what the two
particles are simultaneously.</p>
<p>==== Intermission ====</p>
<p>Two different applications of concepts we've talked about before.</p>
<h1>No-cloning theorem</h1>
<pre><code>Suppose you've got a qubit in the state |ψ〉, in some unknown
state. Now that you have it, you'd like to make copies of it. What
you have in your lab is lots and lots of qubits which you can
initialize to the state |0〉. We also have a lot of fancy
equipment. You think to yourself, surely, given the fact that I
have all this fancy equipment and all these post-docs running
around, we should be able to make at least one copy of this
quantum state.

So we want at least to have the state |Ψ〉 ⊗ |Ψ〉. We want to
start with |Ψ〉 ⊗ 0 and go to |Ψ〉 ⊗ |Ψ〉 using fancy
equipment. We can do plenty of unitary transformations (third
axiom of quantum mechanics: no matter how big your lab is, it's
only going to perform a unitary transformation). Is this possible?
No-cloning theorem says this is impossible.

There's a principle called the Church of the Larger Hilbert
space. If you really want to, you could expand your Hilbert space,
and consider measurements to be something that happens in this
larger Hilbert space, and you're only looking at part of your
data. In this larger Hilbert space, this is unitary in the larger
Hilbert space.

Right now we're considering a closed system. Later we can make
this theorem more general and include everything, but the
statement will remain the same.

All you can do is perform some rotation on your Hilbert
space. However, we must preserve angles. Such a unitary
transformation only exists if we know that |Ψ〉 is one of two
known orthogonal states.

Basically, this tells us that we cannot clone an unknown quantum
state. There is only one exception: when you know that it is one
of two known orthogonal states.
</code></pre>
<h1>Quantum Teleportation</h1>
<pre><code>Related is the concept of quantum teleportation. Quantum
teleportation provides a way to transfer a particle from one party
to another, if the two parties share an EPR state (Bell state).

Quantum teleportation is this protocol by which the first party
performs a joint measurement on two qubits. The result of this
measurement is one of four results, which is shared with the
second party. The second party then performs one of four
operations (a series of quantum gates) on the other qubit and
receives as a result of these operations the original quantum
state.

There's this property of entanglement called monogamy. A qubit
cannot be maximally entangled with multiple qubits.
</code></pre>
<p>These things took a while to figure out. At first, it was completely
unclear. When this was happening in the early 90s, we'd spend a lot of
time figuring these things out. It was not easy. We'll need some more
concepts, though.</p>
<p><a name='7'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Observables, Schrodinger's equation -- Feb 7, 2012</h2>
<h1>Observable</h1>
<p>Operator (i.e. can be described by a matrix) that describes any quantity
that can be measured, like energy, position, or spin. You feed in a quantum
state and receive as output a real number.</p>
<p>Why an operator? If you have a k-level system, then an observable for this
would be a k-by-k Hermitian matrix (i.e. <mathjax>$A = A^\dagger$</mathjax>). Important thing
about hermitian matrices: spectral theorem: orthonormal eigenbasis of
eigenvectors <mathjax>$\phi$</mathjax> that correspond to real eigenvalues <mathjax>$\lambda$</mathjax>.</p>
<p>The real number you get as a result of the measurement -- what you read out
in the measurement outcome -- is <mathjax>$\lambda$</mathjax>. Consider discrete energy
levels; after a measurement, we collapse the wave function into a single
eigenstate.</p>
<p>We already knew what a measurement was. So what happened here, how can we
have a new definition of a measurement? This isn't fair. How can you trust
a course that changes its mind every other week? No complaints? I mean,
isn't it terrible? This is completely different. So what's going on?</p>
<p>Our previous notion of measurement required us to choose some orthonormal
basis. We write out our state <mathjax>$\Psi$</mathjax> in this basis. The result of the
measurement was equal to i with probability <mathjax>$\abs{\beta i}^2$</mathjax>, and the new
state was <mathjax>$\ket{\Psi_i}$</mathjax>. So how does this correspond to what we have now?</p>
<p>We can reconcile them by showing that our old notion was less
formalized. It's only that basis which corresponds to the basis vectors of
some Hermitian matrix.</p>
<p>Pick any arbitrary orthonormal set of vectors and an arbitrary set of real
numbers. Ask: is there any matrix that has these eigenvectors and these
eigenvalues? Argue: always possible. In that sense, the new definition of a
measurement is really the same as the old one.</p>
<p>Consider case where eigenvalues not unique: reconsider notion of orthonormal
eigenvectors as notion of orthonormal eigenspaces. We've seen an example of
this, by the way: when we had a two-qubit system and we only measured the
first qubit. Each of the two outcomes corresponded to a two-dimensional
subspace. There were two eigenvectors with the same eigenvalue. Project the
subspace onto the space spanned by eigenstates corresponding to result of
measurement.</p>
<p>Reasoning: in the general case, you don't project onto a basis vector; you
project onto the subspace that is consistent with the outcome of the
measurement.</p>
<p>What the measurement does is provide some information about the state and
change the state to reflect the outcome. It doesn't restrict itself any
more than it has to.</p>
<p>diagonalization: converting to a different basis, scaling appropriately,
converting back to the original basis.</p>
<p>A way to construct the operator (must be a hermitian matrix) is with an
outer product: you can generate the change-of-basis matrix.</p>
<p>==== Intermission =====</p>
<p>Piazza: posted question about other people wanting midterm moved. Enough
objections such that we will stick with original date: next Tuesday. Posted
yesterday a homework which is effectively a review for the midterm, which
will cover everything up until this lecture. Three problems on homework: 2
are review, 1 is on today's lecture. <strong>Due this Friday at 5.</strong></p>
<h1>Schrodinger's Equation</h1>
<p>Most basic equation in quantum mechanics; describes how a system evolves
over time. Depends on one particular operator, the Hamiltonian: the energy
operator (more specifically, kinetic energy T + potential V). When you
write out the Hamiltonian of this system, the eigenvectors correspond to
(eigen)states with definite energy. The corresponding eigenvalue <mathjax>$E_i$</mathjax> is
the corresponding energy.</p>
<p>So now what Schrodinger's equation says is that the state \psi of the
system is a function of t, and it evolves according to a differential
equation which relates the energy of the system.</p>
<p><mathjax>$i\hbar \pderiv{\psi}{t} = \hat{H} \psi$</mathjax>
(<mathjax>$\hbar \equiv $</mathjax>Planck's constant, <mathjax>$i \equiv \sqrt{-1}$</mathjax>)</p>
<p>The rate of change depends on what the Hamiltonian tells us to do. You can
consider the Hamiltonian talking about interaction between parts of the
system or between subsystems. Forces. Everything.</p>
<p>Now, Schrodinger actually discovered this equation in 1926. This was after
many of the initial discoveries in quantum mechanics. It was after
deBroglie discovered the wave-particle duality. One of the biggest
intellectual events of the twentieth century.</p>
<p>So let's see what this equation tells us about the equations of motion. PDE
solving, yay.</p>
<p>So what we know is that if the state at time 0 was an eigenvector <mathjax>$\phi$</mathjax>,
then the state at time t must be some constant <mathjax>$A(t)\phi$</mathjax>.</p>
<p>precession of individual states; generalization is the summation of the
various eigenstates. If you want to write out the linear operator that
tells you how to go from <mathjax>$\Psi(x,0)$</mathjax> to <mathjax>$\Psi(x,t)$</mathjax>, it's just the diagonal
matrix of eigenvalues. You can check that this is a unitary matrix.</p>
<p>The way you write this unitary matrix in notation is <mathjax>$\exp(-i\lambda
t/\hbar)$</mathjax>. Nothing to be scared by. Look, we're exponentiating a matrix,
but that's nothing to be worried about.</p>
<p>Suppose <mathjax>$\psi(0)$</mathjax> = <mathjax>$\ket{0}$</mathjax>, and you wanted to know <mathjax>$\psi(t)$</mathjax>.</p>
<p><a name='8'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Schrödinger's Equation -- Feb 9, 2012</h2>
<p>Had the sense last time that some of you might not remember all of your
linear algebra. So this time is a hybrid of linear algebra and getting you
up to speed with this bra-ket notation.</p>
<p>What we are going to be doing is looking at it from three or four different
viewpoints to try to get an intuition for why it is the way it is. So when
we get around to trying to solve the SE for specific equations, it's not
just an equation; you have a feel for it.</p>
<p>Goal for today: Figure out why does the Hamiltonian plays a role in
Schrödinger's equation.</p>
<p>So basically, the way we are going about this is that last time, we had a
rather abstract formulation of Schrödinger's equation. Why? It's because
the formulation is so clean. General form: write out hamiltonian,
diagonalize it, and once you understand the eigenvalues and eigenvectors,
you understand why it has the form it does.</p>
<p>So why does it look the way it does? Conservation laws.</p>
<p>Next week, we'll look at it for concrete systems; for continuous systems;
the behavior of an unstrained particle. In each of these cases, we're
trying to build an intuition as to <em>why</em> the Schrödinger equation is the
way it is.</p>
<p>Not going to get into time-dependent hamiltonians until maybe the end of
the semester.</p>
<p>Do Hamiltonians correspond to quantum circuits? The way you implement gates
is by implementing a suitable Hamiltonian. But a quantum circuit
corresponds to a time-varying Hamiltonian. Topics we'll get to closer to
the end of the semester.</p>
<p>What we are starting with are the basics of quantum mechanics. Viewing it
in the case of discrete systems, i.e. qubits. We've already started with
quantum gates, quantum circuits.</p>
<p>We're going back and forth between this abstract version which is very
close to axiomatic quantum theory (but also helps with the understanding of
theory), and physical systems (hamiltonians). After a few weeks of physical
systems, we'll start talking about quantum algorithms.</p>
<p>And then, after we have developed that for a little while, how do you
implement all this in a lab? We'll go back and look at the physics of it.</p>
<p>We're sort of walking this fine line between thinking about quantum devices
as abstract entities; where all you need to know is the axioms of quantum
mechanics; thinking about what you can and cannot do, and what you have to
do to make it all happen.</p>
<p>So let's start with the basics. What I'll do today is I'll describe in a
little more detail Dirac's bra-ket notation. We've already seen this
notation to some extent, but let's do this more systematically.</p>
<p>Remember if you have a k-state quantum system, then its state is described
by a unit vector in a k-dimensional Hilbert space. This is also
equivalently described in ket notation as α{j}|j〉. We love this notation
because it simultaneously highlights two aspects: this is a vector, and it
is information. For example, if k=2, this is a qubit storing a bit of
information.</p>
<p>The dual space (row space) of this, if you write this state as |Ψ〉, is the
bra 〈ψ| (hermitian conjugate). The inner product (square of the length of
the vector) is simply 〈Φ|Ψ〉</p>
<p>People who love the bra-ket notation love it because you don't have to
think. You just do what seems right and everything magically works out.</p>
<p>So if you have a vector |Ψ〉, you can talk about the projection operator
projecting onto |Ψ〉. It's a linear operator. What you want to do is design
the projection operator onto Ψ (often denoted by P) ≡ |Ψ〉〈Ψ|.</p>
<p>Pⁿ should ≡ P, for obvious reasons. |Ψ〉〈Ψ|Ψ〉〈Ψ|: 〈Ψ|Ψ〉 = 1, so
multiple applications of an operator are equivalent to a single
application.</p>
<p>Suppose |Ψ〉=|0〉. What does P look like as a matrix?
[1...0]
[..  0]
[. . 0]
[0  .0]</p>
<p>I = ∑|j〉, therefore. It doesn't have to be in terms of the standard
basis. You could write down the identity in terms of any basis in this
way. Physics refers to this as the "resolution of the identity".</p>
<h2>Example</h2>
<p>Suppose you have a vector and you want to measure it in a general basis.</p>
<p>What happens if we measure |Ψ〉 in the |v〉, |v^{⊥}〉 basis? Do a change of
basis on |Ψ〉. Project |Ψ〉 onto each of the basis vectors. This is one way
of doing it.</p>
<p>==== Intermission ====</p>
<p>Goals for the midterm: fluency with the basics. Purpose of the course: not
a sequence of tests as much as getting something out of it. But to get
something out of it, you should be fluent in the maneuvers presented so
far. Not enough that you can sit down and figure it out in ten minutes.</p>
<p>Midterm will not be open-book or open-notes, but anything that you'd need
to remember will be on the midterm itself. e.g. teleportation protocol
would be given.</p>
<h1>Observables</h1>
<p>An observable is a Hermitian matrix M such that M = M†. So now we have
something called the spectral theorem, which says that hermitian matrices
can be diagonalized: you can write them in a different basis (the
eigenbasis), and you can write them out in this eigenbasis.</p>
<p>Suppose M = X (bit-flip). Xv = λv. (X-λI)v = 0. det(X-λI) = 0. Solve for λ,
which are your eigenvalues, and then we go back and solve for our
eigenvectors.</p>
<p>Here, we're going to do this by inspection. Eigenvectors of X would be
<mathjax>$\ket{+}, \ket{-}$</mathjax>; the corresponding eigenvalues are 1, -1.</p>
<p>Why is this an observable? If you were to create the right detector, we'd
observe something. We'd measure something. What we read out on the meter is
<mathjax>$\lambda\ket{j}$</mathjax> with probability equal to <mathjax>$\alpha_j^2$</mathjax>, and the new state
is <mathjax>$\ket{\Psi_j}$</mathjax>. What Schrödinger's equation tells us is that if you look
at the energy operator H, and then in order to solve this differential
equation, we need to look at it in its eigenbasis. It was not supposed to
be so frightening. You can write U(t) notationally as <mathjax>$e^{-iHt/ℏ}$</mathjax>.</p>
<h2>Why H?</h2>
<p>Why should Schrödinger's equation involve the Hamiltonian? Why the energy
operator? What's so special about energy? Here's the reasoning: from axiom
3 of quantum mechanics, which says unitary evolution, what we showed was
the unitary transformation is <mathjax>$e^{-iHt/\hbar}$</mathjax>. Any unitary transformation
can be written in this form. You can always write it in the form <mathjax>$e^{iM}$</mathjax>
for some Hermitian matrix M. The only question is, what should M be? Why
should M be the energy function? The second thing that turns out (either
something that we'll go through in class or have as an assignment) –
suppose that M is a driving force of Schrödinger's equation. So
<mathjax>$\pderiv{\Psi}{t} = M\ket{\Psi}$</mathjax>.</p>
<p>Suppose there were some observable quantity A that is conserved: i.e. if
you start out with a measurement of |Ψ(0)〉, and you do the same
measurement at time t, if A is a conserved value, then this expected value
should be the same both times. If A is conserved, then AM = MA. A has to
commute with M. This tells us that their eigenvectors are the same. The
fact that energy is conserved, therefore, says that HM = MH. Then we have
one last bit: energy is very special. It is very fundamental; these are the
building blocks; it goes right to the core. H commutes with M not for
special conditions of the system, but rather generally.</p>
<p>So you can reason that M is a function of H. And then you show that it must
be a linear function of H (aH + b), b must be 0, and a must be a constant
(in fact, Planck's constant).</p>
<p>Symmetry plays a very strong role in the way this comes about.</p>
<p><a name='9'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Continuous Quantum States, Free particle in 1D, Heisenberg Relation</h2>
<h2>Feb 14, 2012</h2>
<p>So far we've talked about discrete quantum systems. Today, we're going to
make the transition to talking about continunous quantum systems. In 1
dimension, the particle can be anywhere on the line.</p>
<p>Schrödinger's equation in 1 dimension, Heisenberg relation.</p>
<p>iℏ(∂Ψ(x,t)/∂t) = [-(ℏ²/2m)(∂²/∂x² + V(x)] Ψ(x,t) = HΨ(x,t)</p>
<p>Some things where won't be terribly careful about being precise for
now. Will fix later to extent that you won't be too upset about it
later. Attempt to day is to try to understand these objects on an intuitive
level. Before we do that, let's do a five-minute review of discrete
systems, just to orient ourselves when we go to continuous distributions.</p>
<p>Back to the familiar k-state systems. State is a unit vector in k-dim
Hilbert space, etc. And then we have this notion of an observable (given by
a Hermitian matrix M ≡ M†). What we like about this is that by the spectral
theorem, we have an orthonormal basis of eigenvectors corresponding to real
eigenvalues. Result is that discrete energy levels correspond to orthogonal
vector spaces.</p>
<p>Since this is an observable, the deflection of our meter is λj with
probability |〈Ψ|Φj〉|², and the new state is |Φj〉. We could ask a
couple of questions.</p>
<p>Before we continue: let's look at another way of considering M being
Hermitian: Mij = 〈Φi|M|Φj〉 = conj(〈Φj|M|Φi〉) for any Φi, Φj; not
necessarily just for basis vectors.</p>
<pre><code>* We can try to picture the measurement outcome. What our measurement
  looks like is this: some probability distribution. We can
  characterize this distribution by its moments, much like how we can
  characterize a function by its derivatives. The more moments we have,
  the more we know about our distribution.
    + mean: location.
    + standard deviation: width.
    + skewness: symmetry.
    + kurtosis: peakedness.
* We can consider the mean to be 〈Ψ|M|Ψ〉.
    + First write M in its eigenbasis, where it's a diagonal matrix.
* We can also do the same for variance. Var(X) = E(X²) - E(x)² = E(X²)
  - μ², for obvious reasons. E(X²) = 〈Ψ|M²|Ψ〉: intuitive after
  considering that M² preserves eigenvectors while squaring eigenvalues
  (result of diagonalizability of M).
</code></pre>
<p>Here's what we're planning to do (hopefully) for the rest of the lecture:
it'll be in the form of a sketch, which hopefully will give you a picture
of what happens when you look at a particle in 1 dimension.</p>
<p>Before that: σ (standard deviation) is a measure of spread. If you were
really certain about a physical quantity, you'd have σ ≡ 0.</p>
<p>So, let's have a particle that's free to move about in one dimension. We'll
describe approximately for now; we just want to understand its form. Later
will be much precise, but now we just want to put an image in our minds as
to just where this equation comes from. We'll want to understand position
of the particle x (how it behaves) as well as momentum p. We'll also look
at the uncertainty relation that says ΔxΔp ≥ ℏ/2 (some constant). Show
intuitively that there must be some minimum.</p>
<p>In this continuous picture, x and p behave like something you've already
seen: bit and sign. There's something about the spread of the two. You
cannot know both of those quantities precisely, either in the one, or the
other, or both. The more certainly in one, the less certainly in the
other. Rather than do it by formula and precisely, we'll do it more
intuitively.</p>
<p>Often, when you think you want to explain something so that people really
understand, you want to go slowly. Paradoxically, it's sometimes better to
go fast. Explanation: it's easier to put all the pieces together when you
see the big picture all at once. See big picture first, then observe
individual bits later.</p>
<p>We want to talk about a lot of stuff.</p>
<p>Once again, what we are trying to do is describe the state of the particle
on an infinite line. So now, before you describe it, let's do an
approximation. Let's consider this as not infinite, but very long (take a
limit). Likewise, not continuous but very fine (also a limit). Could be at
one of various positions. Describe your state as this superposition of
states. What we're saying is that Ψ(j) is αj. When we generalize this to a
particle being anywhere on the line, the way to describe it is Ψ being a
continuous function, so Ψ(x) is a complex-valued function on the real
line. As in the discrete case, we want our distribution to be normalized.</p>
<p>Now, suppose we wanted to measure the position of this particle. Out here,
we'd have an observable, M. The corresponding observable in the continuous
case, let's call it x. We'd just do 〈Ψ|x|Ψ〉. Our inner product now is
defined with integrals.</p>
<p>Our observable now takes as input a wave function Ψ and spits out another
function as output.</p>
<p>More fuel for intuition: you should know one of the big discoveries: nature
is described by local differential equations. Every point in space only
considers its own neighborhood. It's concerned only with itself, and
nothing else. So now let's apply that principle here. How that wave
function evolves over time. So the point x is minding its own business and
its own infinitesimal neighborhood. So what does it do? The simplest thing
it does is compare itself to its neighbors, say the average of its
neighbors. (consider perceptron, maybe?) But this yields the second
derivative with respect to x, and the function smooths itself out. So we
must move in an orthogonal direction to avoid collapsing the wave
function, i.e. multiply by i.</p>
<p>Let's now try to understand where the uncertainty principle comes in.</p>
<p>Momentum we can measure in the quantum case; it's sort of a proxy for
velocity, since velocity doesn't really make sense.</p>
<p>Let's consider a fairly standard wave exp(i(kx-omegat)). Now you ask what the
equation of motion says if it's going to evolve. Let's say Ψ(x,0) ≡
exp(ikx). omega is the rate at which it twists over time. A twisting seems to
correspond to some sort of translation. The rate of translation is directly
proportional to k.</p>
<p>So now we have a function of definite momentum. We can then decompose this
wave function in terms of these functions. These are our Fourier basis
functions. So if you want to go from the position basis to the momentum
basis, you take a Fourier transform. In other words, this is roughly
equivalent to what we do when we go from the sign basis to the bit basis,
or vice versa (what a Hadamard gate does).</p>
<p><a name='10'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Free particles, Uncertainty, Quantization</h2>
<h2>Feb 21, 2012</h2>
<p>We talked about things informally last time, and what we were going to do
was see Schrödinger's equation from various viewpoints.</p>
<p>Today, again we'll look at a free particle in one dimension, a somewhat
more rigorous of the uncertainty relation, quantization, and use that as
our first implementation of a qubit.</p>
<p>What we want to do is describe how this state evolves in time. This is what
was described by Schrödinger's equation. Last time, we derived what this
equation should look like (approximately) as a result of certain
considerations.</p>
<p>Clasically, the energy of this particle (which we'll write as a function of
two parameters p and x). ∂ψ/∂t = p²/2m + V(x).</p>
<p>So, first of all, we want to figure out what corresponds to the position in
quantum mechanics? How do you measure the position of this particle? We
said we had a position operator, and when you applied it to ψ(x), what you
got back was xψ(x). Same idea of measurables as before: we're measuring
position, so our eigenvalues correspond to the position of the
particle. What we are requiring from our position operator is exactly the
same thing.</p>
<p>So the momentum operator \hat{p} is ℏ/i (∂/∂x). ℏ is our normalized
Planck's constant. Again, the discrete analogue of this is a
measurable. Once again, we're ignoring constants, since we only really care
about constants.</p>
<p>What the correspondence principle says is that what you should do (when you
know what the classical situation looks like) is to just substitute \hat{x}
and \hat{p} instead of x and p, and put that down for your energy
operator. So why do you do this? Better people than us have done this in
the past, and it seemed to work out for them.</p>
<p>So clearly, what Schrödinger's equation must say is:
iℏ ∂ψ/∂t = -ℏ²/2m ∂²ψ/∂x².</p>
<p>(ignoring potential energy as a result of it being a free particle – not
subject to any potential / potential is equivalent to 0.)</p>
<h1>Uncertainty</h1>
<p>Let's just try to see how our function (given as a function of x) looks as
&lt;a function of p. What we said last time was that was the Fourier
transform. Fourier basis and standard basis are "like oil and water" – if
one is maximally certain, then the other is maximally uncertain. So you
cannot come up with any wave function that is localized in both spaces. So
we can try to quantify this. We had nice pictures, but now we're going to
work directly with operators. It's going to not vague and very precise, so
for some, it'll be great. But for others, it'll be a disaster since there
are no pictures.</p>
<p>Remember: the thing about an observable that we care about most is the
eigenvector decomposition. So the question is: what do the eigenvectors
look like? That determines how nicely they play with each other.</p>
<p>Discrete case first. Remember you had your phase-flip operator Z, bit-flip
X. Considering the eigenvectors and eigenvalues, the claim is that this is
as good as you are going to get.</p>
<p>Another way to measure how different these eigenvectors are is to see
whether these matrices commute or not. If they commute, they have a common
set of eigenvectors. Commuting means XZ - ZX = 0. So we want to look at XZ
- ZX (a commutator, denoted by [X,Z]).</p>
<p>So what does this look like between \hat{x} and \hat{p}? We have product
rule coming into play... yielding [x,p] ≡ iℏ.</p>
<p>We'll use this to derive ΔxΔp = ℏ/2. We'll do this quickly so we'll have
time to talk about the particle in a box.</p>
<p>Recall: given an observable A and a state |Ψ〉, the expected value is
〈Ψ|A|Ψ〉. We also saw that the variance was E(x²) - E(x)², so in this case
σ² = 〈Ψ|A²|Ψ〉 - 〈Ψ|A|Ψ〉². </p>
<p>For now, assume 〈Ψ|A|Ψ〉 = 0. Makes derivation simpler, and we're just
asserting that we don't really lose much (anything, really).</p>
<p>Take Ψ ≡ A|ψ〉, Φ ≡ B|Ψ〉. By Cauchy-Schwarz, we have that this is greater
than or equal to 〈Ψ|Φ〉 = 〈ψ|AB|ψ〉. By symmetry, it's also greater than
or equal to 〈Φ|Ψ〉 = 〈ψ|BA|ψ〉. As a result, (ΔA)²(ΔB)² ≥
|〈ψ|AB-BA|ψ〉/2|² = |〈ψ|[A,B]|ψ〉/2|² = |〈ψ|iℏ|ψ〉/2|² = ℏ²/4. So the
square of the spread of x + square of spread of momentum is at least
ℏ²/4. If you take square roots, you get the proper result. (you can get a
better bound by being more careful by also using the anticommutator. We
were being sloppy for the purpose of making things simpler.)</p>
<h1>Particle in a box</h1>
<p>This is basically just the infinite square well. We want to figure out our
eigenfunctions just by looking at the operator. Again the way we do this is
guess and come up with the right answer by chance. You expect the
eigenfunction to be an exponential, so we guess and check. Life is nice
that way.</p>
<p>We are trying to solve for H|φ〉 + E|φ〉. Guess that |φ〉 = e^{ikx}. Let's
figure this out. Our maneuver is to say that we're dealing with a separable
equation ("decompose this problem" by looking at the eigenvectors of H).</p>
<p>Suppose our state was one of these eigenvectors. We then know what the
Hamiltonian does to it: it simply applies a scalar (the corresponding
energy level). So of course we want to write our function in this basis,
since we know how to solve the simpler differential equation.</p>
<p>The operator affects each eigenvector separately. So we can tack on the
time dependence as an afterthought (to each eigenvector).</p>
<h1>COMING UP</h1>
<p>We'll solve this problem using this very strategy. We know what the
eventual answer looks like: ∑e^{-iEt/ℏ}|ψ(x)〉</p>
<p><a name='11'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h2>Quantization, Particle in a box, Implementing Qubits</h2>
<h2>Feb 23, 2012</h2>
<h1>A more precise review</h1>
<p>By this point, we've talked about a number of things. Discrete/continuous
quantum systems, measurements, and so forth. So what I'd like to do for the
first half of the lecture is give you a slightly more formal overview of
everything we've talked about before: about the model. In some sense what
we've been talking about has been challenging, but in some sense it's also
rather simple (i.e. we can do a more precise, more formal review of what
we've covered quickly).</p>
<h2>Multiple-qubit systems</h2>
<p>So let's start from the beginning. If our state is a discrete system, <mathjax>$\psi$</mathjax>
is an element of a <mathjax>$k$</mathjax>-dimensional vector space.</p>
<p>The second thing we want to say about quantum states is the following: what
happens if you have two quantum systems, <mathjax>$a$</mathjax>, a <mathjax>$k$</mathjax>-level system, and <mathjax>$b$</mathjax>,
an <mathjax>$l$</mathjax>-level system? Now we want to understand what happens when we put <mathjax>$a$</mathjax>
and <mathjax>$b$</mathjax> together and look at them as a composite system? When you put states
together, you need to take tensor products. If we happen to be in the state
<mathjax>$|i\rangle$</mathjax> in one system and <mathjax>$|j\rangle$</mathjax> in the other system, then
corresponding to that we have a state in the composite system as <mathjax>$|i\rangle
\otimes |j\rangle$</mathjax>, which can be written as <mathjax>$|ij\rangle$</mathjax>, if you're being
especially lazy.</p>
<p>The number of dimensions we get is <mathjax>$kl$</mathjax>, which is the dimensionality of the
space in which the composite system lives.</p>
<p>This is called taking tensor products.</p>
<p>The new system inherits the properties of the old one; for instance, how do
you compute inner products? Suppose a-system happened to be in the state
<mathjax>$|00\rangle$</mathjax>, and another was in <mathjax>$|++\rangle$</mathjax>. What is the angle between
these states? If you were computing the inner product, <mathjax>$\langle 00|11
\rangle$</mathjax>, then you would just take the inner products of the pieces
separately.</p>
<p>What is more interesting to us is measuring the probability of a state, and
that corresponds to its magnitude.</p>
<h2>Evolution of states</h2>
<p>We had our Hilbert space, and our evolution was just the rotation of our
Hilbert space. This was a rigid body rotation in that it preserved
angles / distances. So the inner product is not going to change as you do
this rotation.</p>
<p>And then we had our favorite gates, which consisted of things like the
bit-flip (X), phase-flip (Z), Hadamard (H), controlled not (CNOT, a
two-qubit gate).</p>
<p>So now, here's what I wanted to get to. Suppose you have two qubits, and
you apply a gate on each of them. Now you want to understand what operation
was applied. So first we must understand the form of the answer: it will be
a 4x4 matrix. And then to understand how to write out this 4x4 matrix:
effectively, we take the tensor product of the indivdual gate matrices.</p>
<p><mathjax>$$A \otimes B = \begin{pmatrix}
a_{00}B &amp; a_{01}B \\ a_{10}B &amp; a_{11}B
\end{pmatrix}
$$</mathjax></p>
<h2>Observables</h2>
<p>So then you have measurements, and we said that measurements correspond to
an observable M, which is a Hermitian operator, i.e. <mathjax>$M_{ij} = M_{ji}^{*}$</mathjax>.</p>
<p>So now, why is an observable M? Because we said when you have a Hermitian
matrix, by the spectral theorem, you have an orthonormal eigenbasis that
correspond to real eigenvalues. What you get as the outcome of a
measurement is some <mathjax>$\lambda_j$</mathjax>. This occurs with probability equal to
the square of the length of the projection onto the eigenspace
corresponding to <mathjax>$\lambda_j$</mathjax>. The new state is <mathjax>$|j\rangle$</mathjax>.</p>
<p>There is a special observable known as the Hamiltonian <mathjax>$\hat{H}$</mathjax>, the
energy observable. In order to solve the Schrodinger equation, which looks
very complex, if you write it in terms of the eigenvectors, we can neatly
partition it into a number of simpler differential equations, one for each
eigenvector. Since these are eigenvectors, the evolution of the system
leaves the direction alone, and all it does is change the amplitude and the
phase. There is a very nice short-hand for writing this: <mathjax>$e^{-i\hat{H}t}$</mathjax>:
this is our evolution operator, and you can check that it is unitary.</p>
<h2>Continuous quantum states</h2>
<p>So now let's fill in the corresponding picture for continuous quantum
states.</p>
<p>No longer finite, and it's even continuous. So, like a particle on a line,
and now you have a probability distribution representing your amplitude
(sort of; more like intensity). Usually you talk about what the probability
is of being in some range (of being in the neighborhood of x). If you were
looking at x itself, the amplitude would be zero (excepting Dirac
deltas). So now <mathjax>$\Psi$</mathjax> is a function mapping <mathjax>$\mathbb{R}$</mathjax> to
<mathjax>$\mathbb{C}$</mathjax>. It's normalized such that <mathjax>$\int |\Psi|^2dx = 1$</mathjax>. Another way
of saying this is that the inner product of <mathjax>$\Psi$</mathjax> with itself,
<mathjax>$\langle\Psi|\Psi\rangle$</mathjax>, is 1.</p>
<p>So what's the corresponding vector space we have for a continuous vector
space? We need some set of eigenfunctions that span all complex
numbers.</p>
<p>Then we have this notion of observables in these continuous systems, which
is going to be just like it was in the discrete case. So what does it do?
It takes a state <mathjax>$|\Psi\rangle$</mathjax> and maps it to <mathjax>$M|\Psi\rangle$</mathjax>. So we'll
just have some operator that maps a wave function to a not necessarily
normalized wave function.</p>
<p>And so we have two examples that we saw: <mathjax>$\hat{x}$</mathjax>, the position
observable, which maps <mathjax>$\Psi(x)$</mathjax> to <mathjax>$x\Psi(x)$</mathjax>, and then we had <mathjax>$\hat{p}$</mathjax>,
the momentum observable, which maps <mathjax>$\Psi(x)$</mathjax> to <mathjax>$i\pderiv{\Psi(x)}{x}$</mathjax>.</p>
<p>So we need these to have some notion of Hermitian. We must have
<mathjax>$\langle\phi|M|\psi\rangle = \bar{\langle\psi|M|\phi\rangle}$</mathjax>. We call this
sort of operator "self-adjoint".</p>
<p>Remember: integration by parts.</p>
<p>The momentum matrix would be skew-Hermitian (<mathjax>$M^\dagger = -M$</mathjax>), so we had to
multiply by a factor of i.</p>
<p>On this particular homework, all you have to do is work your way through
things like this (whether certain operators are Hermitian or not) and
compute the commutators of certain matrices. Should be an easy or useful
exercise, depending on how used to this sort of thing you are.</p>
<p>So now, let's talk about a particle in a box. We assume there is a box of
length L with infinitely high walls (i.e. infinite square well). Basically,
consider behind the boundaries of these walls there is a potential so large
that the particle cannot afford to leave.</p>
<p>So we want to solve Schrodinger's equation. What are the states? <mathjax>$H =
\frac{\hat{p}^2}{2m} \Psi = \frac{-\hbar^2}{2m}\pderiv{^2}{x^2}
\psi$</mathjax>. Rather than carry this potential around with us, we'll just impose
boundary conditions. <mathjax>$\Psi(0) = \Psi(l) = 0$</mathjax>. So this is H. Remember how we
solved Schrodinger's equation; we solved the eigenvalue problem. We tried
to figure out the eigenvalues <mathjax>$\phi_j$</mathjax> and the corresponding energies
<mathjax>$E_j$</mathjax>.</p>
<p>So now we want to understand what these eigenvalues look like for
corresponding energies. So what's an eigenfunction of this? The guess (what
we want) is for the eigenfunctions to look like e^{ikx}. Just evaluating
the right-hand-side, we get <mathjax>$E_k = \frac{\hbar^2 k^2}{2m}$</mathjax>. This is both
the energy of <mathjax>$e^{ikx}$</mathjax> as well as <mathjax>$e^{-ikx}$</mathjax>. So we guessed what the
eigenfunction looked like, and then we checked.</p>
<p>So we checked that <mathjax>$\psi_E(x)$</mathjax> is going to be of the form <mathjax>$Ae^{ikx} +
Be^{ikx}x$</mathjax>. When you take linear combinations of the two exponentials listed
above, you might as well take linear combinations of <mathjax>$\cos(kx)$</mathjax>,
<mathjax>$\sin(kx)$</mathjax>. This form is nicer because it is easier to impose the boundary
conditions. Enforcing boundary conditions, we get that <mathjax>$C = 0$</mathjax> (which makes
sense; cosine is even, and this function is 0 at x=0) and that <mathjax>$D =
\frac{k\pi}{l}$</mathjax>.</p>
<p>We now want to find C, which we can get by enforcing that our wave function
is normalized. use the <mathjax>$\int (sin^2 + cos^2) = 2\int (sin^2)$</mathjax> trick.</p>
<p>Finally, let's just go back and make two nice observations. Now you finally
see how to implement a qubit. To implement a qubit, you would restrict the
energy to be small enough to be in the first two modes. And then you would
let zero be one qubit and one be the other.</p>
<p><a name='12'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Algorithms</h1>
<h2>Feb 28, 2012</h2>
<h1>Introduction</h1>
<p>Today we're going to make a transition to quantum algorithms. But first, a
brief review of particle-in-a-box.</p>
<h1>Particle in a Box</h1>
<p>The particle in a box is sort of a toy model for a hydrogen atom. In what
sense? In a hydrogen atom, you have a proton and an electron, and the main
force it is subject to is Coulomb attraction. So for our purposes, as a
very first, very simple model, we'll think of writing out Schr\"odinger's
equation in the radial direction.</p>
<p>We'll think of this electron as not three-dimensional, but
one-dimensional (radial). And instead of dealing with the potential as it
is, we'll approximate it by saying what the potential really does is
confine the electron to within some range <mathjax>$\ell$</mathjax>. What we're going to do is
model the situation by saying that the electron is a free particle in a
box.</p>
<ul>
<li>
<p>Aside</p>
<p>It's worth thinking about this: once we solve this, we get a first
  picture what a hydrogen atom looks like. When we plot out the solution,
  what does this tell us about an electron and where it sits? This gives us
  a first approximation; really inexact. But for our purposes, since we are
  not so much wanting an understanding of the hydrogen atom so much as
  wanting a general understanding, this is a great model.</p>
</li>
</ul>
<p>Normally we consider this particle as free to move anywhere, but now we
impose an infinite potential outside of a particular region. Writing out
Schr\"odinger's equation where <mathjax>$H \equiv \frac{-\hbar^2}{2m}
\pderiv{^2}{x^2}$</mathjax>. We initially did this by guessing that the eigenvectors
were of the form <mathjax>$e^{ikx}$</mathjax>. We guessed this, figured out that the
eigenvalues (energies) corresponding to this must be <mathjax>$\frac{\hbar^2 k^2}
{2m}$</mathjax>, and then we said look, what this means is that <mathjax>$e^{ikx}$</mathjax> and
<mathjax>$e^{-ikx}$</mathjax> have the same energy, so we might as well just use the sinusoids
<mathjax>$\cos(kx)$</mathjax> and <mathjax>$\sin(kx)$</mathjax>. We solve for coefficients by imposing the
boundary conditions.</p>
<p>We also went ahead and normalized our wave function by saying <mathjax>$\int_0^\ell
\abs{\psi_n(x)}^2dx = 1$</mathjax>. What this further gives us is that <mathjax>$D =
\sqrt{\frac{2}{\ell}}$</mathjax>. So our general solution is <mathjax>$\psi_n(x) = \sqrt{\frac{2}
{\ell}}\sin\frac{n\pi x}{\ell}$</mathjax>. This tells us about the quantization of
energies. The fact that it takes on these discrete values means that you
get these standing waves of definite energy.</p>
<p>There's also a way of making this analogy a little more quantitative. We
can attempt to go ahead and do that. If we look at <mathjax>$E_2 - E_1$</mathjax> (the energy
difference between the first excited state and the ground state), for our
model, we got <mathjax>$\frac{3\hbar^2 \pi^2}{2m\ell^2}$</mathjax>. Assume <mathjax>$\Delta E \approx
10$</mathjax> eV; let's find out what <mathjax>$\ell$</mathjax> is (compared to <mathjax>$\ell_H \approx 1
\AA$</mathjax>, the actual value). We could substitute and solve, and we get roughly
<mathjax>$3.4 \AA$</mathjax>. As long as you make sure your energy is small, what you know is
that your particle is always in some superposition of the <mathjax>$n=1$</mathjax> and <mathjax>$n=2$</mathjax>
states.</p>
<h2>Precession of phase</h2>
<p>Remember that you are in always in some superposition of states, which
evolves over time. So I hope you can see what your qubit is, now. The
associated value of a qubit corresponds to a particular superposition. If
you do an inner product between any two of these superpositions, you get
complete cancellation.</p>
<p>We get a changing phase, yes, but this is no big deal; we can simply
account for a moving reference frame.</p>
<p>Because we have this phase precession, if you look at what the frequency
corresponds to, it's whatever the frequency of visible light is, let's
say. The fact you have this precession at this frequency allows you to
control this qubit from the outside using light (lasers). So somehow, in
this formulation, what you have is an implementation of qubits, and
secondly, you have a hint of how you're going to control this qubit from
the outside. How do you apply various gates? You now have this method of
reaching in and constraining the evolution of the quantum state.</p>
<ul>
<li>
<p>Aside</p>
<p>One other thing which we may or may not get to is this whole notion of
  cooling. This is a big deal in quantum computing and quantum systems. How
  do you cool your system down to a desired level? Once you're down to the
  quantum level, cooling itself looks like an algorithm. So there's this
  notion of algorithmic cooling. Just wanted to point this out as a lead as
  to where we are going to get to in a few weeks.</p>
</li>
<li>
<p>Intermission</p>
</li>
</ul>
<h1>Quantum Algorithms</h1>
<h2>Inspiration</h2>
<p>A one-qubit system belongs to <mathjax>$\mathbb{C}^2$</mathjax>; a two-qubit system belongs to
<mathjax>$\mathbb{C}^4$</mathjax>; an n-qubit system belongs to <mathjax>$\mathbb{C}^{2^n}$</mathjax>. This is a
result of repeated applications of the tensor product.</p>
<p>Note that even a 500-qubit system requires <mathjax>$2^{500}$</mathjax> complex numbers to
describe. This number is larger than the number of particles in the
universe; larger than the estimated age of the universe in femtoseconds;
even larger than the product of these two numbers. This just comes from the
basic axioms of quantum mechanics. In order to even remember the state of
this 500-qubit system -- just to remember that state, it's almost as if
nature has <mathjax>$2^{500}$</mathjax> pieces of scratch paper lying around somewhere.</p>
<p>Moreover, if the system interacts with something else, with the outside
world, the state needs to be updated -- it needs to be updated, even, at
every moment in time, at every smallest time step. If this were not a
theory which we read about in a science class, it's insane to think that
this is how hard nature must work to keep this tiny system going.</p>
<p>You have a choice, now. You can either get stuck in this philosophical
mode, or ignore how nature stores this information and just focus on how to
make use of this. A computer, once you get past the packaging, is just an
experiment in physics. The only difference between a computer and an
experiment in physics is that in an experiment in physics, you're trying to
understand how physics works, whereas when you're using a computer, you
already understand the physics and are just tricking nature to solve
interesting problems for you.</p>
<p>Furthermore, remember that entanglement disrupts the principle of locality.</p>
<p>So why use classical computers, when nature is working so hard to keep
track of these quantum systems?</p>
<p>It's almost as if quantum systems have the ability to store and process
exponential amounts of information. It's rather exciting: quantum mechanics
tells us that nature is exponentially extravagant. So you could solve
problems exponentially faster. But nature is extremely private. When you
make a measurement, all you see is one of these values. So this is the main
problem in quantum computing. You have this entity who, behind the scenes
is carrying out these totally extravagant gyrations, computations, and you
think to yourself, if we took our most difficult problems and mapped it
onto that? Except that nature also guards all of this very
jealously. Whenever you try to query, nature, tries to pretend nothing much
was going on.</p>
<p>So what quantum computation is about is trying to tease this information
out of nature. How do you design algorithms where you can really map the
question, the problem of interest, into this space such that even the
outcome of the measurement tells you a lot about the system?</p>
<p>We somehow take this 500-qubit system, put it into some state, and set it
to evolve over time. At the end of this time evolution, we make a
measurement and just get back 500 measly classical bits. We say to
ourselves, we couldn't have gotten them ourselves. Either these are the
solution to our problem, or we can post-process them very quickly to get
our solution. Even though this <mathjax>$x$</mathjax> doesn't seem like much, there was a lot
going on to create <mathjax>$x$</mathjax>, and we can extract this information from <mathjax>$x$</mathjax>.</p>
<p>What we can solve in this manner are questions in the form of
puzzles. [ Description of NP-complete problems. ]</p>
<p>For example, the quantum algorithm for factoring, where you're given some
semiprime <mathjax>$n \equiv pq$</mathjax> (although not really necessary) as input. We'll create some
sequence of superpositions, and we'll get <mathjax>$x$</mathjax>.</p>
<p>If <mathjax>$n$</mathjax> were a few hundred bits, <mathjax>$x$</mathjax> would be a few hundred bits, and we'd
be able to extract <mathjax>$p$</mathjax> and <mathjax>$q$</mathjax> in a fairly straightforward manner from
here. Except classically, this would take exponential time to compute (in a
few hundred bits).</p>
<p>What are the tools we'll be using? Hadamard gate, which is a one-qubit gate
corresponding to the two-dimensional DFT, or changing from the bit basis to
the sign basis (namely, between conjugate bases). This is our quantum
Fourier transform, most likely.</p>
<p>What we'll do next time is understand the transformation corresponding to
performing a Hadamard on every individual qubit.</p>
<p><a name='13'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Algorithms</h1>
<h2>Mar 1, 2012</h2>
<p>Now, let me tell you what quantum algorithms look like. You have your
qubits feeding in, and you might have your input x, have a number of work
qubits initialized to <mathjax>$\ket{0}$</mathjax>, and you have your outputs. What we might
do is measure some subset of your output bits. And then what you might do
some classical post-processing.</p>
<p>So what happens inside the box? Inside the box, you have quantum gates that
form some sort of circuit.</p>
<p>For us, the star is the Hadamard transform (for now). Later, it'll be the
QFT, but the Hadamard is a good place to start.</p>
<p>Remember what we said was that we had n qubits. We'll call this <mathjax>$H^{\otimes
n}$</mathjax> (an n-fold tensor product of 1-fold Hadamards). Suppose <mathjax>$H^{\otimes
n}\ket{0^n}$</mathjax>. What's the output? <mathjax>$\sum_{\ket{x}\in \{0,1\}^n} \frac{1}
{\sqrt{2}^n}\ket{x}$</mathjax>. Suppose <mathjax>$u$</mathjax> is some n-bit string. Now what's the
output?</p>
<p><a name='14'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Algorithms</h1>
<h2>Mar 6, 2012</h2>
<p>Today, we are going to resume our study of quantum algorithms, but I'll
start with the basics of what it means to have a quantum circuit in the
first place, and then we'll move on to a quantum algorithm.</p>
<p>Let's start with the first part, which is about the basics of designing
quantum algorithms. What circuits does one use, what does it mean to design
a circuit; things like that.</p>
<p>First question: Quantum computers are a) digital, b) analog. Why digital?
Input is a sequence of zeroes and ones; we input our qubits in some digital
form. Output is also in the form of zeroes of ones -- concept of
measurements.</p>
<p>Internally, qubits look both digital as well as analog: coefficient looks
analog; ket is digital. Really the coefficients are not analog, since we do
not care too much about infinite precision (cannot care, really). Where
else does it come from? It is unitary.</p>
<p>So it's not as though these are going to have chaotic dynamics; being off
by a little step doesn't spell the end of the world. No butterfly effect.</p>
<p>So that's lesson number one.</p>
<p>Lesson number two. So how did we actually design classical qubits,
classical circuits? There is this concept that certain gates that are
universal, e.g. NAND. Talk about how to construct all possible two-input
gates with NAND.</p>
<p>So: quantum gates. We have various examples of quantum gates, e.g. CNOT, H,
X, Z, <mathjax>$\frac{\pi}{8}$</mathjax> rotations. So what do these mean? Suppose you have an
arbitrary gate U that we want to implement. Maybe it's a two-qubit gate;
maybe three; maybe one.</p>
<p>Remember, in this case, we can specify U by 16 complex numbers. But these
have infinite precision. We are not going to be able to implement infinite
precision with finitely many bits. So what we want to do is implement
something that is <mathjax>$\epsilon$</mathjax> close to this. Instead use universal gates to
implement <mathjax>$U_\epsilon$</mathjax>. We'll measure this <mathjax>$\epsilon$</mathjax>, and we'll claim that
these two transformations are very close to each other (i.e. identical
states are sent to similar states; only changes distance by at most
<mathjax>$\epsilon$</mathjax>).</p>
<p>Also, the cost in terms of <mathjax>$\epsilon$</mathjax> is not going to be very large. The
number of universal gates will scale just as <mathjax>$\log^2\frac{1}{\epsilon}$</mathjax>. So
all this, we're just going to take for granted. In fact, in our quantum
algorithms, we'll use relatively simple-looking gates.</p>
<p>So far, what we've learned is that quantum computers are digital, and
there's a universal family of gates.</p>
<p>These were both ways in which quantum computers were similar to classical
computers. Now let's start exploring the differences.</p>
<p>The first difference is that quantum computers are reversible.</p>
<p>You have some quantum circuit. It takes as input some number of qubits,
outputs the same number of qubits. Inside you have quantum gates. That is
your quantum circuit. <mathjax>$U_c$</mathjax> is unitary, which means that <mathjax>$U_c^{-1} =
U_c^\dag$</mathjax>. In general, you will still get the mirror image, except you will
replace each gate by its Hermitian conjugate.</p>
<p>So now we have a problem. Suppose we have a classical circuit <mathjax>$C_n$</mathjax> for
computing f. Now suppose <mathjax>$f$</mathjax> is a boolean function, so <mathjax>$f(x)$</mathjax> is just a
bit. Imagine there was a quantum circuit for doing this. We really are
computing all n bits. These other bits, together with f, allow us to
reconstruct <mathjax>$x$</mathjax>. Since quantum computers are reversible, any arbitrary
circuit is just a injective map.</p>
<p>Remember our basic classical circuit, our NAND gate. This was not injective
-- it mapped four possible inputs to two possible outputs.</p>
<p>Let's remember this qwuestion: why can't you just discard the bits that you
don't need? It turns out, this is a very crucial issue in quantum computing.</p>
<p>If this is a constraint that we have on our quantum circuits (unitary), we
have to do something: we have to make our classical circuits look like
this. We'll show that we can take any classical circuit and make it
reversible. So given a classical circuit, first make it reversible, then
we'll simulate it quantumly. That is our answer.</p>
<p>So how to make classical reversible computation? What you must do, if
you're doing classical computation reversibly, the first thing you must do
is increase the number of inputs. Now, being reversible means that it has
to be true at every step. You can't possibly throw away anything. You can't
ever discard information: you can transform it, but you cannot discard
it.</p>
<p>So now, what this shows is that you can take any classical circuit <mathjax>$C$</mathjax>
which has NOT gates and AND gates, and you can transform it into a
reversible circuit <mathjax>$R_c$</mathjax> with more outputs (we need these to maintain
injectivity). We don't like this junk. What we'd like is to further
transform this into a circuit of the kind that we really like, <mathjax>$\hat{R_c}$</mathjax>,
that preserves the inputs as well as the desirable outputs.</p>
<p>The secret lies with the <mathjax>$CNOT$</mathjax>.</p>
<p>Back to what we did last time: suppose you had a boolean function <mathjax>$f$</mathjax> and a
circuit <mathjax>$C$</mathjax> that represented it. Now suppose you have a quantum equivalent
<mathjax>$U_f$</mathjax>. What we said was that since this is now a quantum circuit, we can
run it over a superposition of inputs.</p>
<p>Let's say you have a qubit that you feed into this circuit. What the
circuit does for you is it creates junk. It happens to be a CNOT
gate. Meaning, this was a circuit that on input <mathjax>$\ket{x0}$</mathjax> outputs
<mathjax>$\ket{xx}$</mathjax>. However, suppose that we intended to do a Hadamard
transform. The "junk" prevents the interference that we desire. This is why
we do not leave junk lying around: we generally do not know what
interference it will cause, or where.</p>
<p>There's a corollary to all of this: <strong>throwing away / discarding is the
same thing as measurement.</strong></p>
<p>So in other words, what all this shows you is that if you had a qubit and
wanted to measure it, one way to measure it would be to throw it away and
never interact with it again.</p>
<p>Claim: Measuring in the standard basis is equivalent to doing a CNOT, and
then continuing.</p>
<p><a name='15'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Simon's Algorithm</h1>
<h2>Mar 8, 2012</h2>
<p>We're still working in this toy model. Last time, we showed that we can get
some sort of speedup for Fourier sampling. While this was on the order of
n, we can actually get a speedup of <mathjax>$2^n$</mathjax></p>
<h2>Review of Fourier sampling</h2>
<p>Applying a Hadamard transform to all inputs, we get somme sort of analogue
to the FFT.</p>
<p>Adding slit patterns (going back and considering double-slit
experiment). Input corresponds to the slit pattern. And then, given the
slit pattern, we say it is hard to figure out what the interference pattern
looks like.</p>
<h2>Simon's Algorithm</h2>
<p>We are given a circuit that computes a function. f is 2-1. Namely, there
are <mathjax>$2^n$</mathjax> possible inputs, and there are <mathjax>$2^{n-1}$</mathjax> possible outputs in a
particular way: there is some secret s of length n, and we know that <mathjax>$f(x)
= f(x \oplus s)$</mathjax>. Other than that, it could be anything. What you want to
do is find <mathjax>$s$</mathjax>.</p>
<p>Let <mathjax>$n = 3$</mathjax>. Let <mathjax>$s = 101$</mathjax>. So:</p>
<p><mathjax>$$f(000) = f(101) \equiv 000
\\ f(001) = f(100) \equiv 010
\\ f(010) = f(111) \equiv 001
\\ f(001) = f(110) \equiv 100
$$</mathjax></p>
<p>So how do you find s? Classically, you'd find two inputs that map to the
same string. You'd expect this to take roughly <mathjax>$2^{n/2}$</mathjax> tries: consider
birthday paradox. What this is saying is classically, this is a hard
problem. And now we are going to see how to solve this quantumly in <mathjax>$n$</mathjax> or
<mathjax>$n^2$</mathjax> steps.</p>
<p>The first thing we are going to do is take this circuit (remember that if
we can compute something, we can also compute it reversibly) and write down
the reverse of this circuit.</p>
<p>Once this is a reversible circuit, we can also implement every gate
quantumly. We then map this to a quantum circuit which does the exact same
thing.</p>
<p>With the quantum circuit, you can input a superposition, and you'll get a
superposition of the outputs as your result. We've seen this before in the
form of phase states, but we'll use this in a different manner today.</p>
<p>Example:</p>
<p>We start with the Hadamard transform, <mathjax>$H^{\otimes n}$</mathjax>, and we feed in
zeroes. So what's the state at this point? It's a total superposition of
all states. After we feed this into our circuit, our state is a
superposition of the sum over all x of f(x).</p>
<p>Working through the math, we find that we get a random <mathjax>$y$</mathjax> such that <mathjax>$s
\cdot y = 0$</mathjax>. Thus we have a single linear equation, and so we just need
<mathjax>$n-1$</mathjax> equations to uniquely solve for s.</p>
<p>Okay. So let's go back and look at a general circuit. So we start with n
zeroes, do a Hadamard to get into a superposition of all possible
inputs. Now we are in the state where we have every <mathjax>$n$</mathjax>-bit state with equal
amplitude, but now it's entangled with this other register <mathjax>$f(x)$</mathjax>. At this
point, we measure these n bits (and we see some <mathjax>$f(z)$</mathjax>) -- and so we got
some random input.</p>
<p>Now we do another Hadamard transform and another measurement. We want to
figure out what we get as the result of this second measurement. We claim
that our output is a random <mathjax>$y$</mathjax> such that <mathjax>$y \cdot s = 0$</mathjax>.</p>
<p>This is what we said before, but now more general.</p>
<p>Let's prove this. After the Hadamard, let's say we're in a state <mathjax>$\sum_y
\alpha_y \ket{y}$</mathjax>; <mathjax>$\alpha_y = \frac{1}{\sqrt{2}}(-1)^{z \cdot y} +
\frac{1}{\sqrt{2}}(-1)^{s \ cdot y}$</mathjax>. Now, we can see that this is equal to
zero if <mathjax>$s \cdot y = 1$</mathjax> and two if <mathjax>$s \cdot y = 0$</mathjax>. Therefore the only
values remaining in this superposition are those such that <mathjax>$s \cdot y = 0$</mathjax>.</p>
<p><a name='16'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Algorithms</h1>
<h2>Mar 13, 2012</h2>
<p>Today, we are going to set things up for the quantum factoring algorithm,
which we will cover on Thursday. To do that, we have to generalize the
Hadamard transform into the quantum Fourier transform. What we are going to
cover is the quantum Fourier transform: its properties as well as how to
use it.</p>
<p>Today, we'll regard period-finding as an abstract problem we want to
solve. Next time, we'll show how to use period-finding to factor.</p>
<p>So what's a quantum Fourier transform? It's really a quantum implementation
of the discrete Fourier transform.</p>
<p>So if <mathjax>$\omega$</mathjax> is a primitive nth root of unity, then all of the powers
<mathjax>$\omega^j$</mathjax> are also roots of unity.</p>
<p>So the quantum Fourier transform is going to look just like the Hadamard
transform except there are phases in it.</p>
<h2>The discrete Fourier transform</h2>
<p><mathjax>$$
F = \frac{1}{\sqrt{n}}\begin{pmatrix}
1 &amp; 1 &amp; .. &amp; 1
\\ 1 &amp; \omega &amp; \omega^2 &amp; .
\\ . &amp; . &amp; . &amp; . &amp; .
\\ 1 &amp; . &amp; . &amp; . &amp; .
\end{pmatrix}
$$</mathjax></p>
<p><mathjax>$F_{jk}  = e^{ijk2\pi/n}$</mathjax></p>
<p>Primitive square root of unity: <mathjax>$e^{i2\pi n}$</mathjax>. When we do <mathjax>$F_n$</mathjax>, it's the
same, but with phases.</p>
<h2>Showing that <mathjax>$\braket{F_i}{F_j} = \delta_{ij}$</mathjax>...Properties of the Fourier Transform</h2>
<p>This is a proper circuit, and in fact, you can implement it very very
efficiently.</p>
<p>The QFT is very efficient to implement by a quantum circuit.</p>
<p>Let's talk about what you'd get if you tried to implement it.</p>
<p>Considerations with regards to cyclic shifts: effect only shows up in
phases.</p>
<p>So by the way: in quantum computing, what is the significance of phases?
They don't matter in the context of a measurement.</p>
<p>To eliminate effects of relative phase, we do a Fourier transform and then
measure. Basically, multiplication-convolution property.</p>
<p>One more property of Fourier transforms, and then big picture.</p>
<p>The next property is the periodicity property of Fourier transforms. Part
of a much more general property that we won't talk about.</p>
<p>Suppose that <mathjax>$k\divides N$</mathjax>. Suppose that our superposition has period
k. The claim is that if you do a Fourier transform, you get something
that's periodic with period <mathjax>$N/k$</mathjax> (time-frequency uncertainty
principle).</p>
<p>Note that this quantum Fourier transform can be implemented in <mathjax>$O(\log n)$</mathjax>
qubits, but only gives us the value at one index.</p>
<p>What I'll do for next time is to sweep some things under the rug; try to do
these things so very cleverly that you don't notice. Furthermore,
sometimes, if you see things too slowly, it's hard to understand. So next
time, I'll work hard to make sure that you see the big picture. So if
there's one lecture where you come in and think that you're going to be
fully alert, next time should be it.</p>
<p><a name='17'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Factoring</h1>
<h2>Mar 15, 2012</h2>
<h1>Introduction</h1>
<p>Turns out that if you want to factor a number, it is sufficient to show
that we just need to split it up into its components.</p>
<p>The length of the input is <mathjax>$\log N$</mathjax>. That is, the number of bits.</p>
<p>So let's say that we've got a 1024-bit semiprime N. Linear is not at all
feasible -- larger number than age of universe in femtoseconds. So what we
want is to factor this in <mathjax>$\log N$</mathjax>. The best classical algorithms we have
run in some sort of exponential time.</p>
<p>So what we can see is a quantum algorithm that runs in time <mathjax>$\log^3 N or
\log^2 N$</mathjax>. All that matters is that it's polynomial with respect to <mathjax>$\log
N$</mathjax>. Now, factoring is extremely important because it is used in
cryptography -- RSA (which is behind various cryptographic schemes like
TLS).</p>
<p>Two things we'll need to understand: quantum subroutine -- finding the
period of a periodic function, and show how we can solve factoring using
this subroutine. For that, we'll need to understand something about modular
arithmetic. We'll use these to show how to go to factoring in polynomial
time.</p>
<h1>Period-finding</h1>
<p>Given a periodic function f with period k such that <mathjax>$\{0, 1, ..., M-1\}
\mapsto S$</mathjax> (i.e. <mathjax>$f(x) = f(x+k)$</mathjax>), assuming that we are working <mathjax>$\mod M$</mathjax>,
and k divides N, the challenge is to find k.</p>
<p>To appreciate this problem, think of M and k as being very large. You are
given some circuit for computing f: you input x, and you get as output
<mathjax>$f(x)$</mathjax>. This is a little like Simon's algorithm.</p>
<p>Now we're going to use M as the dimension of our quantum Fourier
transform. We'll do this quickly and somehow output k. So let's see how we
do that.</p>
<p>Recall properties of Fourier transform: convolution-multiplication property
(this manifests as phases applied to the output, and upon measurement, this
phase conveniently drops out), treatment of periodic functions (<mathjax>$\sum \ket
{jk} \fourier \sum \ket{j\frac{N}{k}}$</mathjax>) -- output is also periodic.</p>
<p>Our period-finding circuit will look very familiar. What we do is start
with a Fourier transform of dimension M, and input the state zero into this
Fourier transform. The result is a superposition over all states.</p>
<p>Now, let's feed this into <mathjax>$U_f$</mathjax> (with enough scratch zeroes to fill all the
inputs), then measure the second register. Suppose we get some z as the
result of our measurement. What must the first register of <mathjax>$U_f$</mathjax> be? A
superposition over all the states equal to <mathjax>$z \mod k$</mathjax> (<mathjax>$\sqrt{\frac{k}{m}}
\sum_j\ket{jk + z}$</mathjax>). Now, if you measure this, you get a random number
<mathjax>$mod M$</mathjax>, which gives us nothing.</p>
<p>So what we want to do, therefore, is put this z into the phase so we can
ignore it, i.e. feed this into the quantum Fourier transform. Now we want
to measure. Now, measuring, we get some <mathjax>$r\frac{M}{k}$</mathjax>, where r is some
random integer between 0 and <mathjax>$k-1$</mathjax>. Recall, what we want is k. We can
consider the gcd of different measurements. Presumably if we sample a few
times and take the gcd, then this will readily lead to our goal. (note that
our samples must be collectively relatively prime in order for us to get
the correct answer, so <mathjax>$\log N$</mathjax> samples is an approximate upper bound).</p>
<p>Note that the gcd can be found quickly using Euclid's algorithm.</p>
<h1>Shor's Algorithm</h1>
<p>So now we want to factor. This algorithm works for any number, but for now,
we're concerned only with semiprimes: <mathjax>$N = pq$</mathjax>, for <mathjax>$p,q$</mathjax> prime.</p>
<p>Here's a claim: Given that you can solve this problem (order-finding), then
you can factor. Let <mathjax>$ord_N(x) =$</mathjax> order of <mathjax>$x$</mathjax>. (the minimum <mathjax>$r &gt; 0$</mathjax> such
that <mathjax>$x^r = 1 (\mod N)$</mathjax> -- this exists iff x relatively prime to N
(Fermat's Little Theorem). This assumes that <mathjax>$\mathtt{gcd}(x,N) = 1$</mathjax> -- if
it isn't, then we can trivially factor.</p>
<p>The claim is that if you can find the order of <mathjax>$x \mod N$</mathjax>, you can
factor. Classically, this wasn't even considered because finding the order
of <mathjax>$x$</mathjax> was potentially more difficult than factoring. But now we have this
completely magical period-finding algorithm.</p>
<p>Claim: if the order is even and <mathjax>$x^{r/2} \neq -1$</mathjax>, one factor is either
<mathjax>$gcd(N, x^{r/2} - 1)$</mathjax> or <mathjax>$gcd(N, x^{r-2} + 1)$</mathjax>. Somehow, once you've
figured out the order, it's easy to find the factors: this is for a very
good reason.</p>
<p>There's a secret fact: if N is a composite, when you take the square root
of one, you have more than just <mathjax>$\pm 1$</mathjax>. These square roots are great,
because once you've found them, you've factored the number.</p>
<p>Consider this:</p>
<p><mathjax>$$\newcommand{\divides}{\big|}
x^{r/2} \neq \pm 1
\\ y \neq \pm 1
\\ y \pm 0
\\ N \not\divides\;\; y
$$</mathjax></p>
<p>Thus</p>
<p><mathjax>$$
x^r = 1
\\ y^2 = 1
\\ y^2 - 1 = 0
\\ N \divides y^2 - 1
\\ N \divides (y+1)(y-1)
$$</mathjax></p>
<p>We exploit the periodicity of modular exponentiation: f is periodic with
period r (the order). Thus we can use the period-finding algorithm to
determine the order of x.</p>
<p>Thus to factor N, we pick x at random mod N and use the function <mathjax>$f(a) =
x^a$</mathjax> in our period-finding subroutine. What does a subroutine do? We invoke
the subroutine many times, and each time we get some number, and we take
the gcd... and eventually, from the subroutine, we get r.</p>
<p>Repeat this until r is even and <mathjax>$x^{r/2} \equiv -1$</mathjax>.</p>
<p>Compute <mathjax>$gcd(x^{r/2} + 1, N)$</mathjax> and output this.</p>
<h1>Recap</h1>
<p>Note that what we stressed here was the quantum part of this algorithm. If
you wish, you can see the details of the modular arithmetic: chapter 0
in CS170 text. For those of you who have the background, last chapter.</p>
<p><a name='18'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Search</h1>
<h2>Mar 20, 2012</h2>
<p>This is the main problem with quantum algorithms, that you're sort of
searching for a needle in a haystack.</p>
<p>So how long does it take? Usually a function of how large the haystack
is. One way to think of it is that you have a table with n entries, and one
of these is marked, and you're looking for the marked entry.</p>
<p>So classically, you could of course try every entry until you find the
marked one, which takes on the order of n steps. Randomized, you could
expect to find it halfway through your search.</p>
<p>What we're going to see today is called Grover's algorithm. It's a quantum
algorithm that does this in <mathjax>$\sqrt{n}$</mathjax> steps. It's very strange in that you
get to know without looking at all of the steps.</p>
<p>So... what does this have to do with anything? In general, when we are
trying to find an algorithm for something (when we are trying to solve a
computational problem), our problem is as follows: given some input x, we
want to find something. Whether this is 3-SAT, TSP, factoring; we want to
find some output (answer).</p>
<p>Often finding the answer is difficult, but once you have it, you can
convince yourself that it's a good answer (i.e. it's in NP).</p>
<p>There's a real dichotomy: searching for an answer might be exponentially
hard, but checking said answer is easy (i.e. verifiable in polynomial
time).</p>
<p>It turns out that even though checking the answer is easy, we <em>believe</em>
that finding the answer is hard. There are all sorts of problems in
here. We strongly believe that <mathjax>$\mathrm{P} \neq \mathrm{NP}$</mathjax>. What we can
show is that if there are hard problems, then the NP-complete problems are
definitely hard.</p>
<p>Remember, all NP-complete problems are just search problems. So this
searching for a needle in a haystack is actually at the crux of these
problems.</p>
<p>Thus with Grover's algorithm, we can get a quadratic speedup for these
NP-complete problems.</p>
<p>Given a function <mathjax>$f \{1 .. N\} \mapsto \{0, 1\}$</mathjax>, find x such that <mathjax>$f(x) =
1$</mathjax>. We'll focus on the hardest case where we have only one possible x.</p>
<p>We could also convert this into a quantum circuit. Now, we can feed in a
superposition of states, and you'll get the same superposition of
corresponding outputs.</p>
<h1>What the algorithm will do</h1>
<p>Let's consider <mathjax>$N = 2^n$</mathjax>. The way our algorithm will work is that it'll
start with this superposition of all these states. How do we do that? A
Hadamard.</p>
<p>Then we apply the function, then apply a bit flip (X). All of the states of
our superposition that correspond to zeroes are now ones, and the one state
that corresponds to one is now zero.</p>
<p>If you were to consider these amplitudes and compute the arithmetic mean,
it's approximately <mathjax>$\frac{1}{\sqrt{N}}$</mathjax>. So what we're going to do is this
really funny operation; we're going to reflect all these amplitudes about
the mean. If it's above the mean, it goes below the mean by an equal
amount; if it's below the mean, it goes above the mean by an equal
amount. We can iterate this until roughly the halfway point.</p>
<p>This particular algorithm is called the quantum algorithm for searching a
database, which is nonsense. In order to use a quantum algorithm, you must
first feed the entire database into the quantum algorithm. Even if
searching took a single step, you've already taken n steps to convert it.</p>
<p>The entire point of this algorithm is to search for a Travelling Salesman
path, for instance.</p>
<h1>Implementing</h1>
<p>We'll start by doing a Hadamard on our original state of zeroes, and now
we'll have our superposition over all states.</p>
<p>For the second step, the suggestion is that we should use the circuit for
<mathjax>$f(x)$</mathjax>.</p>
<p>The third step is strange: it's a reflection about the mean. So what's the
mean? <mathjax>$\mu = \sum x\alpha^2_x \ket{\alpha_x}$</mathjax>. Let's first understand what
it means to reflect about the state <mathjax>$\ket{0^n}$</mathjax>. We leave alone the
component in the <mathjax>$\ket{0^n}$</mathjax> direction and flip the phase of every other
component. So a reflection about <mathjax>$\ket{0^n}$</mathjax> would look like
<mathjax>$\begin{pmatrix} 1 &amp; 0 &amp; 0 &amp; ... \\ 0 &amp; -1 &amp; 0 &amp; ... \\ 0 &amp; 0 &amp; -1 &amp; ... \\
... &amp; ... &amp; ... &amp; ...\end{pmatrix}$</mathjax>. So how do we do this for the uniform
vector? We simply do a change of basis such that this is our zero vector,
do this operation, then revert our basis. This is usually called D, our
diffusion operator. <mathjax>$D = H^{\otimes n} Z^\prime H^{\otimes n}$</mathjax>.</p>
<p>Replacing each <mathjax>$\alpha_j$</mathjax> with <mathjax>$\beta_j \equiv 2\mu - \alpha_j$</mathjax> is just the
reflection about the mean.</p>
<h1>Actual circuit</h1>
<p>We know how to do the first two stages. Then we want this special
transformation: first do a Hadamard, then reflect about <mathjax>$\ket{0^n}$</mathjax>. We
have a function that outputs one whenever this isn't <mathjax>$\ket{0^n}$</mathjax> --
something we can implement classically, so this is not a problem -- then we
can feed this into our conditional phase flip.</p>
<p>The important thing about these algorithms is that they have special
structure, and so they have small corresponding quantum circuits.</p>
<p><a name='19'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Guest lectures: implementation of qubits</h1>
<h2>April 3, 2012</h2>
<p>Kevin Young: kcyoung@berkeley.edu</p>
<p>We'll start with how to implement qubits using spins, and eventually
culminate in NMR.</p>
<p>Today, what we're going to do is start looking at physical implementations
of QC. Will continue through the end of next week. How to build an actual
physical quantum computer. Implementation choice: NMR (one of first QC
where a quantum algorithm was demonstrated).</p>
<p>Start with basics, i.e. fundamental building blocks: spin qubits. Approach:
start with experiments people did quite a while ago, back when people were
still trying to understand QM, what systems were quantized. The experiments
we're going to look at, we're going to use their results to build up a
physical theory and apply this theory to qubits. We're going to look at how
this gives us nice pictures to use.</p>
<p>Ultimate goal of lecture: understand how to write down the state and work
with the state of a two-level system.</p>
<p>We're going to start out with some experimental results, assuming we know
enough QM to push us along a little bit: understand quantum states and how
they work. Not going to necessarily understand right away what quantum
model we can use to describe these experiments.</p>
<p>Backdrop: look at experiment called the Stern-Gerlach device. Conflicting
theories about how magnetic field of small atoms should behave. Two
theories. One: electrons should act like little tiny bar magnets ("bar
magnet theory") -- one feature: these acted like classical bar magnets --
magnetic dipoles that can be oriented arbitrarily in a magnetic field. Two:
in light of all this new QM, in the presence of a magnetic field, then this
bar magnet should only take one of two possible directions: up and down
(quantum theory).</p>
<p>Simple experiment: looking at how classical bar magnets behave in magnetic
fields. Background: if I put a bar magnet in a magnetic field, the
classical description corresponds to how much energy it has depending on
its orientation. Since bar magnets like to align with magnetic fields, you
can write down that energy <mathjax>$U = -\vec{\mu} \cdot \vec{B}$</mathjax>. B is the
magnetic field; <mathjax>$\mu$</mathjax> is the magnetic dipole moment. If parallel, we have a
relative energy of -1, and if antiparallel, we have a relative energy of 1
(relatively high energy). Shows that dipole likes to be aligned with
magnetic field.</p>
<p>What Stern and Gerlach noticed was that we can separate out parallel from
antiparallel by making the magnetic field not constant. The magnetic moment
is aligned with the field, so in this case, energy is just <mathjax>$-\mu B$</mathjax>. So the
energy will go down if magnetic field goes up. Reasoning: objects want to
move to lower potentials. Wants to bend toward area where potential energy
is lower. If dipole is pointed up, it'll move and point down.</p>
<p>Now let's say we had an oven, and by saying it's an oven, we mean that it
just spits out a continuous stream of these quantum or classical dipoles of
totally random spins (as random as the theory will allow), and we connect
the output of this oven to a SG machine. Let's say we have quantum dipoles
coming out of that oven. In the quantum model, on the screen, we will see
two points (for the most part). The classical theory predicts a continuous
distribution.</p>
<p>Saw two peaks.</p>
<p>Reasoning for the classical result to not be flat: orientation is uniformly
chosen from points on unit sphere.</p>
<p>Argument of Summerfeld (quantum theory): wrong theory, but correct results.</p>
<p>So more playing around with SG experiment. Oven spits out these completely
random quantum particles. And then it hits this device. One of the things
we need to do is give it a label corresponding to direction of magnetic
field. We can label this by <mathjax>$\hat{n}$</mathjax>. What we're going to get out is two
beams. We're going to label these two beams the same way we labeled the SG
device. We'll label the top one using some quantum notation we've already
learned. For now, we'll call these <mathjax>$\ket{\hat{n}^+}$</mathjax> and
<mathjax>$\ket{\hat{n}^-}$</mathjax>. Check if these are appropriate labels by feeding into a
second SG device, also pointing the same direction.</p>
<p>Saw only one beam coming out in the same direction as the other one. This
is a little bit affirming. I can do an experiment that is effectively
measuring something: the alignment (or anti-alignment) with the field lines
of the box. Measurements; since we measure again in the same basis, we get
the same result.</p>
<p>Nice, interesting result, but now let's change the situation again. Now we
have <mathjax>$\hat{n}$</mathjax>, and we only let <mathjax>$\ket{\hat{n^+}}$</mathjax> through. Now this second
box is pointed in a different direction. What do we get if m is very close
to n?  <mathjax>$\ket{\hat{m}^+}$</mathjax> is very bright (relatively). Probability of <mathjax>$+$</mathjax> is
<mathjax>$\frac{1}{2}(1 + \hat{m} \cdot \hat{n})$</mathjax>, and probability of <mathjax>$n$</mathjax> is
<mathjax>$\frac{1}{2}(1 - \hat{m} \cdot \hat{n})$</mathjax>. How do we find probabilities in
QM? Squared inner product.</p>
<p>These equations relate the experiment to a theory we haven't figured out
yet. So we need to figure out a way to describe this. SG as entangling
degrees of freedom.</p>
<p>So: back to what we were talking about before. Must build physical theory
that is consistent with these relationships. One thing we haven't done yet:
(we know these things are quantum states) decide dimensionality. We can
always write these as vectors, but how many numbers are we going to need to
describe these. We need two numbers to describe the points on a
2-sphere. Fundamental: only got two answers out. The simplest picture that
you could imagine is that you have a 2-level quantum system. If all of your
experiments could be described by two outputs, then the first thing that it
might be worth trying is describing this quantum state with a
2-vector. Could be wrong, but it's a good place to start.</p>
<p>In physics we really like things that are up and down, so we'll give these
special names. Instead of calling these <mathjax>$\ket{z^+}$</mathjax> and <mathjax>$\ket{z^-}$</mathjax>, we'll
call these <mathjax>$\ket{0}$</mathjax> and <mathjax>$\ket{1}$</mathjax>. Represent all these <mathjax>$\hat{n}$</mathjax> states in
terms of <mathjax>$\ket{0}$</mathjax> and <mathjax>$\ket{1}$</mathjax>. We know that if in fact our system is a
2-dimensional quantum system, <mathjax>$\hat{n} = \alpha\ket{0} + \beta\ket{1}$</mathjax>. So
what we're going to figure out is if we can determine <mathjax>$\alpha,
\beta$</mathjax>. Something useful: go back to polar (spherical) coords. What we're
going to do now is see if we can figure out something about <mathjax>$\alpha$</mathjax>,
<mathjax>$\beta$</mathjax>. We know that if we choose <mathjax>$\ket{0}$</mathjax>, then <mathjax>$\ket{0} \equiv
\ket{z^+}$</mathjax>. (z is direction SG device points). We want to see if we can
write <mathjax>$\ket{n^+}$</mathjax> in terms of zeros and ones.</p>
<p>Working out the math, we get <mathjax>$\abs{\alpha} = \cos\frac{\theta}{2},
\abs{\beta} = \sin\frac{\theta}{2}$</mathjax>. However, we don't have phases
(yet).</p>
<p>Note that we don't care about absolute phases; relative phases are all that
actually matter (reasoning: we can multiply through by some complex
exponential to cancel out the phase on one term).</p>
<p>Let's say that an x SG device is moving, and it hits a y SG device, and it
outputs <mathjax>$\ket{y^+}, \ket{y^-}$</mathjax>. Only difference between these states is
the absolute phase (rather, the relative phase between the two states).</p>
<p>Working out the math (once again), we get <mathjax>$\frac{1}{2}\parens{1 +
\cos(\lambda_y - \lambda_x)} = \frac{1}{2}$</mathjax>, so <mathjax>$\lambda_y, \lambda_x$</mathjax> are
perpendicular (relative phase is <mathjax>$\frac{\pi}{2}$</mathjax>).</p>
<p>What this tells me is that I can represent any quantum state as a unit
vector. So if I have some state <mathjax>$\ket{n^+}$</mathjax>, I can associate it with a point on
a unit sphere. This picture also tells me that <mathjax>$\ket{n^-}$</mathjax> is the opposite
point on the sphere. Orthogonal states correspond to antiparallel vectors
(antipodal points).</p>
<p><a name='20'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Guest lectures: implementation of qubits</h1>
<h2>April 5, 2012</h2>
<p>Recap: last time, we covered SG machines and the possibility of expressing
states as points on an n-sphere (by specifying n angles). Punchline:
one-to-one correspondence between states in a two-level system and points
on the 2-sphere.</p>
<p>One of the things we did on Tuesday was send these states through devices
that measured their states. Summarizing all we know about measurements: if
we can talk about some measurement (that corresponds to a Hermitian
operator), and we have some device that takes some unknown state
<mathjax>$\ket{\psi}$</mathjax> and output two beams that are orthogonal (on the Bloch-sphere,
these are antipodal points); if I repeat the same measurement immediately,
then we'll get the same result.</p>
<p>A measurement corresponds to a Hermitian operator, and each measurement
outcome is one of the eigenvalues of that operator. Why do we consider
Hermitian operators? Diagonalizable with orthonormal eigenbasis
corresponding to real eigenvalues (i.e. spectral theorem).</p>
<p>What we want to do is construct a matrix to represent this measurement. We
first need some sort of matrix representation of our kets. Taking advantage
of the fact that we have Hermitian operators, some operator Q always has a
diagonalization <mathjax>$SDS^\dag$</mathjax>.</p>
<p>(constructing the bit flip (NOT) gate X, which was most of a problem on the
QM midterm yesterday :D)</p>
<p>One thing that's going to be on your homework is that <mathjax>$S(\hat{n})
\ket{\hat{n}}$</mathjax> is going to be the matrix that returns +1 for</p>
<p>Pauli matrices <mathjax>$Z = \begin{pmatrix}1 &amp; 0 \\ 0 &amp; -1\end{pmatrix}$</mathjax>, <mathjax>$X =
\begin{pmatrix}0 &amp; 1\\ 1 &amp; 0\end{pmatrix}$</mathjax>, <mathjax>$Y = \begin{pmatrix}0 &amp; -i\\ i
&amp; 0 \end{pmatrix}$</mathjax>.</p>
<p>Physicists refer to these as <mathjax>$\sigma_x, \sigma_y, \sigma_z$</mathjax>. These
correspond to some way of measuring the spin. If I send some random state
through here, I can figure out the expectation value of that state using
these operators. Let's say I have some state <mathjax>$\hat{n}$</mathjax>, and I stick it
through the Z block. I'm going to get out some zeros and some ones. I
learned from experiment that the probability of getting zero is
<mathjax>$\frac{1}{2}(1 + \hat{n} \cdot \vec{z})$</mathjax>, etc.</p>
<p>(<mathjax>$\vec{S} \equiv \hat{X}\ket{0} + \hat{Y}\ket{1} + \hat{Z}\ket{2}$</mathjax>; it's a
vector of matrices)</p>
<p>Expectation we can calculate in one of several ways: <mathjax>$\sum_i \prob{x_i}
x_i$</mathjax>; <mathjax>$\braKet{\hat{n}}{Z}{\hat{n}}$</mathjax>. They give the same answer, which is
encouraging.</p>
<p>We can start to write the (quantum) Hamiltonian of the system with
electrons in a magnetic field: <mathjax>$\mu B \cos\theta$</mathjax>. We're assuming <mathjax>$\mu, B$</mathjax>
constant. Considering the Hamiltonian to be <mathjax>$-\mu B\hat{Z}$</mathjax>, the
expectation value is certainly what we expect, so we'll go into a more
advanced case: <mathjax>$H = -\mu \vec{B} \cdot \vec{S}$</mathjax>. In physics, for an
electron, this is the Bohr magneton <mathjax>$-\frac{e\hbar}{2m}$</mathjax>, so it's
negative. NMR uses radio waves; electron spin radiance uses
microwaves. This is just due to the difference in the magneton.</p>
<p>This in a way corresponds to a classical description. The thing is to see
how that Hamiltonian affects states.</p>
<p><mathjax>$H = -\mu_0 B_0 Z$</mathjax>. What describes time evolution of a quantum system?
Time-dependent SE. Solution is <mathjax>$\Psi(t) = \exp(-\frac{i}{\hbar} H t)
\ket{\Psi(0)}$</mathjax>. What this means is that <mathjax>$\ket{\Psi(t + dt)} = (1 -
\frac{i}{\hbar} H dt) \ket{\Psi}$</mathjax>. Taylor series tends to be a terrible way
to exponentiate matrices, since the radius of convergence is really
small. However, we get lucky because these are Hermitian matrices, so they
are diagonalizable with real eigenvalues, which is easy to do quickly.</p>
<p>Pauli matrices are especially nice in that they actually alternate between
themselves and the identity. This has interesting results: <mathjax>$e^{i\theta X} =
I\cos\theta + iX\sin\theta$</mathjax>; <mathjax>$e^{i\theta \hat{n} \cdot \vec{S}} = I \cos
theta + i(\hat{n} \cdot \vec{S})\cos\theta$</mathjax>. This shows up a lot since
physicists tend to pick magnetic field as Z. Originally devised by Zeeman,
so it'll often be known as the Zeeman Hamiltonian or the Zeeman effect.</p>
<p>The system precesses. This misbehavior is analogous to internal angular
momentum in classical mechanics.</p>
<p>Peculiar property of fermions (half-integer spins). Requires two
revolutions. (twists relative to the universe?) At this level, easiest to
understand as the cost of having this nice physical picture. We're really
doing rotations on complex vector spaces.</p>
<p>Limitation of this picture is that it's only half of the representations we
can do in the complex space.</p>
<p><a name='22'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Guest lectures: implementation of qubits</h1>
<h2>April 12, 2012</h2>
<p>(notes from last time were on paper)</p>
<p>One last homework due next week. Will give feedback on projects after
that. 3 multi-part problems. Should not be too hard.</p>
<p>Review: we can do arbitrary single-qubit gates. Wrote down expressions for
doing arbitrary phase rotations. THe simplest model for two qubits
interacting with each other that feels like <mathjax>$H_{int} = J\sigma_z^{(1)}
\otimes \sigma_z^{(2)}$</mathjax>. If we were in a single qubit, we chose special
states: <mathjax>$\ket{0},\ket{1}$</mathjax>. Eigenstates of <mathjax>$\sigma_z$</mathjax>. Arbitrary
superposition of these.</p>
<p>When we have two qubits, we can pick a similar basis, but now our system is
composed of 2 qubits, so we need four basis states (can easily form these
by taking tensor products of our previous basis states).</p>
<p>effective magnetic field of the qubit is itself measured by a Pauli
operator.</p>
<p>If we want to build a matrix representation of an operator, we just need to
know how it acts on each of our basis states. To set up our conventions,
<mathjax>$\sigma_z\ket{0} = 0$</mathjax>; <mathjax>$\sigma_z\ket{1} = -\ket{1}$</mathjax>.</p>
<p>If J positive, favors antialigned (antiferromagnetic); if J negative,
favors aligned (ferromagnetic). Condensed-matter people love to study
antiferromagnetic things. End up with frustration in triangle lattice.</p>
<p>The way we construct the tensor product matrix is by sticking the second
matrix B onto each element of A. What I mean by that is that <mathjax>$A \otimes B
\equiv \begin{pmatrix}A_11 B &amp; A_{12}B &amp; ... \\ A_{21}B &amp; ... &amp; ...
\\ ... &amp; ... &amp; ...\end{pmatrix}$</mathjax>. It's worth your time to convince yourself
that this is the right way to do the tensor product. Think about how you're
writing down your basis states.</p>
<p>Now that we have this operator, let's think about what it does to our
system. Let's look at it strictly from the lab frame. So we're not going to
take out the Larmor precession. Write out full Hamiltonian.</p>
<p><mathjax>$H = \mu_0 B_1 \sigma_z \tensor I - \mu_0 B_2 \sigma_z \otimes I + J
\sigma_z \otimes \sigma_z$</mathjax>. One thing you can do is look at the spectrum of
the Hamiltonian: the available energies (eigenvalues of Hamiltonian).</p>
<p>By putting an interaction on these two qubits, I've given myself some way
of doing a CNOT: a nontrivial tensor product. One thing that is important
is that these qubits are indistinguishable somehow. If I want to control
one but not the other, they need different resonance frequencies. If you're
going to pick some molecule to stick in your quantum computer, you can't
choose one with the usual symmetries. Something like plain acetylene
wouldn't really work wekk: both carbons have the same
environment. Indistinguishable. But by replacing one hydrogen by a
deuterium, we've changed the resonant frequency by just a little bit so
that our system is now resolvable.</p>
<p>Let's go back into a rotating frame. In a rotating frame, what we've done
is subtract out the rotating part of the hamiltonian. We can still do the
same mathematical transformation. Why? These operators commute. Two
different systems, so you can know both simultaneously. No uncertainty
relation.</p>
<p>Notice that the state <mathjax>$\ket{00}$</mathjax> and <mathjax>$\ket{11}$</mathjax> get a positive phase after
some time t, and <mathjax>$\ket{01}$</mathjax> and <mathjax>$\ket{10}$</mathjax> get a negative phase after some
time t. Recall that the <mathjax>$\pi$</mathjax>-pulse changes the parity of a state: it takes
an even-parity state and switches it to an odd parity state.</p>
<p>First is hamiltonian evolution for time <mathjax>$\tau$</mathjax>, and second, we do an X-gate
on the first qubit, and then third, we do hamiltonian evolution again for
<mathjax>$\tau$</mathjax>, and fourth, we do our X-gate again. I'll do 0 explicitly. We start
out in the state <mathjax>$\ket{00}$</mathjax>. Hamiltonian evolution (for this system) under
a time t looks like <mathjax>$e^{-J\tau}\ket{00}$</mathjax>. After the second step, we move
into the state <mathjax>$e^{-J\tau}\ket{10}$</mathjax>. After the third step, we have the
state <mathjax>$e^{J\tau - J\tau}\ket{10}$</mathjax>. And then, after the fourth step, we get
back <mathjax>$\ket{00}$</mathjax>. So by doing this series of operations, I've effectively
eliminated the effect of this hamiltonian (not ideal, but has the same net
result.)</p>
<p>This procedure is going to be very important to us: dipolar
decoupling. It's dipolar because you're dealing with these magnetic
dipoles, and this interaction in a sense couples these two qubits, and
you've turned this interaction off. On Tuesday, we'll talk about dynamic
decoupling, where it's basically the same procedure used to eliminate
noise.</p>
<p>One of the assumptions we've made is that the X-gate is fast compared to
<mathjax>$\tau$</mathjax>. It takes some time to do that X-gate, and while that's happening,
the system is evolving, and so you're accumulating some errors. Problem
with doing these X-gates fast.</p>
<p>Let's think of the exact sequence of controls we need to do to implement a
Bell state. So the first thing we do is the dipolar decoupling, as
discussed, so that we have the same state after some time has elapsed. Now,
we have to do a Hadamard gate: sequence of X, Y pulses that looked like
<mathjax>$X(\pi/2), Y(\pi/4), X(\pi/2)$</mathjax>. Now we want to do a CNOT by applying a
<mathjax>$\pi$</mathjax>-pulse at one of the frequencies.</p>
<p>This sequence of operations gives us exactly the Bell state that we wanted.</p>
<p>When you start building a larger quantum computer, the idle times start
becoming vital: even worse than we've discussed (Tuesday).</p>
<p>A lot of pulse-design for NMR revolves around faulty gates: how can I make
these errors cancel each other out?</p>
<p><a name='23'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Guest lectures: implementation of qubits</h1>
<h2>April 17, 2012</h2>
<p>Last time, we talked about two-qubit gates. Today, we're going to talk
about why NMR quantum computers are not scalable and dephasing/decoherence.</p>
<p>So, one of the most successful demonstrations of an NMR quantum computer so
far was factoring the number 15. Used a molecule <mathjax>$F^{19}C^{13}$</mathjax> as their
nuclear spins, and then iron, etc. In order to construct a molecule to use
it in a quantum computer, each qubit must be in a different local
environment so that the spectrometer can see a different resonant frequency
for each qubit.</p>
<p>Carbon exists with several different isotopes: <mathjax>$C^{13}$</mathjax> has spin
<mathjax>$\frac{1}{2}$</mathjax>, for instance.</p>
<p>Carbons are easy to distinguish. Either surrounded by fluorines (very
electronegative) or irons (metals).</p>
<p>Also not just using one of these: fill up generously-sized sample-holder,
and you end up with ~<mathjax>$10^{22}$</mathjax>. Also important: this system is generally
analysed at room temperature. At room temperature, the effect of thermal
excitations on quantum systems is fairly large. Back-of-the-envelope way of
estimating whether you're in the ground state or not: if your energy gap is
very big compared to <mathjax>$\tau$</mathjax>, you'll likely be in the ground state. But
typically in NMR systems, the converse is true: energy gap is very small.</p>
<h2>Density matrices</h2>
<p>Quantum mechanics is frequently concerned with quantum probabilities
(intensities of the wave function, so to speak). These are not the only
probabilities we can consider.</p>
<p>Person flips a coin. If heads, gives state <mathjax>$\ket{\psi}$</mathjax>. If you're doing an
experiment and measure, what you want to do is describe what's coming out
consistently. One way: describe state as list of tuples,
e.g. [(.5 0) (.5 1)]. Not very useful. Expectation of operator A:
<mathjax>$\braKet{\psi}{A}{\psi}$</mathjax>.</p>
<p>trace of <mathjax>$\rho_A$</mathjax>. Density matrix: if probabilities sum up to 1, trace of
density matrix is 1.</p>
<p>Remember Bloch sphere: states on Bloch sphere describe quantum states. If I
have some probabilistic sum, the density matrix <mathjax>$\rho$</mathjax> is <mathjax>$\sum_k p_k
\ketbra{\psi_k}{\psi_k}$</mathjax>. For a single qubit, I'm interested in making
measurements. The measurements I usually have access to are the Pauli
matrices (plus the identity), which form a basis for all Hermitian matrices
for two-level systems -- quaternion lie group, almost. Pauli matrices are
traceless.</p>
<p>Thus I can write the density matrix in terms of these quaternions. <mathjax>$\rho$</mathjax>,
then, will be <mathjax>$aI + b\sigma_x + c\sigma_y + d\sigma_z$</mathjax>. All I have to do,
now, is figure out a,b,c,d. I know that the trace of <mathjax>$\rho$</mathjax> is 1, so a must
be <mathjax>$\frac{1}{2}$</mathjax>.</p>
<p>Now let's say I want to take the expectation value of <mathjax>$\sigma_x$</mathjax>. That's
equal to the trace of <mathjax>$\rho \sigma_x$</mathjax>. Working this out, we get b is
<mathjax>$\frac{1}{2}\avg{\sigma_x}$</mathjax>. The rest follows in a similar
manner. (remember that <mathjax>$\sigma_i\sigma_j = \sigma_k\epsilon{ijk} +
\sigma_i\delta_{ij}$</mathjax>)</p>
<p>Something else is really nice here: you know that pure states are such that
the expectations of <mathjax>$\sigma_x$</mathjax>, <mathjax>$\sigma_y$</mathjax>, <mathjax>$\sigma_z$</mathjax> are easy to
calculate: the state is an eigenstate of <mathjax>$\hat{n} \cdot \vec{S}$</mathjax>.</p>
<p>We can now say something: pure states live on the Bloch sphere, while mixed
states live within the Bloch sphere.</p>
<p>No measurements that can distinguish between states with same density
matrix. Completely mixed state.</p>
<h2>Decoherence</h2>
<p>How these things evolve over time. Populations, coherences. Time evolution:
rewrite as <mathjax>$\int p_b \rho_b db$</mathjax>.</p>
<p>Populations and coherences: intuition is notion of coherent superposition
vs. incoherent superposition (classical prob. of up, classical prob. of
down; off-diagonal terms are 0).</p>
<p>Start having quantum coherences <mathjax>$\implies$</mathjax> values showing up in
off-diagonal terms.</p>
<p>Magnetic field will just cause phase to go around at some rate.</p>
<p>Hahn (?) echo to extend coherence: only if magnetic field is not
fluctuating. Great at eliminating low-frequency noise.</p>
<p>In an NMR system, you tend to have inhomogeneous broadening.</p>
<p>Decoherence comes in two favors: both flavors are very bad. This is called
dephasing: losing the phase from the system. Typically comes with a time
scale, <mathjax>$t_2$</mathjax>. If you do this series of Hahn echos, the coherence will very
quickly decay. Remember, these magnetic fields are slightly fluctuating.</p>
<p><mathjax>$t_2^*$</mathjax> is decay that gets almost completely eliminated by Hahn echos, so
less relevant, generally.</p>
<p>There's another type of decoherence: suppose I set up my state in the
excited state. Could be noise that relaxes the state to the ground
state. This relaxation is given by time <mathjax>$t_1$</mathjax>. If you set up some state on
the Bloch sphere, and you don't do your complication very quickly, it'll
start to decohere.</p>
<p><mathjax>$t_2$</mathjax> is controllable. Can utilize correlations of that noise, various
techniques to mitigate its effects. Relaxation very difficult to eliminate:
what you could try is symmetrization. Can never get this echoing
behavior. Eventually, all of these states will go down to the mixed
state. Eventually all the states tend toward the zero state if there's
relaxation.</p>
<p>Decay of magnetization; Bloch equations. Decay in certain directions
corresponds to certain time constants. So that's about everything. Did want
to talk for a few seconds what happens when you try to scale NMR.</p>
<p>Because you have these thermal issues, you can't prepare the ground state
in exactly where you want. You want everything in the ground state. Because
of thermal issues, you have a probability of being in all of the
states. Make something called a pseudo-pure state. <mathjax>$\epsilon$</mathjax> times the
ground state plus <mathjax>$1-\epsilon$</mathjax> times the fully-mixed state. When you start
adding qubits (e.g. with 7), <mathjax>$\epsilon$</mathjax> gets smaller. If you get 100 qubits
(molecule with 100 different spins on it) and a standard sample size,
there's 100 qubits per molecule. There's a 99.9999999% chance you have 0
molecules sitting in the ground state.</p>
<p>Also, the colder your system gets, that's certainly better, but you need to
push those temperatures really low, and at some point you're not doing
liquid-state NMR any more (molecules are just tumbling; dipolar coupling
between molecules balances out, very narrow lines), you're dealing with
solid-state NMR (broadening of lines). Ways of coping: magic-angle spinning
-- narrows lines a bit.</p>
<p>Thursday: Haffner will come back to talk a bit more about another
system. Umesh will then come back to talk about AQC and quantum crypto.</p>
<p><a name='24'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Guest lectures: Experimental Quantum Computing</h1>
<h2>April 19, 2012</h2>
<p>Professor Haffner: will speak about experimental QC. One of leading experts
in ion traps.</p>
<p>Specific impl. of quant. information prcessing. Idea is fueled by building
a scalable quantum processing device for whatever motivation you have. Many
approaches. What people thought 10-15 years ago: landscape has not actually
changed too much in recent years. Couple options shown to not work; most
likely will; and some have made progress.</p>
<p>Implementation of qubits: initialization of quantum registers, logic
operations, maintaining coherence. NMR initially very successfully, but
could be shown that this technology not scalable: exponential cost for
initialization: prob of finding particle in ground state drops
exponentially with no. of qubits because simply the prob of being in ground
state decreases.</p>
<p>Concentration for today: trapped ions. Mention: superconducting quantum
bits -- new, looks promising.</p>
<p>Picture of quantum computer. Quite complicated. Important thing: realize
that the physics is very simple, and that's what you need for quantum
processing device: very isolated, very clean. All in this vacuum chamber
(rest is just tools). Ion trap: by applying correct voltages, we can
confine single ions. trapping direction much stronger radially than
axially. Distance from each other on order of <mathjax>$5\mu\mathrm{m}$</mathjax>. These ions
are what we call quantum bits: nothing but two-level system: we forget
about all other levels. Particular excited state: chose <mathjax>$D_{3/2}$</mathjax>
(implementation detail). Transition is a two-photon transition: has two
angular momenta. Unlikely to drop (since it needs to spit out two photons),
so we have about a second for quantum processing.</p>
<p>We also have this p-level around. Very important in this context, since it
allows us to see the ions.</p>
<p>Di Vincenzo criteria:</p>
<h1>Scalable physical system, well-characterized qubits.</h1>
<h1>Ability to initialize the state of the qubits</h1>
<p>(need to set up a system)</p>
<h1>Long relevant coherence times, much longer than gate operation time</h1>
<p>(require this to be quantum, and we need to be able to implement arbitrary
operations)</p>
<h1>Universal set of quantum gates</h1>
<h1>Qubit-specific measurement capability</h1>
<p>(need to be able to read it out)</p>
<p>No infinitely-scalable system (believed to be finite particles in
universe), so we mean mostly-scalable, i.e. not exponential to scale.</p>
<p>Experimental procedure: initialization in a pure quantum state. Very high
probabilities: the idea is that you exploit large differences of coherence
times. (done by shining lasers)</p>
<p>Quantum state manipulation: also done with lasers.</p>
<p>Quantum state measurement by fluorescence detection (every 10 ns I get a
photon into a <mathjax>$4\pi$</mathjax> solid angle, etc. From a quantum mechanical view, this
is pretty interesting: prepare in s,d, and start scattering photons, and
the ion decides whether it's light or dark. Also works with multiple
ions. Instead of zero and one, I will use s and d since I am talking about
physical images.</p>
<p>With very high fidelity (~99.99%) we can detect this state. Essentially
limited by time it takes for the d state to the ground state. Many orders
of magnitude better than other implementations.</p>
<p>What we do now is initialize in ground state, shine in laser for a given
time, then read out dark or bright, then plot probability. Then you see
oscillations that correspond to the Bloch sphere, and you plot these.</p>
<p>How do we distinguish between <mathjax>$s+d$</mathjax> and <mathjax>$s+id$</mathjax>? What does that mean? What
does that phase mean? I can shine in this laser and stop here. Might have
also noticed I can prepare in <mathjax>$s$</mathjax> state; how can I prepare in <mathjax>$is$</mathjax> state?
This problem of the phase occurs because in quantum mechanics, you must be
especially careful regarding what you can observe. Will show experiments.</p>
<p>So what is this phase about? For this phase, you need a phase
reference. The two phases we will have are the phase of the laser field and
the phase of the atomic polarization. Assume for now that we have a
dipole transition, not a quadrupole transition. <mathjax>$s$</mathjax> and <mathjax>$p$</mathjax> state. If I
look at where my electron is, I will find that in the upper part it
interferes constructively, but from the timing-dependent Schrodinger
equation, relative phase is governed by energy difference. What this means
is that you can have a minus sign, and it will be found lower.</p>
<p>The electron probability moves up and down with energy difference between s
and p state. Exactly the optical frequency: laser frequency. If I want to
drive transition, must apply laser matching that energy difference.</p>
<p>Atom with atomic polarization that goes up and down: how laser can drive
transition. Electric field shakes electron. If phase right, I can increase
this dipole moment. If phase wrong, I get destructive interference.</p>
<p>By switching laser phase by <mathjax>$\frac{\pi}{2}$</mathjax>, we switch from constructive to
destructive interference. By shifting the phase by this amount, we're not
putting any more energy in the system, so it's not evolving.</p>
<p>When I switch the phase, I am no longer rotating about the x, but now the
y.</p>
<p>So far we were talking about single ions. Now consider multiple ions (where
most problems show up).</p>
<p>change voltage by electrooptic deflector: deflects light beam based on
voltage. Neightboring ions are hardly excited. Residual excitation of cost
here since never really zero. Way to correct: apply dipolar decoupling.</p>
<p>Suppose you are ~1 A, and your neighboring ion is about 50 <mathjax>$\mu \mathrm{m}$</mathjax>
away. Exploiting here: ions move together. Coulombic attraction. Two
pendula coupled by a spring have normal modes. Most common is center of
mass mode where all ions move together. All have different frequencies. Can
use laser to excite these modes. Main mechanism: selectively push on one
ion with a laser.</p>
<p>Review of quantum mechanics of harmonic oscillators. Four levels: display
slightly differently. Combination of two-level system with harmonic
oscillator. Plot energy, label different states. Ion beam at ground
state. Electron ground state, electron excited state, etc. And then I can
apply a laser to drive this electron transition.</p>
<p>Think of it really as a ball being at the bottom of some harmonic
potential. Very crude approximation. Point is that we can think of this as
an abstract Hilbert space which you can connect with lasers. Same
frequency: carrier transition. In this transition, motion is not
changed. Then we can detune the laser; we have energy conservation at
particular energies.</p>
<p>Blue side-bands, since blue-shifted, etc. Frequency multiplied by
<mathjax>$\hbar$</mathjax>. When you scan the laser frequency, you can see some
excitations. There are other excitation probabilities. Three harmonic
oscillators, since we're working with three dimensions. Radial modes,
radial minus axial modes, etc. Can also do transitions where excitation of
state destroys a photon. Raising and lowering operators.</p>
<p>e.g. radial production of phonons, axial destruction of phonons.</p>
<p>What we can do, for instance, is increase motion in one direction while
decreasing it in another direction.</p>
<p>You learn things like dipole-forbidden. It's really a quadrupole
transition, suppressed by <mathjax>$\alpha^2$</mathjax>. Gives the difference of 10ns
vs. 1s. Don't worry about details.</p>
<p>We looked already at this exciting the electronic transition. Can also tune
laser to sideband, and see more Rabi oscillations with Rabi frequencies:
Reduced by <mathjax>$\eta = kx_0$</mathjax> Lamb-Dicke parameter. Can calculate; actually
probably would take an hour as well.</p>
<p>Let us now create some Bell states. See how we can use this toolbox to
create Bell states. Take two ions prepared in s state, but also
laser-cooled center of mass to ground state. Doppler effect. What we do now
is three pulses: first a pulse onto right ion for a length <mathjax>$\pi$</mathjax> on the
carrier transition, i.e. flip state but not motion. Now, go with laser to
other ion and apply a blue side-band pulse for length <mathjax>$\frac{\pi}{2}$</mathjax>. And
now we have the last pulse, which will somehow create the bell
state. Tuning our laser to the right ion and applying a <mathjax>$\pi$</mathjax>-pulse. What's
happening is we go to the s state and remove a photon excitation. We
de-excite the motion (which was common to both ions). The original part of
this superposition, which was left around, won't happen: no state with
correct energy.</p>
<p>If we have zero excitations in our quantum oscillator, then we can't take
out an excitation. We can separate out the motion, and what we left with is
sd + ds. Remember: we're talking only about the center-of-mass
motion. Normal mode spans the full space of the two ions moving.</p>
<p>Bell-states with atoms: NIST: beryllium, fidelity of 97%; Innsbruck:
calcium, fidelity of 99%, etc.</p>
<p>We all know that there is an infinite number of Bell states, which have
some phase incorporated. Need to play around with the length of the
<mathjax>$\frac{\pi}{2}$</mathjax> pulse. Must show coherence: interference with each
other. Plus sign makes sense. Not sometimes plus, sometimes minus. We want
to also know relative phase of the superposition.</p>
<p>What we do is develop a method to measure the density matrix. A measurement
yields the z-component of the Bloch vector. Measuring diagonal of the
density matrix is straightforward: enter measured values into this
diagonal. So how, then, are you going to measure these off-diagonal
elements, which determine the phase of this coherence?</p>
<p>How do I, say, measure the projection onto the y-axis? Rotate about x-axis
(apply <mathjax>$\frac{\pi}{2}$</mathjax>-pulse). Enter value here, then prepare same state
again. Do the same with projection onto x-axis.</p>
<p>Now we need to generalize to 2 qubits. Must try all combinations. Need to
do x,y rotations, nothing to first, nothing to second. etc. Analysis, some
linear algebra. Then we come up with the density matrices.</p>
<p>These are actually all measurements. You can even go to more complex
states: largest: 16 zero-qubits + 16 up-qubits. Huge matrix.</p>
<p>W state, etc.</p>
<p>Want to now show some nice things about quantum mechanics: can now prepare
these states, and can now measure individual qubits. Suppose we measure the
red qubit here in the center. Projection onto a self-consistent space.</p>
<p>problems with Hilbert spaces. One more qubit would have increased analysis
time by a factor of 24.</p>
<p>In the last 20 minutes, we've talked only about generation of bell
states. Not yet a quantum state. Original proposal to do controlled-not,
Cirac-Zoller, geometric phase, Malmer-Sorensen gate.</p>
<p>We use a little more complicated mechanism, which is harder to
understand. What we want to do is manipulate our two ions in this
manifold. Put all states. Drive two photon transitions: to move from SD to
DS. Do this by detuning laser from excited state. Equivalent paths:
constructive interference. When you analyze this carefully, you can see
this is a two-qubit universal gate.</p>
<p>Don't need to address ions: automatically implements a gate. Experimentally
easier: higher fidelity, etc.</p>
<p>Analysis of coherence. Applying two single-qubit gates to two ions:
contrast of interference fringes goes up to 1: high-fidelity bell state, so
gate works exceedingly well. One case: gate duration of 51 <mathjax>$\mu
\mathrm{s}$</mathjax>, average fidelity of 99.3(2)%.</p>
<p>Talk about errors. In theory, the fidelity would be sufficient.</p>
<p>Parity + when equal, parity - when unequal, etc. Such an interference
pattern predicted. If not happening, interference fringes have less
contrast. Fidelity decreases as we apply more gates.</p>
<p>Even after 21 equivalent gates, still 8% fidelity.</p>
<p>Scaling of this approach?</p>
<p>Problems:</p>
<ul>
<li>
<p>Coupling strength between internal and motional states of a N-ion string
  decreases as <mathjax>$\eta \propto \frac{1}{\sqrt{N}$</mathjax> (reasoning: if you excite
  one ion, a single photon needs to excite the whole ion chain; a single
  photon gets absorbed by the whole ion chain. More difficult for single
  photon to kick entire chain if chain is big), but problem does not scale
  exponentially. From a math point, we are fine (no exponential
  resources).</p>
</li>
<li>
<p>More vibrational modes increase risk of spurious excitation of unwanted
  nodes.</p>
</li>
<li>
<p>Distance between neighbouring ions decreases <mathjax>$\implies$</mathjax> addressing more
  difficult.</p>
</li>
</ul>
<p>So we need to divide: idea behind using segmented traps.</p>
<p>One problem is complexity. Everything can fail. Suppose one component fails
with error 0.1%, with 10000 components, this will never work.</p>
<p>In some sense the ENIAC looks similar in complexity. What we have done to
make things better was to put a box about it: probability of misalignment
gets worse.</p>
<p>We need to divide the system into smaller pieces: where most (if not all)
of effort of ion-trapping goes at the moment. This is an idea which
actually comes from Leibfried and Wineland, who envisioned many ions
trapped in some structure, and voltages moving ions around. Advantage:
small ion string.</p>
<p>Can show that within 50us we can move ions on the order of a millimeter,
which is huge. Shown on time scales, which are comparable to gate times, so
not too expensive.</p>
<p>Experiment, for instance: sketch of ion trap. What they have done is move
ions between points, and what they have shown is coherence (Ramsey fringes
on a single ion). When they transported, the contrast is approximately the
same. This tells us that the quantum information is not lost during
transport.</p>
<p>Another development is to make the traps easier. People are interested in
using conventional lithography to build easier traps. Recent development:
surface traps. All on one surface; can use microfab techs. Can basically
analyse electrostatics, and ions trapped on such a surface.</p>
<p>That is basically where the experiments are. People are building these
devices and trying to control them. Main challenge. Once we can control
these, we have real scalable quantum processing.</p>
<p>If you want to read about these things, you can look in this review which
is written in a way with hardly any math.</p>
<p>Review on "quantum computing with trapped ions"
http://xxx.lanl.gov/abs/0809.4368</p>
<p>most recent progress: NIST, Boulder
http://www.nist.gov/pml/div688/grp10/quantum-logic-and-coherent-control.cfm</p>
<p>Innsbruck
http://wwww.quantumoptics.at/</p>
<p>University of Maryland
http://www.iontrap.umd.edu/publications/recent_pubs.html</p>
<p>Basic ideas of how this works, physics is fairly clear: quantum mechanics at its best.</p>
<p><a name='25'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Cryptography</h1>
<h2>April 24, 2012</h2>
<p>Today we will speak about quantum cryptography. The main question: how to
agree on a secret key? Alice &amp; Bob sitting at distance, can communicate
over insecure channel. Want to agree on shared random key. Often running,
can use private-key crypto, do whatever they want. Getting started, they
want to exchange this private key.</p>
<p>The problem is that Eve is listening on the line. So how do they accomplish
this? Here's the setup: there's a quantum channel which they share. Alice
can send qubits to Bob. They also share a classical channel, except that
they have no control over the classical channel. All they know is that it's
authenticated (public-key signing, perhaps).</p>
<p>Eve also has access to the quantum channel. What we want to do is develop
this protocol: sharing of the random key without loss of confidentiality.</p>
<p>So what happens in classical cryptography? RSA (public key
crypto). Everything we're speaking about today is working under the
assumption that A&amp;B haven't met yet and are only now establishing this
private key.</p>
<p>Why do we need quantum cryptography? Shor's breaks RSA. What we are trying
to achieve is unconditional security -- the only thing you need to assume
in order to guarantee security is that the laws of physics hold (i.e. QM is
an accurate model). Has been implemented using today's cryptography.</p>
<p>What we will talk about today are the principles of quantum crypto.</p>
<p>Qubits used here are polarizations of photons. Polarization as orientation
of light wave as it propagates. In some direction orthogonal to direction
of propagation. Polarization is a qubit. Nice thing: polarizing filter
blocks photons whose polarization is perpendicular to the orientation of
the filter and transmits photons whose polarization is aligned with the
orientation of the filter. It gives us a measurement axis for the photon.</p>
<p>The probability that the photon is transmitted by the second filter is
<mathjax>$\cos^2\theta$</mathjax>. Measurement of the qubit.</p>
<p>What we are saying is that we could write our qubit state <mathjax>$\ket{\psi}
\equiv \alpha\ket{0} + \beta\ket{1}$</mathjax>. Zero vertically-polarized, one
horizontally-polarized. One part of superposition goes through, other part
blocked. Self-consistency. We could also write this in some other basis
<mathjax>$\ket{u}, \ket{u_\perp}$</mathjax> at some angle <mathjax>$\theta$</mathjax>.</p>
<p>This is really qubits in the same language that we had, except we're
thinking about them as spatially-oriented, just as we thought about
spin. Completely analogous.</p>
<p>So here's what we're planning to do. Two ways to encode a bit of
information. Could either encode in rectilinear (vert/horiz) or in diagonal
(+,-). So when Alice wants to transmit a bit to Bob, if she was using the
rectilinear basis, she'd transmit horizontally/vertically polarized
photons. Bob would then use either a vertical or horizontal filter. Similar
concept with a diagonal polarization.</p>
<p>Remember: all channels are visible to everyone.</p>
<p>Why use both these polarizations? Has to do with uncertainty principle:
these are Fourier transform pairs, so maximally uncertain. You'll recall we
did this in the second or third lecture. We talked about the bit and sign
bases. There's an uncertainty principle between the two. You have a choice
of measurement basis (could be one, could be other, could be a mix) to
determine how much information you get. You cannot get perfect information
about the state of said qubit.</p>
<p>Eve, who doesn't know which basis the information is being sent in, really
cannot figure out both. If Eve tries to measure in the wrong basis, then
she completely destroys the information.</p>
<p>thought regarding decision of which basis to choose: send a bell
state. Confirmation would be on this classical line, just saying "I got &amp;
measured the bell state"</p>
<p>Implementation is actually done without bell states. Very difficult to
implement bell states.</p>
<p>Let's suppose Eve entangled the transmitted qubit with one of her
own. By doing so, she's randomized the state.</p>
<p>The BB84 protocol (that we're going to discuss) was invented in 1984 but was
not proven correct until about a decade ago. People assumed
correctness. Reason: subtle. All other attacks you could think of, but they
don't work. But how do you show that no attack will work?</p>
<p>How do we make use of this scenario? How do we distinguish between Bob and Eve?</p>
<p>Repeat 4N times (if we want to end up with N random bits):</p>
<p>Choose random bit, randomly select basis. Announce choices of
bases. Discard if choices different. Eve can see all of this.</p>
<p>Final result: roughly 2N shared bits. Select N random positions, confirm
that they're the same. Remaining N bits are secret key.</p>
<p>Ensures confidentiality of message. Integrity of key is guaranteed by
communications on classical channel.</p>
<p>Potential corruption of shared key (attack on integrity): Eve just needs to
corrupt one bit. 50% chance of catching this. Refine: more sophisticated
protocol.</p>
<p>Beautiful way of dealing with this, provable correctness.</p>
<p>Single-photon generators imperfect. Occasionally emit two photons. Eve can
intercept one, let the other go, and that breaks the scheme (known vector
of attack).</p>
<p>Polarization over these distances? This is the interesting thing about
photons. If you transmit a photon, there is almost nothing that decoheres
it. Can maintain coherence over long period and long distance. Can transmit
through optical fiber, and it will maintain its polarization for something
like 60 - 70 km.</p>
<p>Issue is why 60-70 km? Because signal gets attenuated. Every so often, you
have to amplify the signal, but of course we don't want to amplify the
signal; we just want to transmit it. Usually involves measurement and
retransmission.</p>
<p>People are trying to build amplifiers that don't do that: small quantum
computers that take the photon, error-correct, and retransmit. But not
implemented yet.</p>
<p>Security of BB84: Since Eve does not know the correct orientation, she
cannot measure the polarization without disturbing it.</p>
<p>Proof of unconditional security based on axioms of QM is difficult and
dates back to about 2000.</p>
<p>Practical considerations:</p>
<ul>
<li>imperfect measurements: channel noise causes shared btis to not agree.</li>
<li>Figure out noise rate, determine whether acceptable.</li>
<li>In this case, Alice and Bob exchange parity bits to correct mismatches.</li>
<li>Can only guarantee that Eve does not know too many bits out of the
  remaining N.</li>
</ul>
<p>Randomness distillation. Suppose we are left with 4 bits, and we know the
noise rate is at most a quarter, so Eve knows at most one of these
bits. Want to distill into bits Eve does not know about. Extract key via
XORs. Claim: no matter which bit Eve knows, each bit looks completely
random to Eve.</p>
<p>Choose random hash function to hash these bits. What we can prove is that
Eve has no information regarding the resulting hash. Must deal with these
issues: mismatches and Eve's knowledge.</p>
<p>Turns out that hash function itself doesn't have to be random. Should work
even if hash function is public (and surjective?).</p>
<p>Actual theorem: suppose you pick a hash function H at random, and now let's
say that <mathjax>$N \mapsto M$</mathjax> (n-bit strings to m-bit strings), and that x is
chosen according to some distribution.</p>
<p>Lemma: left-over hash lemma. If you look at the pair H (specified somehow,
chosen at random), H(x) (m-bit string; H(x) is some string), the claim is
that this distribution is close to the uniform distribution on m-bit
strings, and so you cannot tell the difference between this result and some
random m-bit string.</p>
<p>Has been implemented. Was famous experiment done at a lake near
Geneva. Three locations with optical fiber going between these
locations.</p>
<p>Challenges with atmospheric photon transmission and detection. Background
photons, daylight radiance, night radiance. How to distinguish? Start:
timing pulse -- expect a photon in 1 us, within a window of 1 ns. What can
we control? Narrowness of window of time; part of spectrum which sunlight
that does not use (or least-used), and a very narrow window of frequency,
at that; look at very small solid angle. So we're isolating in terms of
position, momentum, and time. Once you do all of these things you realize
that you can cut down this <mathjax>$10^{13}$</mathjax> to something very tiny.</p>
<p>So why use photons? Why not use some particle with very strong coherence?
Photons are nice -- very stable, coherent. So what would this other
particle be?</p>
<p>Must take into account GR. Photon essentially does not interfere with
anything else. Remember how hard it is to do cavity QED. To take a photon
and create a gate using said photon is very difficult to do. You put the
photon in a cavity and couple the qubit to the cavity and the cavity to
some other qubit. Outside of these extraordinary efforts, photons are
fairly stable.</p>
<p>Other considerations for photon transmission: efficient lasers (want some
source such that exactly one photon can be transmitted). Already that is
enough to get this off the ground.</p>
<p>Exaamples of 10 km QKD. Commercially available quantum crypto systems.</p>
<p>And then there's this fact. You can prove that these things are secure, but
they aren't really: one possible attack: shine strong laser at Alice; can
figure out internal settings.</p>
<p>Device-independent cryptography. Want to prove quantum crypto scheme secure
based purely on quantum mechanics. What is interesting is that you can show
that in principle, you can create some systems. Theoretically possible to
do.</p>
<p>Quantum key distribution, then use classical private key cryptography,
i.e. schemes secure under quantum cryptography (not known to be broken; no
proximal reason why those would be breakable, given the quantum algorithms
we know).</p>
<p>Two things: course projects. Some of you have sent email giving 2-3
paragraphs describing what you'll be doing and what sources. What would be
good would be if the rest of you could send something hopefully by later
today.</p>
<p>Project presentations: next week Thursday. Will set up in location to be
determined (hopefully here). Will go from 9:30 to 1, perhaps. Go through
all project presentations. Make sure you have a good typed presentation
that fits into ~20 min. With questions, presumably no presentations will go
over 25 min.</p>
<p>Roughly 10 groups. Will try to arrange for pizza -- at some point we'll
break for lunch.</p>
<p>What day will the paper be due? The paper will be due the end of the
following week (end of finals week).</p>
<p>Let's say that there might not be a breakdown in the sense that if you do
particularly well in one, it'll compensate for the other.</p>
<p>Two other issues: 1) there's a question for EECS majors: what should this
course count as? Science requirement? EECS requirement? 50/50? Would be a
useful thing to sort out. Would like to take existing notes for this class
and make them more consistent with what was taught this semester. Two
things: if you've been taking good notes in class, I'd love to have a copy
of those.</p>
<p><a name='26'></a></p>
<h1>CS 191: Qubits, Quantum Mechanics and Computers</h1>
<h1>Quantum Walks and the Dirac Equation</h1>
<h2>April 26, 2012</h2>
<p>Last lecture of the semester. Talk about two things: start with quantum
walks and Dirac equation, and then I'll tell you a little about other
topics in quantum computation you might be interested in. Larger picture,
who, how to pursue.</p>
<p>Before we start, let's review something about classical mechanics. Suppose
we are doing a random walk on a discretized line, so we have grid
points. At each step, we move randomly. How long to reach a distance <mathjax>$n$</mathjax>?</p>
<p>You may recognize this: after k steps, this is given by a binomial
distribution centered at zero, and the standard deviation is about
<mathjax>$\sqrt{k}$</mathjax>: central limit theorem. We can work this out: if you look at the
position after <mathjax>$k$</mathjax> steps, we have some distribution. We want to know what
the variance of this distribution is, and thus what the standard deviation
is. Turns out that the variance grows as <mathjax>$k$</mathjax>, and so the standard deviation
grows as <mathjax>$\sqrt{k}$</mathjax>. Since each step is a random variable (independent from
all other steps), we can exploit linearity of expectation to find this <mathjax>$k$</mathjax>.</p>
<p>Thus if we want to reach this distance safely, we should expect to walk
roughly <mathjax>$n^2$</mathjax> steps. That is the penalty for randomness: a factor of <mathjax>$n^2$</mathjax>.</p>
<p>Now assume that instead of dealing with a classical particle and a
classical walk, we're dealing with a quantum particle.</p>
<p>In the classical case, the position is <mathjax>$x$</mathjax>, which is an integer; there is a
coin flip <mathjax>$b$</mathjax>, which is <mathjax>$-1 \lor 1$</mathjax>, and at each step, you flip the coin
and increment <mathjax>$x$</mathjax> by <mathjax>$b$</mathjax>.</p>
<p>In the quantum case, we again have <mathjax>$x$</mathjax>s and <mathjax>$b$</mathjax>, but now we're keeping
track of everything. The state includes both <mathjax>$x$</mathjax> and <mathjax>$b$</mathjax>. Whatever the coin
flip says, we move accordingly. And now we must flip the coin. How to flip
the coin, since it's now a quantum bit? Apply the Hadamard to it. That is
our quantum walk on the line.</p>
<p>Now, we could do the same thing, start from the origin, walk for <mathjax>$k$</mathjax> steps,
and how far do we get? When you do this quantum walk, you end up with most
of the mass at some constant multiplied by <mathjax>$k$</mathjax>: it really walks at constant
rate. Why?</p>
<p>What accounts for the chance at origin being roughly zero in the quantum
case?</p>
<p>We must go back to the classical case and understand this. There are many
ways to return to the origin, but in the quantum case, each way comes with
a phase, and these phases tend to cancel out. When you shoot out to the
ends, you get constructive interference, whereas at the origin, you get
destructive interference.</p>
<p>Qualitatively, the quantum walk behaves very differently from the classical
walk. Remember: in quantum mechanics, you don't have a notion of a
trajectory.</p>
<p>You can also define a continuous version of that by defining an appropriate
Hamiltonian. The Hamiltonian you would need is exactly what you think: it's
the Pauli matrix <mathjax>$\sigma_x$</mathjax>. We'll see how to write this behavior
explicitly in a bit: this will result in the Dirac equation.</p>
<p>So now, let's see how to apply some of these ideas about quantum
walks. What are these useful for? Algorithms. This relates to a quadratic
speedup in the simple case. Tells you if you were using random walks to
design an algorithm, if you switched over to quantum, you'd get quadratic
speedup. You do get quadratic speedup or much speedup for most of these.</p>
<p>What's interesting is a quantum algorithm for formula evaluation: quadratic
speedup for evaluating a boolean expression.</p>
<p>Applications: minmax tree where values are zero and one. And is min, Or is
max.</p>
<p>This finds its use in quantum algorithms and other places. What I want to
talk about today is Dirac's equation, which can be explained nicely with
quantum walks.</p>
<p>This was when he was reconciling quantum mechanics with special relativity,
which also led him to the role of spin and the relativistic origins of
spin. Also led him to his discovery of antimatter. This was really quite a
remarkable event in physics, and what was interesting was that also, in all
this was just how much courage Dirac had in terms of looking at this
problem, finding this very simple equation, and having the courage to stand
by something so new that had so many major consequences.</p>
<p>So let's go back: we have a particle whose energy is classically
<mathjax>$\frac{p^2}{2m}$</mathjax>. Quantumly, this is <mathjax>$\frac{\hat{p}^2}{2m}$</mathjax>, where <mathjax>$\hat{p}
\equiv \frac{\hbar}{i}\nabla$</mathjax>. So now, let's try to understand
relativistically that the energy is given by the Klein-Gordon equation
(Einstein's theory of relativity, really, which arises from invariances of
moving frames), which says that <mathjax>$E^2 = p^2c^2 + m^2c^4$</mathjax> (where <mathjax>$c$</mathjax> is speed
of light), and <mathjax>$p^2c^2$</mathjax> is the kinetic form.</p>
<p>If you try to figure out what this is saying, when a particle has speed
much less than that of the speed of light, you can pull out <mathjax>$mc^2$</mathjax>, and you
get <mathjax>$mc^2\sqrt{1 + \frac{p^2}{m^2c^2}}$</mathjax>. Since this is small, you can
approximate this as <mathjax>$mc^2(1 + \frac{p}{2mc^2})$</mathjax> (first-order Taylor
expansion with respect to p). Expanding this, we get <mathjax>$mc^2$</mathjax> (energy
associated with rest mass) added to <mathjax>$\frac{p^2}{2m}$</mathjax>. And that's exactly
what you want: that is the total energy.</p>
<p>So all is fine and well, and now, what Dirac was trying to do was figure
out what the corresponding quantum equation is: <mathjax>$H^2 = \hat{p^2}c^2 + m^2
c^4 I$</mathjax> (where <mathjax>$I$</mathjax> is the identity). This is the square of the
Hamiltonian. How do you compute the Hamiltonian itself? This is exactly
what Dirac was trying to do: he was trying to compute the square root of
this operator. Youc an try to compute square roots, use Taylor series, it
blows up, and it doesn't really look like anything. And then he had this
insight.</p>
<p>Let's use units where <mathjax>$c=1$</mathjax>. What we're trying to do is compute <mathjax>$H =
\sqrt{p^2 + m^2 I}$</mathjax>, where both of these are operators. Here was the flash
of insight: what he realized was if you wrote the Hamiltonian by doubling
the dimension as <mathjax>$\begin{pmatrix}\hat{p} &amp; mI \\ mI &amp;
-\hat{p}\end{pmatrix}$</mathjax>. So what happens when you square this? We get
<mathjax>$\begin{pmatrix}\hat{p}^2 + mI &amp; 0 \\ 0 &amp; \hat{p}^2 + mI \end{pmatrix}$</mathjax>.</p>
<p>Has this feel about it that in trying to solve this especially difficult
problem, and by stepping outside of what seem to be the rules of the game,
it suddenly becomes very simple. And then instead of saying this is
illegal, perhaps these actually are the correct rules of the game.</p>
<p>And so what Dirac said was that there's an extra degree of freedom: it's a
qubit -- spin. So now we can try to understand what this tells us about how
the particle moves relativistically. If we write that out, we want to solve
<mathjax>$i\pderiv{\Psi}{t} = H \Psi$</mathjax>. Let's do case 1: <mathjax>$m = 0$</mathjax>.</p>
<p>So what's our state space? There's the position of the particle, and then
there's spin. The Hamiltonian is going to act on the whole thing. What will
this look like? In general, it's acting on the two spaces together. If you
were to write out the state vector, it consists of the component with spin
<mathjax>$b=0$</mathjax> and the component with spin <mathjax>$b=1$</mathjax>.</p>
<p>With the massless particle, <mathjax>$\pderiv{\psi}{t} = -\nabla\psi$</mathjax>, so in the
one-dimensional case, <mathjax>$\psi$</mathjax> is moving right with the speed of light. So
there are two solutions, depending on your spin qubit: in one case, you're
moving right at the speed of light, and in the other case, you're moving
left with the speed of light.</p>
<p>So what happens in general? You have this term that corresponds to motion
left or right at the speed of light, and then you have the term that
corresponds to the mass. The greater the mass, the more often you flip the
coin. The presence of the mass term corresponds to a new direction after
each coin flip, so to speak. Recall that we moved <mathjax>$ak$</mathjax> for some <mathjax>$a$</mathjax>. With
no mass, <mathjax>$a$</mathjax> is <mathjax>$c$</mathjax>. As we increase the mass, <mathjax>$a$</mathjax> decreases.</p>
<p>There's another thing you might think about: in the classical case, after k
steps, you move <mathjax>$\sqrt{k}$</mathjax>. You can move one step per unit time right or
left. But of course we want to let that unit tend to zero, so <mathjax>$k$</mathjax> tends to
infinity.</p>
<p>In fact, what Dirac did was work out this problem, and he worked out the
statistics of this walk. He didn't call it a quantum walk, but that's what
he implicitly did.</p>
<p>So that's it regarding quantum walks and the Dirac equation. I'll now spend
the next ten minutes talking how to further pursue quantum computing. If
you have specific questions, feel free to ask.</p>
<p>There are many different areas here in quantum computing, which is
partitioned into three primary flavors of research: theory work -- consists
of quantum algorithms (design), complexity theory (QBP = P?), information,
crypto. The boundaries will vary depending on your source.</p>
<p>Quantum information theory: quantum analog of classical information theory:
how much classical information can I transmit in each qubit? What's the
value of quantum information? And the second part: error correction and
fault-tolerance. If you want to build a quantum computer, one thing you
have to worry about is decoherence. Previously people thought that quantum
states were not protectable: they degrade over time as the environment
decoheres them. This is a way of putting this quantum information inside a
sort of error-correcting envelope for protection. Even after being subject
to errors, we can still recover the original message (a quantum state).</p>
<p>Physically, you think about these errors as heating of the system (increase
of entropy). What do you do? Take fresh qubits all initialized to zeros
(supercooled), and do heat exchange. Take all the heat (in the form of
errors), isolate it, and push it into these cold qubits. Now these errors
are sitting inside these new qubits, which we can then discard --
refrigeration. If you do that, that's called fault-tolerance.</p>
<p>Cryptography we know about. There's one subject I haven't talked about:
post-quantum cryptography. Quantum algorithms break most of modern crypto:
RSA, Diffie-Hellman, you name it. What we'd like to do is restore
public-key cryptography, and eventually use private-key cryptography. You
could use quantum cryptography, but even though there are existing systems,
they're very difficult to use.</p>
<p>There's a different way out: how about designing public-key cryptosystems
which quantum computers cannot break?  Very active field of research. If
you think about it, this may be the biggest practical impact of quantum
computation in the very near future (next few years). Would be very
interesting if that happens; it's not the quantum computers that would have
the impact, but rather the threat of quantum computers.</p>
<p>Two other fields are simulating quantum systems: the starting point for
quantum computation, to simulate this, we normally would need an
exponential amount of work to simulate. So how would you simulate quantum
systems efficiently on a quantucm computer? There are interesting results
here: how would you, for instance, run the quantum metropolis algorithm?
The second question: how to simulate on a classical computer. Here, the
question is not how to simulate general systems, but rather, could it be
that natural quantum systems are somehow much simpler and can be simulated
very efficiently, even if they are highly-entangled? There is a renaissance
of information in this field.</p>
<p>Special systems can be solved explicitly (closed-form). Those can be
simulated on a classical computer. There are many others that can't be
solved explicitly, but they have certain properties that we can take
advantage of.</p>
<p>And finally, there is a lot of work on experimental quantum
computing. Various techniques.</p>
<p>In terms of resources: Haffner teaches a course on quantum computing from a
more experimental viewpoint. In terms of the physics department, there's
Haffner, Clark (superconducting qubits), Stamper-Kurn (Bose-Einstein
condensates, optical systems), Szdiki, Crommie. In the chemistry
department, there's Waley, who might teach this course next year. There's
also a colleague in computer science: Kubiatowicz -- quantum architecture.</p>
<p>How to put together? Let's say that three years from now, ion traps work
and scale to a few hundred qubits. Now how would you put them together to
do interesting computations? What are the architectural tradeoffs: should
you keep qubits close or teleport, how to manage ECC, etc.</p>
<p>Few places other than Berkeley; Waterloo (IQC, perimeter institute),
Caltech, MIT, U. Maryland -- growing group, CQT in Singapore (which
actually offers a degree in QC). Number of resources. And then there are
groups in Europe which are very strong: Munich, Germany, Paris. There are
lots of resources internationally, but also there are plenty of
opportunities for summer schools if interested or graduate work in the
area.</p>
<p>If you want any more information, you can email or stop by.</p></div><div class='pos'></div>
<script src='mathjax/unpacked/MathJax.js?config=default'></script>
<script type="text/x-mathjax-config">
MathJax.Hub.Register.StartupHook("TeX Jax Ready",function () {
var TEX = MathJax.InputJax.TeX;
var PREFILTER = TEX.prefilterMath;
TEX.Augment({
  prefilterMath: function (math,displaymode,script) {
      math = "\\displaystyle{"+math+"}";
      return PREFILTER.call(TEX,math,displaymode,script);
    }
  });
});

var a  = document.getElementsByTagName('a'),
    ll = a.length;
if (ll > 0) {
  var div = document.getElementsByClassName('pos')[0];
  div.style.float = 'right';
  div.style.position = 'fixed';
  div.style.background = '#FFF';
  div.style.fontSize = '90%';
  div.style.top = '10%';
  div.style.right = '5%';
  div.style.width = '15%';
  for (var i = 0; i < ll; i++) {
    div.innerHTML += '<a href="\#' + a[i].name + '">'
                     + a[i].parentElement.nextElementSibling.nextElementSibling.innerHTML
                     + '</a><br />';
  }
  var div = document.getElementsByClassName('wrapper')[0];
  div.style.width = '80%';
}
</script></div>