Some (but I'm told that not all of the) believers of Quantum Computing (QC) assert that its possibility is ensured (or even required) by the Laws of Quantum Mechanics (QM). In my opinion, such an assertion is based on two fundamental confusions.
Firstly, the Laws of QM are merely a refutable model (or assumption) about the real world, they are not the reality itself nor can they ever be proved to provide a full description of reality. (This is indeed a generic remark that applies to any model of reality, but it is good to bear it in mind when one wants to talk about ``lack of assumptions'': The assumption that QM provides a ``correct'' description of reality is no less an assumption than the conjecture that one-way functions exist. On the contrary, it seems that the latter assumption may be proved correct whereas the former can only be refuted (and can never be proved correct).)
Secondly, as far as I know (and here I may be wrong), QM says that certain things are not impossible, but it does not say that every thing that is not impossible is indeed possible. For example, it says that you cannot make non-Unitary transformations, but this by itself does not mean that you can effect any Unitary transformation that you want.
The above concerns are quite abstract and seem unrelated to the most important discovery of QC: The existence of a simple and fast algorithm for factoring integers in the QC model. But the above concerns (and ramifications of them) become relevant if one asks what does the aforementioned discovery mean.
As far as I am concern, the QC model consists of exponentially-long vectors (possible configurations) and some ``uniform'' (or ``simple'') operations (computation steps) on such vectors. (The length of the vectors, which correspond to a standard work-tape, is exponential in the length of the actual input.) The key point is that the associated complexity measure postulates that each such operation can be effected at unit cost (or unit time). My main concern is with this postulate. My own intuition is that the cost of such an operation or of maintaining such vectors should be linearly related to the amount of ``non-degeneracy'' of these vectors, where the ``non-degeneracy'' may vary from a constant to linear in the length of the vector (depending on the vector). Needless to say, I am not suggesting a concrete definition of ``non-degeneracy'', I am merely conjecturing that such exists and that it captured the inherent cost of the computation. I would further suggest that this issue is related to the transition from QM behavior to ``seemingly classical'' behavior.
(Indeed, a recent paper of Scott Aaronson (Multilinear Formulas and Skepticism of Quantum Computing) suggests a concrete definition of such ``non-degeneracy'' (or ``complexity'') and contains a paragraph (on bottom of page 6) that is very much in spirit of the previous paragraph. I don't feel qualified to express an opinion on the specific definition he suggests. My main disagreement with Scott is conceptual: He says that it is up to the ``skeptics'' to make a concerte suggestion (of such a ``complexity'') and views their arguements as weak without such a suggestion. In contrast, I think it is enough for the ``skeptics'' to point out that there is no basis to the (over-simplified and counter-intuitive to my taste) speculation by which a QC can manipulate or maintain such huge objects ``free of cost'' (i.e., at unit cost). I'd say that it is up to the ``believers'' to articulate why the more plausible conjecture, by which such manipulations have a cost (as anything in life) that corresponds to their ``complexity'', does not hold.)
I wish to stress that I am not concerned with the question of whether or not QC that factor integers of the size used in commercial applications of RSA will be built in our life-time. I am concerned of the question of whether the (simplified, in my mind) model of QC (with unit cost operations) is an adequate model of reality. Needless to say, this question seems to lie more in the domain of physics than in that of computer science.
[Written in Jan. 2004. I have held the aforementioned opinions since I first heard of QC in the early 1990's.]
Back to Oded's page of essays and opinions or to Oded's homepage.