home > teaching > project descriptions 2009/10

Susan Stepney's Project Descriptions 2009/10

1

Raymond Birch


[4D hypercube]
Visualising Quantum Algorithms using Hilbert Curves
[Hilbert curve mapping of 6D hypercube] [Hilbert curve mapping of 4D hypercube]

Quantum algorithms occur in high dimensional spaces -- visualising their effect is difficult, as it is difficult to visualise n-dimensional hypercubes. The family of Hilbert curves [1] can be used to lay out the vertices of hypercubes in a manner that preserves (some) locality properties, and has a simple relationship between the maps of hypercubes of different dimensions.

You will develop a general approach to visualising quantum algorithms [2] mapped on Hilbert curves. You will apply the approach to Grover's quantum search algorithm [3] and for Shor's QFT algorithm [4] across a range of dimensions, demonstrating how the resulting behaviours for different numbers of qubits are related.

  1. Eric Weisstein. Hilbert Curve. Mathworld
  2. M. A. Nielsen, I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000
  3. Lov K. Grover. A fast quantum mechanical algorithm for database search. arXiv:quant-ph/9605043v3
  4. Peter Shor. Algorithms for quantum computation: discrete log and factoring. In Proc. 35th Ann. Symp. Foundations of Computer Science, pp 124-134. IEEE, 1994.

2

Chris Riley


[example L-system output]
LSystems in JCSP

JCSP [1] is a class library for Java that provides CSP-style parallelism capabilities.

L-systems [2] are parallel generative grammar systems originally developed for simulating plant growth. The various symbols in the productions are interpreted as "turtle graphics" style instructions, and used to draw fractals reminiscent of biological growth patterns.

You will design and implement an L-system tool in JCSP, matching the parallel structures of the implementation language with the parallel rewriting of the L-Systems, and exploiting the object oriented nature of Java (so that symbols know how to rewrite themselves, how to draw themselves, etc). Depending on progress, you will investigate context free L-systems, context sensitive L-Systems (where symbols communicate with their neighbours to determine their context), and environmental L-Systems (where symbols communicate with an external environment to determine inputs). If time permits, you will investigate generalised growth grammars, where the symbols are connected in a graph, rather than in a string.

  1. JCSP latest version
  2. Przemyslaw Prusinkiewicz, Aristid Lindenmayer. The Algorithmic Beauty of Plants. Springer. 1990

3

George Dando


Entropy of flocks v. swarms

Realistic-looking flocking behaviour can be simulated with remarkably simple interaction rules [1,2]. The "Singular Value Decomposition entropy" [3,4] of a boid flock indicates properties of the flock. In this project you will investigate how the SVD entropy can be used to distinguish emergent properties of flocks as a function of their parameters.

You will create an instrumented boid flocking simulation and use it to determine the effect on SVD entropy of

  1. the mass of the flock members, varying from "gnats" to "747s" (which affects the turning speed, among other things).
  2. the radius of visibility of the flock members (how far, or how many flockmates, they can see)
  3. the cone of visibility of the flock members (how far behind them they can see)
  1. Craig W. Reynolds. Flocks, herds, and schools: a distributed behavioral model. Computer Graphics 21 25-34 1987
  2. Craig W. Reynolds. Boids: Background and Update
  3. EME lecture notes: Lecture 9 (Complexity 1), slides 20-22
  4. W. A. Wright, R. E. Smith, M. Danek, P. Greenway. A Generalisable Measure of Self-Organisation and Emergence. ICANN 2001, LNCS 2130, 857-864, Springer 2001

4

Ali Afshar Dodson


Breaking the law in Sugarscape

It is common belief that people are willing to break laws if they believe they have a chance of escaping punishment. This theory is often cited in Peer-2-Peer piracy cases [1].

Sugarscape [3] is an artificial society simulation developed by Joshua Epstein and Robert Axtell based on the consumption and trade of “sugar”. It is one of the leading agent based models and has been used for a number of interesting sociology experiments [2]. The current Sugarscape code is available from SourceForge.

We propose to adapt the Sugarscape agent based model to form a society of variably “dishonest” agents. These agents will have the ability to break the trading laws of Sugarscape, by “stealing” sugar. They will have a chance of being caught, and “punished”. The (small, variable) probability of breaking a law will depend on the agent’s belief that it will get caught.

We will test the hypotheses that (i) agents will commit crimes as long as they believe they will get away with it, and that (ii) this strength of this belief depends on the number of agents they see being caught and punished (rather than on the proportion of agents, or the severity of the punishment).

The first stage is to formalise these questions in a way that makes sense in the Sugarscape environment, and such that the "answer" is not merely a simple consequence of the way the question is posed.

The second stage is to modify Sugarscape to support the new rules, and to design and run an appropriate suite of experiments to test the (formalised) hypotheses.

  1. Guardian technology, February 2009.
  2. J. M. Epstein. Generative Social Science : Studies in Agent-Based Modeling. Princeton University Press, 2006.
  3. J. M. Epstein and R. Axtell. Growing Artificial Societies : Social science from the bottom up. Brookings Institution Press, 1996.