Quantum Approximate Optimization Algorithm implemented in Qiskit
Partitions a social network into Influencers vs Followers by solving the Max-Cut problem.

Given a social network graph where:

• Nodes = Users (Alice, Bob, Carol, Dave, Eve, Frank)
• Edges = Friendships / connections
• Edge weights = Interaction strength / influence score

QAOA finds the partition of users into Group A (Influencers) and Group B (Followers) that maximises cross-group connections — the Max-Cut solution.

pip install qiskit qiskit-aer networkx matplotlib scipy numpy

Or using the requirements file:

pip install -r requirements.txt

python qaoa_social_network.py

Edit the bottom of qaoa_social_network.py:

results = run_full_pipeline(
    p           = 1,     # QAOA depth — try 1, 2, or 3
    shots       = 2048,  # Measurement samples per circuit evaluation
    top_k       = 10,    # How many bitstrings to show in probability chart
    save_figures= True,  # Saves all plots as PNG files
)

Higher p → deeper circuit → closer to optimal, but slower to optimise.

The pipeline produces 4 visualisations:

• Blue nodes = Group A (Influencers)
• Red nodes = Group B (Followers)
• Amber dashed edges = Cut edges (maximised by QAOA)
• Grey edges = Non-cut edges

• X-axis: bitstrings (each character = one user, 0=GroupA, 1=GroupB)
• Y-axis: probability of measuring that bitstring
• Bar colour: darker = higher Max-Cut value
• Best solutions cluster at the top

• H gates: initial superposition layer
• Rzz gates: cost unitary U_C(γ) for each edge
• Rx gates: mixer unitary U_B(β) for each qubit
• Repeated p times

• Shows ⟨C⟩ (expected cut value) improving across iterations
• Flat region at the top = convergence achieved

Social Network Graph
       ↓
  Max-Cut QUBO Formulation
  Maximise: Σ(i,j)∈E  wᵢⱼ · (xᵢ + xⱼ − 2xᵢxⱼ)
       ↓
  Ising Hamiltonian
  Hc = Σ(i,j)∈E  (wᵢⱼ/2)(1 − ZᵢZⱼ)
       ↓
  QAOA Circuit  (p layers)
  |ψ(γ,β)⟩ = U_B(βₚ) U_C(γₚ) … U_B(β₁) U_C(γ₁) |+⟩ⁿ
       ↓
  COBYLA Classical Optimiser tunes γ,β
       ↓
  Measurement → Probability Distribution
       ↓
  Best Bitstring = Max-Cut Partition
       ↓
  Group A = Influencers | Group B = Followers

qaoa_social_network.py   ← Main implementation (all-in-one)
requirements.txt         ← Python dependencies
README.md                ← This file

Generated outputs:
social_network_partition.png
probability_distribution.png
qaoa_circuit.png
convergence_curve.png

Cost Function (Max-Cut):

f(x) = Σ_(i,j)∈E  wᵢⱼ · (xᵢ + xⱼ − 2xᵢxⱼ)

Ising Hamiltonian:

Hc = Σ_(i,j)∈E  (wᵢⱼ/2)(1 − Zᵢ⊗Zⱼ)

QAOA State:

|ψ(γ,β)⟩ = [∏ₖ U_B(βₖ) U_C(γₖ)] |+⟩^⊗n

Cost Layer:

U_C(γ) = e^{−iγHc}  =  ∏_(i,j) Rzz(2γwᵢⱼ)

Mixer Layer:

U_B(β) = e^{−iβΣᵢXᵢ}  =  ∏ᵢ Rx(2β)

IBM Quantum — Quantum Computing in Practice, Episode 3 (Olivia Lans, 2024)
https://youtu.be/P3s7TIMIvZ0