Metadata-Version: 2.4
Name: qiskit-graph-walks
Version: 0.1.0
Summary: Quantum walk algorithms for graph problems (spatial search, isomorphism testing) built on Qiskit.
Author: Rex Rowan
License: Apache-2.0
Project-URL: Homepage, https://github.com/RexRowan/qiskit-graph-walks
Project-URL: Issues, https://github.com/RexRowan/qiskit-graph-walks/issues
Keywords: qiskit,quantum computing,quantum walk,graph theory,graph isomorphism,spatial search
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: Apache Software License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Physics
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: qiskit>=2.0
Requires-Dist: networkx>=3.0
Requires-Dist: numpy>=1.24
Requires-Dist: scipy>=1.10
Provides-Extra: dev
Requires-Dist: pytest>=7.0; extra == "dev"
Requires-Dist: pytest-cov; extra == "dev"
Requires-Dist: matplotlib; extra == "dev"
Dynamic: license-file

# qiskit-graph-walks

Quantum walk algorithms for graph problems, built on [Qiskit](https://www.ibm.com/quantum/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

| Module | What it does |
|---|---|
| `qiskit_graph_walks.ctqw` | Continuous-time quantum walks (`H = -gamma*A` or the graph Laplacian), circuit construction and exact simulation. |
| `qiskit_graph_walks.dtqw` | Discrete-time (Szegedy) quantum walks -- works on any graph, not just regular ones. |
| `qiskit_graph_walks.search` | CTQW spatial search (Childs & Goldstone, 2004) with automatic parameter optimization for arbitrary graphs. |
| `qiskit_graph_walks.isomorphism` | CTQW-based graph invariants for isomorphism testing -- a genuine proof of *non*-isomorphism when fingerprints differ, a documented heuristic otherwise. |

## Installation

```bash
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](https://qiskit.github.io/ecosystem/) -- see
`CONTRIBUTING.md` if this repo is ever proposed as a member.)

## Quickstart

### Continuous-time quantum walk

```python
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

```python
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

```python
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`](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`](docs/algorithms.md) -- the math behind each
  algorithm, with references.
- [`docs/isomorphism.md`](docs/isomorphism.md) -- honest treatment of
  what the isomorphism fingerprint does and doesn't guarantee.
- [`examples/`](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

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

## License

Apache 2.0. See [LICENSE](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.*
