Lucas DixonTeaching → MSc Project: Discrimination nets for fast quantum reasoning
MSc Project Proposal:

Discrimination nets for fast quantum reasoning

Possible supervisors: Lucas Dixon,

Update: Now completed

This project has now been completed by David Joseph Douglas, details of the Quantomatic svn, under the core-matching-tmp directory.

Subject Areas:

Algorithm Design
Formal methods: Specification Verification and Testing
Programming Languages and Functional Programming
Software Engineering

Principal goal of the project:

To investigate discrimination nets for the graph-based presentations of compact closed categories and how this can speed up reasoning about quantum information processing.

Description of the project:

An important branch of research into quantum information has shown that quantum systems can be described as graph-based presentations of compact closed categories [1,2]. Additional structure, beyond that of the compact closed category, is captured as equations between graphs. Important characteristics of a quantum system can be seen graphically. For instance, separable states (non-entanglement) corresponds to disconnected components in a graph. By rewriting the graphical presentations, quantum information processing can be simulated and properties of quantum systems can be proved.

The process of rewriting graphs requires the left-hand side of a graphical rule to be found (matched) inside the graph being rewritten. When rules are stored in a list, the time to find the matching graphs increases linearly with the number of rules. This results in rewriting being prohibitively slow. The traditional solution employed by tree-based rewriting systems is to use a discrimination nets [3] to efficiently filter out most rewrites (typically in time logarithmic to the number of rules).

The aim of this project is to create a discrimination-net like algorithm for the graph-based presentations of compact closed categories. The project can be taken in a couple of directions, depending on the interests of the student:

Resources required:

Nothing special; access to a DICE machine.

Degree of Difficulty:

Students undertaking this project will need to be able to quickly understand the graph-matching definitions in [2]. However, given this, there are a variety of ways to tackle this project, from relatively easy metrics for filtering graphs, which can easily be implemented, to more a in-depth algorithm design and analysis.

Background needed:

Either knowledge of algorithms and run-time analysis, or familiarity with functional programming is needed.