What is a Quantum Algorithm? (Part 2: “It” from “Qubit”)

I’ll begin this post with and addendum to the previous part of this series: originally I began this with the intent to sum up (in abstraction) how I understand the concept of quantum algorithms in a fairly practical way. This is still ultimately the goal, but as the previous post grew and my reading material diverged over time, I’ll admit before it goes any further that the rest of this narrative might take on a second, more philosophical perspective running in parallel to the original. I am ultimately fascinated by the concept of a digital, information-theoretic reality (something along the lines of what Fredkin and many other Physicists are proponents of) and may just delve a little more into the ideas and history concerning it. If nothing else I’ll try and do it in moderation!

And now, without further ado, let’s skip to the good bit.

Classical vs Quantum

In the previous post, I explored the idea that information can be considered as something physical. In fact, as before, I’d take it a step further and claim that it is the fundamental basic component of our reality. I first likened the universe to a giant computer, but now I ask you to consider that it precisely is one (for further reference see Lloyd, Zeilinger, and many others – I recommend also looking at the works of Edward Fredkin and John Wheeler – note this is not his original essay but rather a discussion based on its ideas). There is a beauty in viewing the laws of Physics as ultimately being information-theoretic (i.e. obeying rules which come down to the storage, communication and processing of information in some way). Any physical system registers information merely by existing and processes it by virtue of time and hence dynamic evolution (Lloyd). Systems interact via the language of information wherein the syntax is then understood to be the laws of Physics.

As I hinted at at the end of my last post, this would imply that Quantum Mechanics (as far as we understand it, at least) should then behave in a way that’s compatible with this worldview – i.e. it should also function via the storage, communication and processing of information. At first glance, to anyone that’s ever dabbled in QM, this seems a little outlandish. If there’s one thing that’s mysterious when it comes to the idea of QM, it’s the notion of “knowing” anything. A quantum state is essentially almost unknowable.

I’ll explain what I mean by this (hopefully in relatively simple terms) in the next bit, but for now, suffice it to say that QM is precisely all about information, as we’ll soon see. It is, in fact, the reason I personally got invested in the notion of ‘digital Physics’ as well as many others in recent decades. Thus the idea of computation, or quantum computation and therefore quantum algorithms is not a far-removed one. Ultimately, I’d argue that in the same way we see a dichotomy of ‘classical’ and ‘quantum’ Physics (else you want to add Relativity in there, which is fair but not what I’m addressing at the moment and which, if required, fits pretty neatly into the narrative too), there is a dichotomy of classical and quantum information – although ultimately we have to realise that one truly relates to the other . That is part of why information is such a powerful building block of reality.

So… Quantum Information

Look, I’m not planning to give you an introductory course on QM (and perhaps I should, but this post is more of a way for me to unleash all the pent-up philosophy I have in my blood than a detailed lecture), but I do, in brief, plan to explain what parts of QM are relevant specifically to Information Theory. This bit requires at least some previous understanding of QM or perhaps information theory (Computer Scientists and Mathematicians very welcome) but I hope that for anyone curious enough to do some background reading, this will be just as useful.

Let me start with the source of this post’s title: John Archibald Wheeler and his idea of “It from Bit” (Wheeler). Essentially, he proposed (though was not necessarily the first to do so), what we’ve been exploring thus far: that quantized information is the basis of our reality.

It from bit. Otherwise put, every it—every particle, every field of force, even the spacetime continuum itself—derives its function, its meaning, its very existence entirely—even if in some contexts indirectly—from the apparatuselicited answers to yes or no questions, binary choices, bits. It from bit symbolizes the idea that every item of the physical world has at bottom—at a very deep bottom, in most instances—an immaterial source and explanation; that what we call reality arises in the last analysis from the posing of yes-no questions and the registering of equipment-evoked responses; in short, that all things physical are information-theoretic in origin and this is a participatory universe.

You can see above that asking questions and registering answers is key to this notion of an information-theoretic world. This is precisely what we do with quantum states (say electrons, atoms and anything else that is on the scale considered small enough to exhibit ‘quantum effects’ – more on that later). The quantum state itself is a question and its measurement is a reception of the answer – “It from Qubit” (where a qubit is a unit of quantum information analogous to the bit).

To be more precise, the way we often visualise quantum states are as wavefunctions, or rather as (kind of, sort of) probability distributions of some variable – be it position, momentum, energy or some other so-called observable. These probability distributions arise from the idea that should we measure a thing (or rather, interact with it somehow by looking/touching/smelling what-have-you) – be it classical or quantum- we will get a response and that this response will come from some finite set of possible responses. Note: finite not because they are limited in any way inherently, but rather finite because our measurement device (be it a sensor or our own eyes or anything else) can only register so many bits of information, which limits the combinations of those bits that we can possibly ever learn about the thing we’re measuring at the time of measurement. This limit, however, is a hard one, since the only way information can be processed is via interaction. When I say there is no inherent limit, what I mean is if someone had a more precise measurement device, they could get more information out. The fun fact is that there does appear to be a limit on the device.

The reason we say we can never know a quantum state is because when we say quantum state we’re actually referring to the probability distributions (wavefunctions) of all these observables we could measure. Measurement only gives you a sample, a single outcome from this set of possible outcomes and it tells you nothing about the actual probability of that event – or the probabilities of other events that could have happened (i.e. it tells you nothing about the whole wavefunction). Furthermore, this information now becomes inaccessible to you, because the wavefunction (or rather, probability distribution) has now collapsed. The sample is all that exists – it is now classical information, contained in a classical-sized brain and a classical-sized measurement device and will remain as such until you somehow ‘erase’ that knowledge (by forgetting it, generally, or adding chaos and randomness to the data). Measurement is essentially information transfer (i.e. communication).

This is compatible with the idea of classical information, by the way. The uncertainty of quantum observables generally exists locally (the question why, by the way, is a good one and I personally do not have a good answer for it – nor does anyone else as far as I know). What this means is that the values we can measure only seem vary within a precision that’s small enough to be considered ‘quantum’. So when I say probability distribution, I mean events which have large probabilities in the wavefunction are so similar to each other that our large existence in the macroscopic classical world generally does not allow us the precision to see these variations. What we see when we look at the ‘deterministic’ classical world around us is an average of all the quantum values of the electrons and other tiny, quantum specs that make up the massive objects around us – including our own bodies. A book on the table, made up of impossibly many tiny quantum ‘particles’, each with some immensely tiny variation in position, will look completely stable and unmoving to the eye which cannot possibly see these particles in isolation – or their uncertainties.

There are several more interesting factors in quantum states, however, than just the idea of having them behave as probability distributions. For one, a quantum state can have something reminiscent of ‘negative’ probabilities (this way of expressing it was taken from Aaronson although I’ll admit it might not be the most precise). Like actual waves, quantum wavefunctions can interfere with each other and event probabilities can be enhanced or destroyed via this interference:

Interference of waves: constructive (left) where two wave amplitudes added together give a larger overall amplitude magnitude of the resulting wave and destructive (right) where the two amplitudes interfere to cancel out and give an overall amplitude of 0 for the resulting wave.

You can imagine the above picture as being of waves in water, but the mathematical description is the same for wavefunctions in many ways . This notion of interference can actually be exploited in quantum computing (which, I swear we’ll get to at some point). Measurement probabilities only deal with squared amplitudes of the wavefunction, so the probabilities are always positive (and, importantly, real, since the wavefunction’s amplitude is a complex number – that’s another interesting part of QM I don’t have time to explore right now).

The second concept which truly differentiates quantum from classical is something called entanglement. What it does, apparently, is to encode information by merging several quantum systems into a single entity (without going into too much detail here – more in the next post). Even more bizarrely, it appears to make space and time become pointless at the fundamental level of reality, leaving only that which is information-theoretic. In the words of Wootters:

[It is] remarkable that, even though entanglement by itself does not constitute a communication channel, the presence of entanglement allows modes of communication that are not possible without it.

What the above all implies is that QM specifically seems to make statements about information. Measurement, interference and entanglement are all merely effects of the processing, storage and transfer of information which – admittedly – behaves very particularly at the resolution of quantum mechanical objects. Interestingly, when looking at it from the perspective of information theory, there doesn’t seem to be a clash between the classical and the quantum – merely a question of averages and ensembles of events (states).

What next, then?

With the philosophical bit done, I’ll call it a day here and promise that the next post will be far more practical in nature. Importantly, the ideas of interference, entanglement and the way that quantum states seem to store distributions rather than concrete, deterministic information will all play a part in why processing information via quantum states is such a valuable ability for us. We’ll see that (assuming we build devices that are actually sensitive enough to all this strange, tiny behaviour) quantum mechanically information is far richer and more interesting when we try to manipulate it to serve our goals – although its strangeness is also a limit. We are only limited by our precision and we are lucky to have such a strange and wonderful resource in our hands, at least in solving very particular problems.

For now, Merry Christmas and adieu!

One thought on “What is a Quantum Algorithm? (Part 2: “It” from “Qubit”)

  1. I rather like the idea, I believe due to Philp Ball, of the “20 Questions” game in which the group answering the questions has not picked a subject. The first question is answered essentially randomly, but as the questions progress, each answer must allow for a subject compatible with all previous questions.

    This means it takes each answer longer and longer as the answerer has to think back and pick something that fits all previous questions. The analogy is how it takes more and more energy to drill down deeper into nature.

    But what I especially like is the notion that reality (i.e. a wavefunction) doesn’t actually define anything real until we start asking questions (making measurements). A very cool analogy!

    Liked by 1 person

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: