qiskit-graph-walks

Quantum walk algorithms for graph problems, built on Qiskit.

Coined and continuous-time quantum walks are usually presented as physics demos of ballistic spreading on a line or a lattice. This package treats them as algorithmic primitives for graph problems instead: spatial search on arbitrary graphs, and graph-invariant fingerprinting for isomorphism testing, both built directly on top of Qiskit circuits so they compose with the rest of the Qiskit ecosystem (transpilation, backends, noise models, etc.).

What's here

Installation

git clone https://github.com/RexRowan/qiskit-graph-walks.git
cd qiskit-graph-walks
pip install -e ".[dev]"

Requires Python >= 3.9, Qiskit >= 2.0, NetworkX >= 3.0.

(Qiskit >= 2.0 is required for eventual submission to the Qiskit Ecosystem -- see CONTRIBUTING.md if this repo is ever proposed as a member.)

Quickstart

Continuous-time quantum walk

import networkx as nx
from qiskit_graph_walks import ContinuousTimeQuantumWalk

G = nx.petersen_graph()
walk = ContinuousTimeQuantumWalk(G)

circuit = walk.circuit(time=2.5, initial_vertex=0)   # a Qiskit QuantumCircuit
probs = walk.probabilities(time=2.5, initial_vertex=0)  # exact per-vertex occupation

Spatial search

from qiskit_graph_walks import SpatialSearch

search = SpatialSearch(nx.complete_graph(16), marked_vertices=7)
result = search.optimize()
print(result.gamma, result.time, result.success_probability)
# -> matches the Childs-Goldstone closed form for the complete graph

circuit = search.circuit(result.gamma, result.time)
circuit.measure_all()

Graph isomorphism testing

from qiskit_graph_walks import are_possibly_isomorphic

result = are_possibly_isomorphic(graph_a, graph_b)
print(result.summary)

Read this before trusting the isomorphism result: a fingerprint mismatch is a genuine proof of non-isomorphism. A fingerprint match is not a proof of isomorphism -- it means the test didn't find a difference, which is not the same thing. See docs/isomorphism.md for what this technique can and can't do, including a worked example of a classic cospectral (but non-isomorphic) graph pair that it does successfully separate.

Documentation

• docs/algorithms.md -- the math behind each algorithm, with references.
• docs/isomorphism.md -- honest treatment of what the isomorphism fingerprint does and doesn't guarantee.
• examples/ -- runnable scripts for each module.

Scope and known limitations

• The Szegedy walk (dtqw.py) builds its step operator as an explicit dense unitary matrix. This is exact and easy to verify, but doesn't scale past small graphs (roughly up to a few hundred vertices before the dense linear algebra becomes the bottleneck). Synthesizing the walk operator into an elementary-gate decomposition for larger graphs is a natural next contribution -- see open issues.
• SpatialSearch.optimize() uses local numerical optimization (Nelder-Mead) seeded from the complete-graph closed form. For graphs very different in structure from the complete graph, consider trying several seeds, since a single local optimizer run is not guaranteed to find the global optimum.
• The isomorphism fingerprint is a heuristic invariant, not a decision procedure. See docs/isomorphism.md.

Development

pip install -e ".[dev]"
pytest tests/ -v

License

Apache 2.0. See LICENSE.

References

• Farhi, E. & Gutmann, S. (1998). "Quantum computation and decision trees." Physical Review A, 58(2), 915.
• Childs, A. M. & Goldstone, J. (2004). "Spatial search by quantum walk." Physical Review A, 70(2), 022314.
• Szegedy, M. (2004). "Quantum speed-up of Markov chain based algorithms." FOCS 2004, 32-41.
• Douglas, B. L. & Wang, J. B. (2008). "A classical approach to the graph isomorphism problem using quantum walks." Journal of Physics A, 41(7), 075303.
• Rudinger, K. et al. (2012). "Comparing algorithms for graph isomorphism using discrete- and continuous-time quantum random walks." J. Comput. Theor. Nanosci.