In the previous post, we have had a first look at the connections between incompleteness, or logical independence -- roughly, the fact that for any mathematical system, there exist propositions that that system can neither prove false nor true -- and quantumness. In particular, we saw how quantum mechanics emerges if we consider a quantum system as a system only able to answer finitely many questions about its own state; i.e., as a system that contains a finite amount of information. The state of such a system can be mapped to a special, random number, an Ω-number or halting probability, which has the property that any formal system can only derive finitely many bits of its binary expansion; this is a statement of incompleteness, known as Chaitin's incompleteness theorem, equivalent to the more familiar Gödelian version.
In this post, we will exhibit this analogy between incompleteness and quantumness in a more concrete way, explicitly showcasing two remarkable results connecting both notions.
The first example is taken from the paper 'Logical Independence and Quantum Randomness' by Tomasz Paterek et al. Discussing the results obtained therein will comprise the greater part of this post.
The second example can be found in the paper 'Measurement-Based Quantum Computation and Undecidable Logic' by M. Van den Nest and H. J. Briegel; the paper is very interesting and deep, but unfortunately, somewhat more abstract, so I will content myself with just presenting the result, without attempting to explain it very much in-depth.
As we have already seen, there is a deep connection between randomness and incompleteness, brought to light mainly by the work of Gregory Chaitin. It is intuitive in a way (though of course we are exploring areas to which intuition is a far from reliable guide): as far as a formal system is concerned, the answers to questions it does not determine may be chosen at will, i.e. randomly -- somewhat more formally, if T is a formal system, and G its Gödel sentence, i.e. a sentence which T can neither prove true nor false, then both (T + G) and (T + ~G), i.e T with either G or ~G (the negation of G) added as an axiom, will be consistent systems. In the framework of algorithmic information theory, a system T can only derive the value of finitely many bits in the binary expansion of a halting probability; the remaining ones, as far as one can consider them to have a 'true' value, do have that value for 'no reason', at least as far as T is concerned. Importantly, the number of bits T can derive is related to T's Kolmogorov complexity, i.e. its information content: loosely speaking, you can't get more information out of T than it already possesses. (This prompted Chaitin to formulate his 'heuristic principle': "You can't get a 10-pound theorem from 5 pounds of axioms".)
This principle is central to the paper by Paterek et al. As axiomatic systems, they consider simple propositions about Boolean functions of a single variable -- in many ways, the most simple systems imaginable. They encode axioms and propositions into quantum states in such a way that a measurement can be regarded as a test of logical dependence -- whenever the proposition is dependent, i.e. its truth value can be deduced from the axioms, measurement yields a definite outcome; however, if the axioms do neither prove nor disprove the proposition, the outcome of the measurement is random!
I find this to be a remarkable result; however, before we discuss it in greater depth, perhaps a few words are necessary to ward of some potential confusions.
First, as Paterek et al. note, the systems they study are not subject to Gödel's theorem (in a sense, they are 'too simple' or too weak for Gödel's proof to apply); indeed, they can even be completed -- i.e. augmented with further axioms in such a way that they indeed are able to decide truth or falsity of any theorem that can be expressed in their language. But, it is important to note that Gödelian incompleteness, while unfortunately being subject to quite a bit of mysticism, is nothing special -- it is not a different kind of incompleteness, but fundamentally the same kind of thing as is present in 'ordinarily' incomplete systems, that can in principle be completed. What's interesting about it really is that it applies, by the Gödelian construction, to all systems of a certain power -- to all universal systems, where universality here means, as introduced previously, the capacity to emulate all other at most universal systems (since if a system is universal, it can 'emulate' the natural numbers, i.e. derive all theorems derivable about them, and, since the theory of natural numbers contains undecidable statements, i.e. is incomplete, it must be incomplete itself). (Which is equivalent to requiring the system to be capable of universal computation.)
One can draw an analogy to the notion of size after Cantor: the fact that the set of real numbers is bigger than the set of natural numbers is no different from the fact that a set of seven elements is bigger than a set of five elements; the surprising thing is that the notion of 'bigger' does not stop once you get to infinity -- that some infinities are bigger than others.
Both the existence of a 'biggest' set and the existence of a set of axioms capable of proving all mathematical truths are reasonable expectations -- however, both turned out to be wrong, in related ways.
One might also worry that the identification of random measurement outcomes and independent propositions is trivial -- certainly, after the fact, one can always find such an association, even in a classical setting. One can always find a mapping between measurement outcomes and truth values of propositions, simply by interpreting these propositions as being about the measurement outcomes. But this is not what's being done here. Rather, at least in principle, one can extend the scheme to experimentally test whether any given proposition is formally independent from some axioms, even without knowing the answer beforehand!
Now let's take a look at what Paterek et al. use to make this work.
Boolean Functions
A Boolean function is a function of Boolean variables, i.e. 'binary' variables that can take one of two possible values, commonly denoted as '0' and '1'. The simplest of these functions only take one argument, and return one value. It is easy to see that there can be only four such functions, each of which can be specified by two bits of data. The first function takes the argument 0 to the value 0, and the argument 1 to the value 0, as well -- we can abbreviate this as (0,1) → (0, 0). In this notation, the other three functions are (0,1) → (0, 1), (0,1) → (1, 0), (0,1) → (1, 1). Thus, to specify each of these functions, it suffices to specify its image, the second pair of values; (0,1) then uniquely picks out the second function, (1, 1) the fourth, etc. One can interpret this as each function being described by two bits of axioms, with each one bit axiom taking the form 'the argument x is taken to y'. The fourth function would be described by the following axioms:
- The argument 1 is taken to 1
- The argument 0 is taken to 1
These things might all seem rather trivial -- certainly, the axiom systems you can construct from Boolean functions of a single argument are not very interesting. But they do serve as a conceptual model, and it is often useful to analyse the simplest possible cases before moving on to more interesting things.
And some simple derivations are already possible even here -- for instance, from the axioms above, the proposition 'the function is constant' follows. Note that this proposition again does not serve to characterise the function, as it does not tell us whether the function's value is 1 or 0; it is thus a one bit proposition, and only augmented with one more bit of data (such as 'the argument 1 is taken to 0') can it serve as a replacement axiom system to characterise the function.
In order to talk about these axiom systems in a quantum mechanical setting, we need some quantum system capable of encoding their properties; such a system is found in the elementary two-level system, more familiar as a qubit.
Qubits and Qubit Observables
A qubit is a quantum system that, like a bit, can be in one of two states, written commonly as |0⟩ and |1⟩; however, unlike a bit, and unlike anything familiar from the classical world, it can also be in a superposition of these two states, |ψ⟩ = a|0⟩ + b|1⟩, where a and b are complex numbers such that |a|2 + |b|2 = 1. We will not at this point worry about what, exactly, a superposition is -- it is enough to know that performing an appropriate measurement on the qubit will find the state |0⟩ with probability |a|2, and conversely the state |1⟩ with probability |b|2.
The relation between the wave function of a quantum system and the outcome of experimental measurements is a bit of a technical one, and I will only give a brief overview here, without attempting to introduce the full Hilbert space operator formalism of quantum mechanics.
The central notion is that of an observable. In classical mechanics, an observable is a physical property of a system that can be determined by some manipulations, i.e. experiments, on the system. Observables thus may be things like the speed and position of a classical particle, or its energy, etc. In quantum mechanics, every observable is associated with a linear operator -- a mapping on Hilbert space that takes it to itself, i.e. that takes a state of a quantum system and maps it to another state --, for which an equation such as the following holds: Ô|o⟩ = o|o⟩, where Ô ('O-hat') is the operator associated to the observable O, o is the value a measurement will return, and |o⟩ is a state of the quantum mechanical system in which it can be taken to have a definite value with respect to the observable O.
So, in order to encode our axiom systems into quantum mechanics, we need operators that return dichotomic values upon measurement; for convenience, one uses the values -1 and +1 rather than 0 and 1, which does not really mean more than a change of notation. Thus, we want operators such that Ŝ|ψ±⟩ = ±1·|ψ±⟩. These can be found in the form of the three so-called Pauli matrices, σ1, σ2, σ3. In fact, together with the identity operator I, whose action on a state is essentially to leave it as it is, these can be combined to form any observable of a two-level system.
The key property of these Pauli matrices is that if a system is prepared in a state |ψ3±⟩, by which I mean a state such that a measurement corresponding to σ3 yields either +1 or -1 with certainty (called an eigenstate of σ3), i.e. σ3|ψ3±⟩ = ±|ψ3±⟩, then measurements corresponding to σ1 and σ2 yield a completely random outcome, i.e. either +1 or -1 with 50% probability. One can interpret this as being a result of the finiteness of information contained within the system: a qubit has an information content of just one bit; this bit is exhausted by giving a definite answer to the question represented by the σ3-measurement. Thus, one cannot extract any information through performing the other two measurements -- their outcomes must be maximally uninformative, i.e. random.
This can be interpreted as providing a direct link between information-theoretic incompleteness and quantum randomness -- as a formal system can't derive the values of more bits of the binary expansion of a halting probability than it has information itself, a quantum system can't give definite answers to all questions one can ask of it via measurement. This introduces the notion of complementarity into quantum mechanics: roughly, complementary observables have the property that gaining information on one observable entails a loss of information about the other. This should remind you of the well-known example of uncertainty in the measurements of position and momentum -- the better you know one, the less well-defined the other becomes.
Logical Independence and Quantum Randomness
We are now ready to take a closer look at the paper's main result. The idea is to encode a one-bit axiom -- like those exhibited above -- into a quantum state, such that subsequent measurement reveals the logical dependence of a proposition on this axiom. The procedure through which this is done is essentially to prepare the qubit in a well-defined state, then have it propagate through a 'black box' that encodes the values a given binary function yields on it through suitable transformations, and then perform a measurement equivalent to a certain proposition. As we have seen, this measurement will yield a definite answer if and only if the qubit is in an eigenstate of the corresponding Pauli matrix.
All that is left then is to establish a mapping between propositions and eigenstates, such that whenever a proposition is independent, measurement results are random. It is crucial here that this mapping is not arbitrary; indeed, the scheme can be extended to multi-qubit systems, such that one can perform experiments that correctly determine logical dependency even if it is not known beforehand whether or not a proposition can in fact be derived from a certain axiom system. In principle, it is thus possible to use quantum systems to decide the derivability of propositions within axiomatic systems.
A qualitatively new aspect emerges when one considers more complicated axioms and propositions. An n-bit proposition may be thought of as consisting of n one-bit propositions; these, individually, may be either derivable or independent from the axioms. Thus, the composite proposition can be taken to be 'partially derivable', meaning measurements corresponding to this proposition will be 'partially random' -- some outcome may be more likely than another. This could hint at an explanation for the origin of quantum probabilities.
As in the previous post, it is thus the notion of independence, of incompleteness, that introduces quantum mechanical complementarity into the physical world -- and with it, the many strange and fascinating phenomena of quantum theory.
Graphs, Logic, and Quantum Computation
The second paper I mentioned in the beginning of this post, Measurement-Based Quantum Computation and Undecidable Logic, again offers a hint at a connection between undecidability and quantum phenomena, though the connection is less clear, and the discussion more abstract. The discussion takes place within the framework of quantum computation. It is widely believed that quantum systems, utilised for computation, can outperform classical devices significantly -- even though they can't compute more than classical systems, they can in some situations do so faster.
An often-cited example is the factorisation of numbers: for any integer n, find those prime numbers that, if multiplied, are equal to n. This is an important problem in cryptography, because it is hard to solve, but its solution is easy to verify -- multiplying a few numbers takes, on a modern computer, barely any time at all. So the knowledge of the solution to a particular factorisation problem serves as a convenient ID -- you are likely to only have this knowledge if you have been told the solution beforehand, so a quick answer to the question 'What are the prime factors of n?' validates you as trustworthy.
Quantum computers have the promise (or, depending on how you look at things, pose the threat) to change this; they can quickly answer this question, without having been told the solution beforehand.
Van den Nest and Briegel, in their paper, then investigate under what conditions quantum resources may outperform classical ones. To do so, they focus their attention on a special kind of quantum state, known as a graph state. These are states that can be uniquely described by a graph that depicts their 'history', so to speak -- a n-qubit graph state is described by a graph with n vertices that encodes the correlations between the qubits, i.e. roughly which qubits have been brought into contact with one another.
In order to perform their investigation, they note that a graph can be interpreted as encoding a certain logic. Such a logic contains statements about properties of the graph, such as whether or not two vertices are connected by an edge, but also, through suitable connection and quantification, whether or not a graph can be 2-coloured (i.e. have its vertices painted alternately with only two different colours, such that no two vertices having the same colour are connected by an edge).
If all such statements (or their negation) can be derived from the logic associated to a certain graph (or more properly, a family of graphs), then the logic is said to be decidable; if conversely there exist statements that can't be derived -- that is, if they are independent --, the logic is undecidable.
Now, the remarkable result that Van den Nest and Briegel arrive at, which I will just state here, is that precisely if the logic is undecidable, i.e. contains independent propositions, it is possible for the graph state, used as a resource for quantum computation, to outperform a classical computing device -- or conversely, to be not efficiently simulatable classically. Note that this doesn't guarantee a speedup -- in fact, graph states with undecidable logics that don't perform better than classical systems are known. However, no graph state whose logic is decidable can possibly outperform classical systems. An undecidable logic thus appears to be a necessary, but not sufficient condition for a speedup. From a computational standpoint, graph states with a decidable logic are thus equivalent to classical systems.
The Takeaway
In this post, we have examined two examples of a connection between undecidability and quantum phenomena. Put succinctly, they are:
- Quantum measurements yield random results, if they correspond to propositions independent of the axioms encoded in the quantum state
- Quantum resources of a certain kind (graph states) may outperform classical ones, if the logic they are associated with contains independent propositions
Of course, this comes as no surprise: in the previous post in this series, we have already seen strong hints of the same connection. Incompleteness, the inability of a system to answer questions beyond a certain complexity, there caused the system to be only imperfectly localizable in phase space, leading to the emergence of Planck's constant h, the uncertainty principle, and with it, quantum complementarity, and ultimately, utilising the mathematical mechanism of deformation, to the emergence of the full formalism of quantum mechanics -- at least in a heuristic kind of way. The results discussed in this post then serve to bolster confidence in the considerations of the last one.
Keine Kommentare:
Kommentar veröffentlichen