Quantum Combinatorial Optimization

Combinatorial Optimization

Combinatorial optimization problems involve finding the best solution from a finite set of candidates:

where is a discrete solution space. Many are NP-hard, requiring exponential time classically.

Quantum approaches aim to find solutions faster or with better approximation guarantees.

MaxCut

MaxCut: partition vertices of a graph to maximize edges between partitions:

where . The Goemans-Williamson algorithm achieves 0.878 approximation classically.

QAOA provides a quantum approach with potential speedup for specific graph classes.

Traveling Salesman Problem (TSP)

TSP: find the shortest tour visiting all cities exactly once:

TSP can be encoded as a QUBO (Quadratic Unconstrained Binary Optimization) problem for quantum annealing:

where encodes distances and constraints.

Portfolio Optimization

Portfolio optimization selects assets to maximize return while minimizing risk:

subject to and .

The quantum approach:

1. Discretize weights
2. Encode as QUBO problem
3. Solve with quantum annealing or QAOA

QUBO Formulation

Many combinatorial problems can be written as QUBO:

where and is an upper triangular matrix.

The QUBO formulation enables:

• Direct implementation on D-Wave quantum annealers
• QAOA encoding
• Hybrid quantum-classical solvers

Quantum Speedups

Potential quantum speedups for optimization:

The practical advantage depends on problem structure and hardware noise.

Python: MaxCut QUBO

import numpy as np

def maxcut_qubo(graph, n):
    # Formulate MaxCut as QUBO problem.
    Q = np.zeros((n, n))
    for i, j in graph:
        Q[i, i] += 1
        Q[j, j] += 1
        Q[i, j] -= 2
    return Q

def qubo_energy(Q, x):
    # Compute QUBO energy.
    return x @ Q @ x

graph = [(0,1), (1,2), (2,3), (3,0), (0,2)]
n = 4
Q = maxcut_qubo(graph, n)

# Brute force search
best_energy = float('inf')
best_x = None
for x_int in range(2**n):
    x = np.array([(x_int >> i) & 1 for i in range(n)])
    e = qubo_energy(Q, x)
    if e < best_energy:
        best_energy, best_x = e, x

print(f"Best solution: {best_x}")
print(f"QUBO energy: {best_energy}")

QUBO Examples

Maximum Independent Set:

Graph Coloring:

Set Cover: