Linked by Thom Holwerda on Fri 22nd Mar 2013 10:02 UTC

"But a powerful new type of computer that is about to be commercially deployed by a major American military contractor is taking computing into the strange, subatomic realm of quantum mechanics. In that infinitesimal neighborhood, common sense logic no longer seems to apply. A one can be a one, or it can be a one and a zero and everything in between - all at the same time. [...] Now, Lockheed Martin - which bought an early version of such a computer from the Canadian company D-Wave Systems two years ago - is confident enough in the technology to upgrade it to commercial scale, becoming the first company to use quantum computing as part of its business." I always get a bit skeptical whenever I hear the words 'quantum computing', but according to NewScientist, this is pretty legit.

Permalink for comment 556495

To read all comments associated with this story, please click here.

To read all comments associated with this story, please click here.

Member since:

2010-03-08

From my understanding regular computing would have to be based on the same laws of mechanics and properties of our world as everything else, its not as if we can step outside of it, simply because we are ignorant of it.

So, there must be something special about quantum computing that separates it from merely a theoretical description of how things work - to a practical engineering difference.

As I mentioned above, it takes rather small systems for quantum phenomena to become significant. More precisely, what you actually need is something that has as little physical interactions as possible with its surroundings.

That is because when quantum systems are coupled to a macroscopic environment, it causes many quantum effects to vanish over time, in a process known as decoherence. As an example, if you put a system in a "half-zero, half-one" state, it will decay either to the zero or one state. The stronger the coupling, the faster the decay. One way to describe it from the point of view of physics is as information or energy being diffused into the environment and never coming back.

Thus, people who try to build quantum computers have the difficult task of building quantum chips whose state may easily be read on demand, but which are still too weakly linked to the outside world for the aforementioned decoherence effects to become problematic.

Regular computers use transistors and attempt to represent information in binary, 1' and 0's. My understand is quantum computers attempt to use quantum properties to represent and manipulate data.

Ok, but then that's not enough to get it for me, and frankly I was joking earlier, but since you all are trying to help - what's the missing piece here?

It's not enough to just state the states can be 1, 0, or inbetween, what are the states, how do you manipulate them?

A state, in a quantum mechanical sense, is a set of physical parameters that fully describe a system. As an example, electrons in solids can be described by their momentum, energy, and magnetic "spin", while a photon of light can be described by its momentum and polarization.

Often, these parameters are only allowed to take a discrete range of value, which as you can probably guess is particularly useful for information processing purpose : just make somehow sure that only two parameter values are accessible, and you got yourself your "zero" and "one" physical states. And since these are quantum states which we are talking about, nothing prevents a system from being in both states at the same time, with a certain probability of finding it in each during a measurement.

Effectively, such two-level systems have been built in a wide range of physical systems, ranging from atoms in optically reflective cavities to bunch of ions trapped using electrostatic fields, with superconducting micro-circuits somewhere inbetween. The two states in question are often chosen of different energy, so that the system cannot trivially switch between both without exchanging energy with its environment.

But at this point, I have to point out that such a quantum memory or "qubit" is useless by itself. Sure, your qubit may be simultaneously in its "zero" and "one" states, but since you need to perform lots of measurements to know for sure, nothing has really been gained. Besides, as mentioned above, quantum information storage tends to be short-lived due to decoherence effects, with data remaining reliably stored for at most a few miliseconds in the best experiments if memory serves me well.

So the next difficulty in building a quantum computer is to make quantum memories interact with each other, so as to perform computations. And just like with classical computing, the simplest thing which one can think of building this way is logic gates.

Where things become interesting here is that a quantum logic gate is able to act on all possible states of its input at the same time, and return a statistical superposition of all the results at the same time. So if we take, as an example, an unsorted database search algorithm of the form "examine every database entry, return a pointer to the entry that possesses a given key and NULL otherwise", then the only nonzero result is the pointer to our database entry, and we may naively imagine a quantum circuit which finds the right database entry in constant time.

Things sadly aren't quite as simple in practice because all logic gates which destroy information (such as, say, AND and OR) are forbidden in the quantum world. One thus has to deal with other logic gates like the CNOT and Hadamard gates, which arguably reorder information more than they do computation, and thus make programmers' lives more difficult. Due to this, an actual quantum database search algorithm, as derived by Grover et al., ends up with an algorithmic complexity of O(sqrt(N)), which is still a quadratic speedup over classical ones.

Other kinds of search-oriented tasks can benefit from a quantum device's ability to act on multiple inputs at the same time. Perhaps the most well-known one is Shor's algorithm, which factorizes numbers in O((log N)^3) time and is the worst nightmare of everyone who ever implemented RSA-based cryptographic systems. That being said, not all of cryptography is based on the difficulty of factorizing prime numbers, and so far some algorithms have proven to be pretty robust against the minds of quantum computing theoreticians.

Did that answer some of your questions ?

At this point, I don't think anyone has actually built a truly programmable quantum computer, so it's hard to answer this question. For now, most works I've heard of are based on special-purpose circuitry which aims at implementing a specific algorithm, so programming a quantum computer would be kind of like "writing" code using a bunch of logic gates wired as you wish and synced against a common clock signal.

I think that implementing a programmable quantum ALU is a dream of many quantum computing experimentalists, but is still out of reach for now. Theoreticians tend to be ahead in this domain, so I'm sure multiple designs have already been published in scientific literature.

Lots of "I think" in this last part, I know, but I haven't followed this realm closely enough to be perfectly sure about the state of current research. My current field of research (superconductivity) sure involves QM, but it's not quantum computing itself

Edited 2013-03-24 21:49 UTC