Qubits, superpositions, entanglement: Where can quantum computing take us?

The computing industry's 50-year mission to make silicon-based processors smaller and faster will probably come to an end in the next decade or so, as it reaches the atomic level beyond which further miniaturisation becomes impossible.

Already scientists are lining up new alternatives that may yet continue boost processing power, whether it's harnessing the speed and efficiency of optical interconnects to replace copper bottlenecks or adding a fourth circuit element - the memristor - to create more capable chips.

But even further out into computing's future, quantum computing could offer a bold leap into the unknown: computing, but not as we know it.

A quantum computer would really be a fundamentally new type of computer, according to Scott Aaronson, associate professor of electrical engineering and computer science at the Massachusetts Institute of Technology (MIT).

Most types of future computing that have been proposed conform to the Church-Turing thesis - which says that any reasonable, physically realistic type of computer can be simulated by any other reasonable type of computer, even if at a much slower pace.

"For example, I might have a supercomputer that's one million times faster than a Commodore 64 or some crap computer but the crap computer can still simulate the much faster one - it'll just be much, much, much slower but it'll merely be slower by some constant factor," says Aaronson.

"All of the existing computing proposals - whether they're based on silicon or photonics or, I don't know, a system of pulleys and levers - they all satisfy this thesis. Quantum computing is really the first serious proposal that we have that apparently violates that thesis."

As quantum computing appears to step outside Church-Turing's rules, it also means it's able to solve certain mathematical problems that classical computers don't seem capable of solving, at least not without taking a ridiculously long time to do so.

An example of a problem that classical computers struggle with is factoring massive numbers. Current computers find these problems so hard because as the size of the number grow, the problem grows exponentially.

"Anything that grows exponentially - no matter what improvements in engineering there are - it's quickly going to become hopeless," said Aaronson.

"If the only way you know how to solve a problem is by enumerating all possibilities, the number of possible solutions to a problem can just become astronomical - and it can just dwarf any advances in technology."

Quantum computers ought to be adept at solving these problems because of their ability to perform massively parallel computations. However, it's also a problem that suits their "probabilistic" nature - a factor which makes quantum computers useless for...

...many of the everyday tasks we use classical computers for.

Danny Segal, a reader in quantum optics at Imperial College, explains: "What a quantum computer might be able to do for you is to say 'OK, I've been thinking about this for a while and I've come up with 1,000 or 10,000 possible sets of pairs of numbers which have a certain reasonable probability of being the right pair', then you just get an ordinary computer and you just simply check all of those possibilities."

"The quantum computer is 'faulty' in the sense that it's probabilistic - it can only give you with a certain probability what the answer might be and that, for most problems, is useless. Mostly, you'd say 'I don't want a computer that tells me what something might be'. But if you have one of these asymmetric problems [such as factoring] actually that's good enough," he added.

**Quantum computers and the death of encryption **

Modern cryptography is based on the assumption that these factoring problems are very hard - effectively impossible - to solve at the moment.

"It's that phenomenon that underlies almost all of modern cryptography," MIT's Aaronson said. "Any time you order something from Amazon or from eBay or wherever, your web browser is encrypting your credit card number by a code, by some variant of the RSA code, which depends for its security on the belief that factoring enormous numbers is a much, much harder problem than multiplying them.

"So far, that belief has withstood 40 years of tests but if we could build a quantum computer then that would no longer be true."

According to Dave Bacon, assistant research professor at the University of Washington and assistant editor of ACM's *Transactions on Computation Theory* research journal, it's this 'fear factor' that has helped keep funding flowing into research into quantum information processing - despite there being no imminent prospect of commercialising the technology, with a viable quantum computer existing outside a lab remaining decades out, at the very least.

"Governments are funding it because of...

...factoring but also you don't want to be second in this race," Bacon told silicon.com. "That's a major concern for them. It's one of those [research areas] that's easy to sell 'upstairs'."

**What can a quantum computer do? **

But - aside from threatening traditional security models - the question of working out what else quantum computers could be used for will keep researchers busy for years.

According to Bacon one of the most likely applications for quantum computing will be as a tool for scientists.

"There's some hope they'd be useful for chemistry and there's also some hope that they're actually useful for biology because biology probably exploits some quantum effects. Or just understanding large complex molecules is exactly what quantum computers would be good at, as opposed to a classical computer."

But don't expect to be swapping your laptop for a quantum computer any time soon: "Quantum computers would never be used for most computing tasks because they're not necessary for most computing tasks", Imperial's Segal said. "People shouldn't have the notion that they're ever going to get rid of their classical computer and have a quantum computer on their desk because that's not likely to be of any interest to anybody."

Quantum machines created in labs so far remain very small scale, having just a usually fewer than 10 qubits.

A qubit is a quantum bit: the quantum equivalent of a single information register in the memory of a classical computer which can be set to one or zero. However, in a quantum system, the qubit can be set to one or zero or any amount of both at the same time.

"If you want to call a very basic computation which involves just a couple of steps a computation, then yes, we have built quantum computers to an extent," Jason Smith, a lecturer at Oxford University's materials department and tutorial fellow at Mansfield College, told silicon.com. "But that's not what people are interested in. They want something that's actually going to do something useful and so for that you need what we call scalability - you need to be able to take these experiments on a few qubits and you need to be able to expand them to many more qubits and still have the experiment work."

The University of Washington's Bacon added: "In computer science a lot of people spend a lot of time trying to figure out what could [a quantum computer] do? How do you use this massive parallelism? That's what most of the computer scientists do. The physicists on the other hand right spend all this time trying to actually figure out how to build one."

The problem for would-be quantum computer scientists is that until the physicists manage to build one, there's only so much programming the techies can imagine doing on a machine that doesn't exist yet.

"When you programme your [desktop] computer, the great thing about it is you can sit down and hack on it and that's how most computer scientists learn.

"But we don't have a quantum computer to hack around on - so all the hacking is done...

...in our heads, and on sheets of paper, and that's a lot harder to do," Bacon said.

That's because it's extraordinarily difficult to simulate quantum systems efficiently using classical computers: there's just far too much information to keep track of.

"When you want to have lots of quantum systems that you're trying to simulate and all interacting with each other pretty soon it just becomes an unworkable problem," Imperial's Segal said.

However quantum computers are ideally suited to managing lots of variables and modeling complex interactions, so the idea would be to build a network of small-scale quantum machines - so-called toy quantum systems - that collectively equate to a 40 or 50 qubit machine, and use that to simulate more complex quantum systems.

The hope is that building a quantum simulator would enable scientists to tap up some of the potential benefits of quantum information processing in a shorter timeframe than if they have to wait for a fully fledged machine to be created, "which is for sure a long way away", according to Segal.

**Quantum computing and coherence: Don't look now**

Building a viable quantum computer is challenging enough but doing so in a way that can be scaled up piles on even more complexity.

At the heart of the challenge facing scientists is the unusual fragility of the quantum mechanical phenomena they hope to exploit. Quantumness by nature is fantastically fleeting and prone to collapse at the slightly interference - making it difficult to generate and even harder to maintain.

A quantum computer needs to be sealed off from the outside world; a quirk of quantum mechanics means the slightest interference from the environment - be it vibrations, stray particles, even an ill-timed peek by scientists - can cause the quantumness to decohere into a classical physical reality.

The problem of decoherence - and the need for quantum coherence - means a quantum computer has to be a closed yet fantastically well-controlled box while it's processing data; there's no opportunity to measure what's going on during this process as doing so would destroy the machine's ability to crunch data.

As an engineering and technological feat, it's an extreme balancing act to pull off.

"Quantum computing has often been compared to baking a soufflé," said MIT's Aaronson. "Eventually you want to take it out of the oven because you want to eat it but you don't want to take it out of the oven too early - if you do that then it collapses.

"Equally, you want to measure the computer after it's done the computation and it's ready to give you the answer, but you don't want to measure it before that because that will then collapse the superposition [whereby particules can occupy several or all quantum states at once] while it's carrying out the computation."

Why measurement causes quantum states to decohere is an interesting question in itself - according to Aaronson, the best answer may simply be because they have to.

"If there were a way to measure quantum states without collapsing them then quantum mechanics would become completely crazy - much more crazy than it is," he said. "For example, you would be able to use it to send information faster than light. Some people have the misconception that you can...

...do that with quantum mechanics - you can't.

"Einstein says no signals can be faster than the speed of light and quantum mechanics does not change that. It sort of just barely satisfies Einstein, satisfies relatively.

"The problem is if you change quantum mechanics in almost any way - for example, if you said 'OK, what if we were to imagine measurements which wouldn't have to collapse the state?' - then quantum mechanics starts to violate relativity. At that point you are able to send signals faster than light and what Einstein says is, if you can send signals faster than light then that's actually equivalent to sending signals backwards in time, so then you start having to worry about time travel, and lots of paradoxes of that and causality.

"Basically quantum mechanics is this very rigid theory - it seems weird but it has this property that if you change anything about it then it becomes nonsense."

As an aside, this has lead to some unusual suggestions to explain why measuring a quantum state collapses it - such as the Many Worlds interpretation which postulates that there is no such thing as measurement as such: instead, looking at a quantum state means the onlooker becomes entangled with the system, and the universe then splits into as many copies as there are potential outcomes.

"Mathematically that picture is actually the nicest one," according to MIT's Aaronson. "It's the one that makes the most sense mathematically. But then there are downsides - it seems to force you to accept there's all these parallel versions [of existence].

"In any case, I should make clear that quantum computing sidesteps all these issues - you can believe whatever you want about that."

**Trapped ions, photonic qubits and diamonds: Building your own quantum computer**

Even without these philosophical conundrums, quantum computing is a very long-term project. Even how one could be constructed is a matter of great debate, with scientists working to a checklist of fundamentals called the DiVincenzo Criteria.

"You need to be able to initialise your qubits to a pure quantum state; you need to be able to entangle multiple qubits, so you need pairs of qubits to be able to talk to each other somehow; and - this is sort of the absolutely crucial piece - you need the machine to have a long coherence time, which means that the computer has to be shielded from the external environment as its running or at least mostly shielded," Aaronson said. "I guess that scalability itself is another criteria - you have to be able to add more and more qubits to your system."

This means the options for how to build such devices include using trapped ions, photonic qubits and solid state proposals using superconductors, to name a few.

Which of these various technologies looks to be most promising depends a lot on who you ask. Imperial's Segal - who works on building a quantum computer by using ions in penning traps - reckons ion trapping is the frontrunner. However, he concedes there are question marks over its scalability: "The people in the ion trapping community are convinced it can be...

...scaled up to larger numbers of qubits but that's something that's still speculative and people are still working on."

Scalability is apparently not such a challenge for another promising technology - low temperature superconducting circuits that harness electrons as qubits.

"Those systems - OK, they're a little bit tricky to make but in principle if you can make one of those things work, you just have your replication process scaled up to making very many of them on a chip and away you go," Imperial's Segal said. "[However] for them the difficulty really is overcoming decoherence."

Oxford's Smith meanwhile is focused on the potential of using synthetic diamond as a base material for quantum information processing.

"We're interested in looking at the ways electrons, mostly, and nuclei to some extent, behave in solids and trying to harness those properties to manifest quantum information," he said. "The main area that I work on is in diamond - as far as quantum information goes diamond is our material of choice."

What makes diamond a good medium for quantum information processing? For a start, synthetic diamond's chemical purity means there are few stray electrons flying around - so there's less 'noise' to interfere with the quantum system they are trying to build and control. In addition, the vast majority of the carbon atoms in diamond do not have any nucleus spin - which also means there's even less background noise to contend with.

But there could even be a place in quantum computing for computing's old friend silicon, as the University of Washington's Bacon argues.

Quantum dots, another solid state approach to quantum computing using silicon, has the benefit that the technology is probably more scalable and if it can somehow be integrated with existing fabs that would be a huge benefit, he noted.

"Which is going to win? Nobody knows, but certainly people are more likely to say that the superconducting and quantum dots systems are the ones that are probably going to be easiest to scale up," Bacon added.

Using photons, also known as flying qubits, is yet another avenue being explored - and again one that comes with its own contingent of pros and cons.

The largest entanglement of qubits to-date - up to 10 qubits - as been generated using photons which have the advantage of being a very coherent quantum vehicle.

"Photons are great because they don't interact with their environment very much at all," Oxford's Smith said, adding: "Certainly [no entanglement] that big has been done in a solid state yet."

However, being robust in the face of environmental noise has a flipside: getting photons to interact with - and so talk to - each other can be tricky. Add to that the blistering speed photons travel - which can pose problems for controlling flying qubits - and photonic quantum systems are no cake-walk either.

"Nobody can wave a magic wand and say...

...this is definitely the right way forward because there are completely different question marks hanging over the different approaches," Imperial's Segal said.

For the moment, though, quantum information research remains well and truly ensconced in the physics lab but in future it will become less about the science and more of a technology and engineering challenge - once enough rudimentary quantum machines have been built and scaling up the qubits becomes the priority.

**The limits of quantum computing?**

In the meantime the field continues to be a fertile playground for scientists and theoreticians, pushing the limits of the possible, and speculate on what may be impossible.

One probable limitation of quantum computers is their apparent inability to tackle a class of mathematical problems known as 'NP-complete' - a series of unsolved and apparently intractable problems seemingly beyond the powers of today's computers.

It appears that not even quantum computers would be able to solve the NP-complete problems, according to MIT's Aaronson.

"The central conjecture is that there is no efficient algorithm to solve problems of that type. It's a possible belief that quantum computers cannot solve these NP-complete problems, which is a very very serious limitation," he said.

If quantum computers could crack NP-complete, they really would be a force to be reckoned with. "You could see that this would be terrible for mathematicians' job security, this would basically mean that all of mathematical creativity could be automated - could be replaced by some kind of blind mechanical process," Aaronson added.

If - as Aaronson suspects - NP-complete proves to be unassailable, and mathematicians' jobs are safe, that would represent a fundamental limit to quantum computing - and perhaps on computing itself.

**Beyond quantum computing**

Is there anything else further out in computing's future than quantum computers that might be able to push processing beyond these metaphorical event horizons? Probably not, says Aaronson.

"People have speculated about a string theory computer, a quantum gravitational computer, a black hole computer. The problem is we don't really know what the power of these things would be, because we don't have a quantum theory of gravity that would enable us to make predictions about these things.

"Right now, I think it's a plausible hypothesis than quantum computing is really just the end of the line. Yes, you could use black holes or you could use whatever the most exotic physics there is, but all you would be doing is making a very fancy and exotic type of quantum computer. Of course, that's not proved because we don't have the final theory of physics that would tell us that."

In any case, according to Aaronson, any attempt to push computing too far and there really could be an event horizon to contend with. "It seems, from what we currently know about quantum gravity, that there's a fundamental limit to how fast you could ever run any computer - which is that you could do one step in every 10 to the minus 43 seconds.

"Or you could do 10 to the 43rd steps per second. If you tried to run a computer faster than that then what would actually happen is that you would be using so much energy that you would exceed what's called the Schwarzschild value - and that means your computer would actually collapse to a black hole.

"It's that kind of thought experiment that makes it seem like a plausible conjecture that quantum computing is just the end of the line. It is an amazing thing that you can do - but maybe there's nothing more amazing than that," Aaronson said.

That said, uncertainty remains the only sensible principle where quantum physics and technology limits are concerned. "But of course that could be wrong," he added.

## Join Discussion