Energy Landscapes
Imagine you are viewing your surroundings. You look around and notice MOUNTAINS and valleys. In front of you, there's a flat plain with a BUMP in the distance. As you move closer, the BUMP takes on a shape of its own with small, imperceptible HILLS and valleys in its own local vicinity.
Now, instead of viewing your surroundings nearby, take a step back, and see it from a broader frame of reference. These hidden hills and valleys in local areas are a GLOBAL PATCHWORK of the same phenomena.
And if you imagine this landscape as a potential ENERGY function, with the elevation representing the ENERGY at a particular point on an xy-plane, then the valleys and HILLS, i.e. the z-axis, are the local minima and local MAXIMA of the function.
The Adiabatic Theorem
Broadly speaking, the adiabatic theorem states that if you have an ENERGY function and if you slowly and continuously perturb it by ADDING or removing ENERGY, the nested HILLS and sloping valleys of the ENERGY LANDSCAPE will also change in in the SAME, SLOW, continuous manner.
This theorem is the CRUX of quantum computation.
This physical process is the so-called 'black box' algorithm behind ALL of quantum adiabatic computation. Most of the time, the (quantum) physicists I encountered would wave their arms erratically (similar to mathematicians when they're teaching ALGEBRAIC GEOMETRY to grad students) and say that this adiabatic process SEEMS TO WORK.
If questioned further about this process, most would readily admit that they didn't know HOW or WHY it worked.
As a mathematician, my curiosity was not satiated. To simply explain away and state this process worked without any explanation seem suspicious to me. It seemed to me some DEEPER mathematics could explain this whole adiabatic business.
Slowly Perturbing the Hamiltonian
A potential energy function, also known as a Hamiltonian (named after Irish Mathematician William Rowan Hamilton), can be described by its energy states by considering the corresponding square matrix that represents the Hamiltonian, where the so-called eigenspace of the matrix is intimately related to the energy states of the Hamiltonian.
For quantum computation, the interesting quantity that is important is the lowest energy or ground state of the Hamiltonian. When considering the potential ENERGY in its matrix form, the smallest eigenvalue plays the role of the ground state of the Hamiltonian.
A STANDARD tool of MATHEMATICS is to consider the same object in as many different (and equivalent) representations as possible. When an object changes its role by putting on a different mask, the object itself does not change, and ALL of its properties, regardless of the mask that it wears, can lead us to develop a DEEPER understanding about the object itself or the PHYSICAL process that the object models.
Similarly, one can change one object into another via a transformation. This is what happens with Adiabatic Quantum Computation. A Hamiltonian whose ground state gives us the solution to a problem, say, for instance, Boolean Satisfiability is constructed. We will call this Hamiltonian H_F.
Another Hamiltonian that is easily constructible, called H_0, is created as a starting POTENTIAL energy FUNCTION and slowly perturbed to the final Hamiltonian under the smooth transformation: H(t) = (1-t)H_0 + tH_F.
H(t) represents the Hamiltonian at any time between 0 and 1. Note that H(0) = H_0 and H1(1) = H_F.
Now, just because this final Hamiltonian was constructed by us does not mean WE ALREADY KNOW its ground state -- otherwise we would already have THE SOLUTION to our problem!
In order to arrive at our destination, the adiabatic process is applied and the ground state H_0 is followed all the way to find (statistically) the lowest energy state of H_F.
Remember when WE said that if a perturbation happens slowly enough, the energy minima and maxima won't change quickly? That's what's happening with quantum computation! The lowest ENERGY state of the initial Hamiltonian moves slowly as the underlying Hamiltonian is perturbed and CAN BE TRACKED all the way to its final ground state.
But ...
What happens IF YOU have the ground state and the next highest energy state SWAP POSITIONS during the adiabatic process? Then, you're no longer following the ground state all the way to the final Hamiltonian, and you miss the solution to the problem that you were originally trying to solve.
FORTUNATELY, this cannot happen when the adiabatic transformation is SLIGHTLY modified.
In fact, this SLIGHT modification is what is used in PRACTICE, but WITHOUT any understanding or JUSTIFICATION other than IT SEEMS TO WORK!
Indeed, there is some VERY EARLY work by Wigner and von Neumann entitled On the behaviour of eigenvalues in adiabatic processes that says precisely that, i.e. WE DON'T KNOW WHAT'S HAPPENING, but IF WE DO THIS, things seem to work (yay!?!??!??!).
What slight modification is done you might ask? Nothing more than adding a rAnDOm Hamiltonian, H_R, to the equation.
Now, H(t) = (1-t)H_0 + tH_F + t(1-t)H_R
What does adding this raNdOM Hamiltonian do to the energy states? This additional Hamiltonian DISRUPTS any degeneracies that could occur when multiple eigenvalues are at the same ground state. This condition occurs when certain algebraic conditions are satisfied and is called degenerate (although, a better term would be de-generic, or non-generic -- more on that later).
If a degenerate space occurs during the adiabatic process, that is to say, if there is a collapse of TWO (OR EVEN MULTIPLE) eigenspaces onto one another AT ANY TIME, it is unknown which energy state is the ground state when this degenerate space is perturbed back to its NORMAL state.
Throughout the time that I have spent poring through the AQC literature and talking with the (relatively few, I must add!) scientists in this field, no one seems to UNDERSTAND the role of RaNDoMnESs!
Random Matrix Theory
The role of RanDoMNeSS is very important to the adiabatic process as some black-box machinery to be used for quantum computing.
The reason that including a rAndOm Hamiltonian necessarily causes no degeneracy to occur is because a generic or R A n D O m matrix has simple eigenvalues. In other words, a random matrix has no eigenvalues of multiplicity bigger than one, i.e. the characteristic polynomial of the matrix has NO REPEATED ROOTS.
The occurrence where an eigenvalue appears MULTIPLE TIMES IS not COMMON.
What Does It All Mean?
The black-box of quantum computation requires rAnDOmnEsS at its heart to work and because rAnDoM Hamiltonians are added to the energy state after the adiabatic process begins and before it ends, one can apply all the results from RaNdOM matrix theory.
raNDoM matrix theory tells us that generic (or random) matrices have simple eigenvalues and, as such, no degeneracies, i.e. no collapsing of multiple eigenspaces. If no eigenspaces can be collapsed into the same one, then its obvious that the ground state cannot degenerate into the next excited state.
The Minimal Distance Between The Lowest Energy State and the Next Excited State
A VERY IMPORTANT question asked by the quantum physics community concerns the minimal distance between the lowest energy state and the next excited state. If the GAP of the two energy states is too small, then one could accidentally follow the next excited state to the end Hamiltonian.
It turns out that if a RaNdOm Hamiltonian is used to perturb the energy states during the adiabatic process, then MORE knowledge CAN still APPLY. In fact, RaNDoM matrices have on average a well-known gap that is the inverse of the size of the matrix.
For quantum computing, this means that as the number of q-bits is increased, the corresponding size of the matrix representing the Hamiltonian increases exponentially.
From this, we can now conclude that ON AVERAGE the distance between the ground state and the next EXCITED state is exponentially smaller as the number of q-bits increases.
The Future of Quantum Computing
Quantum computing is currently a HOT topic amongst researchers and lots of funding from ALL OVER the world is being pored into it, but the crucial role of RanDoMNesS is being overmissed.
Indeed, new algorithms need to be developed by quantum physicists to use RaNDoMNeSs appropriately so that one can apply quantum computation efficiently.
I do know basics if quantum information and computation as well as basics from randon matrix theory .. but this .. i need to read more often to even get a slight idea of what is going on.
Anyway, its a great read and makes me excited about math in the quantum cosmos
+5%
tl; dr version :
Slowly changing an energy function will slowly change the minima and maxima (i.e. critical points) of the function. The global minima (or the ground state or lowest energy value) is given by the lowest eigenvalue of the matrix that represents the Hamiltonian. This is the quantity that is to be computed by following the ground state of an initial Hamiltonian to the final Hamiltonian.
During the adiabatic evolution, no two eigenstates can be collapsed on one another if using a random Hamiltonian to add in during the perturbative process, as per random matrix theory. However, jumping between energy states can occur if the gap between the ground state and the next excited state is too small. So, the key is to design an adiabatic path that makes this gap as large as possible.
So, the quantum physicists are always asking about what the size of this minimal gap is for any given initial Hamiltonian and a straight line interpolation to the final Hamiltonian. But, since adding in a generic Hamiltonian during the adiabatic process guarantees that no energy levels cross, we need to fully understand the situation with including such a perturbed Hamiltonian, especially if this (as far as I can tell) is what is done in practice due to the 'It seems to work, but we dunno why' philosophy. The why comes from tapping into random matrix theory and using known results regarding the spectrum of the matrix and the average distance between any two eigenvalues of a random matrix.
Since the average distance between any two eigenvalues is 1 / n, where n is the same of the matrix, then the average distance between the ground state and the next excited state is 1/ 2^k, where k is the number of q-bits. We see then that the minimal gap, on average, is 1/2^k.
Now, you could have a special starting Hamiltonian, or a family of starting Hamiltonians that are still generic, but have some more structure. If you use these Hamiltonians, you may be able to beat the average and have better luck. But nobody knows what are good classes of starting Hamiltonians, or if certain initial Hamiltonians are good for certain problems, etc.
I see algorithmic development using this knowledge and discovering techniques that apply these tools as a huge step forward.
Mine too ...
I did this research while working at the Institute for Interdisciplinary Information Sciences in Beijing for about 5 months.
How it all works (and what's going on behind the scenes) really takes awhile to sink in.
I can read the words, even get a sense of coherence but I have to accept some of the more interesting areas of human discovery, like quantum physics and math, are far beyond me. I'm just thankful for all the people like you who have these incredible brains which can operate at the bleeding edge whilst I can enjoy wrestling with comprehension at a concept level!
Thanks. I meant to make the post entertaining and an introduction into the subject area. It's really a pre-lude to a talk that I'll be giving in Boston at SIAM.
I want to point out that coherency is key. I hope it wasn't lost on anyone. I didn't even know how to begin to describe the work I did in developing some algorithms that would turn on or off various q-bits in such a way as they relate to their entangled states.
From what I could understand, if you have k q-bits that are entangled in an n q-bit system, then the corresponding matrix that represents the Hamiltonian will be a 2^n x 2^n system, with a 2^k x 2^k block submatrix (under an appropriate transformation) realizing the underlying subspace of the Hamiltonian that represents the k entangled q-bits.
So, if you have a 3 q-bit system with 2 q-bits entangled, then you have a 4 x 4 block diagonal matrix that represents the entangled state of the two q-bits. Now, because we assume that only 2 q-bits are entangled that means one of them isn't interacting with the other two at all.
How does this translate to the representation in the matrix? 1 q-bit that isn't being entangled with 2 others doesn't fit in a 4 x 4 submatrix on its own? It really ought to be a 2 x 2 submatrix.
So, what's going on with those other 2 dimensions in the row / column space of the matrix?
I'm not entirely sure, but I intend to find out.
Oh I think you did a fantastic job of communicating the subject. I can't wait to hear more! Really good luck with your talk!