 |
 |
|
Quantum Algorithms
Graphs are used almost ubiquitously throughout the different subfields of computer science to represent search tasks involving relational data. Examples include routing problems from operations research, constraint satisfaction tasks in artificial intelligence, pattern matching in information retrieval and pattern recognition, sequencing problems involving protein and genome data in bioinformatics, and graph clustering problems in machine learning and software engineering. The task of comparing two graphs to determine if they are identical, graph isomorphism, is of unknown computational complexity but no efficient algorithms exist. In contrast, inexact graph matching consists of matching graphs of different size which potentially contain structural errors due to noise or natural statistical variation. This problem is perhaps one of the most important of those involving graphs, since it plays a pivotal role in information retrieval. The complexity of sub-graph isomorphism is known to be NP-complete and hence potentially involves an exponential number of computations to perform the underlying search problem. Quantum computing however, offers the prospect of much faster computation, for example Shor's factorisation algorithm. Like graph isomorphism, factorisation is of unknown complexity, but all known classical algorithms take exponential time. There is also a quantum algorithm which could be directly applied to serial search problems, namely Grover's search algorithm, which achieves a time saving of √N over classical algorithms. This research is aimed at investigating some potential approaches to these problems. In [Emms et al 2006a] we considered a quantum mechanical representation of graphs which can be used to approach the problems of graph isomorphism and matching We explored how a spectral technique suggested by quantum walks can be used to distinguish non-isomorphic cospectral graphs. We showed by computation that the isomorphism classes of many known families of strongly regular graphs (up to 64 vertices) are characterized by the spectrum of this matrix, and did not find any counter example. We verified that the smallest regular graphs which are not distinguished with our method are on 14 vertices[Emms et al 2005]. In [Emms et al 2006b] we considered how coined quantum walks can be applied to exact graph matching. The matching problem is abstracted using an auxiliary structure that connects pairs of vertices from the graphs to be matched by way of auxiliary vertices. We locate matches using coined quantum walks on this structure. We have also looked in some detail at the issue of how graphs can be embedded onto a manifold in a stable manner, so that graph matching can be effected via an alignment process. We have also explored embeddings based on quantum walks. Here we have generalised the concept of commute time to quantum walks. When used for embeddings, this induces a modification of the adjacency structure of the nodes that is similar to that resulting from a negative curvature embedding [Emms and Hancock 2007b]. We explored analytically and experimentally the commute time of the continuous-time quantum walk on a graph. Experimentally, we show that the quantum commute times can be used to emphasise cluster-structure [Emms and Hancock 2007a]. Contact: Edwin Hancock 
|