Quantum Computers

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.

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

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.

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.

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!

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.

F(x) = a^x (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"

And wahey, I was thinking "fourier transformation" and then you whipped it out :biggrin: 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?

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.

? quote:F(x) = a^x (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 a^b = a^(b+t) (ie: you kept multiplying a^b by 'a', and eventually got back where you started) then there is no way to tell a^b apart from a^(b+t), and so a^x 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 a^x since x can be as large as you like. Thus some N must correspond to more than one 'x' in a^x.

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"

Lol! 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. )-:

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.

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)

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 :wink:

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)

Well now you do. (-:

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. :wink:

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

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?

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?

Crono said:
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 :razz:

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

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

SaintGreg said:
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?

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

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.

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
:smile:

I didn't realise 'quark' was pronounced 'qwork' until a few months ago :redface: Although acronyms are worse, especially when you're trying to get a job with someone and don't quite know how to pronounce their project!

<DIV class=quote>
<DIV class=quotetitle>? quoting Leperous</DIV>
<DIV class=quotetext>I didn't realise 'quark' was pronounced 'qwork' until a few months ago :redface: Although acronyms are worse, especially when you're trying to get a job with someone and don't quite know how to pronounce their project!</DIV></DIV>

Even so, accents can distort words to a point of un-recognizability. Take the word you say sounds like "qwork", is that really "Kwork" or "Cawork"? I always pronounced it "Cue-Wark" and have always heard it done so.

Another thing, colloquialisms also distort words.. Take the word "wash", as in "To wash a load of clothes". Here in Arkansas, the local born types pronounce it "Warsh" or "Worsh".. Even if you ask them to spell it, it comes up "wash" but when asked "wheres the f**king R?" they just shrug and look at you with that glassy "duh" look.

/ compulsory explanation.

A most interesting read. But, I really don't think a quantum computer can actually be built.

A most interesting read. But, I really don't think a quantum computer can actually be built.

Not yet anyway.

However, ideas are used. Such as quantum encryption, which is unbreakable by current decryption AND if it is "read" before it reaches its destination the data being sent will be altered (the data being a connection code or something as such, since after a connection is made the information transfer would be virtually instantaneous), it's the same as the cat in the box thing. Also, for our most complicated encryptions quantum decryption can calculate every possibility before a current encryption method calculates one encryption (or something like that).

This has been implemented. I believe NEC is releasing a quantum encryption server sometime this year to catch up to some other companies (IBM and Toshiba, I think are the leaders right now ... not sure though).