From Schrödinger’s cat to quantum computers (II)

From analog computers to quantum computers

In this second part of the talk, we move on to discuss quantum computers. They are fashionable, they’re cute. You can boast in bars that you work in quantum computers and you’ll get free beers. But… are they, really, more powerful than their classical counterparts? I have devised a way to explain what is the main difference, and why they might well be more powerful. And it uses an old and forgotten concept: that of analog computer.

What is an analog computer? It is a machine designed to solve a certain computational problem, using physics. For example, the Antikythera mechanism. It is a device which was found in a sunk Greek ship from the Hellenistic times. It has some gears which, when spinning, represented the motion of planets, and helped predict their positions in the sky. In a certain way, the astrolabe is also an analog computer.

The Antikythera mechanism, an early analogue computer.

But let us give a simpler example. Imagine that you must order a large set of numbers, from lowest to highest. You can design an “ordering computer”, in the following way: get some spaghetti and cut each of them to a length corresponding to one of the numbers. Then, you take the full bunch and hit the table with it, flattening its bottom. Now, you only have to pick the spaghetti in order: first, second, third…

spaghetti
Another cute example is the problem of finding the most distant cities in a roadmap. I give to you a list of cities, and the distances those which are linked by a road. An analog computer can be built with a long thread. We cut it to pieces representing the roads joining
each pair of cities, and them we tie them in a way resembling the full roadmap. The knots, of course, represent the cities. Now we pick the roadmap by one of the knots, and let the rest hang freely. We look at the knot which lies the lowest. Now we pick it, and let the rest hang freely. In a few iterations we converge to a cycle between to knots. Those are the most distant cities in the roadmap.

citynetwork
And another one! Consider a 2D map on which we are given the positions of a few cities. We are asked to design the road network of minimal length which joins them all. Sometimes it will be convenient to create crossroads in the middle of nowhere. This is called the Steiner tree problem, and it is considered a “hard” problem. There is a way to solve it fast with an analog computer: we get a board and put nails or long pins on it representing the cities. Now we immerse the full board into soapy water and take it out very slowly. A soap film will have developed between the nails, with some “crossroads”, joining all pins. If we do it slowly enough, the film will have the minimum energy, which means that the total roadmap will have the minimal length. This idea is important: we have converted our computational problem into one that Nature can solve by “minimizing the energy”.

Experiments by Dutta and coworkers, http://arxiv.org/abs/0806.1340

Experiments by Dutta and coworkers, http://arxiv.org/abs/0806.1340

Our paradigm problem to solve will be the spin glass problem. It sounds like a technical problem, but I have a very nice way to explain it: how to combine your goals in life and be happy. Well, we all want things which simply do not go together easily: work success, health, true love, going out with the buddies, children, etc. Let us represent each of those goals as a small circle, and give a weight to each of them. Now I draw “connection” lines among the goals, which can be positive, if they reinforce each other, or negative, if they are opposite. Each line has a “strength”. So, for example, “having children” is highly incompatible with “going out with the buddies”, but it is strongly compatible with “finding true love”. Which is the subset of those goals I should focus on in order to maximize my happiness?

Each node is a "target", blue links mean "compatible", and red means "incompatible".

Each node is a “target”, blue links mean “compatible”, and red means “incompatible”.

I will tell you how to solve this problem, which is truly hard, using an analog computer. We put atoms in each node, and we make “arrow up” mean “focus on this goal”, while “arrow down” will mean “leave it”. Now, experimental physicists, which are very clever guys, they know how to “lay the cables” so that the energy is minimized when the system represents the maximum happiness. Cool.

No, not so cool. The problem is the “false minima”. Imagine that you’re exploring the bottom of the ocean and you reach a very deep trench. How can we know that it is, indeed, the deepest one? Most of the time, the analog computer I just described will get stuck in the first trench it finds. And, believe me, there are many. It’s just the story of my life: I know I can do much better, but… I would have to change so many things, and intermediate situations are terrible. But today I feel brave, I really want to know how to be happy.

landscape
Quantum mechanics comes to our help. Remember that atoms are quantum, and that their arrows can point in some other directions, not just up or down. So I put my analog computer, made of real (quantum) atoms inside a giant magnet, which forces all spins to point rightwards. Remember: \left|\rightarrow\right> = \left|\uparrow\right> + \left|\downarrow\right>, so now each one has 50% probabilities of pointing up and pointing down, like Schrödinger’s cat. Maximal uncertainty. I know nothing about what to do. Let us lower slowly the power of the magnet. Nature always wants to minimize the energy, so we pass through some complex intermediate states, highly “entangled”, in which some atoms decide early which position to choose. They are the “easy atoms”, for which no competition with other atoms exist. The “difficult atoms” are the ones in which you have more doubts, and they stay in a “catty” state for longer time. When, finally, the power of the magnet has come to zero, all atoms must have made up their minds. We only have to read the solution, which is the optimal happiness one.

Sure? It all depends on the speed at which we have turned the magnet off. If I am greedy and do it fast, I will ruin the experiment, and reach any “false minimum” of the energy. So, a false maximum of the happiness. All this scheme is called “adiabatic quantum computation”. For physicists, “adiabatic” means “very slow”.

How slow should I go? Well, this is funny. Apparently, most of the time it’s not very important. But there is a critical moment, a certain “phase transition” point, when the entanglement between the atoms is maximal. Then, it is crucial to advance really slowly. As an analogy, think that you have to take a sleeping baby from the living room to his cradle. There is always a fatidic moment, when you have to open the damned doorknob. If you are unlucky, you may have more than one. But, for sure, at least you’ll have one.

And, what if we’re so clever that we have left all doors open? That’s what worries us physicists most. There is a conjecture, that there is some kind of “cosmic censorship”, that will impose a closed door in the path of every difficult problem. Nature might be evil, and has put obstacles to the possibility of solving difficult problems too fast. It would be a new limit: the unsurmountable speed of light, the unstoppable increment of entropy… and now that? It is worth to pay attention: the next years will be full of surprises.

This is the second part of a lecture I originally delivered in the streets of Madrid for the “Uni en la calle”, to protest the budget cuts in education and science in Spain, in March 9, 2013. And, later at a nice high school in Móstoles.

Advertisements

Superhighway (or funny minima)

I proposed this problem to my calculus students. It turned out to be more interesting than I thought (thanks, Ignacio and Noema).

The government intends to build a superhighway without speed limit so, therefore, without curves. It will start from city A, and should pass as close as possible to cities B and C.

In order to solve it you should start by stating what you mean by “as close as possible”. An option is to minimize the sum of the distances. But then, you get the following funny configuration:

Cities B and C are at the same distance from A, and make up a right angle. Intuition dicatates that the best route for the highway would be the bisector. Let d(A,C)=d(A,B)=1. Then, the sum of the distances from the cities to the highway is \sqrt{2}. But there is a better highway! You can just break the symmetry between B and C and make the road pass through C exactly. Then, the sum of the distances is just… 1.

If this was a real highway, the politician in charge would tell us that symmetry is also worth. Citizens of B may riot with un asymmetric solution… So, now let us change our target function. Let us minimize the sum of the squares of the distances. In that case, the bisector gives a square total distance of 1, same as the asymmetric road… Can you explain it?

Which is the best choice? Of course, it depends on the reason for which you’re fighting with the problem. If it is just to pass an exam, any of them will do…:) [Of course, there are many other alternatives. A student minimized the sum of the squares of the distances from the points to the straight line in the y direction. This makes sense in some cases, e.g.: when you’re fitting experimental points to a line.]

So, choosing the right function to minimize is crucial in practice… Kadanoff once explained in a talk that the government of the city of London has ordered a huge global study of traffic, taking into account both public and private transport, energetic and economic issues, taxes and prices, eeeeeverything. They made an enormous computer program that was running for days and, finally, told them the answer, how to optimize traffic in London. They had to remove all traffic lights. Why???? The program had many things into account… also the fact that in street car accidents, it’s normally old people who die. And old people do not pay taxes, they receive their pension money from the government. So it was convenient to remove the traffic lights… So, you see: garbage-in, garbage-out. Yes, maths is a nice girlfriend, she gives you more than you put in the relationship… but she can do no miracles. If you’re stupid, she can’t fix that…

Arco capaz… is there an English word?

Hm… I should start this story from the beginning, as Alice once was told. I make a living from teaching college maths in Madrid, but half of the time I do it in English. (No, no randomness involved, though). I asked my calculus students to solve this problem:

“A soccer player runs with the ball perpendicularly to the goal line, but a little bit to the right of it. Forgetting about the opponent players, when should he shoot?”

My idea was just an optimization problem, but, alas, some of my boys and girls are really smart… and one of them asked me: “Javi, how do you say ‘arco capaz’ in English?” Oh, embarrassment! I didn’t know the word!

Ehm… let’s go by parts, as Jack the Ripper said. For those of you not fluent in the language of Cervantes, arco capaz is the geometrical locus of the points in the plane from which a given segment is seen under a certain angle. It must be an arc, as you can see from the pic:

Okey dokey, so the boy was right, you can solve it using this construction. All you need is… well,  won’t say, just give your proposals :)

Anyway, the interesting part comes now. OMG, I felt so bad that there was a technical word I couldn’t say in English… so I run to wikipedia (all praise be given to her), clicked arco capaz in Spanish, clicked the English button et… voilà? No! It took me to a concept which is completely unrelated!

Hm… how could wikipedia (APBGTH) fail me???? Then I found this link in wordreference (also all praise… whatever) in which… the hypothesis was advanced that there was no word in English for that concept! They even cited a webpage where Patrick Morandi, head of dept of maths in the New Mexico state university, used the Spanish term…

After that I found few entries with the French term “arc capable”, but the term in Spanish is really common!! All first year students in science and engineering have heard about it! So, perhaps this is the second word (first in science) that goes from Spanish to English. The first one was mosquito

But why is the concept not lexicalized in English? I can give no citations, but I heard (my grandpa, long back) that it was born in navigation science. Using it, you can find out where you are on the map very easily as soon as you have three landmarks that you can recognize… Did sailors use a different technique in other countries? Maybe they used it but they didn’t give a name to it? I can imagine: “Captain Haddock, please draw the two… ehm… yes, draw the two circles and see where do they intersect”, “Which circles?”, “Yes, the circles from which the two given segments are seen under the correct angles…” Messy.

Yes, giving names to the correct things can save a lot of work. Or give a lot of work, if you do it wrong…