Wolfram Science

Jamie Williams: Entanglement Dynamics in Quantum Cellular Automata

Natural Sciences lecture series

Jamie Williams of Wolfram Research discusses quantum computing with NKS

Jamie described a quantum system where atoms are loaded in a lattice-like array, providing an alternative quantum circuit model. Lattice-like structures occur naturally, but can also be engineered. It is desirable to be able to address individual atoms in the lattice, and this can be accomplished by applying global control fields with laser light.

Recent literature has shown that any quantum TM can be efficiently simulated by a 1D partitioned QCA. Another result showed that open 1D lattice composed of alternating array of two types of qubits with Ising-type interactions can be used for quantum computation.

Quantum CA work by considering atoms in cells, where each atom can have one of two spin states, or in fact a superposition of both states. What often happens though is that the states of the cells become entangled, such that the system is not factorizable in general. As Jamie described, normal ECA-type rules don't work for simulating quantum systems, and so his solution is to utilize a block-partitioned QCA, first updating the odd sites in a lattice, and then the even sites. These two steps combine to form one full update step.

QCA are not very amenable to the NKS approach, since the computational resources needed scales exponentially with the size of the system. On a standard computer, up to only about 20 sites can be included. One potential solution for this is Vidal's time-dependent DMRG sumulation of 1D, which could allow over 100 sites, but has the disadvantage of using a truncated representation.

Alastair Hewitt: An Alternative Approach to Anticipative Reinforcement Learning

This was another decision-based talk using NKS, and I found this one just as interesting as the last. Hewitt studied a relatively simple but fascinating model of decision making based on choices between binary states with memory about which decisions led to which states. He had a very large number of of quantities he was using to describing the the behavior of the system, including predicatbility, desirability, and entropy.

The elementary system was a 2D CA with 2 choices, (turn left and no action), and 1 indicator with two states (right direction and wrong direction.) The agent must learn what to do when feedback indicates it is headed in the wrong direction based on past behavior, but with no indication of what moving toward the direction would be. Hewitt presented some state transition diagrams where the agent would determine the correct direction very quickly, but he quickly threw a wrench in the works by giving himself the ability to change the target point in real time.

He showed an interactive graphic of the agent seeking its target. The agent would head off in a direction more or less toward the target, but frequently get stuck in "orbits" once it had passed it on one side. I found it very amusing that the agent would get stuck in these orbits for some number of cycles and then finally get "frustrated" when it received enough negative feedback for each of its actions, and strike off in a random direction which would usually cause it to hit the target a few steps later.

Then he showed multiple agents where some of the agents were other agents targets. Their behaviors were reminiscent of bees milling around a hive, or as one of the audience members eloquently phrased it, "dating."

Hewitt ended with some graphics of distributions of various features of the agents' behavior.

Adrian German: A Space of Solutions for the Easter Egg Problem

Adrian German presented some ideas toward a solution to the so-called "Easter Egg problem" where one has a field with randomly placed Easter Eggs. One wants to unleash a collection of near-sighted agents to path around the field and collect the easter eggs in the shortest amount of time. The question is, "Is there any algorithm that beats random searching. German was convinced that there was and presented the first part of his algorithm. It involved creating rule patterns that the agents would attempt to match to their surroundings with a default case of action if no patterns matched. German only got as far as showing the templates that cause the agent to spiral outward in a path that fills all space before his time ran out.

I am especially eager for German to find an algorithm more efficient than random search, since this is apparently what my Roomba employs to clean the living room and its algorithm is incredibly inefficient. The Roomba crosses its own path many times in its attempt to collect all the "easter eggs" on the living room floor. Here's hoping that German finds results that are employed by the iRobot corporation in their wonderful products.

Jason Jacobs: Substitution Systems Design Process

Pure NKS lecture series

Jason Jacobs describes the design of a substitution system to solve an interesting problem

Can you design a system that, given information about the past, present and future, returns information about the present without affecting the past, present or future. Jacob's solution uses a rewrite automata system in a finite 3D space.

Jason demonstrated various rules in this finite space with a tool he created for designing, running and recording rules.

Ray Dougherty, Information Theory Defines 'Mathematically Conceivable Communication System'

Nature evolves in saltations -- genetic mutations that produced significant changes in organisms.

Ray Dougherty presents a number of saltation examples, and asks if such an event may have been the cause of the development of communication capabilities in animals. There is evidence in this direction, for example in the development of the lizard cochlea. Other examples are inversion or duplication of organs.

Saltation events in the development of the brain and cochlea may well have been the source of the evolution of the information processing capabilities in humans. The evolution tree of the cochlea and the current distribution of its sizes offers support for this hypothesis.

The animal with the largest cochlea is the guinea pig -- its cochlea was developed in a feedback system with the lizard cochlea: lizards predate guinea pig young, but can't hear sounds in a high frequency, creating evolutionary pressure for the guinea pigs to communicate at a higher frequency level.

Ray shows some Mathematica code to map the space of possible cochlea spaces. He then moves into possible approaches to analyzing the shape of the cochlea using mathematical methods. One approach that is bound to fail is trying to map the cochlea into 2D planar surfaces -- that's geometrically impossible.

NKS offers a possible approach to the problem, because its discrete systems offer a good model for "discontinuities". Ray suggests writing a generative grammar defining a mathematical function for each signal complexity for any shape cochlea. The grammar would generate what Ray calls Poincare complexity strings, combining sinusoidal functions in a nested way.

George Danner, NKS and Stylized Problems: Progress and New Directions

George's personal area of focus is business and logistics. George's company builds simulation models to support corporate decision making. His research focuses on individual firms. All individual companies are facing the problem of complexity -- even when compared with a few years ago. Chapter 8 in NKS offers many examples of similarities between computational systems and nature.

In George's consulting business he seems the same striking similarities between NKS and business processes. Examples: airline logistics, behavior of consumers visiting retail stores, search for wells in oil fields. Also at the level of corporate organization, simple programs (and the issue of dealing with them) is faced everywhere -- for example, what is the best model for organizing a company.

One way to bridge between the NKS community and the real-world business operators is to create "stylized problems" that implement and idealize situations that are of conceptual and practical relevance to a large part of the community. One such problem is the so called "Easter Egg" problem, which can be stated as finding a cellular automaton that can discover set black cells on a number of random points laid on the ca lattice using a minimal amount of computation. (Adrian German will be presenting possible solutions for the EEP at the conference.)

George believes that the relevance of computational models for business lays on their capability of forecasting qualitative behavior, rather than predicting specific numeric quantities -- there is little interest in recreating in NKS problems that have been successfully targeted by statistical methods, but rather to tackle new problems with the new tools that have been made available by NKS.

One area where George is enthusiastic about is using NKS methods for optimization -- and George's company will sponsor a symposium on the topic. Refineries that rely on 50-year old linear-programming optimizers are at least partially responsible for the fact that the price of oil has reached high levels in the US.

Michael Kelly, Cellular Automaton Models for Market Prices

Michael Kelly presents CA models for market prices. He identifies problems with the ECA rule 90 model presented in the NKS book -- traders do not only talk to the person next to them, but rather to many more people. Also, the ECA model doesn't exhibit unimodalitty, fat tails, or negligible skewness which are characteristic of financial time series. It also presents wild flucutations that happen much less often in fm's than in real stock markets.

A first alternative is to look at totalistic CA's. (One immediate issue about those:, they normally assume that all traders are equal, which is not the case.) Some models exhibit adequate volatility, but have very high skewness. Compare to: geometric Brownian motion model.

By introducing a geometric brownian motion with a CA as its stochastic generator more realistic results can be obtained. The next obvious question is: an option prices be generated by Cellular Automata?

Again, the standard normal random variable is replaced by a cellular-automation generated one. The frequencies are consistent with the ones obtained from a standard normal random variable. However the option price calculations using CA's end up being unconsistent with Black-Scholes generated ones. The probable reason for that is the martingale property that is inherent to the Black-Scholes model, and CA's doesn't have this property.

Jason Cawley, NKS Time Series

The main idea of this talk was to present NKS ideas for modeling time series. The standard model for financial time series: Random walks, random walks with trends. All the randomness seen in such processes is explicitly introduced into the system at each step (see NKS Ch.7). There are all kinds of statistics that can be done on such models.

NKS, Ch. 8 offers an alternative: use a simple CA based model to encode randomness generation in financial markets. The NKS model uses rule 90. White cells are buy orders, black cells sell orders. One cell represents one trader, who respond to the input of his neighbors. Price series correspond to the number black cells in each state. Note that the randomness in the rule 90 system in encoded in the initial conditions of the system (not at each step as in conventional stochastic models.) The series has "memory": it depends on previous steps.

Extensions of the model: other ECA rules, 3-color totalistic CA's, 2k 2r, 3 color totalistic, 3 color general, uneven cell weights, second difference / acceleration series. Interactive Cellular Automata approach: mix multiple rules. ICA's apply one of two CA rules at a given step, as determined by an external function of time t. ICA's generate richer time series distributions, and by changing rules and interaction functions it is possible to fit time series from financial markets into their behavior.

An explicit experiment is presented by trying to fit the time series for Goldman Sachs (NYSE:GS). Results were found that very closely track the behavior of the stock.

Fritz Obermeyer: Mapping the Space of Programs, Searching the Space of Languages

Pure NKS lecture series

Fritz Obermeyer discusses mining the space of programming languages

Given a simple programming language family like lambda calculus, Fritz asks: what are the simplest few program behaviors? These behaviors form a basis that seems big but really isn't all that big. In an more abstract view, we can consider the behavior space of programs, and define a bigger map, and Fritz argues that this is the worthwhile space to map.

Since programs are elements of an algebra, like constants, binary operations, and equations and/or inequalities, a first starting place for this map is to try computational algebra methods. Fritz gave an example of making a map with the Todd-Coxeter algorithm. In theory, equivalence is undecidable, but in practice, given enough computation, equivalence is largely decidable (Fritz cites 96% in one particular case).

Then in the space of programs, Fritz can calculate the shape of an algebra of programs using Kolmogorov complexity. In order to visualize the space, Fritz posed the space as an eigenvector problem and is able to visually illustrate the difference in different programming styles in a program space. Through proper definition, the space of programs is a Reimannian manifold.

Potential applications of thes techniques include program simplification, using a database of simple rewritings, or software analysis, refactoring based on spatial proximity. It is also possible to program by searching.

Fritz's analysis shows that the average over all languages is simpler than any one.

Fiona Maclachlan: The Distribution of Market Shares in Monopolistically Competitive Markets

Monopolistically competitive markets are much more common in the real world than perfect markets, but perfect markets are the usual assumption in theoretical economics, mainly because they are more tractable from a mathematical perspective. However, there are many empirically observed distributions that lack a formal model that describes them, and thus tend to receive less attention from the economics community. One notable example was the observation that the distribution of intervals between random points corresponded to the market share distribution of the top 4 auto companies in 1967.

Other distributions obeyed the so-called broken stick rule: world religions, price patterns. However, there has been no theoretical model in which to fit the empirical result. More recently, stochastic proportional growth models were proposed for these, but not without problems: distributions are not perfectly log-log, but rather more like power-log on one end, and exponential on the other. One problem with the stochastic proportional growth model is that it relies on a so-called preferential attachment model. But this is not always the case in reality. This raises the question of what kind of distribution would arise in a market without preferential attachment.

Fiona offers one such model: assume uniform distribution of consumers over a given parameter, for instance, "sweetness" for a soft drink. Firms select their "sweetness" parameter at random. One can then (assuming a given distribution of tastes among consumers), assume that consumers will make their choices based on which products lie closest to their preference.

The distributions achieved through explicit simulation of the model that are more consistent with empirical observations than the Pareto distribution. The idea in Fiona's talk is similar to the discussion of Zipf's law (NKS 1014): a simple model using randomness could be the actual underlying generator of this and other phenomena that exhibit power law behavior.