Snarkpit Forum Index » General Banter » Quantum Computers
Quantum Computers
1
2 next page »
Post Reply
Quote
 Re: Quantum Computers
Posted by mazemaster on Thu May 5th at 3:42am 2005

So, I wrote a paper about the basics of quantum computers and Shor's algorithm. In case you are thinking WTF, A quantum computer takes advantage of properties of quantum mechanics to do calculations, and Shor's algorithm is a strategy for factoring numbers really freakin' fast using a quantum computer - far faster than any classical computer. That may sound silly and pointless, but it could be used to crack the previously "uncrackable" RSA encryption, and solve other computation problems faster.

On any other internet forum I wouldn't dare post something as technical as this, but hey Lep posted his dissertation, and some people around here actually knew what he was talking about!

So, without further aideu, I present Quantum Computation and Shor's Algorithm. [addsig]



Quote
 Re: Quantum Computers
Posted by Tracer Bullet on Thu May 5th at 4:55am 2005

I've always been interested and never had the time to read about it... I'll give it a look.

Edit:

Gah... Too much math and not enough physics for this poor chemist's brain to wrap around. I start at the University of Washington in the fall working toward a p-chem doctorate. Maybe after a year of that I will have built up my math skills enough to fully comprehend. I do know a bit more about quantum computing now than I did before, so it was worth it. The whole idea of a bit that was both 1 and 0 always seemed useless to me, but I can certainly see the advantages of being able to do operations on superpositions.

[addsig]



Quote
 Re: Quantum Computers
Posted by mazemaster on Thu May 5th at 5:40am 2005

Yeah, sorry about the math. The mathematical basis for Shor's algorithm gets a bit intense, but hopefully you could understand the parts about qubits and quantum gates and the quantum part of Shor's algorithm. [addsig]



Quote
 Re: Quantum Computers
Posted by Loco on Thu May 5th at 7:26am 2005

My AS physics teacher went on a tangeant about quantum computers once, saying that apparently these things as just 1 and 2 bit machines are insanely fast, actually faster than the human brain. They sound pretty cool, though I'm not sure I could ever get to grips with the concepts behind them!
[addsig]



Quote
 Re: Quantum Computers
Posted by Leperous on Thu May 5th at 8:46am 2005

At the beginning, it might be more "nice" to write that you find the modulus squared of the coefficients to find the probabilities, rather than saying you multiply by the complex conjugate.

? quote:
F(x) = ax (mod N)
If we choose a to be relatively prime to N (the greatest common factor between a and N is 1), it turns out that F(x) must be periodic.

I'm not up on my number theory, methinks this periodicity needs explaining? (it looks simple but I don't see it!) And you should perhaps write F(x;n) = .. here instead.

I love the sentence "the details are not particularly enlightening so they will be omitted," which almost always means "I don't really know the details so they will be omitted" <img src=" SRC="images/smiles/icon_lol.gif">

And wahey, I was thinking "fourier transformation" and then you whipped it out <img src=" SRC="images/smiles/icon_biggrin.gif"> And integrals of the delta function (multiplied with a regular function) representing the registers, too, which could lead to some interesting related analytical results... But, that last section "The Quantum Component of Shor's Algorithm" seems to skip a lot of mathematical details- I would have liked to see some calculations with the Fourier transform, like on Wikipedia, though again I don't know if it's necessary...

If quantum computing can find factors easily, then can't you find sufficiently large prime numbers (e.g. those of the form power tower-1) that are well over the number of qubits (electrons? atoms? organic molecules?) you can hold in your quantum computer? Will this reduce it to something like a polynomial-scale problem, until you feed in a couple more table legs to your computer?





Quote
 Re: Quantum Computers
Posted by Orpheus on Thu May 5th at 9:43am 2005

I don't know anything about "Quantum Computers" but I was thinking about staying at a Holiday Inn and watching "Quantum Leap".

Sorry Mazeman, I couldn't resist.

/Me hopes my lame joking talents doesn't lead to the same fiasco as the last thread of this type.. uhh mentioned.

[addsig]



Quote
 Re: Quantum Computers
Posted by mazemaster on Thu May 5th at 8:22pm 2005

? quote:

? quote:F(x) = ax (mod N)
If we choose a to be relatively prime to N (the greatest common factor between a and N is 1), it turns out that F(x) must be periodic.
I'm not up on my number theory, methinks this periodicity needs explaining? (it looks simple but I don't see it!) And you should perhaps write F(x;n) = .. here instead.


The proof of this basically goes as follows: if there exists a powers 'b' and 'b+t' of 'a' such that ab = a^(b+t) (ie: you kept multiplying ab by 'a', and eventually got back where you started) then there is no way to tell ab apart from a^(b+t), and so ax must repeat with period 't'.

To show that eventually you must get back to the same place you started, you can apply the "pidgeon-hole principle". The logic goes like this: if you have 5 pidgeons and 4 holes, and each pidgeon is in a hole, then at least one of the holes must contain more than one pidgeon. The same thing applies to modular numbers. There are only N "holes" (in mod N) in which to stick numbers, but you can create more than N numbers with ax since x can be as large as you like. Thus some N must correspond to more than one 'x' in ax.



? quote:

I love the sentence "the details are not particularly enlightening so they will be omitted," which almost always means "I don't really know the details so they will be omitted" image


Lol! image The sad thing is that I actually do know the details. I even wrote a whole section on the matrix mechanics of quantum gates, except it was about 4 pages long and I was already over the 10 page limit. )-:

? quote:

If quantum computing can find factors easily, then can't you find sufficiently large prime numbers (e.g. those of the form power tower-1) that are well over the number of qubits (electrons? atoms? organic molecules?) you can hold in your quantum computer? Will this reduce it to something like a polynomial-scale problem, until you feed in a couple more table legs to your computer?


The answer is basically yes. If you make a number bigger than a quantum computer can handle, then obviously the quantum computer cant work with it. The biggest problem currently is that big quantum computers have a lot of problems with errors caused by interactions with the outside world. Thats why currently the biggest quantum computer can only factor 15 = 5*3. image [addsig]



Quote
 Re: Quantum Computers
Posted by Leperous on Thu May 5th at 8:32pm 2005

I don't know of any periodic functions like that, except the exponential of a complex number (and similarly, no numbers with periodic powers unless they are complex and modulus 1) <img src=" SRC="images/smiles/confused.gif">

And yes, environmental decoherence. Though if my dissertation is anything to go by, if it gets very large then you'll get gravitational wavefunction collapse knocking it out





Quote
 Re: Quantum Computers
Posted by mazemaster on Thu May 5th at 8:57pm 2005

? quote:
I don't know of any periodic functions like that, except the exponential of a complex number (and similarly, no numbers with periodic powers unless they are complex and modulus 1) image


Well now you do. (-: [addsig]



Quote
 Re: Quantum Computers
Posted by Addicted to Morphine on Thu May 5th at 9:23pm 2005

The dialogue about this math dissertation is impressive. Can't say I've progressed past calculus (and never will -- I won't be taking any more math classes), so I'm very much lost. But you guys sure as hell seem to know what you're talking about.

Since math is not my forte, if you happen to have any questions about literature send them my way. smiley
[addsig]



Quote
 Re: Quantum Computers
Posted by Crono on Fri May 6th at 12:10am 2005

I have to look at this s**t all day at school, I don't want to see it here too. [addsig]



Quote
 Re: Quantum Computers
Posted by mazemaster on Fri May 6th at 12:18am 2005

You are in college. You get to choose your classes. If you think quantum computers are s**t, then why are you taking classes about them in school? [addsig]



Quote
 Re: Quantum Computers
Posted by Crono on Fri May 6th at 12:28am 2005

I'm not, currently, however, I am chest-deep in computational structures (it's all the same to be honest, the only difference is the theories behind the computations. All that takes to learn is a book or two)

To answer you other questions, it's part of my major and I very well don't get to choose what classes those are.

By the way, it was a joke ... remember those? [addsig]



Quote
 Re: Quantum Computers
Posted by Orpheus on Fri May 6th at 12:42am 2005

? quoting Crono

By the way, it was a joke ... remember those?

Even my poor attempts are for the most part, recognizable as a vain attempt at humor. I honestly did not detect one iota of humor in your post, and I am forever an optimist for your idiosyncrasies. try lightblue next time, or at the very least a smiley :P

[addsig]



Quote
 Re: Quantum Computers
Posted by SaintGreg on Fri May 6th at 12:55am 2005

Cool paper! Does anyone know the "correct" pronunciation of 'qubit' ? I've always thought of it as being 'quibit' cause it sounds cool.
[addsig]



Quote
 Re: Quantum Computers
Posted by Addicted to Morphine on Fri May 6th at 1:00am 2005

I don't know, but when I see it I say " Q - bit " in my mind.
[addsig]



Quote
 Re: Quantum Computers
Posted by Orpheus on Fri May 6th at 1:01am 2005

? quoting SaintGreg
Cool paper! Does anyone know the "correct" pronunciation of 'qubit' ? I've always thought of it as being 'quibit' cause it sounds cool.

isn't that an archaic measurement method? wasn't the Ark so many of them long and wide?

[addsig]



Quote
 Re: Quantum Computers
Posted by Crono on Fri May 6th at 1:06am 2005

Wrong kind of "bit" (as far as I'm aware) [addsig]



Quote
 Re: Quantum Computers
Posted by mazemaster on Fri May 6th at 6:33am 2005

I think its Q-bit, although I am not sure since I have never heard anyone say it out loud. I believe the term Orph is thinking of is the cubit. [addsig]



Quote
 Re: Quantum Computers
Posted by SpiKeRs on Fri May 6th at 8:48am 2005

I look at stuff like this and listen to other peeps who have done computer related courses and wonder what I've actually learnt from my degree. Dont really understand this but looks impressive none the less <img src=" SRC="images/smiles/icon_smile.gif">





1
2 next page »
Post Reply