**Authors**
Jonathan A. Poritz

**License**
CC-BY-SA-4.0

Algebraic Turing Machines with Applications to Quantum Computation Jonathan A. Poritz jonathan.poritz@gmail.com www.poritz.net/jonathan Department of Mathematics & Physics Colorado State University, Pueblo 2200 Bonforte Blvd. Pueblo, CO 81001-4901 University of Colorado, Colorado Springs Rings & Wings Seminar 15 November 2017 This work is released under a Creative Commons Attribution-ShareAlike 4.0 International License Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 1 / 35 The Entscheidungsproblem [=“decision problem”] David Hilbert, 1928: Does there exist an algorithm which on input of a statement in first order logic outputs Yes if the statement is universally valid and No otherwise? But, what is this “algorithm?” Alonzo Church, 1936: Algorithms are defined using “the λ-calculus.” And, Herr Doktor Professor Hilbert: Nope. Alan Turing [Church’s Ph.D. student!], 1936: Algorithms are defined using “Turing machines.” And, Herr Doktor Professor Hilbert: Nope. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 2 / 35 Turing Machines: Formally, Set-up A Turing machine [TM] consists of two sets and a map: • a finite set Σ (the alphabet of symbols to be written on the tape); • a finite set S (of states of the control device), which has two special elements START , HALT ∈ S (in which the state machine starts, and which indicates the algorithm is finished); and • a map T : S × Σ → S × Σ × {−1, +1} (the state machine transition function). [It suffices to work with the alphabet Σ = {0, 1}, and we shall always do so.] A tape is a map τ : Z → Σ (think of it as an infinite tape written with symbols from Σ); denote the set of such tapes as TΣ . Given a TM {Σ, S, T } and some tape τ (the input tape), we set • the current state s ∈ S to be s = START , and • the read/write head location j ∈ Z to be j = 0. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 3 / 35 Turing Machines: Formally, Processing Repeat the following steps until s = HALT : • say T (s, τ (j)) = (s 0 , σ, m): • then change the current state to the new value s 0 and • change the tape to a new one τ 0 given by 0 τ (i) if i 6= j τ (i) = σ if i = j and • change the head location to the new value j + m. Whatever is the value of the tape when [actually, if ] the TM halts is the output tape. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 4 / 35 Turing Machines: The Picture Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 5 / 35 Turing Machines: Universality A Universal Turing Machine [UTM] is a TM U and two maps • an encoding map e which takes as input any TM M and any tape τ and produces a new tape e(M, τ ) ∈ TΣ and • a decoding map d : TΣ → TΣ such that • for any TM M and input tape τ • M halts on input τ with output τ 0 if and only if • U halts on input e(M, τ ) with an output tape τ 00 satisfying τ 0 = d(τ 00 ). Turing: UTMs exist! Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 6 / 35 Turing Machines: Use in Complexity Theory TMs are very good at describing the cost of computation: • How much of the tape is used during a computation – i.e., the largest value of the current head location j – is a measure of the space complexity of the computation. • How many steps the read/write had to take – i.e., how many times through the main loop of the “repeat the following...” above – is a measure of the time complexity of the computation. If we have a computational problem which can have instances of different sizes and there is some bound on the time complexity of a TM which solves that problem then we would say the problem is solvable with that bound. We often talk about polynomial-time problems, and the set P of such. E.g., Multiplying integers is in P, but it is not know if factoring is. The gap between these two is what makes most of public-key crypto work! Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 7 / 35 Turing Machines: Now With Randomness We want to talk about TMs with access to randomness, formalized by • replacing the above deterministic description with one where the steps in the main loop are thought of as drawing according to specified probability distributions; or • giving a deterministic TM access to a second tape full of random bits, and drawing conclusions about distributions of results based on the distributions of the input randomness. We shall not go into the details for these randomized TMs. Strangely, randomness seems to make TMs more powerful! [Below, we shall see a hint of why that might be the case.] For this reason, one usually considers that all actors in a cryptographic protocol have access to probabilistic, polynomial-time TMs, [PPTMs]. Most public-key crypto today is based on the fact that there are PPTMs for multiplication but none is known for factoring. Hence multiplication is a good candidate for a cryptographic one-way function. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 8 / 35 Circuits: Starting with Turing Machines TMs, while good for the Entscheidungsproblem and complexity theory, are not so practical to build in the real world. We would rather make circuits. So imagine: Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 9 / 35 Circuits: Boolean Basics These are similar to [OK, “vaguely reminis- cent of”] Boolean circuits, i.e., things that look like: Boolean circuits are built out of wires which carry either a 0 or 1 [like the cells on a TM tape, stretched out in time!], the logic gates NOT, AND, and OR and, implicitly, the utility gates FANOUT and SWAP. There is a kind of universality for Boolean circuits: while we thought, from simple logic, that we needed all of the logic gates, it turns out instead that NAND [=NOT◦AND] is universal in the sense that, given any Boolean circuit, you can build an equivalent circuit which only uses the logic gate NAND. Sometimes it is convenient to add extra wires which do not carry parts of the input data but are instead pre-loaded always with 0s, and whose values at the end are not counted as part of the output. These are called ancilla. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 10 / 35 Circuits: We Want More Algebra! Let’s make our circuit diagrams look more like the streched-out-TM picture from before. And with More Algebra™ . All wires will go straight across our entire diagram and never simply appear or disappear. The wires will be viewed as carrying a vector in some fixed vector space over a field k – we will usually use k = C, but leave open the possibility that could change – with basis |0i and |1i. [yes, weird notation: blame Dirac!] Vectors in C|0i ⊕ C|1i are called qubits. [for reasons which shall emerge eventually] Here is a “one-qubit gate” to do the basic logic operation NOT: Actually, this NOT usualy gets the special notation Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 11 / 35 Circuits: Controlled Gates, CNOT Often we use the idea of a controlled gate, which passes through some of the qubites without change and modifies others if the control lines are all 1s. For example, the controlled-not or CNOT is the gate [that “⊕” is XOR to computer scientists and addition mod 2 to mathmeaticians] with special notation , where 1 0 0 0 0 1 0 0 CNOT = 0 . 0 0 1 0 0 1 0 Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 12 / 35 Circuits: Controlled Gates, TOFFOLI There is a famous doubly controlled gate, called TOFFOLI with matrix, corresponding special notation, and logical action: 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 Note that TOFFOLI is invertible, so by using it (and NOT or CNOT, which are also invertible), we are doing reversible computation. There are reasons, the physicists tell us, that that is a very good thing to do. TOFFOLI can be used with ancilla to do all of the other logical gates, so it is, in yet another sense, universal for reversible computation. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 13 / 35 Circuits: Digression 1, Universality of TOFFOLI This is fun to work out. Here is one of the more surprising ones, FANOUT: Exercise: Figure out how to use TOFFOLI to do AND, OR, etc. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 14 / 35 Circuits: Where Do Those Vectors Live? and Input A vertical (time) slice of a circuit diagram should have a particular qubit vector on each “wire,” but one may ask: where does the whole thing live? Probably, it seems natural to put the separate vectors together in the direct sum (Cartesian product). But, instead, we shall use the tensor prodcut. The state vector for any time slice of our diagram will thus live n in C2 if we are working with n wires, the n-qubit space. We shall call the basis |0i = |0 . . . 0i = |0i ⊗ · · · ⊗ |0i |1i = |0 . . . 1i = |0i ⊗ · · · ⊗ |1i .. . |2n − 1i = |1 . . . 1i = |1i ⊗ · · · ⊗ |1i the computational basis, and we use it to set up our input of n binary digits. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 15 / 35 Circuits: Where Do Those Vectors Live? and Output Now, assume that the n-qubit vector at the output side of a vector is a n unit vector in C2 , so it can be written as n −1 2X aj |ji, j=0 where each aj ∈ C and n −1 2X |aj | = 1 . j=0 Then we shall say that our circuit yields the n-bit output string which is the binary expression of the number k with probability |ak |, and the above constraint on coefficients implies this is a well-defined probability distribution on the set of 2n possible n-bit strings. This whole process is called measurement with respect to the computational basis. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 16 / 35 Circuits: No Probability [Yet] Note that the gates we have seen are all permutation matrices. Inputs, as we have done them, always make us start with a basis vector. Therefore, computation built out of the these gates will always yield a basis vector at the end of the computation. This corresponds to an output distribution which gives one bit string with probability 1 – so it is deterministic. In a certain sense, we are saying that the structure group of classical (reversible ... but, with ancilla and fan-out that doesn’t change things much) computation is the permutation group S2n . The circuits we have described are ways of building all of the elements of S2n by products of matrices which are tensors of some size identity on the left and the right and one of a small set of convenient gates/permutation matrices. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 17 / 35 Circuits: Unitary Universalist The structure group of the real world is the unitary group – because of quantum mechanics. So it would make sense to imagine special gates that we like to build (analoguously to the special permutation matrices we looked at above) which are now unitary matrices. Then since products and tensor products of unitary matrices are unitary, the entire computation done by a circuit will be a matrix in U(2n ). The way we built inputs, our circuits always start with unit vectors. Therefore, our final output vector will also be a unit vector, and we can do measurement with respect to the computational basis. The computation will be probabilistic, however. We also must imagine that our laboratories can only produce a finite number of specific basic gates. Therefore there is no way the products and tensor products with identities will yield all of U(2n ). Instead, in this context, we say that a set of basic gates of universal for quantum computation if it generates a dense subset of U(2n ). Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 18 / 35 Circuits: BvN Machines Actually, we haven’t used inverses anywhere. So we could explore in a different direction which doesn’t go from permutation matrices to unitary matrices, but instead goes to doubly stochastic matrices. Recall that, by 2 the Birkhoff-von Neumann Theorem, the convext hull in Rn of the set of permutation matrices is the set of doubly stochastic matrices. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 19 / 35 Circuits: Digression 2, Physics – Landauer’s Principle Rolf Landauer (IBM) 1961 says, version by Charlie Bennett (IBM): Any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non- information bearing degrees of freedom of the information pro- cessing apparatus or its environment. Hence the minimum amount of enegergy to change (erase, etc.) one bit is kT ln 2 , where k is Boltzmann’s constant and T is the temperature. Moving around bits without erasure can (in theory) be done with zero energy cost. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 20 / 35 Circuits: Digression 2, Physics – Moore’s Law 1 Described by Gordon Moore, on of Intel’s co-founders, in 1965. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 21 / 35 Circuits: Digression 2, Physics – Nanoscale Problems A Nanometer is a billionth of a meter, 10−9 m. How small is that? * A human red blood cell is about 7000nm. * An Ebola virus is about 1500nm long and 50nm wide. * In a silicon wafer, silicon atoms line up about one every half nm. * Hydrogen atoms are usually said to have a diameter of about an angstrom. [1Å = 1/10nm = 10−10 m.] Feature sizes of integrated circuits this millennium are described as 130nm, 90nm, 65nm, 45nm, 32nm, and 22nm, the current best. Current best means the gate length [basically, how wide is the wire] is around 20nm, e.g., for a NAND gate. But, at around those sizes, dopants don’t dope, insulators don’t insulate, conductors have significant resistance and inductance.... [Numbers on this page may be off by a factor of two or so.] Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 22 / 35 Circuits: Digression 2, Physics – Moore’s Law 2 Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 23 / 35 Quantum Mechanics: Postulate I Postulate I: the State Space The state of an isolated quantum system is described by a unit vector (these are written |φi) in a Hilbert space, the state space of that system. Hilbert spaces are complete, complex vector spaces. The linear structure [adding vectors] is odd: in classical mechanics, state spaces are curved spaces (usually the cotangent bundles of some space of configurations). The complex structure – that vectors can be multiplied by complex numbers √ a + bi – is odd: how should it make sense to multiply by −1 in a real physical system. In applications, the Hilbert spaces are often infinite-dimensional (and required to be separable), such as the L2 -completions of spaces of (twice-differentiable) functions, representing the “probability density of a particle.” Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 24 / 35 A Nice State Space Take a two-state quantum system, such as a single photon, which can be vertically polarized or horizontally polarized a single electron, which can be spin up or spin down an ion suspended in an electromagnatic field, cooled to near absolute zero, which we try to keep in one of its two lowest energy states a cat in a box, about which some maniac (Erwin Schrödinger) only cares whether it is alive or dead and call the states |0i and |1i. The state space is then the one-qubit space H = C2 = C|0i ⊕ C|1i and state vectors will be α|0i + β|1i where α, β ∈ C satisfy |α|2 + |β|2 = 1. A gruesome example is √1 |alivei + √1 |deadi for Schrödinger’s cat. 2 2 Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 25 / 35 Quantum Mechanics: Postulate II Postulate II: Unitary Time Evolution The time evolution of an isolated system is given by a unitary operator acting on the state vectors, |φi 7→ U(|φi) The unitary operator is determined by the specific physics of the situation. E.g, sometimes one figures out the Hamiltonian H of the system (a Hermitian operator) and time evolution is the unitary operator U = e itH . Or, in the case of a 1-qubit system, we might look for physical processes which can act as some desired 2 × 2 unitary matrix, such as 0 1 0 −i 1 0 1 1 1 X = ,Y = ,Z = ,H = √ ; 1 0 i 0 0 −1 2 1 −1 X , Y , and Z are the Pauli matrices and H is the Hadamard gate Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 26 / 35 Quantum Mechanics: Postulate III Postulate III: Measurement Measurements correspond to a family of operators {Mm } where if the system is in state |φi before D the measurement, E the probability of seeing † the value m is p(m) = φ | Mm Mm | φ , and if m is the observed value, p then the system is left in state Mm (|φi)/ p(m). For us, it suffices to make measurements in the computational basis, which means we are in the 1-qubit space H with operators M0 = |0ih0| and M1 = |1ih1|; measurement of the state α|0i + β|1i yields 0 with probability |α|2 and 1 with probability |β|2 , leaving the system in state α β |α| |0i or |β| |1i, respectively. This is the most mysterious of all: states transform in a non-unitary way when observed, so observation is apparently not time evolution of a physical system! Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 27 / 35 Quantum Mechanics: Postulate IV Postulate IV: Combining Systems When two systems are allowed to interact, the combined state space is the tensor product of the separate state spaces. Let n 1-qubit systems interact gives the n-qubit state space H⊗n , which is a complex vector space of dimension 2n with basis |0i = |00 · · · 00i = |0i ⊗ · · · ⊗ |0i ⊗ |0i |1i = |00 · · · 01i = |0i ⊗ · · · ⊗ |0i ⊗ |1i |2i = |00 · · · 10i = |0i ⊗ · · · ⊗ |1i ⊗ |0i .. .. .. . . . |2n − 1i = |1 . . . 1i = |1i ⊗ · · · ⊗ |1i ⊗ |1i For example, there are entangled states, such as the Bell states Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 28 / 35 Quantum Mechanics: All Together Now Postulate I: the State Space The state of an isolated quantum system is described by a unit vector (these are written |φi) in a Hilbert space, the state space of that system. Postulate II: Unitary Time Evolution The time evolution of an isolated system is given by a unitary operator acting on the state vectors, |φi 7→ U(|φi) Postulate III: Measurement Measurements correspond to a family of operators {Mm } where if the system is in state |φi before D the measurement, E the probability of seeing † the value m is p(m) = φ | Mm Mm | φ , and if m is the observed value, p then the system is left in state Mm (|φi)/ p(m). Postulate IV: Combining Systems When two systems are allowed to interact, the combined state space is the tensor product of the separate state spaces. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 29 / 35 Quantum Circuits Just like regular circuits, only more linear algebra: put 2n × 2n unitary matrices in the boxes of a reversible circuit diagram. The ends of some wires can be measured in the computational basis. Universality here means building (exactly or approximately) any gate on n qubits out of combinations of a fixed set of gates on a fixed (small) number of qubits. Several collections are universal, such as U(2) ∪ {CNOT }. There are also qudits, based on d-state quantum systems. Quantum algorithms exists which, e.g.: √ search unsorted databases in O( n) time [Grover], and factor integers in polynomial time [Shor]. Resistance Is Futile: Quantum Computers Are Coming. [So we should now be training the next generation of quantum computer scientists.] Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 30 / 35 Example Quantum Algorithms: Deutsch-Jozsa Problem: given a function f : {0, 1}n → {0, 1} which is either constant or balanced [#(f −1 (0)) = #(f −1 (1))], determine which it is. Use a quantum oracle for U, the quantum gate Uf (|xi ⊗ |y i) = |xi ⊗ |y ⊕ f (x)i Then do: Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 31 / 35 Vary the Structure Group! Because it’s cheaper than inter-dimensional travel The structure group of our universe seems to be U(n). The structure group of the universe of classical computation is Sn . What about other groups [universes]? Circuits built on a family of groups and representations work with diagrams like quantum (or classical reversible) circuits, but the wires have values in a fixed vector space V and the boxes are in some chosen groups, which act on appropriate tensor powers of V via some family of representations Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 32 / 35 So What? Part 1 Well, how about BvN Machines? Why only a group? How about a semigroup? Use the Birkhoff Polytope Bn ! 2 The Birkhoff-von Neumann Theorem: Bn is the convex hull in Rn of the permutation matrices. 1/2 1/2 Includes things like RAND1/2 = . Use the output of such a 1/2 1/2 gate to control another operation ... BvN machines compute the same things as classical probabilistic Turing machines Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 33 / 35 So What? Part B My conjecture, which is mine: only groups and representations which have some negative matrix coefficients admit quantum-type exponential speed-up over classical algorithms. Other types of groups: 1 what about infinite dimensional groups? 2 issues of universality to do with generating interesting groups by a finite number of generators 3 find some intermediate group between S n and U(n) which allows quantum-fast algorithms; in fact, O(3) does fine. ... so find a physical system which can implement O(3) computing. Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 34 / 35 References A great book on qunatum computation: Quantum Computation and Quantum Information, Michael A. Nielsen and Isaac L. Chuang, MIT Press, 10th Anv ed. (2011) Details of varying the structure group: Universal Gates in Other Universes, Jonathan A. Poritz, appeared in G.W. Dueck and D.M. Miller (Eds.): RC 2013, LNCS 7948, pp. 155-167; Springer-Verlag Berlin Heidelberg 2013 (also on poritz.net/jonathan) Jonathan A. Poritz (CSU-Pueblo) Algebraic Turing Machines UCCS R&W 11/15/17 35 / 35