ISIS Report 02/09/08

Quantum Computer or Red-Flag?

A Canada-based company claims to have built the first prototype quantum computer and attracted US$60 million in venture capital. Dr. Mae-Wan Ho investigates

A fully referenced version of this article is posted on ISIS members’ website. Details here

An electronic version of this report with full references, can be downloaded from the ISIS online store. Download Now

Building a quantum computer that could solve problems much faster than the classical computer or are intractable to it has become the holy grail of a new breed of quantum information technologists [1, 2] (Quantum Computer? Is It Alive?, ISISNews 11/12; The Quantum Information Revolution, SiS 22).  

Some start-up companies have even begun to attract serious venture capital. One of them, D-wave Systems [3, 4] (see Box 1), announced a potentially commercially viable quantum computer prototype on 19 January 2007.This was followed by public demonstrations in February and November, at which the baby computer, with 16 and then 28 quantum bits,  was ostensibly solving problems that included a sudoku puzzle and picture recognition.      

However, many of D-Wave’s claims are hotly disputed by researchers within the academic community. One notable critic, Scott Aaronson, runs a blog [5] that also hosts many postings from other scientists, and it does a lot to identify the problems and credibility gaps in the company’s claims. In response to fierce criticisms, a representative of D-Wave admitted that the sudoku puzzle was essentially pre-digested by a classical computer into bite-size (possibly trivial) chunks before it was fed into the quantum computer. The most serious question of all is whether the prototype is really a quantum computer. There is genuine interest in getting to the bottom of the science and technology, but also a collective anxiety that if D-Wave’s claims turn out not to be true, that would damage the reputation of the field and discourage both public and private funding.

So let’s try and unravel some of the mysteries and magic of quantum computation.

What is quantum computation?

Quantum computation is computation based on the quantum mechanical effects of superposition and entanglement [1, 2,  6, 7] (see Quantum World Coming, and How Not to Collapse the Wave Function, SiS 22). Quantum superposition is the simultaneous co-existence of often contrary states such as the proverbial Schrõdinger’s cat being dead or alive, and the spin of an elementary particle being up or down. Quantum entanglement is when different objects or particles behave as one system no matter how far apart they are, and measuring the state of one of them simultaneously determines the state of the other.

Quantum computation operates on the quantum bit or ‘qubit’ instead of the ordinary bit in classical computing. While the ordinary bit is a simple binary 1 or 0, the qubit can hold 1, 0, or crucially, a quantum superposition of 1 and 0. In fact, it can hold anything up to an infinite number of values in superposition [1, 2. 8]. Quantum computers can in theory do computations that are impossible with classical computers or achieve exponential speedup in solving certain problems (see Box 2).

Difficulties in building a quantum computer

There is no shortage of candidate materials for making quantum computers [1, 2, 8]; in principle, anything that can be prepared in the quantum states of superposition and entanglement. These include superconductors, trapped ions, optical lattices, quantum dots, nuclear magnetic resonance (NMR) on molecules in solution, solid state NMR, electrons on helium, molecular magnet, fullerenne-based Electron Spin Resonance, and so on. 

There are practical difficulties in building a quantum computer. One major problem is keeping the components of the computer in a coherent state, so superposition and entanglement can survive for as long as it takes to solve the problem. For most of the candidates, the slightest interaction with the external world would cause the system to lose coherence.

In addition, the material used must be scalable, i.e., it must be possible

to increase the number of qubits for the computer to be really useful; the qubits must also be initializable to an arbitrary starting state; and they must be read easily, so that the answer can be obtained from the computer.

Enters the adiabatic quantum computer

It so happens that the adiabatic quantum computation model has all the required properties of quantum computation, and is also easiest to implement. That’s what D-Wave claims to have done [4].

They have built the world’s first adiabatic quantum computer out of superconductors, and it is the only one that’s scalable, to “thousands of qubits before the end of 2008”, as promised in July this year [9].

Adiabatic quantum computation (AQC) relies on the adiabatic theorem to do calculations [10, 11], and operates differently from standard quantum computation (see Box 2). In AQC, one must construct a complex Hamiltonian (an energy function) whose ground state (minimum energy level) describes the solution to the problem of interest. Next, prepare a system with a simple Hamiltonian and initialize that to its ground state. Finally, the simple Hamiltonian is adiabatically (slowly and without heat exchange) evolved to the complex Hamiltonian. According to the adiabatic theorem, the system remains in the ground state, so at the end, the state of the system describes the solution to the problem. AQC is known to be a universal model of quantum computation [12], i.e., it can do everything that can be done with standard quantum computation.

AQC is a possible method to get around the problem of quantum decoherence. As the quantum system is in the ground state, interference from the outside world cannot make it move to a lower state. If the energy of the outside world, i.e., the temperature of the bath, is kept lower than the minimum energy gap g_m between the ground state and the next higher energy level, the system has a proportionally lower probability of going to a higher energy state. Thus the system can stay coherent for as long as needed.

In practice, as the Hamiltonian is gradually changed, quantum behaviour occurs when multiple qubits are close to a tipping point. It is exactly as this point when the ground state gets arbitrarily close to a first (excited) energy level that a slight disturbance could take the system out of the ground state and ruin the calculation. Trying to perform the calculation more quickly increases the external energy, and scaling up the number of qubits makes the minimum energy gap at the tipping points smaller. In order for the evolution to remain adiabatic throughout, the total time t_f required scales as 1/ g_m ² [13], which means that the bigger the computer, the longer it would take to solve a problem.

The main assumption of the adiabatic theorem is that a well-defined minimum energy gap g_m exists. But in a more realistic situation with decoherence influences from the environment, the energy levels of the qubit register in the quantum computer tend to be smeared out by environmental noise into a continuous band W that allows incoherent tunnelling between the two qubit states. As the broadening typically increases with the number the qubits while the minimum gap g_m decreases, the realistic large-scale system eventually fall into the incoherent regime where the broadened band  becomes much larger than the minimum energy gap, i.e., W>> g_m. This means that the adiabatic theorem will no longer apply. Another difficulty is that as environmental temperature T cannot be reduced indefinitely, it will inevitably be larger than the minimum gap g_m at some point in scaling up. So, according to the latest publication from D-Wave Systems [14], “a new way of understanding the AQC performance becomes necessary.”

Their investigation shows that AQC in the incoherent regime where the minimum energy gap g_m is much smaller than W and T, the probability of getting the right result varies from 1 to ½ for slow evolution. The required computational time in the global scheme is independent of decoherence and temperature T. So even if the large T reduces the probability of getting a correct result to ½, one only needs to repeat the computation on average two times.

The snag is that is that it does not give optimal performance that coherent AQC offers, and for some problems such as the search of a random database, it takes just as long as a classical computer.

The jury is out

Seth Lloyd at the Massachusetts Institute of Technology (MIT) in California, USA, one of the pioneers in quantum computing, and a collaborator in research with D-Wave, is sanguine about AQC because it is a “particularly physical way of trying to solve hard problems.” He is referring to the fact that electrons tend to inhabit the lowest energy level (ground state), especially at low temperatures. And that’s what AQC is based on.

The most interesting aspect of adiabatic quantum computation is that no one knows for sure whether it works in practice.” Lloyd writes in Technology Review MIT [15]. “It may be that for any meaningful problem, the system would have to ooze so slowly that it would take the age of the universe to return an answer. Conversely it may be that even the hardest problem will succumb to an adiabatic quantum computer. Despite the concerted attention of a bevy of physicists and mathematicians, the question of whether adiabatic quantum computing works remains open….” .

In 2002, Lloyd and his graduate student created a design for an AQC based on the superconducting technology that had inspired D-Wave. “At that point, things got interesting”.

Lloyd pointed out that D-Wave has raised about $60 million in funding from venture capitalists, and that as a private company, “it is responsible primarily to its investors rather than to the scientific community.” So it was not surprising that in announcing its success in building an adiabatic quantum computer, the company focussed on commercial applications rather than scientific details. He complained that the press release “provided no device specification that would allow the scientific accuracy of its claims to be assessed. “It seemed possible that the computer was simply finding solutions by being cooled down to its ground state, a fairly dull and not-so-quantum mechanical process, rather than performing the more subtle adiabatic procedure..”

The company’s defence is that such details have to be kept commercially confidential [5], presumably to protect the investments.

Lloyd suggests for a start that D-Wave should be able at some point during the adiabatic computing process to demonstrate that the qubits are indeed in a superposition of both 1 and 0 [15].

Scott Aaronson is even less convinced; he says that [16] “all D-Wave has produced is an extremely expensive and inefficient classical computer with a grand total of 28 bits.” Also he is critical of D-wave’s cavalier claim that its machine will solve ‘NP-complete’ problems that are intractable for classical computers, the best known example of which is finding the shortest route for a travelling salesman visiting a number of cities. Almost all computer scientists also believe such problems cannot be efficiently solved using a quantum computer. Aaronson believes the D-Wave scientists are deceiving themselves, and the company pretty much “a red-flag factory”.

Both Aaronson and Lloyd believe that quantum computers are possible in principle, and that D-Wave’s approach may even get there, but hasn’t done so yet.

Can one really build a quantum computer?

I wonder if the problem isn’t deeper than just finding the right hardware for making the quantum computer. Nobel laureate quantum physicist Richard Feynman first proposed in 1981 that only a quantum computer would be able to simulate quantum processes [15], and as Seth Lloyd points out, the advantage of adiabatic quantum computing is that it uses a particularly physical, potentially quantum, process in solving problems. But can it really simulate physical reality? That was the original motivating question for Turing for the classical computer as it was for Feynman in the case of the quantum computer [1].

Gerald Milburn writing in 1998 [17] asserted that “the physical world is a quantum world”, which makes “a quantum computer not only possible, but inevitable.” He said it might take decades or perhaps a century, but, “a commercially viable quantum computer is a certainty.” Milburn and others basically believe that not only will the quantum computer be able to simulate reality it will be part of the fabric of reality.

I agree that the physical world is a quantum world [18] Quantum Phases and Quantum Coherence, SiS 22) but doubt whether quantum computers as generally conceived is possible, much less inevitable [1, 2].

To my mind, the perfect quantum computer already exists, it is the quantum coherent living organism [19] (see The Rainbow and the Worm, The Physics of Organisms), where astronomical numbers of parallel distributed quantum processing are taking place simultaneously at all times [1]. Take the elementary process of a protein folding into shape, a difficult problem even for the fastest classical computer. It takes about 300 years for a computer to simulate a small peptide of 23 amino-acid residues to fold into shape. By running simulations at the same time on some 140 000 individual computers around the world, researchers took just over three weeks [20]. The protein itself folds to perfection in several microseconds.

The problem of building a realistic quantum computer is at least two-fold. First, there is no quantum algorithm or physical hardware that would simulate the organism apart from the physical, chemical wet ware of the organism itself in all its glorious complexity and molecular diversity. Second, if a perfect quantum computer could be built, it would be radically uncontrollable, like a living organism. It may just give “forty-two” as the answer to the meaning of life, the universe, and everything.

The Institute of Science in Society, The Old House 39-41 North Road, London N7 9DP
telephone:   [44 20 7700 5948]   [44 20 8452 2729]

Contact the Institute of Science in Society