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.
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.
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.
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!
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.
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.
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.
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.
