Computing with Quantum Cats

by John Gribbin

  Published 2014 by Prometheus Books

  Computing with Quantum Cats: From Colossus to Qubits. Copyright © 2014 by John Gribbin. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, digital, electronic, mechanical, photocopying, recording, or otherwise, or conveyed via the Internet or a website without prior written permission of the publisher, except in the case of brief quotations embodied in critical articles and reviews.

  Prometheus Books recognizes the following registered trademarks mentioned within the text: iPad®; iPhone®.

  Cover image © Media Bakery

  Jacket design by Grace M. Conti-Zilsberger

  Inquiries should be addressed to

  Prometheus Books

  59 John Glenn Drive

  Amherst, New York 14228

  VOICE: 716–691–0133

  FAX: 716–691–0137

  WWW.PROMETHEUSBOOKS.COM

  18 17 16 15 14 5 4 3 2 1

  The Library of Congress has cataloged the printed edition as follows:

  Gribbin, John, 1946- author.

  Computing with quantum cats : from Colossus to Qubits / by John Gribbin.

  pages cm

  Includes bibliographical references and index.

  ISBN 978-1-61614-921-5 (hardback)

  ISBN 978-1-61614-922-2 (ebook)

  1. Quantum computers. I. Title.

  QA76.889.G75 2014

  006.3'843--dc23

  2013039964

  Printed in the United States of America

  Acknowledgments

  Introduction: Computing with Quantum Cats

  PART ONE: COMPUTING

  1 Turing and the Machine

  A Child of Empire—Sherborne—Cambridge…and Princeton—Bletchley and the Bombe—The Flowering of Colossus—Anticlimax: After Bletchley

  2 Von Neumann and the Machines

  Jancsi—Johnny and the Institute—Johnny and the Bomb—The American Heritage—A German Diversion—The Second Strand—ENIAC—Von Neumann Picks Up the Ball—Self-Replicating Robots

  First Interlude: Classical Limits

  PART TWO: QUANTA

  3 Feynman and the Quantum

  MIT—From Princeton to Los Alamos—Schrödinger and His Equation—The Experiment with Two Holes—Integrating History—A PhD with a Principle—Cats Don't Collapse—The Gateway to Quantum Computation—Fredkin, Feynman and Friends

  4 Bell and the Tangled Web

  Dropping the Pilot—Von Neumann Gets It Wrong—Spooky Action at a Distance—Bohm Does the Impossible—From Belfast to Bohm, and Beyond—Von Neumann's Silly Mistake and Bell's Inequality—First Fruits—Closing the Loophole

  Second Interlude: Quantum Limits

  PART THREE: COMPUTING WITH QUANTA

  5 Deutsch and the Multiverse

  Everett Sets the Scene—Solving the Measurement Problem—The Worlds of Deutsch—A Measure of Universes—The Good: Cracking Codes Conveniently—The Bad: Limits of Quantum Computation—The Ugly: Making It Work

  6 Turing's Heirs and the Quantum Machines

  The Key Criteria—Josephson and the Junction—Leggett and the SQUID—Computing with SQUIDs—Corralling with Quantum Dots—The Nuclear Option—The Nuts and Bolts of NMR—Trapped Ions Take a Bow—The Teleportation Tango—Fun with Photons

  Coda: A Quantum of Discord

  Notes

  Sources and Further Reading

  Picture Acknowledgments

  Index

  This book grew out of conversations with the quantum computer group at Sussex University, in particular Winfried Hensinger, who opened my eyes to the dramatic progress now being made in the practical application of ideas that seemed esoteric even a few years ago. I already knew something about those esoteric ideas thanks to David Deutsch, of the University of Oxford, and Terry Rudolph, at London's Imperial College. Thanks also to the helpful people at Bletchley Park, Gonville and Caius College, Cambridge, and the David Bohm Archive at Birkbeck College, London; and to John Carl, Frank Carter, Terry Clark, David Darling, Artur Ekert, Lucien Hardy, Mark Hogarth, Betty Houghton, Tero Keski-Valkama, Tony Leggett, Lawrence Lerner, Irfan Siddiqi and Michelle Simmons.

  Both experimental and theoretical physicists are currently excited by the prospect of developing computers operating on quantum principles. There is also a lively interest among the military—a source of a great deal of funding—and big business. Quantum computation is one of the hottest scientific topics of the second decade of the twenty-first century, and it all depends on manipulating quantum entities (electrons, photons or single atoms) that are in two states at the same time—exactly like Schrödinger's famous “dead and alive” cat. Hence my title.

  This is a watershed time in computational science, because quantum computers do much more than operate faster than conventional computers—although they certainly do that. For example, they can be used to crack codes that are literally uncrackable by conventional computers, which is a major reason for the interest of the military and big business. This has been known in theory for decades (Richard Feynman was one of the first people to speculate along these lines); but now working quantum computers are actually being used. Admittedly, as yet they involve very large pieces of expensive and temperamental equipment solving very simple problems, such as finding the factors of the number 15. But nobody who has seen the evolution of conventional computers from expensive, temperamental, laboratory-sized machines full of glowing “valves” to the PC and the iPad can doubt that within a decade the computer world will be turned upside down. More esoterically, such machines will enable physicists to come to grips with the nature of quantum reality, where communication can occur faster than the speed of light, teleportation is possible, and particles can be in two places at once. The implications are as yet unknowable, but it is fair to say that the quantum computer represents an advance as far beyond the conventional computer as the conventional computer is beyond the abacus.

  Conventional computers—often referred to as “classical” computers—store and manipulate information consisting of binary digits, or bits. These are like ordinary switches that can be in one of two positions, on or off, up or down. The state of a switch is represented by the numbers 0 and 1, and all the activity of a computer involves changing the settings on those switches in the appropriate way. My own computer is, while I am writing these sentences using a word processing program, also playing music, and has an e-mail program running in the background that will alert me if a new message comes in. All of this, and all the other things computers can do, is happening because strings of 0s and 1s are being moved and manipulated inside the “brain” of the computer.1

  Eight bits like this make a byte, and because we are counting in base two rather than base ten the natural steps up the ladder of multiplication do not go 10, 100, 1,000 and so on but 2, 4, 8, 16 and so on. It happens that 210 is 1,024, which is close to 1,000, and we are used to using base 10, so 1,024 bytes is called a kilobyte. Similarly, 1,024 kilobytes make a megabyte, and 1,024 megabytes make a gigabyte. The hard drive of my laptop computer can store 160 gigabytes of information, and the “brain”—the processor—can manipulate up to 2 gigabytes at a time, all in the form of strings of 0s and 1s (this is now a rather old machine; “this year's model” can do even better).

  But a quantum computer is something else. In the quantum world, entities such as electrons can be in a superposition of states. This means that quantum switches can be in both states, on and off at the same time, like Schrödinger's “dead and alive” cat. Electrons themselves, for example, have a property called spin, which is not quite the same as what we mean by spin in our everyday world, but can be thought of as mea
ning that the electron is pointing either up or down. If we say that “up” corresponds to 0 and “down” corresponds to 1, we have a binary quantum switch. Under the right circumstances, this switch can exist in a situation where it is pointing both up and down at the same time. Or it can be pointing either up or down, giving three possibilities!

  A single quantum switch that is in a superposition of states can “store” the numbers 0 and 1 simultaneously. By extension from the language of classical computers, such a quantum switch is called a qubit, short for “quantum bit” and pronounced “cubit,” like the biblical unit of length. The qubits are the “quantum cats” of my title. The existence of qubits has mind-blowing implications. Two classical bits, for example, can represent any of the four numbers from 0 to 3, because they can exist in any of four combinations: 00, 01, 10 and 11. To represent all four of the numbers (0, 1, 2 and 3) simultaneously, you would need four pairs of numbers—in effect, one byte. But just two qubits can represent all four of these numbers simultaneously. A set of bits (or qubits) operating as a number store in this way is called a register. A register made up of eight qubits (a single qubyte) can represent not four but 28 numbers simultaneously. That's 256 numbers stored in a single qubyte. Or, as Oxford physicist David Deutsch would put it, it represents 256 different universes in the Multiverse, sharing the information in some way.

  In a functioning quantum computer, any manipulation involving an operation on each of those 256 numbers represented by that qubyte of information is carried out simultaneously in all 256 universes, as if we had 256 separate classical computers each working on one aspect of the problem in our universe, or one computer that had to be run 256 times, once for each value of the number. Looking further into the future, a quantum computer based on a 30-qubit processor would have the equivalent computing power of a conventional machine running at 10 teraflops (trillions of floating-point operations per second)—ten thousand times faster than conventional desktop computers today, which run at speeds measured in gigaflops (billions of floating-point operations per second). These numbers hint at the prodigious power of a quantum computer; but the trick is to find a way of getting useful information out at the end of the calculation—getting the different universes to interfere with one another in the right way to produce an “answer” that we can understand, without destroying the useful information along the way. This trick is now being achieved by several groups around the world, including a research team at my home base, Sussex University. This book will tell you how, in principle, to build a quantum computer. But to set this in context, I want to go all the way back to the beginning of machine computation as we know it—all the way back to the 1930s, less than a long human lifetime ago, and the work of the man who started the ball rolling.

  Card-based census counting machine, 1890.

  One of the forerunners of the computer.

  If necessity is the mother of invention, the computer had two mothers—cryptography and the hydrogen bomb. But there was only one father: Alan Mathison Turing.

  A CHILD OF EMPIRE

  Turing was conceived in India, where his father, Julius, was a member of the Indian Civil Service helping to administer this jewel in the crown of the British Empire; but he was born, on June 23, 1912, in Maida Vale, London, when his parents were on home leave. He already had a brother, John, born in India on September 1, 1908. When Julius returned to India their mother, Sara,1 stayed in England with the two boys, but only until September 1913, when she rejoined her husband and left the children in the care of a retired army colonel and his wife, who lived at St. Leonards-on-Sea in Sussex. There was a nanny who looked after the two boys and the colonel's four daughters, together with another boy whose parents were overseas, and later three cousins of Alan and John. Their mother returned for the summer of 1915, staying with the boys in rented rooms in St. Leonards, and both parents came to England in the spring of 1916—the first time that Alan really had an opportunity to get to know his father. At the end of this leave, in August, Julius Turing returned to India for his next three years’ tour of duty. John had already been sent away to school at Hazelhurst, in Kent; Alan, having been just one of a motley group of children, now became in effect the only child of a single parent, who took him almost everywhere with her, including to the High Anglican church she attended (which he hated) and to art classes (she was an accomplished watercolorist), where he was the darling of the female students.

  Alan was remembered as a bright, untidy child with a predilection for inventing his own words, such as “quockling” to describe the sound of seagulls and “greasicle” for a guttering candle. It was impossible to pull the wool over his eyes—when his nanny tried to let him win a game they were playing by making poor moves, he saw through the subterfuge and was infuriated; when his mother was reading him a story and left a dull passage out, he yelled: “You spoil the whole thing.”2 Nor was he ever in any doubt about the accuracy of his own world-view: he knew, for example, that the fruit which tempted Eve in the Garden of Eden was a plum. But he never could tell left from right, and marked his left thumb with a red spot so that he would know which was which.

  Having taught himself to read (from a book appropriately called Reading without Tears), Alan first encountered formal education at the age of six, when his mother sent him to a local day school to learn Latin. This failed to stir his interest, but highlighted his great difficulty with the physical process of writing, especially with the ink pens in use at the time. His work was always a mess of scratchy scribbles, crossings-out and blots, reminiscent of nothing so much as the spoof handiwork of Nigel Molesworth in the stories by Geoffrey Willans and Ronald Searle.

  Alan's next meeting with his father came in 1919, when Julius's leave included a holiday in Scotland: here the seven-year-old boy impressed his family on a picnic by tracking the flights of wild bees to their intersection to find honey. But in December both parents sailed for India, and Alan returned to the colonel's house in St. Leonards while John went back to school in Hazelhurst. The next two years saw a change in Alan. When his mother next returned, in 1921, she found that the vivacious and friendly boy she had left in England had become “unsociable and dreamy,” while his education had been so neglected that at nearly nine he had not learned how to do long division. She took him away for a holiday in Brittany, and then to London, where she taught him long division herself. She later recalled that when he had been shown how to find the square root of a number, he worked out for himself how to find the cube root.

  At the beginning of 1922, it was time for Alan to follow his brother John to Hazelhurst, a small school for thirty-six boys aged from nine to thirteen, with just three teachers and a matron who looked after the boys. The brothers were together at Hazelhurst for only one term before John left at Easter for Marlborough College and the public-school education for which “prep” schools such as Hazelhurst were preparing their boys. The same year, Alan was given a book called Natural Wonders Every Child Should Know, by Edwin Brewster. This first encounter with science made a deep impression on him, especially the way the author likened the workings of the body, even the brain, to a machine. He was less impressed by the sporting activities that young English gentlemen of the time were expected to enjoy (or at least endure), and later claimed that he had learned to run fast (he became a very good long-distance runner as an adult) in order to keep away from the ball during hockey. He was also disturbed by the imprecision of some of his teachers, and wrote to John that one of them “gave a quite false impression of what is meant by x.” His concern was not for himself, but that the other boys might be misled.

  The summer of 1922 brought the return of Alan's father on leave once more, and another happy family holiday in Scotland. But in September his parents left him back at Hazelhurst, departing down the drive of the school with Sara biting her lip as she watched her son running futilely after the taxi, trying to catch up with them. Bored by school, Alan achieved nothing spectacular in the way of marks, but loved inv
enting things and developed a passion for chemistry—which was purely a hobby: God forbid that a prep school like Hazelhurst should have anything to do with science. Science was almost as conspicuous by its absence at most public schools, so when in the autumn of 1925 Alan surprised everyone by doing well in the Common Entrance examination that was a prerequisite to the transition, his future presented his parents with something of a conundrum. John made an impassioned plea to their parents not to send his unusual younger brother to Marlborough, which “will crush the life out of him,” and Sara Turing worried that her son might “become a mere intellectual crank” if he failed to adapt to public school life. The puzzle of what to do with him was solved by a friend of hers who was married to a science master at Sherborne, a school in Dorset established back in 1550 and brought into the modern public school system in 1869. The friend assured Sara that this would be a safe haven for her boy, and Alan started there in 1926.

  SHERBORNE

  He was due to arrive for the start of the summer term, on May 3, from Brittany, where his parents were living to avoid paying British income tax. On the ferry to Southampton, Alan learned that there would be no trains, because of the general strike; totally unfazed, and still a month short of his fourteenth birthday, he cycled the 60 miles to Sherborne, staying overnight at Blandford Forum. This initiative was sufficiently unusual to merit a comment in the Western Gazette on May 14. The same initiative and independence were shown a little later when Alan worked out for himself the formula known as “Gregory's series” for the inverse tangent, unaware that it had been discovered in 1668 by the Scottish mathematician James Gregory (inventor of a kind of telescope that also bears his name), and even earlier by the Indian mathematician Madhava.

  Alan soon settled into his old habit of largely ignoring lessons that he found boring, then doing well in examinations, while continuing his private chemistry experiments and amusing himself with advanced mathematics. At Sherborne, grades depended on a combination of continuous assessment and examinations, each marked separately but with a final combined mark. On one occasion, Alan came twenty-second out of twenty-three for his term's work, first in the examinations, and third overall. His headmaster did not approve of such behavior, and wrote to Alan's father: “I hope he will not fall between two stools. If he is to stay at a Public School, he must aim at becoming educated. If he is to be solely a Scientific Specialist, he is wasting his time at a Public School.” But Alan escaped expulsion, and was rather grudgingly allowed to take the School Certificate examination, which had to be passed before he could move on to the sixth form at the beginning of 1929. His immediate future after school, however, was decided as much by love as by logic.