Linked by Eugenia Loli on Tue 1st Jul 2008 23:03 UTC
Hardware, Embedded Systems Quantum computers could become a reality very soon, opening up some fantastic possibilities -- including tele-portation, says Richard Gray.
Thread beginning with comment 320957
To read all comments associated with this story, please click here.
quantum computers are practical ...
by kvaruni on Wed 2nd Jul 2008 09:12 UTC
kvaruni
Member since:
2005-06-29

quantum computers are practical today but this article and associated comments are full of hypes. Let me explain. I will tackle the problem (in bold), give a more accurate but far too concise statement (at the end, in italic) and I will try to explain it a bit more in the text that is found in between the bold and italic parts.


Typical personal computers calculate 64 bits of data at a time. A 64- qubit quantum computer would be about 18 billion billion times faster.
---
Untrue. This immediately follows from the idea of a superposition over all bits. But let me explain this a bit more clearly. It is true that a single quantum bit can be both true and false. However, another far more accessible way to look at this is that each option has a certain probability assigned to it. So, instead of saying that a bit is 0 with 100% certainty, you can say that a quantum bit is 79,42% a 0 and 21.58% certain a 1. So yes, a quantum bit can be both 0 and 1, but the problem is that you need to read the value. This is nothing like an ordinary computer. Reading a quantum bit actually destroys the superposition. This means that the qubit collapses to either 0 or 1 with a probability that was described above. It would be more accurate to state that a quantum qubit can somehow hold billions of billions times more information. This, however, is under the assumption that the quantum system is not disturbed and not measured.
---
Great, so I can hold a billion billion times more information, but reading it will collapse it to a single value, making it no more useful than an ordinary computer.


A working quantum computer could be so mind-bogglingly powerful that it would solve in seconds certain problems that would take the fastest supercomputer millions of years to complete.
---
True. But, well, only if you would clearly emphasize the could. In certain things, a quantum computer can be mind boggling fast. For example, if we search a deck of 2 cards for the card we want, we need to look at 1 card to be 100% certain which card it is. (It either is the card we look at, or it isn't. In the latter case, we know for sure that it is the other card we did not look at). A quantum computer can do better and need only look at a single card in a deck of 4 cards to be certain which card is the correct one.
---
Given a very concrete problem, a quantum computer can indeed be a lot faster. Overall, the speedup is not so mind boggling as this conclusion would suggest. But yes, a quantum computer can do things in seconds that would take an ordinary computer millions of years. Then again, a GPU can calculate pi a lot faster than an ordinary CPU. There is no more magic in it than that. It is better suited for a number of jobs, but grandly fails when it comes to some other jobs.


... But a QC could break the most complicated encryption in hours.
---
RSA is dead indeed. But we predicted this! RSA has an inherent weakness. Both you and the public know n, which is the product of two primes. RSA simply relies on the fact that, given n, it is really very hard to find out what the original primes were. However, there are oodles of special properties in this problem, making it only a matter of time before someone found a way to beat RSA. A quantum computer can indeed break RSA. Instead of thousands of years, it needs hours. But for this to work, we first need to make a quantum computer with a couple of thousands of qubits. The biggest we built that had full entanglement consisted out of 7 qubits. Ough. When we move to other encryption algorithms that do not rely on public and private keys, such as AES, a quantum computer fails to deliver to the promise. Agreed, a substantial speedup can be obtained. For example, a key of 256 bit can be cracked by a quantum computer about just as fast as a 128 bit key on an ordinary computer. So instead of 2^256 is is reduced to 2^128. The exponent is actually halved! However, the problem is still in NP. And making a bigger key is still P. Thus simply doubling the key size will stop a quantum computer from reading your most precious information.
---
RSA is dead when a big enough quantum computer can be built. This is an extreme challenge and not to be underestimated. However, alternatives exist and all other types of encryption remain quite safe. So, keep on using AES and the likes.


Quantum computers could also take advantage of another quantum property, teleportation. Teleportation allows information about one particle to be transmitted to another particle some distance away. A quantum computer could use teleportation instead of wires to move bits around inside itself.
---
Well, for this trick to work, you need to create an entangled qubit. This means that you actually have two qubits, but when you read one qubit, you immediately influence the other qubit. Some tricks, and some classical communication, make it possible to exactly reproduce the original qubit in some other place. This is quite cool, since normally a random qubit cannot be cloned. But starting from a basic entangled qubit and transmitting some simple information over a classical communication line makes it possible to destroy the original and obtain the new, exact, copy in the new location. But please, this is not Star Trek "beam me up" style teleportation. Researcher need their funds, and teleportation just sounds soooo cool that they immediately found the funds for fundamental, but far less spectacular research.
---
You can teleport things, given that you can communicate over a normal communication line and given that you already have an entangled qubit. This itself suggests that prior quantum communication needs to be possible before you can even consider teleportation. During the process, you need classical communication. So let's have some wires, okay?


I honestly do not think that QC will come to be any time soon, leave alone applications that would run on it.
---
A number of people stated this or similar ideas. But QC are here, today. Let us think again of a qubit as being both 0 and 1, but with some associated chance. Making a qubit that is 50% a 0 and 50% a 1 is actually very simple. Now, what would happen if we measure this? We get a truly random number generator! This and applications in quantum cryptography are hot in todays quantum world. Quantum cryptography makes it possible to detect when someone is eavesdropping and allows you to have an arbitrarily secure channel of communication. This makes it possible for example to share a common key that no one else knows, eliminating the need for RSA. So quantum computing will actually protect us from quantum computing power ;-).
---
Quantum computers exist today. They are great for generating truly random numbers and for some kick-ass cryptography. Go visit http://www.idquantique.com/ and order your random number generator USB stick today. It will outperform each and every random number generator that utilizes current day computers. Or pick us some quantum cryptography, but mind you that these are quite pricey!


Even if one is built and actually works, I don't see *Personal* Computers as we know going away so soon.
---
Current day classical computers are very speedy and they are very good at basic number crushing. A quantum computer is nothing magical and it cannot solve some random problem. It only consists out a few bits and can only outperform a classical computer given some very specific problems (mostly search problems). But classical computers are cheap, have tons of bits to spare and can do all the rough preliminary work!
---
Classical computers are here to stay, indeed.


I wrote a somewhat accessible paper this year on this subject for those that have sufficient computational and some mathematical background. This may clear up more things.
http://tinf2.vub.ac.be/%7Edvermeir/courses/seminarie/Kim_Bauter...

Reply Score: 12

sakeniwefu Member since:
2008-02-26

So basically, we can hope for a QPU with a RNG and Q(uantum)Sort for our next 128 cores silicon-based CPU but we shouldn't dream of running programs off it.
I'll put my bets on biochemical computers then. After all, we have a working model in our heads.

Reply Parent Score: 2

agrouf Member since:
2006-11-17

What is in your head can't crack a 32bit RSA key in hours, in days or in years.
Studying the brain is quite interesting for curing deseases, but I very sceptical when it comes to computer applications. If what was needed was a brain, we could as well use ours. If we have computer, it is to overcome our brain limitations. No human brain can break a 64bit RSA key in its life time. That is what computers are for.

Reply Parent Score: 2

pedromatiello Member since:
2005-07-13

Great post! And your paper will be very useful to me. Thanks!

Reply Parent Score: 1