Can Schrodinger's Cat Collapse the Wavefunction?

Date: 15 Mar 1997 02:26:05 -0800 (PST)
From: Keith Bowden <K.G.Bowden@uel.ac.uk>
To: quantum-d@teleport.com
Subject: Can Schrodinger's Cat Collapse the Wavefunction?

Classical Computation can be Counterfactual 9/2/96 V1.1
(or Can Schrodinger's Cat Collapse the Wavefunction?)

    Non-mathematical version presented at 
    ANPA West, Stanford University, February 1997 
    (by Prof. Pierre Noyes, Stanford Linear Accelerator Centre).

  Keith Bowden,
  Information Technology, University of East London,
  Longbridge Rd, Dagenham, Essex RM8 2AS.

We show that at least some classes of classical computation can 
be carried out counterfactually in a particular sense.  By 
counterfactually we mean that, given a set of quantum superpositions 
which include the possibility of the (classical) computation being 
carried out, then an observation can be made such that, even if 
the computation is not carried out, the result of the computation 
can be obtained. That is, on some observations, the output of a 
computer run can be obtained without the computer even being switched 
on and depends only on the existence of the computer and the 
possibility of the computation being carried out. As with all 
counterfactual measurements the proportion of "successful" trials 
(ie, those in which the computation does not occur, although the 
result of the computation is obtained) can be made arbitrarily 
large, but the time taken to get the output is the same as that 
which would be needed in order to carry out the computation. The 
interest is in circumstances where there is a reason not to carry 
out the computation (such as the likelihood that it would permanently 
change the computer) but we still wish to know the result.

Although the computation is classical, the overall setup including 
the measuring device constitutes a quantum computer, and our result 
is essentially a special case of Josza's algorithm [Josza, 1995] 
which shows that all quantum computation [Deutsch, 1985] can be 
carried out counterfactually. However today's technology is many 
years away from building a general quantum computer in Deutsch's 
sense. Our paradigm demonstrates that by considering a quantum 
computer to consist of a combination of classical and nonclassical 
parts, and by restricting the quantum part to observation and the 
classical part to computation, we can build interesting devices now. 
We consider how we can widen the class of counterfactual classical 
computations and come across some unexpected results and interesting 
speculations.

INTRODUCTION

Consider a terrorist who has obtained a collection of bombs from 
some dubious source, so that he is not certain which, and indeed how 
many, of the bombs are dud. As a card carrying terrorist he needs to 
know which are usable bombs. Clearly he can accumulate dud bombs by 
throwing the bombs, one by one, at a wall, and collecting the ones 
that do not explode. Unfortunately this process does not work in 
reverse; the only way of finding out which bombs are usable destroys 
them. Just to make the problem a little harder we will specify that 
the trigger of each bomb is sensitive to a single photon. Specifically 
the bombs either absorb the photon and explode, or transmit the 
photon and are duds. It is, in principle, impossible to identify 
usable bombs by any nondestructive classical process.

In 1993 Elitzur and Vaidman published a paper that showed that, 
unexpectedly, a readily available device (actually a Mach-Zender 
interferometer, but here and elsewhere dubbed a Bomb Tester) could 
be used that would identify usable bombs, nondestructively and 
conclusively, at least half of the time. A Mach-Zender interferometer 
consists of two silvered and two half silvered plane mirrors arranged 
[as in Fig (1)] such that one of the half silvered mirrors splits a 
light beam into two, the two mirrors are then arranged such that 
they deflect the two half beams which then rejoin at the second half 
silvered mirror. The path lengths of the two half beams are set equal 
(or an integer multiple of half-wavelengths of the light apart). It 
can easily be seen that interference will occur such that the input 
beam seems to pass directly through the device, albeit with a lateral 
shift. Consider the case when the input beam enters horizontally, 
then the output beam will exit horizontally, and photons from the 
two half beams arriving at the second half silvered mirror in any 
other direction will either be corrected by reflection or lost by 
destructive interference.

> 
>             /                  /
>            / - - - - - - - - -/   ---> 
>           /|                 /|
>  
>            |                  |            No bomb (ie. bomb is a dud)
>                                            reversible process
>            |                  |            phases recombined/restored
>                                            merely lateral shift
>            |/                 |/
>  --->  ----/ - - - - - - - - -/
>           /                  /
> 
>          
>                                                                 D2
>                                                               ^
>                                                               |
>       But in this case,                                           
>       the bomb blocks the                   /                  /
>       photon, leading                      / - - - - - - - - -/    
>       either to (50%,50%):                /|                 /|
> 
>            a) a detection                  |                  |      
>               at D2, or else
>            b) none at all...               |                  |
>               (boom)
>                                            |/        b        |/
>                                  --->  ----/ - - - - o - - - -/
>                                           /          m       /
>                                                      b
>                       
>                            Fig. (1) 

Now consider the case when one of the half beams is blocked (say the 
bottom one [in the diagram]). Interference can no longer occur at the 
output. The remaining half beam will be split by the second half 
silvered mirror such that a quarter of the input photons leave hori-
zontally, and a quarter vertically. Now consider what happens if we 
turn the intensity of the light beam down so that only single photons 
are passing through the device in a measurable time interval. Quantum 
mechanics says that if neither of the beams are blocked interference 
will still occur and if the input beam is horizontal, then photons 
will only leave the device horizontally. If the lower beam is blocked 
as before, then a quarter of the photons will leave the device hori-
zontally and a quarter vertically. Now the crux of the argument is 
that whenever a photon leaves the device vertically we know that the 
lower half beam is blocked, even though the photon did not traverse 
this route in order to find out!

This mode of observation is known as counterfactual measurement. To 
resolve the tale with which we began this section, the terrorist can 
use the device described by blocking the lower beam with the trigger 
of a bomb, then there are four cases. Either 

1. the input photon travels the lower route and the bomb is usable in 
which case the photon is absorbed and the bomb explodes and is lost, 
or 

2. the input photon travels the lower route and the bomb is dud, in 
which case it does not explode and the photon is transmitted, 
destructive interference occurs at the output and the photon leaves 
the device horizontally, or 

3. the input photon travels the upper route and leaves the device 
horizontally in which case we cannot distinguish between this case 
and the previous one and the result in each case is inconclusive 
with respect to the status of the bomb, or

4. the input photon travels the upper route and leaves the device 
vertically in which case we know that interference has not occurred 
and that the bomb would have absorbed the photon and exploded if it 
had instead followed the lower route.

So, by sacrificing half the usable bombs, we can identify the other 
half from the duds. Kwiat et al [1996] have devised a method, using 
a sequence of polarising devices, that efficiently increases the yield 
rate to a level arbitrarily close to one. It is only required that 
there is a possibility of interference for the system to work. Finally 
note that in the indistinguishable cases 2. and 3. in which inter- 
ference occured that we can not identify the route that the photon 
took. 

THE MIRROR ARRAY

At a workshop, at the Isaac Newton Institute, in November 1995, 
Richard Josza presented a paper [Josza, 1995] showing that any quantum
computation can be carried out counterfactually. The  quantum computer 
was invente by David Deutsch and described in a celebrated Royal 
Society paper [Deutsch, 1985]. It consists of a quantum device which 
is initially set in a superposition (in a similar way to the Bomb 
Tester) arranged so that when a measurement is taken, information is 
collated from computation which is counterfactually occurring in each 
of the superposed states. Deutsch thinks of it as parallel computation 
in which part of the computation is occurring in each of a number of 
parallel universes. This is known as the Many Worlds interpretation 
of Quantum Mechanics. Josza's presentation led us to consider if it 
would be possible to replace the bomb in the E-V Bomb Tester with a 
classical computer that could be "bomb tested". It was not initially 
obvious if this could be achieved with a Turing Machine but certain 
restricted classes of computation are obvious candidates. The mirror 
array described in the following below demonstrates clearly that there 
are classes of computation that can be carried out counterfactually 
in this sense. The device is a bit string classifier, which actually 
classifies certain classes of random walk.  

The computation that we will consider involves the classification of a
set of bit strings of length n^2, by associating with each an integer,
the output, with value 0 or 1. The device with which we will carry out
the classification consists of an n by n Cartesian array, in the x-y
plane, of plane mirrors mounted such that they can swivel on axes in 
the z-direction and can take angles of 45 degrees and -45 deg only to 
the grid. The spacing of the grid is an integer multiple of the wave-
length of the photons to be used. The bits in the bit strings are 
mapped to the settings of the mirrors in the obvious way, 45 deg for 
a 1 and -45 deg for a 0. The mirrors are silvered on both sides and 
the array is enclosed in a BLACK square box with sides parallel to 
the axes of the grid. An opening at the top left of the box allows 
the entry of photons in a beam parallel to the x-axis and a similar 
opening at the bottom right allows exit. 

Then a horizontally incoming photon will eventually either travel
right through the box on a kind of random walk until it leaves
through the door marked EXIT or be absorbed by the black surface of
the box. It is easy to see that the photon cannot reverse its path
and leave the device. Then for every allowable bit string and
associated set of mirror settings the computation has a one bit
output 1 if the photon leaves the device and 0 if it gets absorbed.

This is clearly a bit string classifier. It can also clearly be
bomb tested and the output obtained counterfactually. To remove
the possibility of classical usage we can connect a bomb to the
absorber in the usual way. Note that the output can only be
obtained counterfactually if it is 0 and not if it is 1. Note the
restriction on the device such that the path lengths of the two
arms must be equal, or differ by an integer number of wavelengths
of the light frequency used. This situation is easily created by
ensuring that the spacing of the mirror array is such a multiple
and that the interferometer is otherwise symmetrical. By relaxing
this restriction it would be possible to set up the device such
that it classified by path length.

A COUNTERFACTUAL TURING MACHINE

In the last section we showed that it is in principle possible 
to perform at least some classes of classical computation counter- 
factually and with today's technology. In this section we consider, 
in principle, how wide the class of counterfactual classical 
computations might be made. Consider an electron interferometer 
set up as described above. It does not matter for now what a half 
silvered electron mirror looks like, the technology is possible in 
principle. The advantage of electrons is that they are slow and 
could, in principle, be delayed long enough to allow a conventional 
computation to take place. Consider the situation when an electron 
travelling the lower path is caused to initiate the running of a 
classical computer. The electron is slowed down to allow the 
computation to continue, and then absorbed or transmitted and
accelerated according to whether the (one bit) output of the 
computerprogram is 0 or 1 respectively. The same changes in 
travelling arrangements are suffered to an electron in the other 
symmetrical path of the device. Then intuitively we have made a 
device that will bomb-test a PC. What next? A human being? The 
stock market? The UK economy?

But hold on... this speculation contradicts one of the basic laws 
of quantum mechanics which is that if you can tell which path the 
particle travelled then interference cannot occur. If a PC runs it 
gets hot; this is one of a variety of ways in which we can identify 
whether or not the electron has triggered a real computation. If 
interference cannot occur in case 2. above, in our description of 
the bomb tester, then we cannot distinguish between case 2. and case 
4. and our strategy is confounded. 

So what class of computations can we perform such that we cannot tell 
whether the computation has been physically performed or not? One 
criterion is that the computations must be reversible, that is that, 
after the computation has been performed, it must be possible to return 
the system to its initial state, or at least one that is (in principle?) 
indistinguishable from its initial state. Clearly this is true of the 
mirror array which undergoes no change during the computational process. 
It is also true of the class of quantum computers, because quantum
computation is defined by a unitary transformation. We can, if we 
wish, define this reversibility as part of the computational process 
and write

computation : input [times] registers=R --> output [times] registers=R 

where during the individual steps in the process the values in 
the registers (computer memory) can vary, but at the end of the 
computation they have to be set back to their initial values, 
and only the output bit can vary, and that is held nonclassically 
in our scheme. There are a number of ways to implement such a 
system with classical technology, eg helical logic [PHYSCOMP94, 
Dallas, Texas]. 

Another way of attacking this problem is to build the device such 
that the classical computer is always running, and that the presence 
of a photon triggers a particular input to be presented to the 
computational process, rather than starting the process itself. In 
this scheme the computation must still be logically reversible, but 
does not have to be thermodynamically reversible. It is only required 
that the thermodynamical processes be symmetrical with regard to 1's 
and 0's, ie they must consume the same amount of energy regardless 
of which state a bit is in or which way it is switching.

The interferometer and the classical computer together constitute 
a trivial (not universal!) quantum computer. By combining classical 
devices with interferometers in networks it is possible to build other 
interesting quantum machines. These will be discussed further in the 
published version of this paper.

CONCLUSIONS

In a small article in the Guardian, the week I write this paper, 
British Telecom have announced their development of a technology known 
as Quantum Encryption. This scheme allows the, in principle, secure
transmission of an encryption key between two remote people with old
fashioned names. Similar schemes allow quantum teleportation, the
ability to transmit unknown quantum superpositions down a conventional
communications channel, and dense encoding, effectively giving two 
bits for the price of one through a noisy environment. Quantum 
computing is now riding on the back of the ability of quantum 
factoring algorithms to destroy conventional encryption security (as 
well as its theoretical interest). (The idea of quantum key encryption 
was first devised by Gilles Brassard and others at PHYSCOMP92, Peter 
Shor's factoring algorithm was first announced at PHYSCOMP94, both in 
Dallas, Texas.) Kwiat at el (1996) have considered counterfactual 
measurement as a means of photographing a hazardous environment (such 
as a plasma) without disturbing it, and shown that the rate of 
counterfactual measurement cold be made arbitrarily high. Josza 
extended this idea to show that any quantum computation could be 
carried out counterfactually. In this paper we looked at restricting 
Josza's result to the classical case and show that at least some 
interesting classical computations can be carried out with todays 
technology. It is clear that, as electromagnetism drove the technology 
of the 20th century, quantum theory may well drive the technology of 
the 21st. It is strange, however, that a theory that has been around 
since the first decade of this century did not find application until 
the last decade. 

It is interesting to speculate on the form that some of these 
inventions may take. Increasing financial restriction in the UK 
academic sector has led me to wonder whether the bomb tester could 
be used to guarantee that one day a week could be reserved for 
academics for research time. In fact a Counterfactual Clocking-In 
Machine could be used to give an even greater dividend, at least 
for work restricted to computer usage. We have considered in this 
paper the idea of a human being "bomb testing" a classical computer. 
If the input to a day's work is a bit string, and the output is a 
bit string, there is no reason why this should not be carried out 
in reverse, the computer bomb-testing the human being. The bomb tester 
is set up as a "clocking-in" machine so that on arrival at work the 
lucky employee looks through a pair of lenses. If he sees a photon he 
does his day's work, if not he goes home and takes the day off, or 
catches up on his research. The bomb tester then counterfactually 
obtains the bit string the employee would have produced had he stayed 
at work for the day. In a similar way a bomb tester connected to a 
terminal in the stock market could look at the effect on the stock 
market of, say, a large investment in QM  Devices Incorporated, or 
even a change in the interest rate. The bomb tester in this case is 
not just bomb testing a human being, but the whole of the inter- 
national financial system. The fact that these systems are not
reversible does not prove that they cannot be measured counterfact- 
ually. Indeed the field is open theoretically. It would be interesting 
to have a result proving the limitation of counterfactual measurement 
to finite systems or otherwise. More serious applications may arise 
from counterfactual holography, counterfactual EPR, ar a counter- 
factual Bohm-Aharanov effect.
 
The idea that it might be possible to bomb test a human being, that 
is to find out the answer he would give to a particular question 
without ever asking him that question, led me to the conclusion that 
it might be possible to counterfactually observe the classical part 
of such a complex system as a human being, to find out what he would 
compute mechanically and methodically, but not the part associated 
with intuition, creativity and willpower, often thought to be the 
"quantum part" of thinking. 

For instance consider a PC running an algorithm that uses random 
numbers to achieve a result. It is well known that any particular set 
of pseudorandom numbers as generated by most computer languages, can
quickly have limitations when it comes to many complex applications 
such as graphics. By modifying a PC with a simple plug-in board that
generates true quantum random numbers from a device such as a noisy 
back biased diode it is possible to create a device that overcomes 
these limitations. Our first thought was that this modified PC could 
not be bomb tested. However the following argument easily shows that 
quantum noise can be measured counterfactually as readily as any other
information stream. Consider the bomb tester as described in the first
section operating on a bomb modified such that instead of it being
predetermined that the bomb is usable or a dud, the decision is made 
by the decay of a radioactive material enclosed within the bomb. If 
decay occurs within a certain period (in which there is a fifty fifty 
chance of it occuring) then the bomb will be made safe, otherwise it 
is usable. This decay can clearly be measured whilst the photon is in 
flight, before it reaches the bomb. QED. We find this a strange idea, 
that we can generate quantum noise from a series of events that never 
happened. All that is required is the existence of the source of the 
noise and the possibility (however small) that it could generate it.

Finally we mention that we are looking at the work of  Etter [1996] 
and Lewis [1996] on parts and wholes in quantum mechanics to under-
stand how to build quantum computational devices out of components 
(see also [Barenco, 1995] and [Deutsch, 1997]).  

REFERENCES

Baez, J. [1995], "This Week's Finds in Mathematical Physics (Week 
70)." World Wide Web on http://math.ucr.edu/home/baez/week70.html

Barenco, A. et al [1995], "Elementary Gates for Quantum Computation."
Submitted to Physical Review A.  

Deutsch, David [1985], "Quantum theory, the Church-Turing principle 
and the universal quantum computer." Proceedings of the Royal Society
of London, A 400, 97-117

Deutsch, D. et al [1997], "Universality in Quantum Computation." World
Wide Web. See http://eve.physics.ox.ac.uk/Articles/QC.Articles.html

Elitzer and Vaidman [1993] "Quantum-mechanical Interaction-free Measurements."
Foundations of Physics, 23, 7, 987

Etter, T. [1996], "Quantum Mechanics as a Branch of Mereology."
Proceedings of PHYSCOMP96, Boston, USA.

Josza, R. [1995], "Counterfactual Quantum Computation." Presented to 
the Workshop on New Connections between Mathematics and Computer 
Science, Isaac Newton Institute, University of Cambridge, November 
1995.

Kwiat, P. [1996a], "The Tao of Interaction-Free Measurements." World
Wide Web on http://p23.lanl.gov/Quantum/kwiat/ifm-folder/ifmtext.htm

Kwiat, P. et al [1996b], "Quantum Seeing in the Dark." Scientific
American, November 1996.

Lewis, D. [1996], Parts of Classes, Blackwell.

Spiller, T. [1996], "Quantum Information Processing: Cryptography,
Computation and Teleportation." Proceedings of the IEEE, 84(9), pp.
1719-1746.