PDA

View Full Version : Quantum compurter performance

Digix
2008-Oct-23, 08:27 PM
How do we logically explain quantum computer speed.

imagine that I have some quantum computer and you have usual one.
we need to crack some password and same that you do in one day my computer does in one jiffy.

you are working hard, increase your computer capacity select bigger password but still my computer cracks it i one step while yours requires few years.

ok, then you use namnotechnology create galaxy sized computer with unimaginable power, and still you need more time than age of galaxy to crack same password that my old computer can crack again in one step.

lets say that you doesn't know how my computer works so it looks like mine is infinitely faster than yours?

obviously that contradict with theory of information, and logic
if all data transfers are performed in finite speed less than c, then how computer can do multi step calculations in about zero time?

assume we know nothing about quantum stuff, but I just got that device from some aliens.
how would you explain logically that infinite performance?

stutefish
2008-Oct-23, 08:39 PM
Your search space has to be big enough to contain all possible outcomes, and your power source has to be powerful enough to "energize" the entire search space simultaneously.

A 4-byte password couldn't be cracked by a 2-bit "quantum computer" such as you describe in a single step: Your search space would be far too small to consider 4 bytes worth of possibilities.

And if the number of possibilities were large enough, you'd need an array the size of a small moon to consider them all, and would be hard pressed to find a power source capable of initializing the entire array.

nauthiz
2008-Oct-23, 09:45 PM
imagine that I have some quantum computer and you have usual one.
we need to crack some password and same that you do in one day my computer does in one jiffy.
Thankfully it's not quite so simple. In the case of password cracking, the quantum computer can try passwords on the traditional computer only as fast as the digital computer will accept them.

However, for the time being quantum computers will probably be much slower than conventional computers on all but a few select problems such as factoring large integers. So the quantum computer is probably a much worse choice for cracking passwords than a conventional computer would be.

Now if it's cracking encryption we're talking about, the QC would be very strong against encryption systems that depend on the difficulty of factoring large integers on the current crop of computers. All you have to do to get around that, though, is switch to an encryption algorithm that's based on math that isn't so easy for quantum computers.

Alternatively, in the short term you could take advantage of the fact that quantum computers will initially be extremely expensive to build by sticking with a 'quantum-weak' encryption algorithm but increasing the key size. With a sufficiently large key, you could make it be just too expensive to build a QC that's powerful enough to crack the encryption.

Digix
2008-Oct-23, 09:58 PM

basically qyantum computer is bidirectional, it doesnt care in which direction to perform calculation.

lets say we have some inexpressible function x=f(y) then only way for usual computer to find value of y us to try all of them and see which one match.

quantum computer can do reverse calculation in same speed as it does forward.

so in case that you make reasonably big quantum computer you are sure that it can outperform everything that theoretically is possible in classic way.

stutefish why do you say so?
quantum computer is basically a bidirectional circuit that performs some calculation

PraedSt
2008-Oct-23, 10:44 PM
Digix, you seem to be arguing that quantum computing is illogical because it implies FTL information transfer.
As far as I'm aware, computations on a quantum computer take a not-insignificant amount of time, so it'll never really seem to be 'infinitely fast'. Have I understood you correctly?

nauthiz
2008-Oct-23, 11:00 PM
lets say we have some inexpressible function x=f(y) then only way for usual computer to find value of y us to try all of them and see which one match.
Sadly, I don't believe it's quite that easy. I don't understand all the physics involved, but here's what I do grasp:

It is basically that using a quantum computer is a lot more complicated than just throwing qubits at a traditional algorithm and seeing what comes out: Chances are, the result will be a bunch of qubits that are still in a state of superposition, so when you read each qubit the answer you get will be a random selection of the qubits' states. They're not necessarily even ones that correspond to each other within the context of a single result for the function.

Take XORing [1, 1] and [0, 0] with [1, 0]: Running them through one at a time, you'll get [0, 1] and [1, 0], respectively. If you instead superpose the input values together in a quantum computer and XOR that with [1, 0], you'll get something along the lines of (I'm not going to bother with using proper notation here) [{1,0}, {1,0}], and by reading those qubits out one at a time you could get all of the following possible results: [1, 1], [1, 0], [0, 1], [0, 0]. Note that only two of those results correspond to answers you might really get by XORing those values together, and the other two are not. In other words, the quantum computer has not given us a way to do a bunch of XOR operations really really fast. It's only given us a really fancy way to generate complete garbage. Worse yet, it will take us a really long time (comparatively speaking) to generate this garbage because reading a qubit collapses its state so we'll have to run the operation at least four times - likely well more than four times - to make sure we've gotten all the worthless answers the quantum computer is prepared to give us.

However, when operations are being performed on superposed qubits it's possible for interference patterns to develop, and these can combine to 'erase' parts of a qubit's state. I'm not sure exactly how that works, but you can take advantage of this by designing an algorithm where the interference patterns 'erase' every state except for the ones that belong to the correct answer. That's great: we only have to read the results once, and the result we get has the added advantage of being reasonable. That's the way quantum computers will generally be used. It's worth noting, though, that while these algorithms can offer remarkable speedup over classical algorithms, they still tend to fall far short of the performance that's often suggested in the popular media. To take the example of integer factorization: If we really were able to just throw a giant superposition of qubits through the quantum computer and get our answer out the other end in one go, that would be a O(1) (constant time) algorithm - that's very fast, a rare and beautiful thing. In reality, though, the algorithm that famously promises to make all the world's cryptographers cry in their beer, Shor's algorithm (http://en.wikipedia.org/wiki/Shors_algorithm), only promises to give an answer in polynomial time, O( (log N)3) to be precise.

That's still a nice advantage, it only helps us for factoring integers. For other problems, different specifically-tailored algorithms are needed. If such an algorithm has not been developed yet, you'll be stuck running the same routines that traditional computers rely on, making a quantum computer just a very expensive device for doing things the old-fashioned way. Worse yet, for some such as everything in NP-complete, there are serious doubts about whether it's even possible for quantum computing to offer any advantage in solving them - meaning that your quantum computer is still going to have a hard time scheduling CPU time for processes and making sure there isn't too much wasted space on its hard disk.

Digix
2008-Oct-23, 11:05 PM
basically yes, it is FTL
also I am not sure about how much time quantum computer requires for some calculation, but for one I am sure that qunatum complexity increases lineary while claccic complexity increases exponentialy.

of course you need time to feed data time to perform calculation step and time to read result, but still we have same result quantum computing is almost indefinitely faster when it has high enough complexity.

this is not noticeable for few qbit designs because
2+2 = 2 ^2 so no gain. but imagine if it is 1000 qbit 2^1000 is practicaly indefinitely more than 2*1000.

Digix
2008-Oct-23, 11:23 PM
Sadly, I don't believe it's quite that easy. I don't understand all the physics involved, but here's what I do grasp:

I also have no full understanding how does it work but basic is bidirectional calculation
as I understood from your explanation we only can read one bit per calculation

that makes everything worse, but bearable now we just can solve calculations that have only single or few solutions, or else they will mess up everything

but still in case of password there is only one password possible
unless we make special way to mate many passwords valid and this will confuse computer.
but it is possible to add more rules, like password must be with lowest digit sum value, or something else to clear multiple possibilities.
.

nauthiz
2008-Oct-24, 01:07 AM
as I understood from your explanation we only can read one bit per calculation
No, you can read all the bits. The problem is, if you don't remove all but one possible state for each qubit in the course of calculation then you won't get an answer when you try to read the result from the quantum computer. You will get a random number.

but still in case of password there is only one password possible
Even if the problem you're doing has only one correct answer, there's no guarantee that the random number that the QC gives you is the correct one. Take an extension of the XOR example I gave above:

We'll do a function that takes two bits again, and XORs them with [1, 0]. But now it takes the two bits that come out of that calculation and XORs them with each other.

Doing this the old-fashioned way with [1, 1] and [0, 0] as the input, you will always get a result of 1. Doing this with [1, 1] and [0, 0] superposed together might give you an answer of 1 half the time and an answer of 0 half the time, even though 1 is the only correct answer.

mugaliens
2008-Oct-24, 10:22 AM
How do we logically explain quantum computer speed.

imagine that I have some quantum computer and you have usual one.
we need to crack some password and same that you do in one day my computer does in one jiffy.

Here is an encrypted word:
01011010
11110111
01101011
11111011
10111010

Decrypt it.

I'll even give you some hints!

1. Each 8-bit byte represents a letter of the English alphabet.
2. The unencrypted word has 5 letters.
3. The word can be found in any english dictionary.

If you had all the computing power of the world at your disposal, event the best quantum computers, for all time, you would still be unable to decrypt this word.

Do you know why? Because the keyspace is larger than the message space. Thus, the number of possible solutions include all 5-letter words which meet the "hints" given above.

My point is that much has been written about "quantum computing," but when it comes to encryption, it's as easy to defeat as any other attack (to those who know encryption)

stutefish
2008-Oct-24, 05:46 PM
The word is "hints", obviously.

Digix
2008-Oct-24, 06:12 PM
My point is that much has been written about "quantum computing," but when it comes to encryption, it's as easy to defeat as any other attack (to those who know encryption)

that does not matter, I dont care about security here. just the fact about quantum computer performance

I would like some explanation of such possibility in terms of usual logic
without resorting to FTL comunication that seems impossible.

basically I have computer which performs actions that are impossible if light speed is the limit of communication speed.

nauthiz
2008-Oct-24, 06:27 PM
that does not matter, I dont care about security here. just the fact about quantum computer performance

I would like some explanation of such possibility in terms of usual logic
without resorting to FTL comunication that seems impossible.

basically I have computer which performs actions that are impossible if light speed is the limit of communication speed.

I don't your question can be answered. You're right, the kind of calculation you think quantum computers would be able to do is probably impossible. Which is why quantum computers can't do it.

Grey
2008-Oct-24, 06:35 PM
Digix, what I think folks are saying is that your ideas of what a quantum computer can actually do are mistaken. It's true that it looks like a quantum computer may be able to perform certain operations much faster than a classical one. But even in those ideal cases, it's nothing like reducing a time complexity from exponential to linear. It's reducing time complexity from exponential to polynomial. That's still a big leap forward, but it's not the leap you describe. No, a quantum computer cannot take an irreversible function and calculate it just as fast backward as it can forward. I'm not sure where you got that impression, but it's simply not the case.

tdvance
2008-Oct-24, 06:36 PM
that does not matter, I dont care about security here. just the fact about quantum computer performance

I would like some explanation of such possibility in terms of usual logic
without resorting to FTL comunication that seems impossible.

basically I have computer which performs actions that are impossible if light speed is the limit of communication speed.

The oversimplified explanation is "super-massive-parallel" computations. A quantum computer essentially does lots of trials simultaneously, and one arranges things so that the successful one or ones survive. Think of Schroedinger's cat--hypothetically both dead and alive till you look in the box, then the waveform collapses and it is one or the other. This really does happen at the particle level and can be more than just two states--imagine lots of simultaneously-superposed states, each one representing a different trial. You arrange for things that the probability of the waveform collapsing onto the one successful trial is much more than that of collapsing on the other unsuccessful trials. The result is, you can search for a needle in a haystack made of n dried grass blades or stems, in time proportional to the square root of n, whereas a classical computer would have to go through all n blades to find the one that is really the needle. It doesn't have much to do with speed of light--just lots of things being done simultaneously.

Digix
2008-Oct-24, 06:56 PM
The oversimplified explanation is "super-massive-parallel" computations.

that wont help because there is no way to fit that amount of machinery into same volume. even if you make computer in quark level.

also I cant find any logical equivalent of quantum functions.

so basically quantum computer just cant be simulated with any comparable size classical computer.

and that makes quantum mechanic illogical because logic is unsuitable for modeling it.

Digix
2008-Oct-24, 07:07 PM
Digix, what I think folks are saying is that your ideas of what a quantum computer can actually do are mistaken. It's true that it looks like a quantum computer may be able to perform certain operations much faster than a classical one. But even in those ideal cases, it's nothing like reducing a time complexity from exponential to linear. It's reducing time complexity from exponential to polynomial. That's still a big leap forward, but it's not the leap you describe.

No, a quantum computer cannot take an irreversible function and calculate it just as fast backward as it can forward. I'm not sure where you got that impression, but it's simply not the case.
that was on one of web pages about quantum computers there they were compared with reversible logic gate computer.
seem that it can actually perform reverse calculation, but there are problems to read the result so you need to perform calculation lots of times.

PraedSt
2008-Oct-24, 07:18 PM
It's reducing time complexity from exponential to polynomial. That's still a big leap forward, but it's not the leap you describe. No, a quantum computer cannot take an irreversible function and calculate it just as fast backward as it can forward.

Thanks Grey. I was trying to understand that too.

nauthiz
2008-Oct-24, 08:39 PM
so basically quantum computer just cant be simulated with any comparable size classical computer.

Quantum computers are still merely Turing-complete, which means that they can't do a single thing that you can't do on a regular computer. It's just that they can do some of them a bit faster.

nauthiz
2008-Oct-24, 08:54 PM
that was on one of web pages about quantum computers there they were compared with reversible logic gate computer.
seem that it can actually perform reverse calculation, but there are problems to read the result so you need to perform calculation lots of times.
Reversible logic gates do not let you do reverse calculation. They're simply logic gates whose operation is a one-to-one function. (NOT, for example.)

They don't let you arbitrarily do math backwards, though. Doing so isn't even possible except for a very small subset of functions. Take the example f(x)=x2. Let's say we know that this function was just run and gave a result of 4, and we want to know what the input was. Unfortunately, we can't, because there are two possible input values (2 and -2), and we have no way of knowing which is the correct one.

Digix
2008-Oct-24, 09:16 PM

Quantum computers are still merely Turing-complete, which means that they can't do a single thing that you can't do on a regular computer. It's just that they can do some of them a bit faster.
that is true, but that is the whole point: it is faster, and enormously faster.
its like comparing snail with space rocket (o course in rare cases only).
however we can also assume that usual computer can work at speed of light and quantum computer still manages to outrun it.

Reversible logic gates do not let you do reverse calculation. They're simply logic gates whose operation is a one-to-one function. (NOT, for example.)
no they are not one to one but one to many since backwards 2-and gate will give you 3 valid input combinations to get 0 at output
I will try to find that page again. unfortunately such backward computing system complexity expands exponentially.

They don't let you arbitrarily do math backwards, though. Doing so isn't even possible except for a very small subset of functions. Take the example f(x)=x2. Let's say we know that this function was just run and gave a result of 4, and we want to know what the input was. Unfortunately, we can't, because there are two possible input values (2 and -2), and we have no way of knowing which is the correct one.
both 2 and -2 are correct. in case of 1=sin(x) function it is ok to get any random valid x value
in most practical jobs you don't need all possible solutions

nauthiz
2008-Oct-24, 10:13 PM
however we can also assume that usual computer can work at speed of light and quantum computer still manages to outrun it.
I'm not sure I understand what it means to calculate at the speed of light. How do you convert FLOPS to m/s?

nauthiz
2008-Oct-24, 10:24 PM
no they are not one to one but one to many since backwards 2-and gate will give you 3 valid input combinations to get 0 at output
They absolutely must be 1:1.

Logic gates cannot give two answers, so if a function is surjective then that means that there cannot possibly be a logic gate that reverses the operation.

Logic gates must also be willing to accept all possible combinations of input bits. Our theoretical operation that reverses a surjective function cannot be implemented as a logic gate because it would not meet this criterion, due to the pigeonhole principle.

Digix
2008-Oct-24, 11:14 PM
I'm not sure I understand what it means to calculate at the speed of light. How do you convert FLOPS to m/s?

we have computer size (diameter), speed of light and assume that one calculation takes one signal transmission form one to another side of computer

of course we can use parallelization and that makes it little more complex. but still in that case we must send data and result to from from some distant core. and if you make solar system sized computer it will be unable to perform more than one calculation in time less than required for light pass its radius.

lets assume that one gate is one hydrogen atom size (it cant be smaller)
them we calculate number if gates required for calculation that translates into core diameter. then we can calculate maximum possible core speed in FLOPS
if you like some parallelization
then core speed is insignificant but we just calculate time required to send data from most distant core to our terminal.

exact numbers do not matter, because we just make equation
exponential size increase vs polynomial or whatever is fro quantum computer.

at some degree of complexity you will clearly get quantum computer overrunning fastest possible normal computer.

Digix
2008-Oct-24, 11:23 PM
They absolutely must be 1:1.

Logic gates cannot give two answers, so if a function is surjective then that means that there cannot possibly be a logic gate that reverses the operation.

Logic gates must also be willing to accept all possible combinations of input bits. Our theoretical operation that reverses a surjective function cannot be implemented as a logic gate because it would not meet this criterion, due to the pigeonhole principle.

Of course usual logic gate cant do that. If they could there would be no need for quantum computers, Lets say we have gate AND so we can build simple circuit which will try to find and present to you some combination that gives you correct result.
it is same as password cracking, you try many combinations until you you get one valid.
so reverse calculation computer will be highly parallel device which tests all possible combinations and gives you one of few that are valid.

spratleyj
2008-Oct-24, 11:25 PM
How do we logically explain quantum computer speed.

imagine that I have some quantum computer and you have usual one.
we need to crack some password and same that you do in one day my computer does in one jiffy.

you are working hard, increase your computer capacity select bigger password but still my computer cracks it i one step while yours requires few years.

ok, then you use namnotechnology create galaxy sized computer with unimaginable power, and still you need more time than age of galaxy to crack same password that my old computer can crack again in one step.

lets say that you doesn't know how my computer works so it looks like mine is infinitely faster than yours?

obviously that contradict with theory of information, and logic
if all data transfers are performed in finite speed less than c, then how computer can do multi step calculations in about zero time?

assume we know nothing about quantum stuff, but I just got that device from some aliens.
how would you explain logically that infinite performance?

I'm not trying to be rude, but it's hard to understand you because of your poor English - is English your first language?

And I thought quantum computers were still "futuristic" or are there functioning ones?

Digix
2008-Oct-24, 11:32 PM
I'm not trying to be rude, but it's hard to understand you because of your poor English - is English your first language?

And I thought quantum computers were still "futuristic" or are there functioning ones?
English is not my native language, I think that is obvious :shifty:
Quantum computers do exist, but only very simple ones. As I know biggest one is 8 bit, and it cant outperform normal computers yet.
actually these are not even complete computers but quantum logic gates.

alainprice
2008-Oct-24, 11:38 PM
I remember reading a while ago that quantum computing had been accomplished using organic molecules and reading the resulting 'goo'.

I wish I had time to explore it, sounded neat.

cjameshuff
2008-Oct-25, 12:34 AM
I remember reading a while ago that quantum computing had been accomplished using organic molecules and reading the resulting 'goo'.

That's not quantum computing, though it takes a similarly extremely parallel "solve it all at once" approach. Quantum computers, as mentioned, are extremely primitive at the moment, but do exist...and their development has spun off technologies that have found use in things like modern hard drives.

Digix: You either greatly misunderstand the way quantum computers work, or the claims of the people who build them...I can't really tell which. Yes, the time it takes to solve a problem is limited by the speed-of-light lag across the computer. Since they aren't usually that big across, and can do some things with a single operation that more conventional computers would require a considerable number of steps to perform, they could greatly exceed the performance of conventional computers for some problems. The highly controlled operating conditions and time required for setup and read-out of results mean they're unlikely to be very good general purpose computers...eventually, maybe a co-processor system.

mugaliens: it's not always possible to hide the type of encryption used, or prevent larger samples of encrypted data from being taken. Many types of encryption could indeed be vulnerable enough to attack by quantum computers to be unusable. You *can* generally derive the private key of an encrypted message and the public key, and then decrypt the message...it just takes an impractical amount of processing time for any conceivable conventional computer (with reasonable key sizes).

However, there are other methods...if it really comes down to it, one-time pads can be used for stuff that *really* has to be secure, and those are utterly unbreakable. (As you mention, there's no way to tell the message from any other possible message of the same length...and if you pad the message to a standard block size, the number of possibilities expands to all messages of that length or shorter, preventing heuristics based on probable human language sentences from being used.)

ASEI
2008-Oct-25, 01:14 AM
Do you know why? Because the keyspace is larger than the message space. Thus, the number of possible solutions include all 5-letter words which meet the "hints" given above. Thank you! I don't know how many times people claim that all encryption is flawed and vulnerable. Not if you really care to do it right.

I don't know why you couldn't build an equivalent analog computer that creates interference with classical amplitudes. Why not encode multiple bits in fractional bases of multiple electrical channels and superimpose those? I guess I'll have to learn more about what's involved in their interference algorithms.

Digix
2008-Oct-25, 02:12 AM
Digix: You either greatly misunderstand the way quantum computers work, or the claims of the people who build them...I can't really tell which. Yes, the time it takes to solve a problem is limited by the speed-of-light lag across the computer. Since they aren't usually that big across, and can do some things with a single operation that more conventional computers would require a considerable number of steps to perform, they could greatly exceed the performance of conventional computers for some problems. The highly controlled operating conditions and time required for setup and read-out of results mean they're unlikely to be very good general purpose computers...eventually, maybe a co-processor system.

this just means that quantum computers can work faster than light.
and this statement contradicts with relativity.
or if we say they don't use FTL then entire quantum mechanic is illogical. because how it can do something that is impossible.

Digix
2008-Oct-25, 02:22 AM
Thank you! I don't know why you couldn't build an equivalent analog computer that creates interference with classical amplitudes. Why not encode multiple bits in fractional bases of multiple electrical channels and superimpose those? I guess I'll have to learn more about what's involved in their interference algorithms.
that wont work, because everything will interfere with everything and there will be mess, you only want photon interference with itself.
maybe in some cases it can be possible but not usable
All that quantum stuff is almost absurd because it involves at least one infinity.
infinite communication speed, infinite set of possibilities or maybe infinite precision of analog to digital conversion or something that i don't know.
but something needs to be infinite. Or else you cant simulate quantum stuff with non quantum logic in real time.

tdvance
2008-Oct-25, 03:02 PM
no they are not one to one but one to many since backwards 2-and gate will give you 3 valid input combinations to get 0 at output

A reversible and-gate has more than one output line. Any setting of the input lines results in a unique setting of the output lines. It is a one-to-one and onto function.

tdvance
2008-Oct-25, 03:06 PM
I'm not trying to be rude, but it's hard to understand you because of your poor English - is English your first language?

And I thought quantum computers were still "futuristic" or are there functioning ones?

There are small functional ones, on the order of 7 cubits or so. I read somewhere 15 was factored into 3*5 by one using Shor's algorithm (a polynomial-time quantum computer factoring algorithm). What's difficult is making one with enough cubits to do something not more easily done with existing computers.

Digix
2008-Oct-25, 04:05 PM
A reversible and-gate has more than one output line. Any setting of the input lines results in a unique setting of the output lines. It is a one-to-one and onto function.

of course single 2-and reversible gate requires 8 outputs (2x4)for reverse calculation

mugaliens
2008-Oct-25, 05:12 PM
Thank you! I don't know how many times people claim that all encryption is flawed and vulnerable. Not if you really care to do it right.

I believe it's because encryption is, for most people, including the technical writers that write about it (and often mis-write about it), a puzzling field.

I don't know why you couldn't build an equivalent analog computer that creates interference with classical amplitudes. Why not encode multiple bits in fractional bases of multiple electrical channels and superimpose those? I guess I'll have to learn more about what's involved in their interference algorithms.

I've long wondered if it weren't possible to create such a computer using intersections from standing waves. Such approaches, however, would simply be analog versions of the countless numerical approaches to encryption, particularly PKI, which use functions who's solution in one direction results in myriads of possible solutions (private key x algorithm --> public key), but who's solution in the other direction results in just one possible solution (public key x message --> encrypted message) that's only solvable via the private key. Thus, one can walk around with a bunch of different public keys, all of which are tied to a single private key.

Here's a tidbit about which most people are unaware: The reason keylength is restricted is that the number of possible solutions is tied to the keylength. Even with recursive approaches (as opposed to one-time random cypher pads), one can still render the encrypted message unbreakable by using a sufficiently long keylength (and keeping the message sufficiently short) such that the keyspace is larger than the message, thus rendering the set of all possible solutions for that keylength larger than the set of all possible solutions based on the message length alone.

mugaliens
2008-Oct-25, 07:25 PM
Someone recently asked me to explain why having a key space larger than the message space can render the encrypted message unbreakable.

Let's tackle this using the most basic, binary approach, and the XOR function (http://en.wikipedia.org/wiki/Xor). Put simply:

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

Think of it as "+" while disregarding the carryover. Thus, the first three hold true. The answer to the last would be 10, but if we disregard the 1 that was carried over, we're left with the 0. In computer science, this is technically referred to as "bitwise operation" or "addition without carry," and the technique is used in RAID 3, 4, 5, and 6 for creating parity information, because it's incredibly fast.

Let's take an 8-bit word and play with it a bit (pun intented).

A: 01101001

Sorry, 01101001, but you're moniker is ripe for the picking! I beg your forgiveness, but I hope you feel honored.

Then, let's generate a totally random 8-bit value.

B: 00110111

Finally, let's XOR them together to see what we have.

C: XOR(01101001,00110111)=01011110

Let's stack them so it's easier to see the process and the result:

01101001 - Message
00110111 - Key
---------
01011110 - Encrypted Message

Now, let's say that A is the message, and B is the key. The result is C. Thus, A XOR B = C. Put another way, XOR(A,B)=C

Decrypting the message is ridiculously easy - simply perform a second XOR function using the key and the encrypted message:

01011110 - Encrypted Message
00110111 - Key
---------
01101001 - Message

Neat how that works, huh?

Those of you who're thinkng on their feet might realize that this is the basis of the "pre-shared key" approach, and it is one variant. Others use algorithms which allow them to use shorter keys, but with the advent of a portable hard drive or thumbstick by which non-reused shared keys can be distributed, anyone who can program in basic or any other language can write a simple program which implements the pre-shared key, one-time pad cypher, that's absolutely (not just virtually) impossible to crack, even if all the computing power of the entire world for now and all time were brought to bear on it.

Of course there is a way to crack it: find and steal the pre-shared key, preferrably without the bad guys knowing about it (that way, you can read their e-mails at your leisure). But that's James Bond stuff.

There are many ways of making B truly random, or sufficiently random so as to defy all attempts to determine any pattern. Slow-polling with interleaved inversion of pseudo-random data, with pseudo-random interval variation is but one such method. Suffice to say this is easily done, and done millions of times a day throughout the world.

In this special case, the length of key B (the "key space") is equal to the length of message A (the "message space"). Furthermore, since it's 8 bits long, we have 28, or 256 possible variations of that key. But these same criteria apply to the message. That is, there are preciely 256 possible combinations of 1s and 0s in an 8-bit byte (word).

Thus, it's said that the key space is equal to the message length. In this case, it's uncrackable, as is the case when the keyspace is larger than the message space.

Technically, this is called a "one-time pad cypher," the only two provisions of which is that the cypher pad (the key) has more variations than is possible given the spaces of the message, and that the pad be random.

You may have heard of the term "block cypher (http://en.wikipedia.org/wiki/Block_cipher)," which uses a variation of this, called the Feistel cipher (http://en.wikipedia.org/wiki/Feistel_cipher). DES (http://en.wikipedia.org/wiki/Data_Encryption_Standard)is one such scheme. Given enough time, however, these can be cracked, because the keys used in block cyphers are smaller than the message length, and DES, with it's 56-bit key, is not considered secure, although triple DES, which uses an effective 168-bit key, is 2112, or 5.192x1033 times more secure, and as such, is considered to be "practically secure," meaning that it would take an inexorably long amount of time to crack the encrypted message.

In contrast, the Advanced Encryption Standard uses block and key sizes in any multiple of 32 bits, with a minimum of 128 bits and a maximum of 256 bits. It employs those in substitution-permutation network, not a Feistel network. It was approved by the NSA for use in TOP SECRET material, and is the first such encryption technique made available to the public. Further approaches using PKI infrastructure and fractal mathematics are said to be even more secure, although the following axiom remains true: So long as the message space is larger than the keyspace, it is theoretically possible to conduct a successful brute-force attack.

loglo
2008-Oct-25, 10:52 PM
Getting back to the OP, the question comes down to how quantum interference is interpreted. If you take the Copenhagen interpretation then you have virtual particles carrying the eigenstate information and so there are essentially no limitations on number of particles you can throw at the calculation. No light speed limits are broken as the configuration space where the eigenstates are defined does not have a time component and besides virtual particles don't have to follow the same rules as real ones, within the bounds of the Uncertainty Principle.

If however you take the approach of David Deutsch, the guy who invented the algorithm for a universal quantum computer, a la Turing, then the eigenstate information is held by real particles in parallel universes, ie he uses the Many-Worlds interpretation. Again no FTL rules are broken as SR just doesn't apply between universes.

Deutsch is a scientific realist, as opposed to a logical positivist, so he doesn't like invoking "virtual" particles to perform "real" calculations. In fact he believes the observation of quantum superposition proves the Many-Worlds hypothesis. See for instance his New Scientist interview (http://www.newscientist.com/channel/opinion/mg19225811.800).

Most other physicists working in the area, it seems, don't have any such hangups and are happy to use whatever works without attributing reality to parts they can't directly examine. The Copenhagen version of QT is essentially an algorithm, there is no accepted "physical" explanation for how it works, it just makes successful predictions.

Either way there is no conflict with relativity, it just depends on how real you think virtual particles have to be. Since the CI and the MW are, so far, just two descriptions of the same theory then the choice between them really just comes down to personal philosophy.

sabianq
2008-Oct-26, 02:24 AM
If you had all the computing power of the world at your disposal, event the best quantum computers, for all time, you would still be unable to decrypt this word.

The word is "hints", obviously.

hahahahaha.. lol

is the biological analogue computer we call the brain a form of quantum computer?

i had thought that the strength of the quantum computer came from the ability to use "yes", "no" and "maybe".

would not this type of computer also have the ability to reason (and have intuition) giving a decisive edge over conventional binary computers?

just a thought

"Is the brain a quantum computer?"
http://cogsci.uwaterloo.ca/Articles/quantum.pdf

and
Hameroff, S. (1998b). Quantum computation in brain microtubules? The Penrose-Hameroff “Orch OR” model of
consciousness. Philosophical Transactions of the Royal Society of London A, 356, 1869–1896.
Kak, S. (1995). Quantum neural computing. Advances in Imaging and Electron Physics, 94, 259–313.
Kak, S. (1999). Quantum computing and AI. IEEE Intelligent Systems, 14, 9–16.
LaForte, G., Hayes, P., & Ford, K. (1998). Why Gödel’s theorem cannot refute computationalism. Artificial Intelligence,
104, 265–286.
Nanopoulos,D.V. (1995). Theory of brain function, quantum mechanics and superstrings. Retrieved June 15, 2005,
from http://xxx.lanl.gov/abs/hep-ph/9505374
Nielsen, M. A., & Chaung, I. L. (2000). Quantum computation and information. Cambridge, England: Cambridge
University

mugaliens
2008-Oct-26, 01:13 PM
is the biological analogue computer we call the brain a form of quantum computer?

i had thought that the strength of the quantum computer came from the ability to use "yes", "no" and "maybe".

would not this type of computer also have the ability to reason (and have intuition) giving a decisive edge over conventional binary computers?

No. Provided the key space is larger than the message space, the solution is indeterminant. That is, the solution set = all possible solution sets.

It's like saying, "Given y=3x+2, solve for y." Well, there is no solution for y, other than the set of all numbers, and that does you no good, as you're looking for a specific number, or in the encryption business, you're looking for a specific message, the one that's encrypted, not the set which includes all possible numbers.

Given my previous example, where the key space = the message space, the solution set was all possible messages (256, given the 8-bit binary byte).

I agree with the authors of your link in that the brain, even though quantum effects govern all interactions, is nevertheless not itself a quantum computer.

tdvance
2008-Oct-26, 07:35 PM
is the biological analogue computer we call the brain a form of quantum computer?

Penrose thinks it might be, but most who study the brain don't. Though more is not known than known about the brain, the evidence does seem to point to it being a massive analog/digital hybrid neural net, possibly even with some kind of FM (frequency of impulses encoding the data).