The following is an artificial example of adiabatic computation introduced here solely for the purpose of explanation. Suppose we encounter an algebraic function such as:
Suppose we are looking for the point x where this function reaches its minimal value. One way to solve the equation is to use the well known fact that the minimum or maximum value of a function is where its derivative (its ‘slope’) equals 0. We can compute the derivative and equate it to 0. Since the function is of a 3rd degree, its derivative is of the second degree, and we end up solving a quadratic equation. This is the analytical way of solving the problem, which is based on 17th century mathematics.
The physical adiabatic (and quantum) way of solving this problem is different. Let’s look at a simpler equation like:
f(x) = x2
We can simulate this simple equation and its solution on a physical model. Think of a ball or a roller coaster train falling down a ‘hill’ into a deep ‘valley’. Suppose this ‘valley’ is in the shape of our equation f(x) = x2.
|
If you leave the ball somewhere on the slope it will descend until it reaches the lowest point in the valley. You can read the solution of the equation by reading the location of the ball (in fact, you already know the solution, it is x=0). The physical model we have just described helps us in computing the problem. We could build a model of the valley out of stones, electronics, or even some biological material. This model is really a computer. Reading the point where the ball is stationary is like reading the results from a printer. The problem represented to our stone-aged computer is actually very simple, but do not underrate this ‘computer’, it will turn out to be very powerful!
Suppose we are now represented with a more complicated problem. We will do something very strange that will turn out later to be reasonable. Instead of inserting new inputs to the same computer, we will change our computer continuously until it fits the new problem. The theory (that is, quantum theory) shows that if we do it slowly enough we can read the results off the ‘computer’ by reading the new location of the ball (all this is done on a quantum apparatus so the example here with a ball is solely for illustration purposes).
Evolving our computer continuously from the initial state to its final shape is done in the same way as evolving the function. We change the coefficients of our old function f(x) = x2 and turn it slowly into the function f(x) = ax3+bx2+cx+d. The coefficient of x3 must go from 0 to a, the coefficient of x2 must go from 1 to b, the coefficient of x must go from 0 to c, and the coefficient of 1 must go from 0 to d. This will take our simple equation, which we’ve already found the solution to, into the more complicated equation, the one we are trying to solve. It is implicitly suggested here that we know how to build a computer for the initial and simple problem, and that we know how to evolve the initial computer continuously into the final computer by playing with the stones. The only thing we do not know is the solution to the new problem.
|
What will happen to the ball? Well, if you do everything very slowly you will find the ball resting in a location which is the minimum point of the new equation. At least this is what the adiabatic principle of quantum mechanics is all about. Changing the view very slowly guarantees that if you start with a solution to the first simple equation, (a solution that you can easily compute) you will end up with a solution to the complicated equation that you want to solve. All in all, you have solved the mathematical problem physically without using manipulations of variables.
A few technical remarks for the professional reader: the example above is written very heuristically, hiding the physical details. In fact, we look at what is called the Hamiltonian, which is the operator that is responsible for the time evolution of the state vector. The initial Hamiltonian has minimal eigenvector that corresponds to the solution of the initial simple problem. We change this Hamiltonian very slowly until it becomes the final Hamiltonian. This is the Hamiltonian with minimal eigenvector that corresponds to the solution of our final problem. We can build the final Hamiltonian but we do not know its minimal eigenvector. If we evolve the Hamiltonians slowly enough, then having started with a minimal eigenvalue of the simple equation, we end up with a minimal eigenvalue, which this time is the solution we were seeking. If the evolution is done too quickly, we might end up with an eigenvalue with a higher energy.
This method looks very powerful, almost magical! Alas, there are several difficulties in its application. One of the questions is how slowly do we have to go. It could be that we reduce some type of complexity of the mathematical problem but we pay with time complexity. Therefore, it is not clear if such a computer is more or less efficient than other computers. Well, it turns out that for some problems, its efficiency could be better than the efficiency of classical computers.
Where does the name ‘adiabatic’ come from?
The term Adiabatic comes from the theory of thermodynamics. Adiabatic means ‘without changing the amount of heat’. There are several processes that one wants to conduct without changing the amount of heat. Usually, these processes are done very slowly. This guarantees that they will be reversible. Quantum computation is also a reversible process, and the above computation is carried out very slowly, hence the term adiabatic.
You can see that adiabatic computation raises some interesting problems as to the relation between classical and quantum computation.
Further reading:
For further reading see Quantum Computation by Adiabatic Evolution, by E.Farhi, J.Goldstone, S.Gutmann, and M.Sipser.
TFOT reported in 2007 on the Canadian company D-Wave which reportedly demonstrated a 16 and later on 28-Qubit Quantum Computer under the title “adiabatic quantum computing”.
About the author: Boaz Tamir holds a Ph.D. degree in Mathematics from the Weizmann Institute of Science. In 2008 he recived a second Ph.D. from the department of History and Philosophy of Science at the Bar Ilan University.
