Quantum Computing

I've received quite a bit of interest on the topic of quantum computing (and to a lesser extent quantum cryptography). I figured that I'd post a small tutorial on Quantum computing as well as a few links to further understand the basics of quantum mechanics (which my tutorial doesn't cover especially well). If I receive enough interest, I might be influenced to post an intro to quantum mechanics too, now that finals are over and all.

First, here are some general articles about quantum mechanics:
http://www-theory.chem.washington.ed...m/quantum.html
http://www.qubit.org/intros/comp/comp.html

Just remember, if you don't understand it at first that is normal. No one fully understands it, and I for sure don't have more than a general basis of it from my own research and from classes I have taken. Anyways, enjoy... (btw, I had to just make it a link, because I couldn't really format the tutorial properly for the forums. I hope you guys don't mind).

http://www.rpi.edu/~coulls/

-Wizeman

Well, for the 31 of you that actually cared to look at this tutorial, I figured you might be interested in an announcement made by IBM. Turns out that IBM has produced a Quantum Computer that performs Shor's algorithm to find the factors of a number (in this case 15). If you read my tutorial, you'd know that Shor's algorithm was made in 1994 by AT&T's Peter Shor to find the factors of a number using a quantum computer. So, what does this mean? It means that pretty soon current encryption techniques will be useless!

Here is the link: http://www.research.ibm.com/resource..._quantum.shtml

Regards,
Wizeman

Man, this is not easy to understand!

It's interesting, though, that these quantum computers are so incredibly fast that they can crack existing encryption algorithms in a matter of minutes, when with ordinary computers it would be impossible.

I guess it's all somewhat in a development phase, so we don't have to worry yet. I mean, if these computers can crack for example PGP real fast, we would all need a quantum computer to encrypt our messages. And I suppose we all can't afford one, heh, not me anyway.

These computers could probably do a lot of other incredible stuff too, but when harddisks and memory chips aren't fast enough, where not gonna see that. So it's for the difficult mathematical problems we will use this fancy technology.

Hey, Wizeman, post some more about this topic! I just love this stuff!

Well, actually, it is a common misconception that in order to foil quantum decoding of encrypted messages, you should use quantum computers to encrypt the messages. In reality, however, this makes no difference. The major reason that quantum computers can crack today's encryption algorithms is because they all utilize the multiplication of two (usually very large prime numbers). This produces an even larger prime that is used to encrypt the message. The thing that makes the decryption possible is that quantum computers can do multiple "calculations" at any given moment, whereas a traditional computer needs one moment for each computation (depends on the speed of the processor, instruction set, etc...). So, where traditional computers would need to go through LOTS of cycles to try and find the numbers that multiply together to find the large prime used in encryption (this is called factoring), a quantum computer can do it in one "cycle," if you will. Basically, as long as cryptography continues to use factoring as a methods of producing encryption keys, then they will be vulnerable to quantum computers, regardless of whether the encryption was run on a traditional machine or a quantum computer.

There are, however, some quantum computer specific cryptography schemes which are somewhat interesting, but more detailed than I wish to go into in this particular post, which would make cracking quantum cryptography impossible (at least with our current knowledge of quantum mechanics).

You are right in the fact that the quantum computers that have been developed so far are not able to crack PGP or any other type of encryption that is greater than, say 4-bits. Actually, as the numbers they wish to factor get larger (let's say in the 128 bit range, or approximately 3.5 x 10 ^ 38 in decimal), then they must produce molecules that have just as many spins, not to mention the fact that they have to deal with decoherence ( in lay-mans terms, interaction between the quantum system and the outside world), which again increases with the number of spins and the size of the molecule.

If you don't understand the stuff, but you have a serious passion for it, I'd highly suggest reading the two links I have at the top of the first post, and then proceeding to my tutorial/paper. Finally, if you understand it up to that point, you should really check out this:
http://xxx.lanl.gov/abs/quant-ph/?9809016

Thanks for your reply!

-Wizeman

'ello everyone!

I just wanted to let you guys (and gals) know that I found a website that explains both past and present quantum theories in a very easy to understand manner. In addition, it is also quite thorough in covering technological uses of quantum mechanics (tunneling and computer...). If you feel you need a bit of a refresher on quantum mechanics, or you would really like to understand it, I'd highly recommend checking this website out:

http://library.thinkquest.org/C005775/frameset.html

Regards,
Wizeman

Quote:

---

Originally posted by Wizeman
I've received quite a bit of interest on the topic of quantum computing (and to a lesser extent quantum cryptography). I figured that I'd post a small tutorial on Quantum computing as well as a few links to further understand the basics of quantum mechanics (which my tutorial doesn't cover especially well). If I receive enough interest, I might be influenced to post an intro to quantum mechanics too, now that finals are over and all.

First, here are some general articles about quantum mechanics:
http://www-theory.chem.washington.ed...m/quantum.html
http://www.qubit.org/intros/comp/comp.html

Just remember, if you don't understand it at first that is normal. No one fully understands it, and I for sure don't have more than a general basis of it from my own research and from classes I have taken. Anyways, enjoy... (btw, I had to just make it a link, because I couldn't really format the tutorial properly for the forums. I hope you guys don't mind).

http://www.rpi.edu/~coulls/

-Wizeman

---

You state that DES uses the factorization of large numbers. It does not. You probably mean RSA, although Diffie-Hellman may be crackable by similar methods. Clearly, if you can compute fast enough, you can crack DES too, but you don't need factoring algorithms!

Well, actually, DES uses factoring to create its key, as does all other encryption techniques. And, if you know anything about encryption methods, if you are able to determine the key, you are able to decipher the message. The difference with DES is that 1) it is a block cipher and 2) it is symmetric. So, before you go out of your way to belittle me, perhaps you should have a more full understanding of exactly what is going on in encryption.

Also, Diffie-Hellman is a method of key distribution, NOT an encryption algorithm.

Regards,
Wizeman

"Well, actually, DES uses factoring to create its key, as does all other encryption techniques"

This is patently false and indeed shows that you are not familiar with encryption. The very idea of a key is that it should be random. There may be factoring techniques used in some obscure Random Number Generator, but good RNGs use real sources of randomness. Such randomness sources are scarce, but some RNGs use disk latency and keyboard timing in conjunction with arbitrary input from less reliable entropy sources such as a human being.

Stick to your quantum theory.:)

Regards, Richtig

hmm, now that we know that the popular ciphers should soon be easily crackable with the right encryption, we should probably start thinking of ways to make the new generation of ciphers extremely hard to crack even to the new gen of computers.

Let's start on a familiar basis for now: Anyone know some good one-way functions?

Now onto another matter...how to make the keys harder to...get(for lack of a better term at the moment).

An interesting quality of quantum physics that could be applied(if I understand it correctly):

Particles of light(at the least) could be split into two twins which basically act as if they are one even though they may be in different positions. Now what if these were used with the proper function(s) to create variable keys that could be exchanged in something like a Diffie-Hellman maneuver?

I have not had time to think these thoughts fully through, so I expect there to be errors, but I hope this gets some of those thought processes going.

I also re-propose something another member has already proposed: a crypto forum.

Thank you for your time and thought.

Kezil:

Actually, quantum mechanics is inherently a great system for distributing keys. A method has been developed to use photons sent through filters (these filters change the "spin" of the photon) to send info to other parties. Because the photon must go through the filter to be "interpretted" at the other end, it because instantaneously evident that someone has tampered with the key/info. It is actually quite a bit more difficult than that, and is drawn out to greater detail: here

Regards,
Wizeman