Re: Nielsen & Chuang

From: Bruno Marchal <>
Date: Wed, 26 Nov 2003 15:35:44 +0100

Hi Nicole,

I have promised to you some negative (and positive)
comments on Nielsen and Chuang book on quantum computation.
Rereading it in that state of mind, I realize I could make a comment
at each line, and I despair a little bit because it witnesses the gap
between "philosophers" "logicians" and "physicists" ("i" am
a mathematician, although I never asked for: I have studied math
because I suspected that Godel's theorem and Church thesis
bring light to the mechanist approach of the mind-body problem
which is the problem I am really working in).
First of all let me insist that Nielsen and Chuang book is one
of the better book for introducing quantum computation and quantum
information. It is also a beautiful book, and a solid one!

Below is a sentence, taken from the introduction, which illustrates
my perplexity (page 4) (emphasis by the authors):

"This assertion, known as the *Church-Turing thesis* in honor
of Turing and another pioneer of Computer Science, Alonzo
Church, asserts the equivalence between the physical concept
of what class of algorithms can be performed on *some physical
devices* with the rigorous mathematical concept of a Universal
Turing Machine. The broad acceptance of this thesis laid the
foundation for the development of a rich theory of computer
science." (Nielsen & Chuang page 4)

I challenge anyone to find the word "physical" or any allusion
to physics in the whole work of Church, or even in the whole
logical work of Church, Kleene, Turing, Post, Godel, etc. (See the
book edited by Martin Davis "The undecidable" which contains
the original papers. Church proposed to identify the set of
intuitive or effective computable functions with the mathematical
set of functions definissable in his "Lambda formal system".
The intuitive idea of effective computability is the idea of computing
by finite means whatever big the resource needed in the process are
once they are finite but unbounded.
Although Church never mentioned the notion
of "physical" I do appreciate the idea that going from "physical' to
mathematics is interpreted as an increase in rigor. I know David
should not appreciate this, because David has proposed a physical
version of Church Thesis as a more modern version of it, and
of course this is the point where I disagree in FOR. Deutsch thesis
is very interesting by itself, and it is better not to confuse it with
the proposal of Church. Note that the first who proposes "Church Thesis"
is Emil POST, who proposes it as a law of mind, and gives from it
the first simple and direct proof of the incompleteness theorem.
Post seems to have anticipated the whole story from Godel to the
immaterial monism of my thesis! (Well, actually in a footnote
added later Post said that after discussing with Turing he came
back to dualism, but he did anticipate the form of immaterialism
monism which I show inherent to the comp hypothesis.

Another example: more funny and more typical (in the spirit of

"Furthermore, measurement changes the state of a qubit, collapsing
it from from its superposition of I0> and I1> to the specific state
consistent with the measurement result. [...]
Why does this type of collapse occur? Nobody knows. As discussed
in chapter 2, this behavior is simply one of the fundamental postulates
of quantum mechanics." (N & C page 15)

I guess Nielsen and Chuang are just stating the quintessence of
the don't ask feature of Copenhagen philosophy. But why does people
add a "fundamental postulate" nobody knows, and actually nobody
can understand especially putted in that way? Here I would have
appreciate a footnote telling that some people does not believe that
such a collapse ever occur, and pointing to some literature (Everett,
Deutsch, etc.) which gives some explanation why the memory of such
collapse can be explained in strict respect of quantum linearity.
I believe in the long term the collapse gives a wrong idea of what
entanglement could possibly be in term of quantum information
(as I found apparent in the work of Cerf and Adami).

A last example is the box 8.4 on Schroedinger's cat, it gives the
wrong idea that information on a cat which is in a superposition state
(alive + dead), by leaking into the external world will transform
that superposition state into a ensemble of cat being either alive
or dead.
I really does not understand what they mean. Such explanation
is meaningfull in a MW, or in a non-collapse QM. The box gives the
wrong feeling that a real collapse can be explained in QM, ...

OK. It is an excellent book for learning QC and QI, but read
a book like "the conceptual foundation of QM" by Bernard
d'Espagnat, along with FOR book to prevent some implicit
Copenhagen "philosophical" prejudices.
Quantum computation is born through very fundamental
question asked by Einstein (notably) and dismissed by Bohr.
Through the work
of Bell, Feynman and Deutsch, those Einsteinian realist
questions have been shown testable (Bell ) and even
exploitable (Deutsch, Shor, etc.). It is a pity that, when
interesting fundamental questions leads to applications,
people feel to be allowed to dismiss the original questions.
It is on the contrary a sign that the questions were
meaningful, and, even if only for possible new future application (!)
worth to be taken seriously, and investigate closely.

For quantum computation, you can also read the very excellent
book by Gruska. This one is rigorous at all level, i.e. in the math,
in the physics, and in the philosophy (that's very rare!).
But nothing being perfect, the Gruska book is not so pedagogical,
so, read perhaps the book by Nielsen and Chuang, and consult



At 09:48 06/05/03 +0200, Bruno Marchal wrote:
>At 13:12 05/05/03 +0200, ISING (Barberis) Nicole <>
> wrote:
> >Is anyone on this list working their way through "Quantum Computation and
> >Quantum Information",
> >by Michael A. Nielsen and Isaac L. Chuang? Any comments? Do you know of
> >any good student links regarding this book?
>My opinion is that Nielsen and Chuang 's book is one of the best textbook
>on Q Comp and Q Information.
>A good introduction to the Quantum which can serve as a bridge (from
>elementary math to Nielsen and Chuang) is the book by David Albert (Quantum
>Mechanic and experience, Harvard University Press 1992).
>Having said this I should add that Nielsen and Chuang are clearly not
>in foundational matters and there is a definitive lack of rigor in philosophy.
>I will give some example once I have the book under the hand. (Remind me if
>I forget)
>------------------------ Yahoo! Groups Sponsor ---------------------~-->
>Get A Free Psychic Reading!
>Your Online Answer To Life's Important Questions.
>Your use of Yahoo! Groups is subject to
Received on Wed Nov 26 2003 - 09:40:50 PST

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:09 PST