Quantum computers are not ‘Turing machines’, a term which we will (mis)use to mean very, very approximately ‘ordinary computers’, for our purposes here, and because of this dissimilarity, it may well be that the set of problems that quantum computers can handle is different from that which all ordinary computers can. Thanks to Alan Turing, Alonzo Church, and others, I forget, it has been proved that all normal computer architectures are as capable as each other when ‘capability’ is defined by the set of problems that these machines can solve given that the problems are chosen such that there are no limits on RAM. Different computer architectures may be faster or slower though, and different models may of course run out of RAM or total disk space allocated for virtual memory, which makes for another practical difference.
However, since imho QCs do not conform to the definition of a Turing machine, they may be able to solve new problems. So this is the source of much of the fuss about QC. Overwhelming speed advantages on certain QC-friendly problems is also extremely important.
(I’m using the term Turing machine not in the original, very earliest sense of Turing’s one particular theoretical design of an extremely simple machine, whose mathematics Turing studied. He did not build this machine. I’m using it in the very general sense of ‘the class of computers that are equivalent to the original machine in terms of what they can achieve’, as defined earlier.)
