Question about quantum computing

[Flatworm]

I have read a few articles (aimed at amateurs) about quantum computing. It seems the main attraction is the idea of performing the same operation on a huge number of inputs simultaneously through quantum superposition. Basically you have a bunch of specially constructed memory elements, each of which is in a superposition of the "logic 1" state and the "logic 0" state.

There's a lot of talk about work being done to overcome decoherence- for now let's just assume this kind of difficulty can be overcome.

What I can never find an explanation for in these articles is this: Wouldn't the result show up as a superposition of states? How do we disentangle the superimposed states in the output and relate them to specific inputs?

For example, we line up 128 qubits with the "logic 1/ logic 0" superposition, and use them to brute-force a convetional cipher needing a 128-bit key. How do we detect a match for the known plaintext in the output, and how do we know which key produced it out of the 2^128 possible ways the input could collapse?

 

[69dodge]

What I can never find an explanation for in these articles is this: Wouldn't the result show up as a superposition of states? How do we disentangle the superimposed states in the output and relate them to specific inputs?

My not-very-expert understanding: Quantum computation is not just a simple matter of, in effect, running lots of classical computations simultaneously and so getting all their answers as quickly as you could get one answer classically. You have to make a measurement, which collapses the superposition. So you still get just one answer. But that one answer will in general depend on all the states that made up the superposition. You have to arrange things so that the separate evolutions of each state in the superposition, followed by their combination through the collapse of the superposition to a single state, gives you the answer you want. Exactly how to do this arranging depends on the specific problem you want to solve, and it's not necessarily easy. (Or even necessarily possible, I imagine.)

 

[Dragon]

You could try sending a PM to "Tez" on this forum. He is a professor at Imperial College, London and was researching this very subject. Well, he was a couple of years ago when we had a forum outing to Skeptics in the Pub. He doesn't seem to post much these days but a PM might generate an email so worth a try.

 

[Flatworm]

I have sent Tez a PM; hopefully he will drop by and clear things up a little.

 

[Alkatran]

Well, if we were on a classical computer and all we were given was the sum of a bunch of runs of the algorithm, I would make the output 0 if the input didn't work, and return the input if it did work.

I'd be left with.. the answer.


I doubt that's how it works in quantum computers, though.

 

[Art Vandelay]

Well, trying to explain QC is rather difficult if you don't already have a mathematical background, so I'm going to assume that you understand linear algebra. Now, each state can be represented as a vector, and each operation can be represented by a linear operator (there are further restrictions, but I'm not going to get into that). The entire operation of the computer can then be modeled as the product of an initial state with a sequence of operators, to produce a new vector.

Now, I think that what the OP is getting at is that if we want the answer to be deterministic, then we need to have the final vector be one in which each q-bit is either zero or one. I haven't seen any of the specific algorithms, so I don't know how that would be implemented. You'd want to have some sort of cancelling going on.

 

[Tez]

I got your PM flatworm - I'm on the road at the moment - will be back home Wednesday and will post a fuller reply. The short answer is that you dont use the quantum superpositions to search for ciphers directly etc. You use quantum interference to perform a SFFT (super-fast fourier transform) - one that works in log(N) time instead of the N*log(N) time (I think it is) of the standard FFT. Turns out factorising numbers can be realted to finding such fourier transforms, and many security of many cryptographic systems are related to factorizing or similar number theoretic problems.

 

[Grundar]

That would indeed speed up things. Thank you Tez, i had been wondering the same thing.

/Hans

 

[Flatworm]

Thanks everyone, especially Tez.

It looks like I have some reading to do on existing quantum algorithms and factoring via the DFT.

 

[Tez]

My not-very-expert understanding: Quantum computation is not just a simple matter of, in effect, running lots of classical computations simultaneously and so getting all their answers as quickly as you could get one answer classically. You have to make a measurement, which collapses the superposition. So you still get just one answer. But that one answer will in general depend on all the states that made up the superposition. You have to arrange things so that the separate evolutions of each state in the superposition, (which affect each other via positive or negative reinforcement due to quantum interference), followed by their combination through the collapse of the superposition to a single state, gives you the answer you want. Exactly how to do this arranging depends on the specific problem you want to solve, and it's not necessarily easy. (Or even necessarily possible, I imagine.)

Very close to spot on, I added a phrase to indicate precisely where the magic happens...

 

[Tez]

Hmm - well I promised a fuller explanation - and I do now I find myself with a few free hours to read the forum - but can't think of what in particlar to say about this somewhat large topic. Do you have any specific questions flatworm (or anyone else)? If not I'll just assume you understand it all perfectly

 

[Tez]

Well - here is one comment. Suppose you did want to search for the factors of a number N. If you try to do an exhaustive search then you basically need to examine all the numbers up to [latex]\sqrt{N}[/latex]. However, on a quantum computer exhuaustive searching like this can always give you an extra "quadratic speedup" - in general if there are M items to be checked, one of which is the desired item, a quantum computer can find the desired item in [latex]\sqrt{M}[/latex] "checking steps". (A regular computer would, on average, have to check M/2 of the things - a much larger number.) So naively applying a quantum computer to the problem of factorization would let you exhaustively search for the factors in [latex]\sqrt{\sqrt{N}}[/latex] steps... This is still much worse than Shor's algorithm which takes O(log(N)) steps of course, but is interesting as a much more widely applicable principle. (The realisation this is possible is due to Lov Grover, about whom I have many stories...)

(Sorry I can work out how to get the latex fonts to be about the same size as the text ones!)

 

[hammegk]

Given a simple problem.

An adequately sampled time-domain signal, say each millisecond, and the need to filter it in time-domain using a filter of operator length 500 samples:

I'd guess the quantum computer could be coded -- if coded is even the right word -- to perform the 500 multiply & adds needed for each output point as a single operation.

If that made sense ...

Say we wanted 2000 output points; could the quantum computer also be coded to perform all 2000 of the 2000 then-needed 500 multiply & adds as a single operation? My guess is no, that wouldn't be doable.

 

[Tez]

Given a simple problem.

An adequately sampled time-domain signal, say each millisecond, and the need to filter it in time-domain using a filter of operator length 500 samples:

I'd guess the quantum computer could be coded -- if coded is even the right word -- to perform the 500 multiply & adds needed for each output point as a single operation.

If that made sense ...

Say we wanted 2000 output points; could the quantum computer also be coded to perform all 2000 of the 2000 then-needed 500 multiply & adds as a single operation? My guess is no, that wouldn't be doable.

It can do them all in parallel, so yes - it takes as long to do all of them as to do one of them. The problem is that the answer is contained in a quantum superposition, and the tricky thing is to design algorithms to interfere in the right way so as to get the answer you want out. If the answer has some periodicity then Shor showed how this extraction could be done efficiently with a quantm version of the DFT...

 

[Art Vandelay]

How to make them the same size:

Option 1:
Well - here is one comment. Suppose you did want to search for the factors of a number N. If you try to do an exhaustive search then you basically need to examine all the numbers up to [latex] \sqrt{N}[/latex].

Option 2:
Well - here is one comment. Suppose you did want to search for the factors of a number N. If you try to do an exhaustive search then you basically need to examine all the numbers up to [latex]\tiny \sqrt{N}[/latex].

 

[hammegk]

It can do them all in parallel, so yes - it takes as long to do all of them as to do one of them. The problem is that the answer is contained in a quantum superposition, and the tricky thing is to design algorithms to interfere in the right way so as to get the answer you want out. If the answer has some periodicity then Shor showed how this extraction could be done efficiently with a quantm version of the DFT...

Testing for understanding, in the specific case I mentioned, is it correct that would require 2000 parallel computers since each output point is a single value?

I realize my time-domain filter could be more efficiently performed by fft, but could my simple multiply & add for each point of the filter also be accomplished with the single value being the final result of the quantum superposition? And in this case, the 2000 needed outputs would need 2000 paralleled processors if done simultaneously?