Review of "Machines, Logic and Quantum Physics"

Reviewer: E. Knill
Review Number: Jul 2001 # 1

Author(s): D. Deutsch, A. Ekert, and R. Lupacchini
Citation: "Machines, Logic and Quantum Physics," The Bulletin of Symbolic Logic 6, 265-283 (2000)
Paper ID: bsl.6.265
Reviewed: Wed Jul 4 00:35:41 2001
Fields: Quantum Computation and Information
Categories: Not Recommended

Review:

This paper surveys Deutsch's ideas about quantum computation as a universal machine capable of performing any computation implementable using physical objects (theChurch-Turing Principle). It begins with a general philosophical discussion of the role of mathematics and physics, building excitement with numerous question and exclamation marks. An elementary introduction to the properties of quantum interference is given, which expands into a discussion of quantum algorithms and quantum Turing machines. The paper ends by explaining how quantum computers might add to what is accepted as ``proof''.

The paper has nice explanations of specific models and algorithms. Unfortunately, its discussions of the relationship of mathematics to physics, and of quantum computers to physical computers and to simulations of quantum evolution, is confusing and often misleading. In the beginning, mathematics is said to provide a precise language for making predictions, while physics is a ``theoretical, conjectural and empirical'' science. Later, it claims that a particular interference effect cannot be learned from an a priori mathematical construct, that it requires quantum theory. This appears to claim, perhaps unintentionally, that quantum theory is not also a mathematical construct. In this case, the part of quantum theory dealing with finite dimensional Hilbert spaces is sufficient for making the appropriate predictions. The authors then proceed to redefine the notions of mathematical logic by suggesting that a unitary operator which squares to the flip of a two-level system is a ``logical operation'', thus contributing to the existing confusion between quantum logic as a theory of certain orthomodular lattices and as a term referring to unitary operators used as gates in quantum computation. In the context of simulating physical systems by quantum computation, ``finite physical system'' means ``finite dimensional quantum system''. Earlier the paper seemed to suggest (via the example of ``walking across a room'') that the physics of particles in a box should be considered ``finite'', but the quantum mechanics of such particles requires infinite dimensional state spaces. (Deutsch's [Proc. Roy. Soc.Lond.. A 400 (1985) 97-117], notes that according to some ideas about the thermodynamics of black holes, the state space of a system enclosed by a finite area can be huge, but still supposedly finite.) The impression is that classical computers are held to a higher standard than quantum computers for what physics they are supposed to be able to simulate.

The writing is remarkably focused on Deutsch's work, omitting important references that would be helpful to readers not already familiar with quantum information. For example, the famous Deutsch-Jozsa algorithm is attributed to a paper of Deutsch's alone instead of the influential joint paper (not cited here) by Deutsch and Jozsa [D. Deutsch and R. Jozsa, Proc. R. Soc. Lond. A 439 (1992) 553--558]. (Deutsch's earlier paper contains only the one-bit version of the problem with a non-deterministic algorithm that fails to demonstrate the advantage of requiring the oracle only once.) One of the effects of this focus on Deutsch is a misrepresentation of what is known about how ``natural'' evolution can be simulated on a quantum computer. The authors make a connection between Deutsch's idea of a universal quantum simulator and the suggestion for simulating quantum evolution made by R. Feynman, claiming that Deutsch proved efficient simulation. In fact, the connection is tenuous. Deutsch only considered the question of realizing an arbitrary unitary operator on $N$ levels, and the complexity of Deutsch's realization is polynomial in $N$ . Feynman's suggestion is associated with simulating $n$ particles or degrees of freedom, whose state space has size $N$ exponential in $n$ , with polynomial in $n$ (not $N$ ) physical resources (see the end of section 4 of the cited paper by Feynman [Int. J. Th. Phys. 21 (1982) 467-488]. Thus the work of Deutsch and of Bernstein and Vazirani (also cited, but see the much more complete [SIAM J. Comp. 26 (1997) 1411-1473], do not demonstrate polynomial in real time simulation of physical evolutions. A good starting point for learning about when such polynomial simulations are possible is Lloyd's [Science273 (1996) 1073-1078].

Overall, the thrust of the paper is to redefine mathematical notions of computation, logic and proof, rather than to consider the models of quantum information and computation as an addition to existing tools. For example, the authors discuss the possibility that a quantum algorithm could be used to efficiently determine that statement $A$ is true, while the shortest symbolic proof of this statement might be too long to be accessible. The authors suggest that a realization of the quantum algorithm constitutes a proof. An alternative view is that a realization of the quantum algorithm gives us evidence of the existence of a (traditional) proof. That is, once quantum computers exist, we may have another tool for verifying proofs, sometimes without ever explicitly writing them down. It is worth noting that this situation already exists with probabilistic computers: Imagine a claim like ``The fraction of $x\in \{1,...,2^n\}$ satisfying $A\left(x\right)$ is in $[f-1/n,f+1/n]$ ,'' where $A$ is readily checkable. It is often much easier to demonstrate this by random sampling than to prove it. The confidence can easily be made as high as that associated with believing the answer of a physically realized quantum algorithm.

Acknowledgments. A short version of this review will appear in Mathematical Reviews MR control number 1803634.

URL of this review: http://quickreviews.org/cgi/display.cgi?reviewID=knill.bsl.6.265

Reviews of same paper - by same reviewer - in same categories
Write or edit a review of this paper - Add bibliographic data for the paper
Add an alternate citation for this paper - Search the database for one or more alternate citations

Main page - New search