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