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

This paper surveys Deutsch's ideas about quantum computation as a universal
machine capable of performing any computation implementable using physical
objects (the*Church-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 [*Science***273** (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