PaperlayerView exact revision on arXiv

Source-linked AI summary

Classical approach to the graph isomorphism problem using quantum walks

B. L. Douglas, J. B. Wang

arXiv:0705.2531v2quant-ph

TL;DR

No polynomial-time algorithm is known for graph isomorphism on general graphs. This paper develops classical and quantum graph-isomorphism algorithms using quantum walks; its classical algorithm distinguished all tested non-isomorphic graphs, while its ability to distinguish general graphs remains unproved.

  • Problem

    No polynomial-time algorithm is known for general graph isomorphism, a problem of practical interest that is also connected to computational complexity.

    Source: §I · p. 2

  • Method

    The paper develops classical and quantum graph-isomorphism algorithms using quantum walks, including phase operations defined relative to reference nodes.

    Source: §I · p. 3, §III · p. 8

  • Results

    The classical algorithm distinguished all tested non-isomorphic graphs, including groups traditionally considered difficult to distinguish, but its ability to distinguish general graphs remains unproved.

    Source: §VI · p. 18

  • Takeaways & Limitations

    For polynomially growing state spaces without noise or quantum measurements, the paper finds quantum walks efficiently implementable on a classical computer.

    Source: §VI · p. 18

    Whether the algorithm distinguishes general graphs remains open, and the complexity estimate does not account for potentially exponentially small amplitude differences.

    Source: C. Complexity of algorithm · p. 12, §VI · p. 18

Abstract

from arXiv · show

Given the extensive application of classical random walks to classical algorithms in a variety of fields, their quantum analogue in quantum walks is expected to provide a fruitful source of quantum algorithms. So far, however, such algorithms have been scarce. In this work, we enumerate some important differences between quantum and classical walks, leading to their markedly different properties. We show that for many practical purposes, the implementation of quantum walks can be efficiently achieved using a classical computer. We then develop both classical and quantum graph isomorphism algorithms based on discrete-time quantum walks. We show that they are effective in identifying isomorphism classes of large databases of graphs, in particular groups of strongly regular graphs. We consider this approach to represent a promising candidate for an efficient solution to the graph isomorphism problem, and believe that similar methods employing quantum walks, or derivatives of these walks, may prove beneficial in constructing other algorithms for a variety of purposes.

I. INTRODUCTION

Graph isomorphism matters for applications and computational complexity, but no polynomial-time algorithm is known for general graphs. The paper presents a graph-isomorphism algorithm based on quantum walks and focuses on establishing polynomial scaling.

I. INTRODUCTION

  • Graph isomorphism has drawn sustained attention because of its practical applications and its connection to computational-complexity questions.Many algebraic and combinatorial structures can be encoded efficiently as graphs.Source: §I · p. 2
  • No polynomial-bounded algorithm is known for general graph isomorphism, and its exact complexity status remains unknown.Efficient algorithms do exist for certain restricted graph classes and work well on many practical instances.Source: §I · p. 2
  • The paper emphasizes polynomial versus non-polynomial computability, while noting that its current implementation may not be optimized.The authors identify establishing a polynomially scaling algorithm as the immediate theoretical direction.Source: §I · pp. 2–3
  • The paper develops an algorithm using quantum walks on graphs to distinguish pairs of graphs and tests it on graph sets.It also discusses classical implementations and a corresponding quantum algorithm.Source: §I · p. 3

II. QUANTUM WALKS

Quantum walks differ from classical random walks through memory and interaction between simultaneously sampled paths, producing distinct spreading behavior. The paper describes their graph-based operations, their classical simulation, and observations that motivate using walk distributions to distinguish graphs.

II. QUANTUM WALKS

  • Memory and simultaneous sampling of paths are both needed for spreading like the quantum walk’s interference-pattern distribution; unitarity can be relaxed for classical implementations.The interaction between paths distinguishes quantum walks from classical random walks and Markovian processes.Source: §II · p. 4
  • For the quantum walk’s characteristic spreading, both memory and simultaneous path sampling are needed, whereas unitarity is not strictly necessary to reproduce similar distributions.The paper contrasts the quantum walk’s interference patterns with the Gaussian distribution of a simple classical random walk.Source: §II · p. 4
  • On a graph, each vertex has edge-associated sub-nodes; the shift swaps paired edge amplitudes, while the coin mixes amplitudes within each vertex’s sub-node group.A step is represented by the unitary matrix U = S.C on the extended position space.Source: §II · p. 5
  • Quantum walks are reversible and do not approach a stationary probability distribution; distributions on highly regular graphs or graphs with large automorphism groups often show periodic behavior.This contrasts with the classical random walk’s familiar spreading pattern.Source: §II · pp. 3, 5
  • Walk-amplitude distribution complexity is strongly related to automorphism-group size, and sensitivity to small graph changes motivates using distributions as graph certificates.These observations motivated investigating graph-isomorphism algorithms based on quantum walks.Source: §II · pp. 5–6
  • A walk step on an n-vertex graph can be simulated classically in O(n^4) time using the described direct implementations of the shift and coin operations.The matrix-multiplication bound is at most O(n^6), but the shift and coin can each be implemented with an O(n^4) upper bound.Source: §II · p. 6

III. PROPOSED GI ALGORITHM

Simple quantum walks distinguish graphs that are not walk-equivalent, but can miss similar graphs, including strongly regular graphs with the same parameters. The proposed approach adds phase patterns around reference nodes, using label-invariant vertex and edge groups to distinguish more graphs.

III. PROPOSED GI ALGORITHM

  • Simple walks cannot distinguish all walk-equivalent pairs, including strongly regular graphs with the same parameters and some vertex-transitive graphs.They do distinguish graphs that are not walk-equivalent.Source: §III · p. 7
  • Phase additions can break walk symmetries without changing graph connectivity and can be applied to nodes or edges.The paper describes phase as adding no significant computational cost to the walk.Source: §III · p. 8
  • With multiple reference nodes, paths from those nodes interact, making their geometric connectivity relevant to the resulting walk.The algorithm considers selections of reference nodes and aims to distinguish non-isomorphic pairs through their resulting amplitude distributions.Source: §III · pp. 8–9
  • To avoid dependence on vertex labels, phase additions are restricted to distance-defined vertex groups and the edges within or between those groups.The groups are defined relative to a chosen reference vertex.Source: §III · p. 8

A. Algorithm

The algorithm runs phase-modified walks for every ordered pair of reference nodes, records amplitudes, and compares within-graph and between-graph match tables. A table mismatch certifies non-isomorphism, while the converse remains unproved.

A. Algorithm

  • For each graph, the walk starts in an equal superposition; phase is added around two reference nodes and selected node and edge groups during up to 2n steps.The algorithm records the amplitude at one reference node and repeats the process for all n^2 choices of reference-node pair.Source: A. Algorithm · p. 9
  • Pairwise comparisons among a graph’s amplitude sets form an n^4-entry table, marking matches as 0 and non-matches as 1.These within-graph tables establish a baseline for comparison.Source: A. Algorithm · pp. 9–10
  • The algorithm builds two within-graph tables and a cross-graph table from pairwise comparisons of the amplitude sets.The cross-graph table directly compares amplitude distributions from the two graphs; the within-graph tables compare each graph with itself or its permutations.Source: A. Algorithm · p. 10
  • Repeated walk steps propagate amplitude differences to the measured reference nodes, making their partial states sufficient for the algorithm’s comparisons.The paper describes this propagation as recursively partitioning vertices according to connectivity relative to the reference pair.Source: A. Algorithm · p. 10
  • A mismatch between the cross-graph comparison table and either within-graph table certifies that the graphs are non-isomorphic.The authors report that whether equal tables imply isomorphism remains an open proof question, though computational tests support it.Source: A. Algorithm · p. 10

B. Discussion of algorithm

Two reference nodes are essential because single-node phase propagation cannot distinguish strongly regular graphs with the same parameters. Interactions between paths from multiple reference points can reveal relative connectivity, as illustrated by a pair of 16-vertex strongly regular graphs.

B. Discussion of algorithm

  • A single reference node cannot distinguish strongly regular graphs with the same parameters because phase propagates identically from that node.The paper attributes this to identical counts of paths of each length between points at fixed distance.Source: B. Discussion of algorithm · pp. 10–11
  • With two or more reference points, interacting path amplitudes can expose relative connectivity, which repeated steps propagate through the vertex set.The algorithm’s distinguishing criterion is connectivity relative to all possible reference-point pairs.Source: B. Discussion of algorithm · p. 11
  • For two strongly regular graphs with parameters (16,6,2,2), one reference-node pair matched 144 other pairs in its own graph and none in the other graph.The paper uses this difference in matches to distinguish the graphs.Source: B. Discussion of algorithm · p. 11

C. Complexity of algorithm

The algorithm’s stated running-time bound is O(n^7), based on constructing amplitude sets and comparing them. This bound excludes the precision potentially needed to resolve amplitude differences, which the authors leave as an open issue.

C. Complexity of algorithm

  • O(n^7) is the stated upper-bound scaling of the algorithm in its present form.Constructing amplitude sets takes O(n^7), while the comparisons add O(n^4).Source: C. Complexity of algorithm · p. 12
  • The complexity calculation does not account for the precision required to compare probability amplitudes.The authors note that relevant differences could be exponentially small relative to graph size.Source: C. Complexity of algorithm · p. 12
  • Whether amplitude-precision demands can be circumvented, at least in the classical case, is left for further study.The paper identifies relative rather than absolute amplitude values as a possible basis for such a workaround.Source: C. Complexity of algorithm · p. 12

D. Addendum to the algorithm - finding an isomorphism

The addendum extends the walk-based test to seek an explicit isomorphism when a graph pair is not distinguished. Its polynomial-time outcome is either a verified isomorphism, a non-isomorphism result, or evidence that the algorithm does not solve GI.

D. Addendum to the algorithm - finding an isomorphism

  • The extension relies on the Turing equivalence of testing graph isomorphism and finding an isomorphism between isomorphic graphs.Matches from the relabeled comparisons are assembled into a mapping and checked.Source: D. Addendum to the algorithm - finding… · p. 12
  • For an undistinguished pair, the method fixes one node’s label in each graph and repeats the comparison across all n^2 node pairs.The labeling can be fixed by adding a self-loop or gadget.Source: D. Addendum to the algorithm - finding… · p. 12
  • The addendum makes each comparison end in a verified isomorphism, a definite non-isomorphism result, or proof that the algorithm does not solve GI.A candidate mapping is checked against the graphs’ adjacency matrices.Source: D. Addendum to the algorithm - finding… · p. 13

IV. TESTING ALGORITHM

The algorithm was tested pairwise on varied graph classes, including strongly regular graphs and projective planes. It distinguished every non-isomorphic pair tested, while a simpler two-phase variant missed some especially similar pairs.

IV. TESTING ALGORITHM

  • The tests included many strongly regular graphs with shared parameters and projective-plane groups, chosen as difficult cases for graph distinction.All graphs in each selected group were compared pairwise.Source: §IV · p. 13, Table I · p. 14, Table II · p. 15
  • For 32,548 strongly regular graphs with parameters (36,15,6,6), 2 × 10^5 of 5.3 × 10^8 pairs shared the incomplete certificate and required direct comparison.The certificate reduced the number of direct comparisons; all tested non-isomorphic graphs were distinguished.Source: §IV · pp. 13–14
  • All non-isomorphic graphs tested were successfully distinguished by the algorithm.The tests included groups of strongly regular graphs and other graph classes, with graphs compared pairwise.Source: §IV · pp. 13–14
  • The simple two-phase scheme distinguished all tested pairs except a pair of strongly regular graphs with parameters (40,12,2,4).The exception was the point graph of GQ(3,3) and its dual; the original scheme with further phase additions was required for some generalized-quadrangle dual pairs.Source: §IV · pp. 14–15

V. QUANTUM IMPLEMENTATION

The quantum version compares graph-walk amplitudes through an added connecting node, using repeated measurements rather than direct access to the probability distribution. Its stated scaling depends on assumptions about amplitude differences and measurement probability.

V. QUANTUM IMPLEMENTATION

  • Quantum access requires repeated measurements because the evolving probability-amplitude distribution is not directly available, making the algorithm non-deterministic.The quantum process is also constrained to be unitary.Source: §V · p. 16
  • A connecting node compares amplitudes from the two graphs: equal amplitudes cancel under a π-phase shift, while unequal ones can produce a non-zero measurement.The method requires repeated measurements to reach the desired accuracy.Source: §V · p. 16
  • For fixed accuracy, the stated measurement count is O(log(n)) when the average probability at a node scales as 1/n^c for some constant c.The estimate assumes the non-zero measurement probability remains constant at each step.Source: §V · p. 17
  • The quantum algorithm scales as O(n^5log(n)^2) < O(n^6), assuming efficient quantum-walk steps.Its comparisons cycle over n^4 combinations, with O(n) steps and an O(log(n)) cost per walk step.Source: §V · p. 17
  • The polynomial-time estimate is conditional: if non-isomorphic graphs’ amplitude differences shrink exponentially with graph size, the complexity may no longer be polynomial.The quantum complexity consideration likewise assumes amplitude differences scale at worst polynomially with graph size.Source: §V · p. 17
  • The walk accesses at most n(n−1) states, so its polynomially growing state space permits classical simulation in polynomial time.The passage gives an upper bound of n^2 memory and says the quantum implementation requires only log(2e) qubits for e edges.Source: §V · p. 17

VI. CONCLUSION

The conclusion presents quantum walks as a way to distinguish graph pairs and reports successful tests on the non-isomorphic graphs examined. It also identifies unresolved questions about general-graph performance and the reach of classical simulation.

VI. CONCLUSION

  • For polynomially growing state spaces without noise or quantum measurements, the authors say quantum walks can be efficiently implemented classically.They leave open which quantum-walk algorithms cannot be implemented classically.Source: §VI · p. 18
  • The classical walk-based algorithm distinguished all tested non-isomorphic graphs, but whether it distinguishes general graphs remains open.The authors identify proving its general performance as future work.Source: §VI · p. 18
  • The authors identify path interactions as the key property used to distinguish graphs and propose quantum walks as candidates for problems requiring rapid state-space sampling and path-interaction control.Walk derivatives with multiple-step memories are also suggested for future study.Source: §VI · p. 18
Loading 0705.2531v2…