Coreworld TAC

From FreeBio

Quantum Coreworld—TAC Report


Alexander (Sasha) Wait
Biophysics program, Harvard University


2pm, Tuesday, 12th of July, 2005. 2nd Floor Conference Room (room 204) Seeley G.Mudd Building, Harvard Medical School, 250 Longwood Avenue, Boston, MA, 02115.


Thesis Advisory Committee:

  • George M. Church (adviser)
  • Peter W. Shor
  • Gerald J. Sussman
  • Jack W. Szostak
  • James M. Hogle (program director)


Abstract

It is my hypothesis that quantum lifeforms—simple assembly language programs free to use the Controlled-NOT, Hadamard, and π / 2 Phase gates as well as 1-bit measurement gates—will have a selective advantage in an otherwise natural, abstract biosphere. This set of quantum gates can be practically simulated on a classical computer (Aaronson and Gottesman 2004). The quantum states permitted by CHP operations can be highly non-local. In the work described here, I attempt to find general conditions under which evolution by Natural selection leads to exploitation of this non-locality. Image:Coreworld-tac-report.pdf


Contents

Introduction

Does the underlying physics of a living system change its properties in a qualitative way? Could a different physics permit entirely new types of life? These questions have prompted me to construct the Quantum Coreworld. This world is inhabited by assembly language programs; the language—an extended version of corewar's Redcode (Dewdney 1984)—permits programs to use certain quantum operations on quantum bits (Aaronson and Gottesman 2004). Somewhat fancifully, the aim of this project is to engineer, or discover, toy quantum lifeforms. The latest version is accessible to the public over the Internet at http://science.fiction.org. For a lively overview of digital evolution but without a quantum twist see O'Neill (2003).

Figure 1. Two views of a Quantum Coreworld
Bricks (cubes) arranged in a torus
Enlarge
Bricks (cubes) arranged in a torus
Bricks between cells (red) and bricks in which new programs arise (green)
Enlarge
Bricks between cells (red) and bricks in which new programs arise (green)

The Quantum Coreworld is subdivided into volumes of space, called bricks, arranged in a torus. In Figure 1 the bricks are colored cubes. For comparison with real biology it can help to think of one brick as a femtoliter of water – a cube, one micron on each side. A femtoliter contains billions of water molecules at standard temperature/pressure and enough space for a few simple bacteria. For practical reasons the bricks of each world are grouped into cells that can be computed in parallel. In Figure 1 there are four cells that interact by periodically exchanging neighboring (red) bricks. Depending on its dimensions, in bricks, a Quantum Coreworld is analogous to the “biosphere? that can form around a tiny speck of dust or an Earth-like planet. Necessarily these are very crude models. If computational investigation, however, finds sufficient similarity to real biology, the techniques of mathematical proof—in particular the tools of modern cryptology—might be fruitfully used to analyze the worlds described here.

Why quantum?

On one hand, the most intriguing—and the most far-fetched—outcome of this research is the possibility that toy quantum lifeforms, explored in this work, could help us recognize real quantum lifeforms. On the other hand, the most practical benefit from studying quantum artificial life might be a greater understanding of biological possibilities with more standard physics.

The operations permitted in a classical world and a quantum one—especially the operations we can model on a digital computer—are only subtly different. The Quantum Coreworld is a specific model in which these differences can be examined; this exploration can lead to a better understanding of the world as it is.

Why 3D?

The Quantum Coreworld is three-dimensional because biology is three-dimensional. Furthermore, quantum lifeforms that exploit non-locality can only have a selective advantage over their classical counterparts if cell-like aggregates (and functional organelles) are possible in the world. At the molecular level there is no such thing as a 2D cell!

Discussion

The Earth's oceans consist of roughly one billion cubic kilometers (10^36 femtoliters) of water. In this volume of water Pedulla et al. (2003) estimate that 10^42 phage infections of bacteria—in a global population of 10^30 bacterial hosts—have occurred in the Earth's history. This is the scale on which evolution occurs. An abstract biosphere should, at least, be well defined over this range. Lifeforms such as bacteria or phage will behave very similarly if they are confined to a small volume or a large one. Abstract lifeforms should also behave similarly irrespective of the volume to which they are confined. Computational investigation of such models, however, will be necessarily constrained to very small biospheres and very short time scales. It's imperative to show that modeled phenomena are not artifacts of the particular parameter choices but are robust over the widest set of parameters that can be feasibly simulated.

To create a biosphere for quantum mechanical digital organisms—phage-like viruses and bacteria-like replicators—I have built on a simple game called corewar (Dewdney 1984). This game has provided a rich foundation for several digital evolution systems (Rasmussen et al. 1990; Ray 1992; Adami and Brown 1994; Ofria and Wilke 2004). Since the first corewar tournament at the Boston Computer Museum (Dewdney 1987) the game has continued to attract fans who play it over the Internet. Authors compete vicariously in on-going tournaments through the activity of simple assembly language programs they have prepared in advance. In general, the winning strategies employed by these programs are quite sensitive to the rules of that particular tournament. To understand how this works it's helpful to understand the game in more detail.

Corewar is played in a circular memory array—called a “core�?—in which every location in memory can be addressed from every other location. Each player's program executes at only one location in a given cycle or time slice. Each program, however, is allowed several “tasks�? and these are scheduled in successive cycles. A round lasts for a fixed number of cycles. The core is reset at the end of each round and the competing programs are replaced at new positions in core. Thus, the main parameters of a tournament are: coresize, maximum tasks per program, cycles per round, and number of rounds. The dizzying progression of new strategies that has emerged over the last twenty years is the game's most biological quality.

To create a more natural, biosphere based on corewar, a core should persist as time passes—from round to round—and programs should execute in parallel without time slicing. In previous work (Wait 2004) I designed a coreworld with persistent cores and concurrently executing programs. Since it is well known that corewar programs are highly sensitive to coresize it is preferable to permit multiple cores in a coreworld and to vary the coresize over time. The number of cores can then also vary over time—as coresize varies—while the maximum number of cores is determined by the available memory of the computer. Implementing multiple cores in the same world immediately raises the question of how they should interact. I experimented with several arrangements. In the published work (above) I arranged cores in two dimensional films so that programs could only address memory locations in a portion of each neighboring core.

By letting the size of a coreworld be determined by maximum available memory the above system is extremely vulnerable to the undesirable specialization of programs to worldsize—the total number of locations in all cores. Bacteria, after all, will grow pretty much the same way if they are confined to a few microliters of water or to a few liters. An obvious solution is to simultaneously simulate worlds of different size. With multiple worlds the same problem arises as with multiple cores. How should the worlds interact? And who will write programs for all of these different worlds? At the last TAC progress meeting I was stuck on these points. The description of Figure 1 (from the Introduction) already hints at a solution but before describing it further I should mention another reason to permit multiple worlds to interact.

Evolution in corewar occurs because human players discover new strategies. Recent efforts indicate, however, that evolutionary approaches can be used to write corewar programs successfully (Corno et al 2003; Vowk et al. 2004). In these approaches programs are generated at random, competed against some benchmark suite and this process is repeated on many computers until the experimenter is satisfied. These efforts are not very biological because corewar is not very biological, the interaction (if any) between computer runs is not biological, and, furthermore, the world itself should provide the benchmark suite not the experimenter.

To achieve a more natural corewar—that both evolves autonomously and is relatively insensitive to the arbitrary capabilities of available computer hardware—I use a simple cellular automaton model. The automaton can be characterized by a single parameter—the number of cell types—which determines all other constants. Each successive automaton has one new cell type and twice the number of cells. These cells are subdivided into bricks, as seen in Figure 1 (from the Introduction), which are grouped into cores. Coresize is uniform within a cell and varies from cell to cell. The range of variation depends on the cell size. At each time step cells interact by exchanging classical information with their neighbors. Also, new programs are randomly generated—according to the methods used to generate corewar programs—so that the cellular automaton might, in principle, write itself. With this scheme the smaller worlds add at most a factor of two to the computational effort of simulation, so, it makes sense to simulate all the coreworlds up to the capabilities of available hardware. A phenomenon that occurs in one Quantum Coreworld should also occur in other worlds; if this does not happen, it is probably an artifact. More experiments, however, are required to provide evidence for this assertion.


Quantum mechanics

Quantum effects in the Coreworld are confined to individual cells. Within a cell every operation is serialized so that the state is modified in only a handful of locations per step. From the perspective of programs these steps are stochastic and can seem, effectively, simultaneous. As each quantum operation occurs the step (an integer) is recorded as well as which operation it is and the qubit(s) involved. If simplifications are possible they are performed (eg. a Hadamard followed by a Hadamard) and, when necessary, the resulting circuit is fed to a CHP simulator when measurements occur. The result of the measurement is registered in the classical state of the QVM and recorded in the qubit's history. The circuit can be discarded once it has been evaluated and re-computed from scratch from the history as required.

Stabilizer formalism

Quantum Information Processing (or QIP) is a mathematically well defined distillation of numerous physical experiments (Nielsen and Chuang 2002). The rules of QIP can be used to extend any assembly language with quantum operations on quantum bits.

Figure 1. Quantum gates in the stabilizer formalism
Enlarge
Figure 1. Quantum gates in the stabilizer formalism

In general it is believed to be impossible to simulate QIP efficiently on a classical computer; primarily this is due to the discovery of efficient algorithms for factoring and taking discrete logarithms (Shor 1994.) If the quantum operations belong to gates in the stabilizer formalism, see Figure 2, an efficient simulation is possible for thousands of qubits (Aaronson and Gottesman 2004). Although stabilizer circuits are not even capable of universal classical computation, they are interesting for their non-locality. Some properties of quantum gates in the stabilizer formalism will come in useful later. I state them here (following the above references).

The stabilizer formalism is characterized by the following theorem:

Gottesman-Knill Theorem.
Enlarge
Gottesman-Knill Theorem.


The Pauli Matrices
Enlarge
The Pauli Matrices


The group of n-qubit Pauli operators consists of all tensor products of n Pauli matrices, together with a multiplicative factor of \pm 1 or \pm i. The total number of operators is \left | P_n  \right | = 4^{n-1}. Given a pure quantum state Failed to parse (unknown error): \left | \Psi \right \rangle

we say a unitary matrix U stabilizes Failed to parse (unknown error):  \left | \Psi \right \rangle 
if \left | \Psi \right \rangle is an eigenvector of U with eigenvalue 1, or equivalently if Failed to parse (unknown error): U\left | \Psi \right \rangle \equiv \left | \Psi \right \rangle
 where we do not ignore the global phase.


The Pauli matrices X, Y, Z can also be written as:

X \equiv H P P H Y \equiv P P H P P H Z \equiv P P

The X operation—in the computational basis—corresponds to a classical bit flip. Pauli-X, Pauli-Y, and Pauli-Z are made available to programs (although they could use the above equivalences also.)


Cryptography

The best known quantum cryptography protocol BB84 (Bennett and Brassard 1984)—implemented in the real world—is also easily simulated on a classical computer. The “catch�? is that only the denizens of the simulation could benefit from the simulated security. Consider three such denizens Alice, Bob, and Eve. Starting with a shared private key—a random sequence of classical bits—Alice and Bob can extend their key; Eve cannot obtain knowledge of the extended key without giving herself away.

For this to work, Alice and Bob have access to quantum and classical channels which they will use as required. All parties can prepare quantum states in the computational basis, measure those states in the computational basis and perform, for example, Hadamard operations. No matter what operations Eve can do, in addition to these, she doesn't gain any extra power; her observation of the quantum channel will necessarily disturb that channel. Alice begins by sending n qubits to Bob; she chooses the qubits uniformly at random from the computational basis states or a basis state followed by a Hadamard (four possibilities). Bob receives the n qubits and measures them, first applying a Hadamard (or not) to each qubit at random. The protocol then proceeds in two steps:

Reconciliation: For all n qubits, Bob reveals on the classical channel if he applied a Hadamard prior to measurement. Furthermore Bob unveils the results of, say, n/2 measurements (at random). If Alice also applied a Hadamard, the result of Bob's measurement should match what Alice sent—unless Eve or the environment disturbed the channel—Alice can now announce the error rate on the quantum channel. Based on this error rate—and applying a classical error correcting code—Bob can use the remaining n/2 bits to establish a smaller private key with Alice.

Distillation: If Eve is watching the quantum channel she can surreptitiously measure a few qubits. Since Eve doesn't know if Bob will apply a Hadamard, or not, half the time she measures a qubit she will scramble the result of Bob's measurement; her increased knowledge of the key results in an increase in the error rate above! Alice and Bob may use classical privacy amplification to discard enough bits of their corrected key that Eve has no knowledge (whatever) of any of its bits. If Eve acquires so much information that this doesn't work, Alice and Bob can abort.


Teleportation

The quantum teleportation procedure (Bennett et al.1993) is illustrated in Figure 3 below:

Step 1 Alice and Bob share an EPR pair; Alike keeps qubit A and Bob keeps qubit B.
Enlarge
Step 1 Alice and Bob share an EPR pair; Alike keeps qubit A and Bob keeps qubit B.
Step 2 Alice teleports her qubit to Bob by applying the above circuit and transmitting bits X and Y to Bob.
Enlarge
Step 2 Alice teleports her qubit to Bob by applying the above circuit and transmitting bits X and Y to Bob.
Step 3 Bob receives bits X and Y from Alice; he then applies the above circuit and, thus, completes the teleportation.
Enlarge
Step 3 Bob receives bits X and Y from Alice; he then applies the above circuit and, thus, completes the teleportation.
Figure 3. A Quantum Teleportation in three steps.

The existence of the teleportation procedure permits quantum information to be passed around over classical channels so long as entanglement was previously shared. Since this procedure consists of gates from the stabilizer formalism it can be efficiently simulated if the teleported qubit was itself prepared by gates in the formalism.


Future work

  • Debug and tune random generation of new programs
  • Debug interaction across cells
  • Write a program that entangles itself with progeny
  • Improve visualization/analysis
  • Collect data

I appreciate the committee's help with these endeavors!

References

  • Adami, C. and Brown, T. 1994. Evolutionary Learning in the 2D Artificial Life System 'Avida'. In Brooks, R. and Maes, P. editors, Artificial Life IV, 377-381. Cambridge, MA: MIT Press.
  • Bennett CH and Brassard G. (1984) An update on Quantum cryptography. In Advances in Cryptology – proceedings of Crypto'84, 475-480. Springer Verlag.
  • Bennett CH, Brassard G, Crepeau C, Jozsa R, Peres A, and Wootters W (1993) Teleporting an Unknown Quantum State via Dual Classical and EPR Channels. Physical Review Letters 70:1895-1899.
  • Corno F, Sanchez E, Squillero G. (2003) Exploiting Co-Evolution and a Modified Island Model to Climb the Core War Hill CEC03: 2003 IEEE Congress on Evolutionary Computation, Canberra, Australia, 8-12 Dec 2003, pp. 2222-2229
  • Dewdney AK. (1984) In the game called core war hostile programs engage in a battle of bits. Scientific American, 250:14–22.
  • Dewdney AK. (1987) A program called MICE nibbles its way to victory at the first Core War tournament, Computer Recreations, Scientific American, 14-20.
  • Ofria C and Wilke CO. (2004) Avida: A Software Platform for Research in Computational Evolutionary Biology. Journal of Artificial Life, 10:191-229.
  • O'Neill B. (2003) Digital Evolution. PloS Biology 1(1):11-14.
  • Nielsen MA and Chuang IL. (2000) Quantum computation & quantum information. Cambridge University Press; ISBN 0521635039
  • Pedulla ML, Ford ME, Houtz JM, Karthikeyan T, Wadsworth C, Lewis JA, Jacobs-Sera D, Falbo J, Gross J, Pannunzio NR, Brucker W, Kumar V, Kandasamy J, Keenan L, Bardarov S, Kriakov J, Lawrence JG, Jacobs WR Jr, Hendrix RW, Hatfull GF. (2003) Origins of highly mosaic mycobacteriophage genomes. Cell. 113(2):141.
  • Rasmussen S, Knudsen C, Feldberg R, Hindsholm M. (1990) The Coreworld: Emergence and evolution of cooperative structures in a computational chemistry. Physica D, 42:111–134.
  • Ray TS. (1992) An approach to the synthesis of life. In C. G. Langton, C. Taylor, J.D. Farmer, and S. Rasmussen, editors, Artificial Life II, 371–408, Redwood City, CA, Addison-Wesley.
  • Shor P. (1994) Algorithms for quantum computation: discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science, 124-134, IEEE. http://arxiv.org/abs/quant-ph/9508027
  • Tessier TE, Caves CM, Deutsch IH, Eastin B, Bacon D. (2005) Optimal classical-communication-assisted local model of n-qubit Greenberger-Horne-Zeilinger correlations. http://arxiv.org/abs/quant-ph/0503047
  • Vowk B, Wait AS, Schmidt C. (2004) An Evolutionary Approach Generates Human Competitive Corewar Programs. In Artificial Chemistry and its Applications, part of ALIFE IX. Sept. 12-15, Boston, MA.
  • Wait AS. (2004) The Quantum Coreworld: competition and cooperation in an artificial ecology. In the proceedings of the Ninth International Conference on the Simulation and Synthesis of Living Systems (ALIFE IX), 280-285, Sept. 12-15, Boston, MA.
  • Weinbauer M.G. and Rassoulzadegan F. 2004. Are viruses driving microbial diversification and diversity? Environmental Microbiology 6(1):1-11.

Appendix I: Instruction set

Instructions

DAT terminate (corewar); don't advance nutrient (coreworld)
MOV copy from A to B; use nutrient (coreworld only)
ADD add A to B, result in B
SUB subtract A from B, result in B
MUL multiply A by B, result in B
DIV divide B by A, result in B; DAT if zero
MOD divide B by A, remainder in B; DAT if zero
JMP execute at A
JMZ execute at A if B is zero
JMN execute at A if B is not zero
DJN decrement B, if B is not zero, execute at A
IJN increment B, if B is not zero, execute at A
SLT skip if A is less than B
SEQ/CMP skip if A is equal to B
SNE skip if A is not equal to B
NOP no operation
SPL new task (corewar); NOP (coreworld)
QOP quantum operation on B, specified by A
QCN quantum not of target B, controlled by A

Modifiers

.A Instruction reads and writes A fields
.B Instruction reads and writes B fields
.AB Instruction reads A field of A instruction, B field of B instruction and writes B field
.BA Instruction reads B field of A instruction, A field of B instruction and writes A field
.F Instruction reads both A and B fields of A and B instruction and writes to both A and B fields (A to A and B to B)
.X Instruction reads both A and B fields of A and B instruction and writes to both A and B fields (A to B and B to A).
.I Instruction reads and writes Instruction field, Modifier field, Addressing Modes, A and B fields; (Tag for MOV.I, coreworld only)
.P Instruction reads and writes bound processors (coreworld only)
.Q Instruction reads and writes qubit (coreworld only)
.D* B pointer refers to dual core (coreworld only)
.E* Consume a bound processor, execute faster (coreworld only)

* indicates modifier can be combined with others

Addressing modes

# immediate
$ direct
@ indirect using B-field
< predecrement indirect using B-field
> postincrement indirect using B-field
* indirect using A-field
[ predecrement indirect using A-field
] postincrement indirect using A-field

QOP codes

0 NOP
1 Hadamard
2 Failed to parse (unknown error): \Pi/2
Phase
3 Pauli-X
4 Pauli-Y
5 Pauli-Z
6+ NOP

Appendix II: A simple replicator

;redcode
;name myMice
;standard 2004
 
deltap equ CORESIZE/4

step      equ              64
steps     equ              16

first     DAT               0,          last-first  
begin     MOV           #step,                last
reset     MOV  #last-search+1,              search
          MOV          #steps,               count
loop      DJN.P        energy,             >search
count     DJN            loop,              #steps
search    JMP           reset,                   0

;get all the priv.
continue  JMP            loop,             <search
 
;found some priv. so continue (or boot)
energy    IJN.Q      continue,               begin 
          IJN.P             1,            continue

;check (and set) the lock   
check     IJN.Q          next,               @last

;spawns a new copy in the core
          MOV     #last-first,               first
          ADD              #1,                last 
rep       MOV          @first,               <last 
          DJN             rep,               first
          IJN.P             1,               @last
          ADD   #last-first-1,                last
next      ADD           #step,                last

;check (and set) the dual lock
checkDual IJN.QD        check,               @last

;spawns a new copy in the dual core
          MOV     #last-first,               first 
          ADD              #1,                last
rep2      MOV.ID       @first,               <last
          DJN            rep2,               first 
          IJN.PD            1,               @last
          ADD   #last-first-1,                last
last      JMP           check,                   0

;boot code -- not copied

start     IJN.Q             1,                last
          IJN.P             1,                begin
          end           start


Appendix III: A Quantum Coreworld

Cell 0

Preamble

;QCW
{beginning of first cell}

;MD5 71ac881b0592ecfa650cd8d491187a07 C(0)
{hash of "climate" parameters on input}

;MD5 786ff258f1a0f5217461341ea82b3a4f R(0)
{hash of random context on input}

;MD5 f1aa42773675af4f3da2e96650b6d42f M(0)
{hash of cell memory on input}

Intervention

;I "myMice " (length 29) by "Anonymous" for "2004" standard
I DAT.F    $       0, $      25 B
I MOV.AB   #      64, $      24 B
I MOV.AB   #      20, $       4 B
I MOV.AB   #      16, $       2 B
I DJN.P    $       4, >       2 B
I DJN.B    $      -1, #      16 B
I JMP.B    $      -4, $       0 B
I JMP.B    $      -3, <      -1 B
I IJN.Q    $      -1, $      -7 B
I IJN.P    $       1, $      -2 B
I IJN.Q    $       7, @      15 B
I MOV.AB   #      25, $     -11 B
I ADD.AB   #       1, $      13 B
I MOV.I    @     -13, <      12 B
I DJN.B    $      -1, $     -14 B
I IJN.P    $       1, @      10 B
I ADD.AB   #      24, $       9 B
I ADD.AB   #      64, $       8 B
I IJN.QD   $      -8, @       7 B
I MOV.AB   #      25, $     -19 B
I ADD.AB   #       1, $       5 B
I MOV.ID   @     -21, <       4 B
I DJN.B    $      -1, $     -22 B
I IJN.PD   $       1, @       2 B
I ADD.AB   #      24, $       1 B
I JMP.B    $     -15, $       0 B
I IJN.Q    $       1, $      -1 B START
I IJN.P    $       1, $     -26 B
I DAT.F    $       0, $       0 B
;MD5 ea29c2a48fe8805cf3d084aacf180dfb I
{optional unique intervention and hash (lines starting with I)} 

Climate Parameters

C W 14
{Worldsize = 2^W}
 
C X 2
{# Cores in X dimension = 2^X}

C Y 2
{# Cores in Y dimension = 2^Y}

C Z 2
{# Cores in Z dimension = 2^Z} 

C M 1
{unused}

C F 3722168
{free processors}

;MD5 66b67e47224369d7a5e8b79b5942e8cb C(1)
{hash of climate parameters (lines starting with "C")}

Random context

R b89b808a01ac88c6
{257 additional lines}

;MD5 9438e3daf1a20c868580a74daff188ef R(1)
{hash of random context (lines starting with "R")}

Monomer data

M
{1048 lines} 

                                           a field, b field, bound processors, qubit 
                                           |
M 01080001ea29c2a48fe8805cf3d084aacf180dfb 18 1 0 0
M 0d040101ea29c2a48fe8805cf3d084aacf180dfb f1 19 0 1
  ^^ instruction
    ^^modifier
      ^^a mode
        ^^b mode
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ hash
                                                  
{15334 lines}
;MD5 0874db1a996eb1c57bc4c024f94b790e M(1)
{hash of monomer data (lines starting with "M")}

Cell 1,2,3

{above format is repeated three times for the other cells}