# [FOM] constructivism and physics

Laura Elena Morales Guerrero lem at fis.cinvestav.mx
Fri Feb 10 12:47:43 EST 2006

Dear fomers:

following.

We are going to simulate a computation. We choose to
compute the logical NOT of a single bit (that is, the
negation of a bit or of a qubit) using two special
quantum logic gates. Consider the individual gates
as each being "square-root-of-NOT" gates [Deutsch92].
We denote it as \sqrt NOT. The name comes from the fact
that consecutive applications of two quantum logic
gates can be understood, mathematically, as the dot
product of the operators corresponding to those gates.
Thus the computation that we want to simulate can be
characterised as \sqrt NOT dot \sqrt NOT identical NOT.
What makes this computation "quantum" is the fact that
it is impossible to have a single-input/single-output
classical binary logic gate that works this way. Any
classical binary \sqrt NOT gate is going to have to
output either a 0 or a 1 for each possible input 0 or
1.

Suppose you defined the action of a classical \sqrt NOT
gate as the pair of transformations

\sqrt NOT_cl(0)=1
\sqrt NOT_cl(1)=1

The two consecutive applications of such a gate could
invert a 0 succesfully but not a 1. Similarly, if you
defined a classical \sqrt NOT gates a the pair of transformations

\sqrt NOT_cl(0)=1
\sqrt NOT_cl(1)=0

then two consecutive applications of such a gate would
not invert any input! In fact, there is no way to define
\sqrt NOT classically using binary logic so that two consecutive
applications of \sqrt NOT reproduce the behaviour of a NOT
gate.

Computing NOT illustrates an aspect of quantum computation.
This \sqrt NOT gate is defined in terms of a squared unitary
two by two complex matrix. It acts on a single qubit and
\sqrt NOT dot \sqrt NOT identical NOT operator. The effect of
a \sqrt NOT is quite unlike any classical logic gate. Acting
on a single qubit turns it into a superposition of the two
base states (0 and 1), highly non-classical.

Regards,
LE

On Wed, 8 Feb 2006, Charles Silver wrote:

> 	In one of David Deutsch's papers, he unveils a quantum
> mechanical "machine" which he calls "the square root of not".
> One machine can produce any result, but when two of them
> are hooked together, the reverse of the initial input of the
> first machine is produced.   (I.e., 1 |--> 0, and 0 |-->1.)
> He bemoans the inadequacy of logicians to arrive at such
> a "not" and challenges them to do so.   He says logic as
> presently constructed is empty, but needs to be useful in
> reflecting reality.
>
>
> Charlie Silver
>
> On Feb 7, 2006, at 3:22 PM, John McCarthy wrote:
> >
> > > Physics has often gone in the opposite direction.  Rather than
> > > confining itself to a subclass of "core mathematics", physicists and
> > > engineers have introduced techniques that "core mathematicians"
> > > considered unsound but later treated.  Oliver Heaviside's operational
> > > calculus was deemed unsound but later blessed via (if I remember
> > > correctly) the Laplace transform.  The Dirac delta function and its
> > > extensions were considered unsound but later blessed by Laurent
> > > Schwartz's theory of distributions.  I recall that Feynmann's
> > > integration over spaces of paths went far beyond what Norbert Wiener
> > > and his successors in integration over function spaces had been able
> > > to justify.
> > >
> > > I wouldn't be surprised if chaos theory got itself into non-measurable
> > > sets.
> > >
> > >> Dear FOM'ers,
> > >>
> > >> Can someone please provide some references on connections between
> > >> constructivism in mathematics and mathematical physics?  There must
> > >> be some literature on this topic.
> > >>
> > >> Thanks,
> > >>
> > >> Steve Awodey
> > >> Carnegie Mellon
> > > _______________________________________________
> > > FOM mailing list
> > > FOM at cs.nyu.edu
> > > http://www.cs.nyu.edu/mailman/listinfo/fom
> > >
> >
> > _______________________________________________
> > FOM mailing list
> > FOM at cs.nyu.edu
> > http://www.cs.nyu.edu/mailman/listinfo/fom
> >
>
>