Could a quantum computer perform the tasks of a regular computer?

[box]

I heard one of the problems with quantum computers is there is not a certin output for each input, meaning there is some randomness in their computations. Can this randomness some how be reduced until it becomes negligible? My question is basicly can a quantum computer perform most of the tasks a regular computer can only much faster? Or are there only certin tasks it could perform that would allow some randomness?

 

[setAI]

of course on paper a quantum computer could precisely model any physical system- including any form of classical computer-but the meltdown problem is the monkey-in-the-wrench as it where- but this is an engineering challenge and many solutions are being proposed-

http://arxiv.org/abs/quant-ph/0502050

 

[marlon]

I heard one of the problems with quantum computers is there is not a certin output for each input, meaning there is some randomness in their computations. Can this randomness some how be reduced until it becomes negligible? My question is basicly can a quantum computer perform most of the tasks a regular computer can only much faster? Or are there only certin tasks it could perform that would allow some randomness?

A quantum computer can execute the tasks of an ordinary pc and an ordinary pc can execute all tasks of a quantum computer. The reason is simple if you realize that QM is all about matrices basically. the operations that you need to perform on these matrices (Bra-ket representations) are all 'classical' in nature.

So what is the big difference ?
Well, the thing is that if you, for example, want to compute the output of a function when you give in 1000 x-values, the ordinary computer will need to evaluate the function a 1000 times. The quantum computer can do the job in just one step. The crucial aspect is however that the outcome will be a SUPERPOSITION of |x>|f(x)>...So basically if you want to know the f(x) for the 500th input x-variable you can get the 500th f(x) output. BUT, all the other info will be gone because according to the QM-formalism, the superposition will be broken due to the measurement. Basically, you have no advantage here.

The trick is (and this is the difficult part of quantum computing) to extract the information out of the superposition in an 'indirect' manner by measuring the relative phases of the constituent parts of the superposition. I will refer to Preskill notes on this subject or look for example to Deutsch's Problem, which is quite introductory and easy to understand. In this problem a quantum computer can check whether a function is balanced or not by performing just ONE single measurement. Classically, this is impossible.
You CAN execute this algorithm on a classical pc though, because of the above reasons

marlon
http://www.theory.caltech.edu/people/preskill/