- Python 100%
| Filename | Latest commit message | Latest commit date |
|---|---|---|
- Backward compatible: seed defaults to None (random behavior) - When provided, sets np.random.seed for deterministic results - Usage: --seed 42 |
||
| data | ||
| figures | ||
| google_graphs | ||
| regular_graphs | ||
| .gitignore | ||
| .python-version | ||
| create_graph.py | ||
| dbAdapter.py | ||
| DbAdapterGraph.py | ||
| dbAdapterMariaDB.py | ||
| dbAdapterPandas.py | ||
| Goemans-Williamson.py | ||
| HWRuns.py | ||
| pyproject.toml | ||
| README.md | ||
| requirements.txt | ||
| run_examples.py | ||
| training_all_graphs.png | ||
| training_example.png | ||
| uv.lock | ||
| with_ent_general_db.py | ||
Qubit Efficient MaxCut Solver (QEMC)
A quantum computing implementation for solving the Maximum Cut (MaxCut) problem using PennyLane, with support for both quantum simulators and real quantum hardware (IBM Quantum).
Paper Reference
This code implements the algorithms described in:
"A Variational Qubit-Efficient MaxCut Heuristic Algorithm" arXiv:2308.10383 Link: https://arxiv.org/abs/2308.10383
Overview
MaxCut is a fundamental NP-hard optimization problem in graph theory. Given a graph, the goal is to partition the nodes into two sets such that the number of edges between the sets is maximized.
This project implements a variational quantum algorithm that encodes graph nodes in qubit amplitudes, requiring only log2(n) qubits for an n-node graph. This makes it significantly more qubit-efficient than traditional QAOA approaches.
Key Features
- Qubit-efficient encoding: only
log2(n)qubits needed for n-node graphs - Quantum circuit implementation using PennyLane with StronglyEntanglingLayers
- Support for both local simulation and IBM Quantum hardware
- Experiment tracking with pandas (parquet files) or MariaDB
- Comparison with classical Goemans-Williamson algorithm
- Scalable to graphs with up to 8192+ nodes
Performance
The figure shows QEMC performance compared to the Goemans-Williamson algorithm:
- Top: Maximum cut ratio (Max(QEMC)/Max(GW))
- Bottom: Average performance ratio (Avg(QEMC)/Avg(GW))
- QEMC achieves near-optimal performance (ratio close to 1.0) across graph sizes from 16 to 2048 nodes
Quick Start
Prerequisites
This project uses uv for fast Python package management.
Install uv:
# macOS/Linux
curl -LsSf https://astral.sh/uv/install.sh | sh
# Windows
powershell -ExecutionPolicy ByPass -c "irm https://astral.sh/uv/install.ps1 | iex"
# Or with pip
pip install uv
For more installation options, see: https://docs.astral.sh/uv/getting-started/installation/
Setup
- Clone the repository:
git clone <repository-url>
cd qemc-pennylane-clean
- Install dependencies with uv:
uv sync
Run the Example
Run the example script to see QEMC in action on multiple graph sizes with different learning rates:
uv run python run_examples.py
This will:
- Run QEMC on 4 different graph sizes (8, 10, 12, 14 nodes)
- Test 3 different learning rates for each graph
- Generate a combined plot showing training progress
- Save results to
training_all_graphs.png
Run a Single Experiment
uv run python with_ent_general_db.py <expected_blacks> <graph_file> <layers> <stepsize> <steps> <shots> <backend> <comment> <expected_maxcut>
Example (8-node graph, local simulation):
uv run python with_ent_general_db.py 4 google_graphs/vertices_regular_3_size_8_ind_0.g6 3 0.9 50 -1 sim "test_run" 10
Parameters:
expected_blacks: Target nodes in one partition (usually n/2)graph_file: Path to graph in g6 formatlayers: Number of entangling layersstepsize: Learning rate (0.5-0.95 typical)steps: Optimization iterationsshots: Measurement shots (-1 for exact simulation)backend:simfor local simulator, or IBM backend namecomment: Experiment descriptionexpected_maxcut: Known optimal value (for early stopping)
Project Structure
qemc-pennylane-clean/
├── with_ent_general_db.py # Main quantum algorithm
├── dbAdapter.py # Storage backend switch (pandas/mariadb)
├── dbAdapterPandas.py # Pandas backend (default)
├── dbAdapterMariaDB.py # MariaDB backend
├── Goemans-Williamson.py # Classical GW algorithm
├── run_examples.py # Example script with plots
├── google_graphs/ # Test graphs (8-32 nodes)
├── regular_graphs/ # Larger graphs (up to 8192 nodes)
├── data/ # Saved experiment data
└── figures/ # Performance plots
Storage Backend
By default, experiment results are saved to parquet files in data/. To use MariaDB instead, edit dbAdapter.py:
STORAGE_BACKEND = "mariadb" # Change from "pandas"
IBM Quantum Hardware
To run on IBM Quantum hardware:
- Get an account at https://quantum-computing.ibm.com/
- Edit
with_ent_general_db.pywith your credentials:
provider = IBMQ.enable_account(
"YOUR_TOKEN_HERE",
hub='YOUR_HUB',
group='YOUR_GROUP',
project='YOUR_PROJECT'
)
- Use an IBM backend name instead of
sim
Citation
If you use this code in your research, please cite:
@misc{tenecohen2023variationalqubitefficientmaxcutheuristic,
title={A Variational Qubit-Efficient MaxCut Heuristic Algorithm},
author={Yovav Tene-Cohen and Tomer Kelman and Ohad Lev and Adi Makmal},
year={2023},
eprint={2308.10383},
archivePrefix={arXiv},
primaryClass={quant-ph},
url={https://arxiv.org/abs/2308.10383},
}
License
This project is licensed under the Apache License 2.0.
Acknowledgments
- IBM Quantum Network for hardware access
- PennyLane team for the quantum computing framework
- NetworkX for graph processing
