First Quantum Computing Gate on a Chip 166
An anonymous reader writes "After recent success in using quantum computing for superconducting qubits, researchers from Delft have formed the first Controlled-NOT quantum gate. 'A team has demonstrated a key ingredient of such a computer by using one superconducting loop to control the information stored on a second. Combined with other recent advances, the result may pave the way for devices of double the size in the next year or two--closer to what other quantum computing candidates have achieved, says physicist Hans Mooij of the Delft University of Technology in the Netherlands. Unlike today's computers, which process information in the form of 0s and 1s, a quantum computer would achieve new levels of power by turning bits into fuzzy quantum things called qubits (pronounced cue-bits) that are 0 and 1 simultaneously. In theory, quantum computers would allow hackers to crack today's toughest coded messages and researchers to better simulate molecules for designing new drugs and materials.'"
Cracking (Score:4, Informative)
That's an overstatement. A quantum computer will not suddendly magically crack the strongest codes. Yes, certain algorithms designed for quantum computers, like Grover's algorithm, will reduce the time needed to find the key of a symmetrical cipher with about half the number of bits in the key. However, given for example a 256-bit key you would still have ~2^128 keys to check and afaik 2^128 still takes quite sometime to crack....
Re:A solid milestone... (Score:5, Informative)
Keep in mind that this is a Controlled-NOT gate (a two-input gate) and not a simple NOT gate (a one-input gate). It has been proven that if you can implement two-qubit C-NOT and arbitrary one-qubit operations, you can implement a universal quantum computer (that is, one that can run an arbitrary "quantum program").
There is a deeper reason for quantum computers not to use AND/OR gates, which is their irresibility (AND and OR are two-input to one input gate, which makes them irreversible). Quantum Mechanics is intrinsically reversible, so a quantum computer should be reversible too and that's why it is not common to hear about Quantum AND or Quantum OR.
Pablo B.
Re:Quantum states (Score:4, Informative)
More seriously, a qubit (short for "quantum bit") has two well defined states, 0 and 1 (|0> and |1> for those QM buffs) just as a regular (classical) bit. The difference is that the classical bit has to be in either 0 or 1, while the qubit can be in what is called a "superposition" of those. So you could have a qubit in the 0 state, or in the 1 state, or in the "x% 1 and y% 0" state (where x+y=100). Part of the magic of quantum computers comes from this fact: using the proper operations, you can feed your quantum computer a register which is set up to "all possible inputs" so that it applies the algorithm to all possible values. Some people call this "Massive parallelism". You have to be careful, because Quantum Mechanics does not allow to extract the result of all those calculations (that would be great), so you have to go through some tricks to get useful information out of that "parallel processing".
I hope this helped some!
Pablo B.
Re:A solid milestone... (Score:2, Informative)
Re:Quantum states (Score:5, Informative)
The quantum states you're referring to do have something to do with this. However, their number isn't what's important.
The interesting thing about the quantum computing world is that such states can be in superposition, that is, it is unclear whether or not the state is one or the other. You can only know that if you measure the state, the outcome will be state A in, say, 30% of the time, and state B in 70%. Now, you could probably extend this to 32 different states, but since we're used to bits, we'll build something where we just use two (for instance linearly polarized photons -- 0 degrees = 0, 90 degrees = 1).
Now, there exist methods (or they're being researched) that allow you to put your bit into a superposition of its states. This could, for instance, be so that measuring the state will produce a 0 exactly half the time. Maybe you could put your Schroedinger cat in the box -- dead=0, alive=1...
This by itself is not particularly exciting. But you could do that for multiple bits (say a 32-qubit word) so that measuring it, you get uniform probability to measure any number between 0 and 4294967295. Where it really gets interesting is when you apply quantum operators to your state: They can transform the state without destroying the superposition, i.e. without measuring it. For instance, if your superposition currently gives you 30% chance for measuring a 0 and 70% for a 1, then a CNOT gate would reverse that probability.
Note, however, that a CNOT is a "controlled not": it has two inputs, the control and the target. The control passes through unchanged, but the target is flipped if and only if the control is 1 (i.e. the target output value is identical to the XOR of the input values). In a quantum world, this lets the two bits be entangled: For instance, if the target bit is 1, then the output of the target is 1 iff the control is 0 (target = NOT control). Now suppose that we create a superposition on the control input -- then the control output will be that same superposition, but the target output will be (NOT control) for all control values. In other words, we've just computed a function for all possible input values at once. And you can build these things larger, to do more useful things, such as with a 32-qubit input.
The problem is, you thus get all possible results at the same time, but it's a superposition, and after measuring, you'll only have one result. Why is this useful? Because for one, you can construct some algorithms that transform the problem in such a way as to give a guaranteed result; in other cases, you'll do multiple samples and after a while you'll get your result -- and for some problems, you'll get it orders of magnitude quicker, on average, than on classical computers.
For instance, the Deutsch-Josza algorithm is such an example. Assume I have a function that does one of two things -- it is either constant over the whole input domain, or it is balanced, that is, it returns 0 for exactly half the possible inputs and 1 for the other half. The function, to you, is a black box. How do you determine quickly whether the function is constant or balanced? On a classical computer, you have to test one more than half the inputs, in the worst case, to find out whether the function is balanced or constant. Using the Deutsch-Josza algorithm, you can solve the problem in *constant* time on a quantum computer.
In other words, quantum computing may be interesting for some number-crunching applications. Of course the true capabilities of such a system are not yet completely understood. But I would think that for desktop computing it's probably not too relevant...
Re:A solid milestone... (Score:3, Informative)
I guess it's mostly historical, and that XOR is usually associated with a two-input/one-output gate. Controlled-NOT looks pretty intuitive (the target is negated only if the control is 1), but probably XOR is better because A-inverts-B is exactly the same as B-inverts-A (which seems counterintuitive when you think of it as a CNOT, but it's reasonably simple to see that is the case by just looking at the corresponding truth table).
But I would venture that most people working on trying to build quantum computers would be more familiar with CNOT than XOR in the context of quantum computation (QXOR sounds weird, doesn't it?)
Pablo B.
Re:Inversed qubit? (Score:2, Informative)
The tricky thing is, quantum mechanics won't let you measure anything other one of two values (not strictly true, but go with me on this). But those values don't necessarily have to be 0 and 1, just so long as they are orthogonal to each other.
Okay, to understand that last bit you need to bring in the fact that the proportions of 0 and 1, x and y say, can actually be any complex number, positive, negative, imaginary, whatever, just so long as their magnitudes-squared add to 1. So, then, instead of measuring for the 0 and 1 states, you could measure for "0.5" and "-0.5" states.
This isn't even getting to the confusion of putting these things into gates.
Re:A solid milestone... (Score:3, Informative)
Like transistors, tubes are just amplifiers. Contrary to popular belief, both are analogue components, but they have quite different responses to changes in current (the graphs are a different shape). Many people consider tube amplifiers to produce better sound quality than transistor amplifiers, and tubes will almost always handle clipping better than transistors. There's actually not much a transistor can do that a vacuum tube can't.
Either tubes or transistors can be used to implement logic gates. These gates can be built up to store and process bits of information. In the digital world, they are functionally similar. The advantages of tubes from the analogue world go out the window, and the advantages of transistors (size, speed and cost) come into their own.
Quantum computers are another thing entirely. The computers you and I are using at the moment are deterministic Turing machines. Quantum computers are non-deterministic. Quantum gates deal not in bits, but in qubits. They don't think in terms of binary data, they work with quantum states.
There are many things that these quantum components can do that conventional transistors cannot, but I don't think we'll be seeing quantum gates implementing binary logic in computers any time soon (if ever). The article unfortunately confuses the issue by making it sound like they've implemented a binary operation. CNOT is not a binary operation - it is a quantum operation.
I hate analogies as much as the next guy, but if tubes are the horse and cart, and transistors are our cars, then quantum computing is going to be our interstellar space craft - they suck for doing the weekly shopping.
Re:A solid milestone... (Score:4, Informative)
I am an expert, and I don't think CS is ahead here; rather, I'd say CS and physics are moving forward in a partnership. As best as we understand the relevant complexity classes, quantum computer are not equivalent to an NFA. To put it another way, as far as we know, quantum computers cannot efficiently solve NP-complete problems. I say "as far as we know" because we don't even know for sure whether classical computers can efficiently solve such problems. Quantum information is a fundamentally new concept to CS, however.
Similarly, conventional computers can solve the same set of problems that quantum computers can solve, they just require an expansion of the problem which in the real world requires much more time and/or space to complete.
If you look simply at the domain of solvable computational problems, and don't care about efficiency, then yes, there's no difference. There are, however, communication problems and quantum "games" that cannot be solved with classical information but can be with quantum information.
Re:Quantum Not? (Score:2, Informative)
______
-| NOT|-
-|____|-
the gate has two inputs and two outputs
in direct computation the the inputs are on the left, the outputs on the right
in reverse computation the other way around
let's take direct computation,
say the inputs(left side) are in_x(top) and in_y(bottom) and the outputs(right) out_x(top) and out_y(bottom)
the C-Not performs the following function:
out_x
out_y
BUT it performs this functions simultaneously on a superposition of inputs,
a superposition of inputs for a qbit roughly translates to: something like if I measure the qbit I may get 0 with p probability and 1 with (1-p) probability
algebraically you would express this using in_y = sqrt(p) |0> + sqrt(1-p) |1>
so literally the gate works like this: in the cases when in_x is 1, out_y will be 1 with a probability of p and 0 with a probability of (1-p) - exactly the inverse probabilities of in_y
this is all roughly speaking, there are other more subtle aspects...