Computation, Quantum or Otherwise
This was originally published in our Weekly Newsletter. Each weekend we’ll treat you to stargazing tips and the latest physics news. You can sign up here!
Human Computers
Industry came from science, and with it came a lot of data. Making decisions based on data - and informed by science - required computation. The first analog computers at scale were rooms full of people. A recent account of this history of human computation - and how the scholars are historically undervalued and overlooked - was framed well in Margot Lee Shetterly’s book Hidden Figures, which also became an excellent movie.
Mechanical Computers
There were of course mechanical computers, but they were large and slow and for many purposes, too expensive to scale. Nevertheless, it’s worth pointing out the first such device was made in the 19th century. Charles Babbage’s Difference Engine and proposed Analytical Engine. Of course, there was no firmware or software or even programming language for such a unique machine. Instead, it relied on a mathematician to compute an algorithm for computation. From that perspective, Ada Lovelace was the world's first developer. Her program? Why, to compute the Bernoulli numbers, of course.
Punch Cards
The interface between human and computer has improved a a lot since then. But the mechanical lengths to which individuals would go to get a program solved would astonish developers today. A fun story along those lines can be found in Feynman's memoirs. He supervised the computation group during the Manhattan Project at Los Alamos, and had a pretty remarkable story about the students he supervised in that group. Back then computers were the size of an entire room and had to be fed punchcards. Programming the computers amounting to preparing a set of punchcards to cycle through the whole machine.
Here’s a quick sample from his full account:
“So I waited, and what happened was this. As the cards went through, sometimes the machine made a mistake, or they put a wrong number in. What we used to have to do when that happened was to go back and do it over again. But they noticed that a mistake made at some point in one cycle only affects the nearby numbers, the next cycle affects the nearby numbers, and so on. It works its way through the pack of cards. If you have 50 cards and you make a mistake at card number 39, it affects 37, 38, and 39. The next, card 36, 37, 38, 39, and 40. The next time it spreads like a disease.
So they found an error back a way, and they got an idea. They would only compute a small deck of 10 cards around the error. And because 10 cards could be put through the machine faster than the deck of 50 cards, they would go rapidly through with this other deck while they continued with the 50 cards with the disease spreading. But the other thing was computing faster, and they would seal it all up and correct it. OK? Very clever.
That was the way those guys worked, really hard, very clever, to get speed. There was no other way. If they had to stop to try to fix it, we’d have lost time. We couldn’t have got it. That was what they were doing.
Of course, you know what happened while they were doing that. They found an error in the blue deck. And so they had a yellow deck with a little fewer cards; it was going around faster than the blue deck. Just when they are going crazy - because after they get this straightened out, they have to fix the white deck - the boss comes walking in.
“Leave us alone, “ they say. So I left them alone and everything came out. We solved the problem in time and that’s the way it was.”
Error Correction
Correcting errors is a big deal in computation in general, and data store more specifically. Resilience to error - a redundancy of information - is the standard around most cloud computing services now. Hadoop, Spark and other big data / parallel processing platforms typically replicate data in triplicate and store it in memory.
Error correcting codes are a bit deal, and often they are fascinating mathematical objects. Notably among those are the Golay Code, which is related to the sporadic, simple finite groups that also have applications as far away as string theory. Or at least super conformal field theories.
Enter Quantum Computers
Today, Quantum Computers today are just emerging from the same level of obscurity and technical frailness. Amazon has recently start offering quantum computing as a cloud service. But what is quantum computing and why are folks hyping it?
For certain types of problems, quantum algorithms can arrive at solutions much faster than ordinary computers. These kinds of problems include decryption via integer factorization (aka Shor’s Algorithm) or inverting an unknown (and necessarily large and complicated) function (Grover’s Algorithm).
The former can achieve exponential improvement in computation performance, dramatically reducing the time it takes to find prime factors. The latter can improve performance from linear to quadratic operational times, which still be a substantial improvement for large functions - like finding particular data in a massive, unstructured dataset.
Since much of modern cryptography - including both privacy and cryptocurrency - relies on public-private keys that are derived from factorization of large primes, the rise of quantum computing will probably require a change in our information security strategies fairly soon. Like any good escalation, the technology behind quantum computers also afford a new form of cryptography that is arguably physically impossible to hack.
Selected, Semi-Technical Articles in Quantum Computing
And, of course, Quantum Computing in Particle Physics
I couldn't resist. One amusing - if specialized - application of quantum computation is quantum field theory itself! Specifically, physicists are working on quantum algorithms to model the complicated dynamics of particle collisions at the LHC. PhysicsWorld published a fun article on the subject, based on the paper by Nachman and friends. Please give kudos and respect to APS for publishing this PRL article in an open access format.
