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.

This document part of the archive of the mailinglist quantum-d

http://www.teleport.com/~rhett/quantum-d/posts/v2/kbowden_03-14-97.html