QAOA Implementation for MAX-SAT Problems by Christian NeureuterQAOA Implementation for MAX-SAT Problems by Christian Neureuter

QAOA Implementation for MAX-SAT Problems

Portfolio project
Christian Neureuter
View completed work

QAOA for MAX-SAT Problems

A comprehensive Python implementation of the Quantum Approximate Optimization Algorithm (QAOA) for solving MAX-SAT problems including Max-Cut and MAX 3-SAT using Google's Cirq quantum computing framework.
A deep dive into hybrid quantum-classical computing with a comprehensive implementation of the Quantum Approximate Optimization Algorithm (QAOA) to solve NP-hard combinatorial optimization problems. This project tackles multiple variants of the Maximum Satisfiability (MAX-SAT) problem, including Max-Cut on ring graphs (MAX-2-SAT) and general MAX-3-SAT with arbitrary boolean clauses. The implementation features a robust pipeline built with Python and Google's Cirq framework. It constructs parameterized quantum circuits that encode problem Hamiltonians, using standard ZZ gates for Max-Cut and novel, custom-built 3-qubit gates for the more complex MAX-3-SAT instances. A classical Nelder-Mead optimizer iteratively refines the circuit parameters to navigate the solution space and find high-quality approximate solutions. The project includes extensive performance analysis, calculating approximation ratios by benchmarking QAOA results against a classical brute-force solver and demonstrating performance scaling with increased circuit depth.
TECHNOLOGIES USED
Python • Google Cirq
KEY METRICS
2 NP-Hard Problem Classes Solved
90%+ Approximation Ratios Achieved

Project Overview

This project demonstrates a complete implementation of QAOA, a hybrid quantum-classical algorithm that combines quantum circuits with classical optimization to solve combinatorial optimization problems. The implementation covers multiple MAX-SAT problem variants including:
MAX 2-SAT (Ring of Disagrees): Max-Cut problem on ring graphs
MAX 3-SAT: General 3-satisfiability problems with arbitrary boolean clauses

What is QAOA?

QAOA (Quantum Approximate Optimization Algorithm) is a variational quantum algorithm that:
Uses parameterized quantum circuits to prepare quantum states
Employs classical optimization to find optimal parameters
Provides approximate solutions to NP-hard combinatorial problems
Demonstrates potential quantum computational advantages

MAX-SAT Problems

This implementation addresses multiple SAT problem variants:
MAX 2-SAT (Ring of Disagrees):
Finding optimal vertex partitions to maximize disagreeing edges
Ring graph topology with neighboring vertex interactions
Cost function: C ( z ) = ∑ ⟨ j k ⟩ 1 2 ( 1 − σ j z σ k z )
MAX 3-SAT:
General satisfiability problems with 3-literal clauses
Arbitrary boolean clause structures
Custom 3-qubit gates for clause evaluation
Cost function: C ( z ) = ∑ i j k z i z j z k (with possible negations)
Applications: Network design, VLSI circuit design, clustering, constraint satisfaction, and combinatorial optimization

Project Structure

QAOA/
├── README.md                           # This file
├── LICENSE                            # MIT License
├── requirements.txt                   # Python dependencies
├── .gitignore                        # Git ignore patterns
├── notebooks/                        # Jupyter notebooks
│   ├── qaoa-max-sat-implementation.ipynb  # Complete QAOA implementation & analysis
│   ├── qaoa-code-presentation.ipynb       # Clean presentation version
│   ├── qaoa-presentation.ipynb            # Academic presentation notebook
│   └── qaoa-presentation.slides.html      # HTML slide deck
└── docs/                            # Documentation
    ├── algorithm_explanation.md      # Detailed algorithm explanation
    └── QAOA_for_MAX_SAT.pdf         # Academic research paper

Getting Started

Prerequisites

Python 3.7+
Jupyter Notebook
pip or conda

Installation

Clone the repository:
git clone https://github.com/cneureuter/qaoa-max-sat.git
cd qaoa-max-sat
Install dependencies:
pip install -r requirements.txt
Launch Jupyter:
jupyter notebook
Open and run notebooks/qaoa-max-sat-implementation.ipynb

Key Features

Complete QAOA Implementation
Parameterized quantum circuits using Cirq
ZZ gates for MAX 2-SAT (Ring of Disagrees) problems
Custom 3-qubit gates for MAX 3-SAT problems
Rx gates for mixing Hamiltonian
Multiple Problem Formulations
MAX 2-SAT implementation with ring topology
MAX 3-SAT implementation with arbitrary clauses
Proper operator construction for different eigenvalue requirements
Classical Optimization
Nelder-Mead optimization for parameter tuning
Performance tracking and analysis across problem types
Comprehensive Analysis
Circuit depth performance comparison
Approximation ratio calculations
Brute-force optimal solution verification
Statistical analysis of solution distributions
Professional Visualization
Circuit diagrams for different problem types
Performance plots and probability distributions
Clear documentation and explanations

Algorithm Details

Circuit Structure

The QAOA circuit consists of:
Initialization: Hadamard gates create uniform superposition
Problem Layers:
ZZ gates for MAX 2-SAT encoding
Custom 3-qubit gates for MAX 3-SAT encoding
Mixing Layers: Rx gates provide transitions between states
Measurement: Final measurement in computational basis

Mathematical Foundation

MAX 2-SAT (Ring of Disagrees):
Problem Hamiltonian: H C = ∑ ⟨ j k ⟩ 1 − Z j Z k 2
Uses Pauli-Z operators with eigenvalues {+1, -1}
MAX 3-SAT:
Problem Hamiltonian: H C = ∑ i j k z ^ i z ^ j z ^ k
Custom operators: z ^ = 1 2 ( 1 ± σ z ) with eigenvalues {0, 1}
Handles arbitrary 3-literal clause structures
Common Elements:
Mixing Hamiltonian: H M = ∑ i X i
QAOA State: | γ , β ⟩ = ∏ j = 1 p e − i β j H M e − i γ j H C | + ⟩ ⊗ n

Parameter Optimization

The algorithm optimizes two sets of parameters:
γ (gamma): Controls the strength of the problem Hamiltonian
β (beta): Controls the strength of the mixing Hamiltonian

Results

The implementation demonstrates:
Consistent high approximation ratios for both problem types
Performance scaling with increasing circuit depth (p=1,2,3)
Efficient classical optimization convergence
Verification against brute-force optimal solutions
Statistical analysis showing concentration around optimal values

Performance Highlights

Optimal Solutions: Consistently finds optimal solutions for small instances (n≤10)
Problem Versatility: Successfully handles both MAX 2-SAT and MAX 3-SAT formulations
Scalability: Demonstrates performance across different circuit depths
Accuracy: High approximation ratios achieved through parameter optimization
Educational Value: Complete implementation suitable for learning QAOA concepts

Usage Example

# Core QAOA implementation is in the Jupyter notebooks
# Key functions include:

def qaoa_max_sat_circuit(qubits, betas, gammas, clauses, problem_type):
    """Constructs the complete QAOA circuit for MAX-SAT problems"""
    # Implementation in notebooks/qaoa-max-sat-implementation.ipynb

def evaluate_sat_cost(bitstrings_df, clauses, problem_type):
    """Evaluates cost values from measurement results"""
    # Implementation in notebooks/qaoa-max-sat-implementation.ipynb

# Supports both MAX 2-SAT and MAX 3-SAT problem types

Contributing

This project welcomes contributions! Areas for enhancement:
Hardware-specific circuit optimizations
Additional SAT problem variants (MAX k-SAT for k>3)
Performance improvements and error mitigation
Extended documentation and tutorials
Quantum error correction integration

References

Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv:1411.4028
Google Cirq Documentation: https://quantumai.google/cirq
NetworkX Documentation: https://networkx.org/
Academic Paper: QAOA_for_MAX_SAT.pdf (included in docs/)

License

This project is licensed under the MIT License - see the LICENSE file for details.

Academic Context

This project was developed as part of advanced quantum computing coursework at FAU Erlangen-Nuremberg under supervision of Professor Michael Hartmann, demonstrating:
Practical implementation of variational quantum algorithms
Integration of quantum and classical computing paradigms
Performance analysis and optimization techniques
Academic rigor in algorithm development and testing
Professional documentation and presentation skills

Acknowledgments

Professor Michael Hartmann - Project supervision and academic guidance
FAU Erlangen-Nuremberg - Academic institution and research support
Google Cirq Team - Excellent quantum computing framework
NetworkX Development Team - Graph theory and visualization tools

Contact

For questions, suggestions, or collaboration opportunities, please open an issue on GitHub.
Built for quantum computing research and education
Keywords: Quantum Computing, QAOA, MAX-SAT, MAX-3-SAT, Max-Cut, Optimization, Cirq, Python, Boolean Satisfiability, Quantum Algorithms

0 likes · 16 views · Aug 29, 2025

Quantum computing algorithm development, implemented QAOA for MAX-SAT problems using Python and Cirq.

Timeline

Dec 6, 2021 - Feb 7, 2022

Tags