The quantum theory of knowledge and computation

0:00 Thank you for your attention. Just before I announce today's speaker, I just want to mention that next week, Dr. Julian Barber We'll be speaking, the title of this talk will be Trying to Make Sense of Quantum Gravity. Today we're delighted and fortunate to have Dr. Deutsch of the Mathematical Institute with us. Dr. Deutsch started to work in theoretical physics in the area of astrophysics and has become, in recent years, very interested in foundational issues and in particular in becoming a very articulate, sophisticated defender of the many worlds of interpretation. A version of the universal computation of quantum mechanics as a universal theory. And also, one input being black holes. Dr. Deutsch has started to work intensively on quantum theory of computation. He's a pioneer in this field. And today he's speaking to us on the quantum theory of computational knowledge. The things I've been working on most recently is an easier version of the quantum theory of computation.

2:30 Since it's rather a self-contained way of approaching the theory, I may as well just describe that by way of the introduction of the whole theory of quantum theory of computation. Just as a quick, in a nutshell, the quantum theory of computation is a generalization of the theory of universal computation, Turing's theory, which we must now regard as the classical theory of computation. Because although it is originally pure mathematical theory, in fact if we examine it closely we see that it makes assumptions about the physics of the underlying hardware which are not necessarily real and it turns out that when we allow the underlying hardware to possess properties that belong to the quantum mechanics proper. My new way of looking at this is via quantum computational networks and quantum computational networks are the quantum generalization of logic networks which themselves are really a reflection or physicalization. Let's start by considering the theory of computation for just one bit, that is, an object that has states, say, up and down, as we say in physics, or two distinguishable states, 1 and 0.

5:00 Then it has exactly two states, and that's not true of quantum theory, but quantum theory is true of the unit combination vector, vector 1, you know, the vector of the unit, but also all states, all vectors of the time, alpha, omega, black, are also possible states of the system. So, this quantum two-state system already has a continuum of possible states. This in itself doesn't add any generality of string theory to quantum physics, because although this system has multiple possible states, as I've said, at most two of them, any two quantum vectors, at most two of them are distinguishable. So, for instance, we want to send messages. Using this system, we could send at most one bit of information in one bit, putting it either as one or as two, or else it's one of the states, or alternatively in a quantum sphere. And the fact that we've had an infinity of possible states, so it's allowed to send more than one bit of information in one bit. But the general answer comes when we think of what we can do to this field. These are alternative statements, and these are alternative statements, not the same statements.

7:30 In the classical theory of computation, the theory of computation for one bit is very, very simple. There are only four possible computations, using only the information. They are, that you set the bit to zero, regardless of what it is, that you set it to one, regardless of what it is. The interchange 0 and 1, that is, if it was 0 and you set it to 1, then that's less than 1, or the units alone or together. Those are the four possible computations, and they represent it. So there are four possible computations. Two out of these four are reversible computations, that is, the function that is represented by the computations and the relative function. Those are the two reversible computations. It turns out that the theory of reversible computations is sufficient to describe all classical computations. Both classical theory and quantum theory, the theory of computation for one bit does not provide the fully general theory of computation. I'll come to that in a minute. But in the, what we consider general reversal, we are considering the general theory of computations simply by ignoring some, not by setting some input bits to be expanded. In the quantum theory, the situation is much more complicated, and the theory of computation for one bit is already very interesting and rich. It doesn't contain the full bit of it.

10:00 But it does contain quite a lot. It does contain a large number of the features that make quantum theory and quantum mathematics. The physical transformations that we perform on the quantum state are represented in general by a super scattering matrix. Or, if we restrict ourselves again to a reversible matrix, which again are sufficient, then it's represented by an S matrix or unitary evolution matrix. That has the probability that the input to the conversation is some state, state vector or something, and the output is S or something, but S is the unitary condition. The requirement that S be unitary is a very weak condition in terms of the condition that we have on possible transformations of mathematics. And here is an example where S represents, and through this representation, we represent the state of one. Now, if we have a quantum computer whose effect on one bit was represented by the matrix X, then the input state was this one point, then the output state, which in the previous notation, in the Everett or Ringwell's interpretation, is the state in which the universe, the set of all universes, differentiated themselves into two branches, in some of which...

12:30 However, they continue to behave as a unified whole, which is the reason why it's worth speaking about the acceptability of physics. Well, I said at the beginning that logic networks are just like probability parameters, Here we have, similarly connected in one argument, it doesn't have a class timeline, it is in fact a root or power of the not of two. And this operation on one bit is just the same as the not operation. And in fact, the classical computations are precisely the ones for which algebra is a molecule, not a two. The S-matrices whose entries are all consistent entirely of zeros and ones, which are known as the permutations, those S-matrices are precisely the classical reversible computations, whereas the more general S-matrices, the ones with general complex entries, limited only by the fact that they don't have classifications, I said this was a powerful route to perform this again.

15:00 If you perform this operation and then perform it again, then the result is as if you had performed the same operation but with alpha replaced by 200% or plus 200% and so, if you took, for instance, alpha as a prime of 4, you have a negative, which is the square root of 0, that is, it is entirely equivalent to negating the bigotry. But if you perform it once, then all of the kinds of applications will correspond to this. Now, more generally, we can invent the quantum analogues of general logic gates operating on more than one bit. Again, if they're reversible gates, the number of input bits has to be equal to the number of output bits. So in general, quantum or logic gates can be represented by diagrams or something like this with a certain number of input bits. Classically, if there are any implements, then there are 2 to the n possible implements, and therefore there are 2 to the n factorial possible gates, or possible reversible logic gates. Quantum gates is the number of S matrices in 2 to the n by 2 to the n dimensions.

17:30 We can get a more geometrical picture of what the classical logic gates and the quantum gates are doing by thinking of the spaces of states on which they operate. If you imagine this, as I've said, eight possible input states, zero or one, we can represent these states as the Burtzian cube. If there were n inputs, then this would be an n-measure type of cube. And the gates, the classical reversible logic gates, represent the correspondence with the permutations of the vertices of this cube, or, if you like, the mappings of the cube onto itself. We have the possibility of mappings that do not take the vertices, and in fact, the transformations can't even be represented in a three-dimensional practice. The possible transformations are the unitary, or if one thinks it's unitary, the orthogonal transformations of this basis, not necessarily into itself, corresponding to the mappings of this basis. This is a very hand-waving way of seeing why

20:00 The quantum theory of computation, or quantum computers, might be more powerful in some complexity theory sense than a classical computer because if we have a computational form, a classical computational sort of argument, what we really want to do is to ensure that each one of these states is mapped to an appropriate estimation of the state for the quantum computation. So, if we start with a state that's one of these basis states, then in a classical computation we'll end up with one. But also in a classical computation, at each step, at the end of each computational step, the state will be one of these basis states. But with quantum logic, the possibilities open to us are enormously large and can allow the intermediate state to be linear superpositions of basis states. That is, they can be states that cannot be represented by a simple assignment of 0s and 1s to the bits. So we can take shortcuts across this space in constructing a transformation that will map the basis into itself. And in general, it can be shown that there exist computations, but these shortcuts involve exponentially fewer steps than we need. Achieving the gravitational dynamics of mathematics on the basis of itself. Nothing is ever true in pure physics. It is true in everything. Well, now, there's the question of universality. Let me start with connectives.

22:30 A universal connective, logic, a connective from which it is possible to construct all possible propositional formulas. I should say that the whole drive of what I'm doing here is to bring the theory of computation within physics. So whenever I see a word like construct and computation and bits and so on, I always have to think of what physical process is. What we mean by construct is if we have propositional variables, a computation corresponds, well, some computations correspond to So this is an irreversible computation and a connective is said to be universal if you can describe the operation of any possible gate using only that, using variables and only that connective. What do you mean by using that connective? But we're allowed repeated use of a propositional variable, and we're also allowed function-compositing notation. Well, repeated use of a propositional variable in terms of k is like this. And function-composition corresponds to keeping the calculus of 1, 2, 3, 4, 5, 6, 7, 8, 9, for which we need connectors or union wires.

25:00 For that reason, what is called the universal connective, the gate that corresponds to a universal connective, for example, is not actually a universal gate. The simplest universal gate, I believe, is that, but that's irreversible. And for physical reasons, I'm interested in pursuing the entire theory via reversible gates. Universal date was invented, it's described by Toffoli as recently as 78, there's three inputs, three outputs, actually there are many, in an integral notation in which a and b can be one or zero, but it's only true of course, so the multiplication is the same as that, and this plus with the ring around it is exclusively for addition and multiplication. This is the... The obvious question to ask is, is there a universal quantum gate, it's an S matrix, it is also a three input, three output reversal gate, and it is therefore represented by an eight by eight S matrix.

27:30 Perhaps I should write here, the S-matrix of the Defoli gate is much simpler than the S-matrix of the Defoli gate. For most input states, it just leaves them unchanged, and for two of them, it can be any two, it just interchanges them. S-matrix of the Defoli gate. Now this is one version of NOT, which appears to take alpha, the power of NOT. It also turns out that having constructed rather laboriously the universal quantum gate, it also turns out that almost all gates are universal, although it's hard to arrive at a specific one which has a finer sense of it. So this actually bodes rather well for the possibility of constructing quantum gates. All previous constructions have involved enormously large state spaces and tailoring of the Hamiltonian persistence very finely in a way that is not realized by any spectrum of imagination.

30:00 Whereas constructing machines via gates, which is the way we do it in real life with classical computers too, there one would only have to find a way of manufacturing one specific state. I thought the right hand thing was the universal gate and the left hand thing would be a negative of the total gate, which is the universal gate. Yes, this is the universe of classical calculations and this is the universe of general concepts. And do you really think it's plausible that one could construct a physical system which had some theoretical property corresponding to a rational number, not just a number? Oh yes, and the hard thing would be, if it required it to be rationally specific, then it would be rational. But after all, all those two numbers are irrational. And if it weren't, if it were rational, but we put very large numbers as the numerator, then we would find that what that means is... If the gate would not be universal, there would be some very complex computations that it wouldn't be called, if that number got large enough. When you said that almost all gates are universal, what do you mean by almost all? Well, if we take general S matrices, let's say 8x8 S matrices. You can define a topology from the space of all such objects, let's say using a distance function. Any natural topology, almost all points in space are gates, representing universal gates.

32:30 The way we prove that is to show that there exists a quantum computational network that can construct the universal quantum games that I've shown here out of an arbitrary game. But it might be a very, very complex network. So it certainly isn't the last world as far as dreaming goes. You can't just take any... Another thing is, to manufacture machines, you have to make sure that they're all manufactured identically, or with known values about them. Anyway, that was supposed to be an introduction. So much of an introduction. But what was the time for? Quantum theory of knowledge and computation. And that should immediately make you think, I don't know what I'm talking about. Knowledge and computation are things that shouldn't have any more than politics or philosophy. Knowledge and computation are both configurational properties, that is, they are properties of the state, not of the dynamics of the family. Therefore, there is a strong sense in which they must be independent theory of these things. Must be independent of the underlying hardware that forms them. Of course, they must be performed by hardware, just as politics and philosophy are, but you don't expect to have to know what a philosopher is made of before you can criticise or understand what he's talking about, or before you can understand what philosophy is. And what's more, in the case of computation, which is the one example whose theory worked out in great detail.

35:00 There is a developed theory of computation which precisely has the property that the theory is totally independent of the underlying cardinal. There is, and I'm going to say, that in spite of appearances, there are theory of computation and the theory of knowledge are branches of physics and do depend on it. It does not exist. It can't be expressed as an abstract mathematical theory, except in the way that any physical theory can be expressed in that way. One has to know what is doing the computing. And here I'll just describe some of the ways in which physics gets mixed into the field of computation. In quantum theory, which do not occur in mathematics, there are three legs of theory. If there's a computer fluid which says what, then there's a complexity field which says with what resources. And resources usually means, in the classical context, time and memory.

37:30 Both of those are physical things, but they can be abstracted to refer only to entities that refer to the model. Time means the number of computation steps. Memory capacity means the number of bits of the model. Just to anticipate a little bit, we really should add new ways of physical things. By the way, the tongue is important. And then the third layer is, where is error correction? Now in a classical theory, this is not on the same footing, because in a classical theory it's possible to set up idealized models in which error correction is more necessary. This isn't the case in quantum theory. Error correction is what we call it for engineers or computer engineers. Other engineers and physicists call this the same thing. Stability. Theoretical things are well posed for us. This is the theory of computation, well posed. Well, the connections in the classical theory, these things are all separate. It is possible to construct, and this is in fact historically happening, a theory of computability without ever... Considering any complexity theoretically, it's a very simple tool. We just divide the functions into computable functions and non-computable functions and we never have to work out how long it takes us to do it.

40:00 We can also work out the complexity theory using, again, a physics-independent model of computation, inextricably. I'll start with this connection. Why is it necessary to consider error collection? To find out what is computed by a quantum computer, we have to have a full theory of error correction for the proposed hardware. Well, I can illustrate why this is from the simple theory of one bit that I introduced. And let us suppose that we are allowed, we have an unlimited supply of these, and we want really to perform the computation of not, which is a rather perverse way of performing the not, but let's suppose that we have just a supply of these gates.

42:30 Well, all we can do with these gates to construct a network, since they only have one input and one output, we want to, well essentially all we can do with them. Apart from making disconnected machines, we can connect them together in series, like this, and our only choice is how many of them can connect together. But, actually, within the repertoire of computations that we can perform in this way, we can get arbitrarily close to not alpha here in the irrational. Two of these gates connected together are equivalent to a gate that is S-matrix to alpha. Three of them are three alphas and so on. So we can get any n-alpha connected to these gates for series and since these are trigonometric functions, n-alpha must be interpreted modulo 2 pi and the integer multiples of an irrational number get arbitrarily close to any number, to any real number, including multiples of pi, so by connecting sufficiently many of these things together we can... Now, so we can't actually perform the not-computation using these games, but we can get arbitrarily close to doing so. And arbitrarily close, as far as physics goes, is as close as we can ever do anything. When we say that something is measurable, we mean that it's measurable with an arbitrary high accuracy, that is given in other sources, and a given level of accuracy to measure it to that level of accuracy.

45:00 Oh, I should say that this property that you can get arbitrarily close to computing something, generic computations happen to be singled out as the ones you can perform exactly, are model dependent and dependable day after day. But the completion of those, that is the set of all these computations with arbitrary accuracy, is not model dependent. So therefore it's not useful to adopt the same strict notion of computability. As we do in the classical theory, that is, we say that gates are adequate if we can construct them into a network that actually computes that function. Instead, we have to say that a particular set of gates is adequate to compute a certain function if, for any epsilon, there exists a network constructed entirely out of the given gates that can perform that computation with probability to produce a state that is within epsilon. The probability of detecting experimentally that the actual outcome is not the desired one is less than or equal to epsilon. So therefore both the physical reasons and the technical reasons, it's undesirable to classify functions as being not exactly the same. In this case of the single bit,