tag:blogger.com,1999:blog-11295132.post1319866402436769779..comments2014-04-16T10:57:46.206-07:00Comments on A Neighborhood of Infinity: The Essence of Quantum ComputingDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-11295132.post-84228458139850568362012-11-18T10:33:32.707-08:002012-11-18T10:33:32.707-08:00Really neat, thank you!
To those insisting on &qu...Really neat, thank you!<br /><br />To those insisting on "coherent superposition" as an accurate description of quantum computing, I must ask: Which supersedes, the noun or the adjective?<br /><br />Non-convexity, FTW!Kim-Ee Yeohnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-12118572717104116652012-11-18T10:33:09.271-08:002012-11-18T10:33:09.271-08:00Really neat, thank you!
To those insisting on &qu...Really neat, thank you!<br /><br />To those insisting on "coherent superposition" as an accurate description of quantum computing, I must ask: Which supersedes, the noun or the adjective?<br /><br />Non-convexity, FTW!Kim-Ee Yeohnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-56503663040502349002008-01-08T00:31:00.000-08:002008-01-08T00:31:00.000-08:00Neat post, thanksNeat post, thanksbshanksnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-48712775517598653892007-02-21T07:11:00.000-08:002007-02-21T07:11:00.000-08:00Anatoly,Suppose nature is keeps track of all of th...Anatoly,<BR/><BR/>Suppose nature is keeps track of all of the superposed states simultaneously. Now suppose we have N+1 entangled qubits in a row. You claim that nature is tracking 2^(N+1) states. If this were the case then we could get nature to store 2^N bits in N+1 qubits. Here's the scheme I propose: list your 2^N bits in a row. Label the first one 0, the next one 1 and so on. So we have 2^N pairs (i,f(i)) for i = 1,...,2^N-1. We can encode the 'i' part as N qubits in the obvious way and we can store f(i) as the (N+1)-th qubit. Write this as |i,f(i)>. Now form the state psi that is sum_i |i;f(i)>. This encodes our entire set of 2^N qubits in one state. For example, suppose we wish to store the 4 bits of data (0,1,1,1) then we could encode these as the state<BR/>|0,0;0>+|0,1;1>+|1,0;1>+|1,1;1><BR/>For example, the term |0,1,1> tells us that the 01th (in binary) element in the sequence is 1. So if you claim that nature tracks N+1 superposed states then you must also agree that nature must be using at least 2^N bits to store this state. So we have a pretty cool database here that allows 2^N bits to be stored in N+1 qubits.<BR/><BR/>But now consider how to use this database. For any i in the range 0,...,2^N-1 we expect to be able to extract f(i). Let's reduce it to the simple case: extracting f(0) from psi. We'd like f(0) to be an observable, so we need a Hermitian operator, H, for which f(0) is the eigenvalue. In other words, we want H such that H psi = f(0) psi.<BR/><BR/>Let's take the simplest case N=1. Then our state is |0;f(0)>+|1;f(1)>. We want<BR/>H(|0;0>+|1;0>) = 0<BR/>H(|0;1>+|1;0>) = |0;1>+|1;0><BR/>H(|0;0>+|1;1>) = 0<BR/>H(|0;1>+|1;1>) = |0;1>+|1;1><BR/>From the first and third line we get<BR/>H(|1;0>-|1;1>) = 0<BR/>From the second and fourth lines we get<BR/>H(|1;0>-|1;1>) = |1;0>-|1;1><BR/>So |1;0>=|1;1> which is clearly nonsense.<BR/>So there is no such Hermitian operator, f(0) isn't an observable and the database idea fails.<BR/><BR/>So either (1) nature isn't really keeping track of our 2^N superposed states or (2) nature keeps track of our 2^N states but when we make an observation it throws that information away. I don't know about you, but entities that magically disappear when you observe them give me a bad feeling. At the very least, I'd refrain from calling them 'real'.<BR/><BR/>This isn't really my original point. But it does show that a quantum computer in a superposition of N states falls a long way short of being anything like N computers running in parallel.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-15950857422376091712007-02-20T18:49:00.000-08:002007-02-20T18:49:00.000-08:00Hi Anatoly --- I'm not sure you can gain anything ...Hi Anatoly --- I'm not sure you can gain anything though thinking of the "evolution" of a pure state through time.<BR/><BR/>Whether you take your measurement after one millimeter or one meter, the interference pattern will be precisely analogous to the one as described by sigfpe's linear superposition. No extra "processing" is going on<BR/><BR/>Indeed it could well be wrong to assume that there is a background metric of time ticking away alongside pure quantum states. This is probably an example of what Jaynes would call "the Mind Projection Fallicy"<BR/><BR/>Here's a nice bombastic Jaynes quote, just to get everyone riled up :)<BR/><BR/>"A standard of logic that would be considered a psychiatric disorder in other fields, is the accepted norm in quantum theory"Alhttp://www.blogger.com/profile/06113096184512859955noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-19288082941904051652007-02-20T17:15:00.000-08:002007-02-20T17:15:00.000-08:00Can you explain what you mean further?Yes. Althoug...<I>Can you explain what you mean further?</I><BR/><BR/>Yes. Althought I spoke of states being "real" in a quantum superposition, there was less metaphysics in that then the words perhaps implied. The claim has physical rather than metaphysical content, and it is the situation of a quantum interference that shows this, especially vividly in the case of a single particle.<BR/><BR/><A HREF="http://en.wikipedia.org/wiki/Double-slit_experiment" REL="nofollow">In the double-slit experiment</A>, a narrow beam of light falls on a black surface with two very narrow vertical slits in it close to each other. After passing through the slits the light falls onto a screen parallel to the surface. On the screen there is an interference pictureL periodic bands of darker and lighter regions, rather than two separate identical lit regions<BR/>with darkness everywhere else, which is what you would expect if light behaved like a lot of very small particles (like bullets). In the classical model, the interference is explained by looking at the light as a wave that is split into two waves by the slits and those interfere with each other.<BR/><BR/>When, however, the beam of light is more and more diluted until it consists of a single photon, something happens that cannot be explained in the classical picture: if we repeatedly send in single photons and record the places they illuminate the screen, over time exactly the same interference picture emerges as in the case of a beam of light. In the classical model, a photon, being a particle, must pass through one of the slits<BR/>if it passes at all; we can set up the light emissions so that the probability of it passing through each of the slits is equal. A single particle cannot 'interfere' with itself in the classical model; if it passes through one slit, it'll strike the screen somewhere in one band; if the other - in another; if the two bands overlap, it can even contribute to the them both at the same time (but this isn't interference as understood in the classical physics model, where it is studied in terms of waves). <BR/><BR/>In reality, however, what we see is that a single photon appears to "know" about two slits simultaneously, even though, being a particle, it cannot pass through both at the same time. If we place a detector on one of the slits to tell us when photons pass by, the interference picture on the screen immediately changes to a bullet-like picture of two bands - that is, even photons that pass through the <I>other</I> slit, without the detector in it, are somehow affected by the fact that we are observing a different slit. There is simply no way to explain coherently in the classical model how a single particle, passing through one slit at a time, can build up an interference picture. The unescapable conclusion is that the theory must allow for some kind of interference of the particle with itself. That is the physical content, and the formulas give the exact numbers. The metaphysical explanations (the so-called interpretations of quantum mechanics) differ: some say there is no photon as an entity, there is only the wavefunction that evolves, interferes and then collapses when we make an observation; some say there are parallel universes in one of which the photon passed through one slit, in another through the other, and the only way those universes can interact is through interference of those "copies" of the same photon with each other. And so on. But the essential difference with the classical probabilistic model of a single particle moving around is physical, not metaphysical. <BR/><BR/>When you say that in the quantum case the formalism is the same as i n the classical probabilistic case, merely the "weightings" are complex and not just real positive, that misses the picture of how probabilities are in fact used in both models. In the classical probabilistic case, the probabilities of differnet outcomes are "distributed" at the moment of probabilistic choice, even if we don't know those distributions yet. The photon passes through one slit with probability 50% and the other with probability 50%, and at that moment the probabilities are final. Sure, we can construct our final result sets in an overlapping manner so that sometimes either possibility contributes to a particular result, and its probability is thereby increased. But that's just an example of additivity of probabilities. In the quantum case, the probabilities only 'get assigned' at the moment an observation happens - the photon strikes the screen. You are correct in saying that a complicated picture of interference is possible at that time because the amplitudes are complex and not just real positive; but not less important is the fact that the probabilities are calculated from those complex amplitudes only at the moment of observation. If the amplitudes were complex, but the probabilities were calculated at the slits, interference wouldn't happen. In fact, this is precisely what happens when we put a detector on one of the slits (that detects a photon but still lets it pass through). In the classical probabilistic case, placing a detector that tells us which slit the photon went through but otherwise leaves the photon be cannot change the picture on the screen, quite obviously. <BR/><BR/>In the double slit experiment, in the fraction of time the photon flies from the surface with the slits to the screen is time in which the photon exists in a superposition of two states: one of having passed through the first slit, the other - through the second. Because we know that the final calculation of probabilities, a.k.a. the collapse of the wavefunction, happens only at the moment of observation on the screen, we are forced to conclude that each of those states "evolves" independently and simultaneously with the other. In the two states the photon has different position and vector of movement, and each state changes according to the physical laws (here a simple movement in a straight line with the speed of light towards the screen) simultaneously with the other, at the same time also interfering with the other according to particular formulas. Another way to phrase it is to say that the universe is forced to keep track of each state's information (position and vector of movement) and process that information in parallel. In a system with N photons arranged carefully into a suitable superposition, the universe will be forced to keep track of information about an exponential number of states, simultaneously, until at some point we observe and the wavefunction collapses. By carefully guiding the states through some physical changes (that apply to them simultaneously in parallel) that affect interfernce between them in a direction suitable to us, we increase the chances of an interesting, to us, outcome when we collapse the wavefunction later by observing. Thus Shor's algorithm etc.Anatolyhttp://www.lovestwell.orgnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-62710930326927704902007-02-20T07:30:00.000-08:002007-02-20T07:30:00.000-08:00I agree that the existing quantum algorithms emplo...I agree that the existing quantum algorithms employ superposition in a clever way to enhance/decrease the amplitudes for the wanted/unwanted states respectively. For that we need probability amplitudes. However, the point is that to the extent that quantum computers will eventually be built, they will rely on these superpositions actually existing and evolving during execution. As far as I understand classical computation, such superpositions do not exist classically (with neither real nor complex number coefficients). I mean they do not exist as real physical states even though we could perhaps formally write down linear superposition of states. I guess you see this as soon as you try to run (simulate really) a probabilistic or non-determinsitic computer (or program) - in the general case you get exponential slowdown just as you get when you simulate a quantum computer classically. You simply have to go down all the paths in the computational tree (in a breadth-first search and/or using many parallell processes). Hope I have not missunderstood your post!Anders Bengtssonhttp://www.blogger.com/profile/14139508499015816145noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-30960304253286251982007-02-19T20:45:00.000-08:002007-02-19T20:45:00.000-08:00Could your entire post be summarized by the phrase...Could your entire post be summarized by the phrase, "Bells's Theorem" ? <BR/><BR/>In other words, doesn't Bell's Theorem provide the underpinning of the difference between probabilistic and quantum computing, by showing that quantum mechanics cannot be simulated by any <BR/>"hidden variable" theory ?Sureshhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-29254895809465617962007-02-19T18:40:00.000-08:002007-02-19T18:40:00.000-08:00Anatoly,Some of what you're saying is metaphysical...Anatoly,<BR/><BR/>Some of what you're saying is metaphysical speculation, especially your claim that "only one of these states is actually real". I tend to ignore metaphysical speculation and concentrate on what we can actually measure in experiments.<BR/><BR/>> You can call that state of affairs a superposition of states if you wish<BR/><BR/>I do. It seems like the same sort of thing to me, and the mathematics is very similar.<BR/><BR/>> but the fact is, only one of these states is actually real, and the non-real ones have no way of influencing the real one. No interference can happen.<BR/><BR/>Interference happens all the time in classical probabilistic systems - interference is nothing but the linear combination of vectors. I don't see why you think there's some magic whereby classical systems have one "real" state and quantum systems somehow have all states real. What's different about quantum mechanics is that the weightings in the linear combinations aren't all directed along the positive real axis. I don't see how this makes one state "real". My branching diagram was a perfectly good example of interference in a classical system. The only difference from a quantum system is that in a classical system the interference is always 'constructive' because of the positive weights.<BR/><BR/>Can you explain what you mean further?sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-2982728865431125182007-02-19T18:11:00.000-08:002007-02-19T18:11:00.000-08:00The link to the "old post" just goes to your blog....The link to the "old post" just goes to your blog.Dylannoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-91055503306801156112007-02-19T18:05:00.000-08:002007-02-19T18:05:00.000-08:00I don't see the contradiction between what you sai...I don't see the contradiction between what you said and the "usual" claims about why quantum computing's speedup works.<BR/><BR/>You are correct to put the emphasis on "we can paradoxically make something less likely by adding a new way to achieve it". But the <I>reason</I> we are able to do it, in terms of quantum mechanics, is the fact that the system exists in a superposition of states which are interfering with each other. Quantum interference is the reason that we can paradoxically etc.<BR/><BR/>The crucial difference between a probabilistic classical computer and a quantum computer is not merely the fact that in the latter the amplitudes are complex numbers. In the classical case, you know that the computer exists in some particular state, you just don't know which one it is. You can call that state of affairs a superposition of states if you wish, but the fact is, only one of these states is actually real, and the non-real ones have no way of influencing the real one. No interference can happen. In the quantum case, saying that the computer exists in a superposition of states is not merely saying that it'll be discovered to be in one of them with such and such probabilities when we look under the hood later. It means more than that: it means that all of those states are simultaneously "real"; until the wave collapses they are all "there" co-existing simultaneously in the superposition and <I>that</I> is why they can influence each other and create quantum interference.<BR/><BR/>In the classical case, "nature" needs to keep track of one state only, it's just that we don't know yet which one it is. In the quantum state, "nature" is forced to keep track of exponentially many different states at once - otherwise interference wouldn't happen. As we subject the system to various operators, all the states undergo the operations in parallel; and while we can't reach that huge freebie exponential store of information directly, we can manipulate interference into revealing some of it to us, hence Shor's algorithm etc.<BR/><BR/>So when Bennett et al. say that the power of quantum computers lies in following a superposition through a computation, they refer to a "real" superposition rather than a "formal" one in the classical probabilistic case, and the difference between them is manifested precisely in the "real" superposition's ability to create interference between its states - the "paradoxical" property that you stress. So you're saying more or less the same thing, in different words, it seems to me.Anatolyhttp://www.lovestwell.orgnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-10346684872970467242007-02-19T15:09:00.000-08:002007-02-19T15:09:00.000-08:00You might be interested in the work of Scott Aaron...You might be interested in the work of <A HREF="http://scottaaronson.com/blog" REL="nofollow">Scott Aaronsen</A>. He discusses the limitations und nature of Quantum Computing very well. Don't miss his his Quantum Computing <A HREF="http://www.scottaaronson.com/democritus/" REL="nofollow">lectures</A> <BR/>I especially like his connection of the intractibility of NP-complete problems as conjectured <A HREF="http://scottaaronson.com/talks/colloq.ppt" REL="nofollow">physical principle</A>!Harald Holtmannnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-470241716340709282007-02-19T15:04:00.000-08:002007-02-19T15:04:00.000-08:00There is no real contradiction. Bennett wrote:"......There is no real contradiction. Bennett wrote:<BR/><BR/>"... follow a <I>coherent</I> superposition of computation paths."<BR/><BR/>Coherence means phase correct superposition, or: |a + b|^2.<BR/><BR/>Probability superposition is superposition of the absolute square of the wave functions: |a|^2 + |b|^2. <BR/><BR/>Quantum computing of course only works with the first kind of superposition. This is well known and of course also known by Bennet et. al.Karsten Wagnerhttp://www.blogger.com/profile/09652404623625038743noreply@blogger.com