TheVat

Hello. Some speculate that a quantum mechanical system which somehow uses an infinite superposition of states could compute a noncomputable function. This is not possible using the standard QUBIT machine, because it is proven that a regular quantum computer is PSPACE-reducible (a quantum computer running in polynomial time can be simulated by a classical computer running in polynomial space). What is potentially non-deterministic is extracting the output of a computation in classical terms. The same final quantum state may be measured as different classical states with varying probabilities. However, if you choose your computation such that the final state is an eigenstate of whatever value you intend to measure, such that the probability of one particular classical output is 1 and all others are 0, then it is effectively deterministic. This is not always possible or practical to do, in which case you may need to to run the quantum algorithm many times to extract the effective classical probability distribution, but effective quantum computation depends on structuring your algorithm to boost the amplitude of the intended output as much as possible, while getting all of the wrong answers to destructively interfere, such that you don’t have to re-run your quantum computation an impractically large number of times. I guess there are nondeterministic models (as noted above), which are just that, models of a hypothetical device sometimes called a hypercomputer. But in the RW, computations are deterministic.