Quantum Computing...

[xprow]

Well I thought this would be an interesting topic to discuss. How exactly does a quantum computer work. I read that they already had one able to do factoring of a number that would have taking regular computers way to long to work out. The implications of such computers could be astounding. When do you think we will see them? Also any thoughts you have on such things please post. These kind of topics I always enjoy reading .

 

[Codewiz]

Last I heard(which was 3 years ago) they were just to the point where they could add small numbers. Like 2+3

I also read that the method that was currently being used probably would not work in the long run.

 

[littleprince]

Quantum computing is based on the spin of particles, instead of positive negative charge. ( i think, pretty tired right now).

I think the problem u guys are thinking of, is the Molecular dna computing problem, where dna strands solved one of the NPC shortest paths problem very well. However for larger problems, the dna solution would be there, but mixed in with a lot of garbage, and it woulndt be feasible to sort out the actual solution. I think quantum computers are at least 20-30 years off. I mean, there will be small ones here or there, but in semi mainstream, use, like the cray's used to be, i think its 20-30. 40 for high end use. 50 for home?

 

[Rilescat]

Hello Hello...

You may find this interesting: http://zdnet.com.com/2100-1103-942121.html

I read this article this very morning. It is in regard to a functional quantum transistor. By my understanding it is the first functional quantum transistor to be able to work on spin principle within an electron, and do it all in a single instrument/function.

Very interesting.

I would like to know more about Quantum computing too. Does anyone have some good websites?

Riles.

 

[KillerCow]

OK. I might as well volunteer my limited knowledge. I had a Combinatorics class where the prof was a Computer Science PHD specializing in quantum computing; he used to talk about it as asides...

The jist was that a standard computer works on bits, 1s and 0s, whereas a quantum computer has more states: 1, 0, and both (Principle of Superposition). The idea is that a quantum computer can calculate in parallel what a normal computer does in serial.

i.e.
a brute force factoring algorithm on a normal computer would try to divide a given number by every possible factor, one at a time; but a quantum computer would try to factor by all the numbers at once.

The parallelism would be given by the nature of the quantum bits (q-bits). So in the time that it takes a normal computer to test one factor, the quantum computer could test them all. He never went in depth and I never asked him about it (although I was very interested) because he tended to be condescending whenever we asked him questions. The University offered a grad class on quantum algorithms that I intend to take if I can.

If you are technical in CS, check out Quantum Computing and Shor's Algorithm. Shor's Algorithm is the polynomial time factoring algorithm.
If you are technical in physics, check out this to answer most of your questions.


There are no useful quantum computers acknowledged to exist. The most complex that I ever heard of was a 4-bit adder... or something along those lines. That is not to say that any 3-letter organizations don't have one... one would be infinitely valuable to them.

 

[javeed]

To add to KillerCow's excellent summary, one of the things I found extremely nice about quantum computers was the fact that due to superposition, an 8 qbit number can store a total of 256 values simultaneously (as opposed to an 8 bit number which can only store 1 out of a possible 256 numbers at a time). The end result being, if you multiply an 8 qbit number with another and store the result in a 16 qbit number, you will have the result of multiplying every 8bit number with every other 8 bit number in one fell swoop.

Using this, one can multiply two 64 qbit numbers and get a list of all the 128 bit numbers stored in the resulting 128 qbit number. Can anyone say "PGP et al cracked"? This would make the work done by distributed.net clients around the world moot.

Of course the practical applications are far more than just cracking encryption schemes. The advent and common place usage of quantum computers (which will happen far later than the NSA etc will start using the first prototypes) will mean an effective end to privacy based on conventional cryptographic standards. Perhaps then we'll find an encryption scheme that is truly uncrackable!

Anyway, just my $0.02
Javeed

Edit: Fixed typos

 

[GL]

Apparently, there are uncrackable encryption methods. One of the methods is the one-time cipher pad. However, that is impractical for the key (the pad of randomnly drawn numbers) must be distributed to the receiver. It must be randomnly generated and may only be used once. There is another more interesting method that is apparently uncrackable and uses public key encryption. And of course, it's quantum cryptography I don't have the book handy, but "The Code Book" by Simon Singh has a brief history of quantum cryptography in the later chapters. And, get this: quantum cryptography has already been achieved in practice. Over a distance of approximately 15 km no less! Probably more by now but the book was published a few years ago. I'm sketchy on the details of quantum physics so I don't want to post any erroneous information. But, I'll post what I vaguely remember anyway

Keys are transmitted between sender and receiver. The sender issues information that consists of 1 of 4 possible photon polarizations. This information is of course randomly chosen. The receiver randomly decides to measure the photons rectilinear or diagonal polarization. Next, the receiver publicly announces for each photon, which type of measurement he has made (rect. or diag.) but not the numerical result of the measurement (i.e. 0, 45, 90 or 135 degrees). The sender then publicly announces whether the receiver has made the right kind of measurement. Both parties discard all the cases in which the receiver made the wrong measurement or cases of failed transmissions. The resulting information is a shared secret then - only between sender and receiver. How might this be possible? What if somebody is eavedropping on these two when they are making the key exchange?

The answer lies in Heisenberg's Uncertainty Principle, which states that one cannot observe a system without disturbing it in an unpredictable way. If somebody eavesdrops on the key exchange, the sender and receiver will find out because the very act of attempting to measure the photons will have disturbed the system. The sender and receiver test for eavesdroppers by testing a subset of their data obtained in the process previously outlined. I believe they just test for an abnormally high error (or failure) rate of the transmissions. If this is found to be the case, all information is discarded and the process is re-initiated.

Once the key is exchanged, I believe the method of encryption used is the same as the one utilized in the one-time pad - the Vernam cipher. It's a simple XOR of the cleartext with the key.

I apologize for taking this thread a bit off course, but it's interesting to know that in the event that quantum computers become practical, our privacy of communication may still be achieved by utilizing the very principles that are used in quantum computers to completely shatter any protection offered by conventional public key encryption.

 

[Carceri]

I have no idea where to start, but having taken courses in complexity theory, quantum computing, cryptography, cryptologic protocols and quantum information theory I guess I am expected to contribute to this thread.

First the interesting topic of how fast a quantum computer is. The answer is that we don't know. There are no proof that a quantum computer is any faster than a conventional computer, and with "faster" I mean that it is able to (for example) solve problems that requires an exponentional amount of time in the problem size in linear time.

There is a quantum algorithm for solving the hidden subgroup problem in linear time, which is very interesting since that requires exponential time on a conventional computer. Also discrete logarithms and factoring are special instances of the hidden subgroup problem. The downside is that we have strong indications (although not proofs) that neither of these problems are NP-Complete so even if a linear time quantum algorithm exist (which it does) it does not tell us that a quantum computer can solve NP-Complete problems in linear time. In fact there are strong indications that it can't.

With regards to using a quantum computer to breaking todays encryption algorithms it's clear that algorithms based on factoring and discrete logs can be broken, however algorithms based on the intractability assumption of NP-Complete problems seems to remain secure against a quantum computer. Using quantum search you can search between N elements using Sqrt(N) trials, so using this on a conventional encryption algorithm will reduce the keysize by a factor of 2 (a 256 bit key will be as effective as a 128 bit key, etc.) so conventional algorithms are not easily broken by a quantum computer.

Quantum encryption works today over rather long distances (40 km or so I believe - we did a test at the university where I study). The protocol is impossible to explain without some background info first. It's easy to come up with a protocol if you have a quantum computer at your disposal, but we don't so instead a modified version of the protocol was used. It's called the BB84.

I believe that the largest quantum computer in operation today is only about 10 qbits which is useless for any interesting stuff. The quantum computer needs to be completely isolated from the surrounding universe in order to work without errors. Since this is not possible clever quantum error correction schemes have been developed, but it is impossible (at least today) to increase the number of bits without introducing too many errors. Besides that generating entangled qbits (which are often needed for the quantum algorithms) is a very difficult task (only 1/1000000 or so gives the desired result)

Finally I would like to say that the statement "8 qbit number can store a total of 256 values simultaneously" should be taken with a grain of salt. It can't store 256 values simultaneously in the way we think. It can be any number of those 256 possible values but until we read the results it hasn't decided yet and we may think of it as being all values at the same time.

If anyone's interested I can go into more details...

Edit: Here's a link to the Center for Quantum Informatics at Aarhus University. In the bottom of the slider to the left you'll find a link to their quantum crypto experiment. There are also other information about quantum computing on that page.

 

[jaydee]

Having just finished "The Code Book" GL has mentioned just yesterday, I'll throw in a few of my thoughts. First of all, the one-time pad he described is basically a book of letters that code the alphabet. Every page shows a different representation of each letter; therefore, once you establish how often you change pages (ultra secure is every letter) and in what order you change pages, you can have complete security. However, decoding that message is torture, and if the key falls into the wrong hands then you have to change the whole thing and redistribute such a massive key (remember one alphabetic key for each individual letter of an entire message) ect, so it's rather impracticle on a large scale. If you just use the one-time pad though to cipher a 10 letter password though, it's clearly very managable.

Ok, on to quantum cryptography. (I'm now going to assume that Alice is trying to communicate with Bob, and Eve is trying to intercept (evesdrop) the message.) One thing that has caught my attention is that it seems as though as Eve can mess up any message at will. Sure she can't read it, but if she keeps interfering then it would be the equivilent of someone successfully ping flooding a server wouldn't it? Completely flooding the line so that no traffic can get through?

Carceri, where do you go to school?

even if a linear time quantum algorithm exist (which it does) it does not tell us that a quantum computer can solve NP-Complete problems in linear time. In fact there are strong indications that it can't.

Wow, I thought that was the significance of a quantum computer: being a non-deterministic turing machine, therefore solve exponential-time problems (NP-complete such as TSP) in linear-time. Of course, isn't there a notion that there are no NP-complete problems?

 

[Carceri]

It's funny what people call a one time pad. The one time pad is what was described earlier: Choose a completely random bitstring where each bit is choosen with probability 0.5 and independant of each other, then XOR that bitstring with the plaintext. It's easy to prove that this gives an information theoretically secure encryption. I must admit that I didn't read your description of the alphabet-book thingy thoroughly, but at first sight it doesn't appear to provide information theoretic security.

Ok, on to quantum cryptography. (I'm now going to assume that Alice is trying to communicate with Bob, and Eve is trying to intercept (evesdrop) the message.) One thing that has caught my attention is that it seems as though as Eve can mess up any message at will. Sure she can't read it, but if she keeps interfering then it would be the equivilent of someone successfully ping flooding a server wouldn't it? Completely flooding the line so that no traffic can get through?

Sure, if the quantum channel is a fiber optic line nothing prevents Eve from simply cutting the wire. That will however not reveal any information and the system is still secure.

Carceri, where do you go to school?

At the University of Aarhus (in Denmark) studying Computer Science and Mathemathics.

Wow, I thought that was the significance of a quantum computer: being a non-deterministic turing machine, therefore solve exponential-time problems (NP-complete such as TSP) in linear-time. Of course, isn't there a notion that there are no NP-complete problems?

There are currently no known quantum algorithms for solving NP-Complete problems in less than exponential time. Even a quadratic speedup of an otherwise exponential time algorithm is still exponential. The best known conventional algorithms for factoring still run in exponential time, but we have a quantum algorithm running in linear time. Factoring is not NP complete however, so this doesn't make the quantum computer more powerful than a conventional computer. On the other hand this could indicate that perhaps there do exist a linear time factoring algorithm on a conventional computer?

Sure there are NP-Complete problems. I guess what you want to say is that some people think that P is equal to NP. Still a possibility although you don't find many people that believe that.

Now we are talking complexity theory here's what I find interesting:

We all know the complexity classes P and NP. There are a plethora of other classes, one of them is PSPACE. PSPACE is the class of problems that can be solved on a turing machine using a polynomial limited tape but with no limit on the computing time it can use. It is easy to see that both P and NP are subclasses of PSPACE.

An interesting problem related to the P = NP problem is that we don't know if there exist problems in PSPACE that are not in P. We can also prove that all problems that can be solved by a quantum computer in polynomial time are in PSPACE. Now, if P = PSPACE then a quantum computer is no more powerful than a conventional computer. We don't know the answer, but very few people believe that P = PSPACE. But even if P != PSPACE it doesn't mean that a quantum computer is more powerful than a conventional computer, since it might only be able to solve problems in P in polynomial time (since P is in PSPACE this is fine with the proof that all problems it can solve in polynomial time are in PSPACE)

 

[Mr.IncrediblyBored]

Sorry to bring this back from the dead, but EETimes just published a rather interesting newsbit about this very subject.

EETimes.com:

MADISON, Wis. ? Researchers at the University of Wisconsin in Madison claim to have created the world's first successful simulation of a quantum-computer architecture that uses existing silicon fabrication techniques. By harnessing both vertical and horizontal tunneling through dual top and bottom gates, the architecture lays out interacting, 50-nanometer-square, single-electron quantum dots across a chip.