Sovereign 8s.is mirror of standardgalactic/qemc-pennylane
Find a file
Repository files (latest commit first)
Filename Latest commit message Latest commit date
Yovav Cohen Tene 4e64089b5d Add optional --seed argument for reproducibility
- Backward compatible: seed defaults to None (random behavior)
- When provided, sets np.random.seed for deterministic results
- Usage: --seed 42
2026-01-27 02:00:16 +02:00
data Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
figures Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
google_graphs Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
regular_graphs Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
.gitignore Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
.python-version Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
create_graph.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
dbAdapter.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
DbAdapterGraph.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
dbAdapterMariaDB.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
dbAdapterPandas.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
Goemans-Williamson.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
HWRuns.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
pyproject.toml Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
README.md Add training example image to README, remove unused DrawGraphFromDb 2026-01-25 09:46:28 +02:00
requirements.txt Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
run_examples.py Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
training_all_graphs.png Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
training_example.png Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
uv.lock Initial commit: Clean QEMC implementation 2026-01-25 09:46:20 +02:00
with_ent_general_db.py Add optional --seed argument for reproducibility 2026-01-27 02:00:16 +02:00

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

QEMC vs GW 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

  1. Clone the repository:
git clone <repository-url>
cd qemc-pennylane-clean
  1. 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
Training example on 8-node graph

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 format
  • layers: Number of entangling layers
  • stepsize: Learning rate (0.5-0.95 typical)
  • steps: Optimization iterations
  • shots: Measurement shots (-1 for exact simulation)
  • backend: sim for local simulator, or IBM backend name
  • comment: Experiment description
  • expected_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:

  1. Get an account at https://quantum-computing.ibm.com/
  2. Edit with_ent_general_db.py with your credentials:
provider = IBMQ.enable_account(
    "YOUR_TOKEN_HERE",
    hub='YOUR_HUB',
    group='YOUR_GROUP',
    project='YOUR_PROJECT'
)
  1. 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