Quantum Optimization

Optimization Landscape

Many real-world problems reduce to finding the minimum of a cost function:

Classical solvers work well for moderate sizes, but worst-case instances are NP-hard. Quantum optimization algorithms aim to provide speedups for specific problem classes.

QAOA Deep Dive

The QAOA circuit for depth :

Key properties:

• At , QAOA is equivalent to a single layer of alternating rotations
• For MaxCut on 3-regular graphs, gives approximation ratio
• As , QAOA converges to the exact solution

Parameter optimization is performed classically using gradient-based or gradient-free methods.

Quantum Annealing

Quantum annealing uses the adiabatic theorem to solve optimization problems:

where is the total annealing time. If the evolution is slow enough, the system remains in the ground state throughout.

The D-Wave quantum annealer implements this approach with up to 5000+ qubits, though connectivity limitations and decoherence affect performance.

D-Wave Architecture

The D-Wave quantum annealer uses a Chimera or Pegasus graph topology:

• Chimera: unit cells of 8 qubits in bipartite structure
• Pegasus: more connected, enabling denser problem embeddings

Minor embedding maps problem variables to physical qubits, with chains of qubits representing a single logical variable. The energy of a D-Wave system is:

where are biases and are coupling strengths.

Combinatorial Problems

MaxCut: Partition vertices into two sets to maximize edges between them.

Traveling Salesman Problem (TSP): Find the shortest tour visiting all cities.

Portfolio Optimization: Maximize return while minimizing risk.

where is expected returns, is covariance matrix, and is risk aversion.

Hybrid Quantum-Classical Approaches

The most promising near-term approach combines quantum and classical processing:

1. Decompose the problem into subproblems
2. Solve subproblems with quantum annealing or QAOA
3. Combine solutions classically
4. Iterate until convergence

D-Wave's Leap hybrid solver uses this approach and has been applied to logistics, scheduling, and financial optimization problems.

Python: QAOA for MaxCut

import numpy as np

def maxcut_cost(cut, graph):
    # Compute MaxCut cost for a given partition.
    return sum(1 for i, j in graph if cut[i] != cut[j])

def qaoa_expectation(gamma, beta, graph):
    # Compute QAOA expectation for MaxCut (P=1).
    cost = 0
    for i, j in graph:
        cost += 0.5 * (1 - np.cos(2 * gamma) * np.cos(2 * beta))
    return cost

graph = [(0,1), (1,2), (0,2)]

from scipy.optimize import minimize
def objective(params):
    return -qaoa_expectation(params[0], params[1], graph)

result = minimize(objective, [0.5, 0.5], method='COBYLA')
print(f"Optimal gamma: {result.x[0]:.4f}")
print(f"Optimal beta: {result.x[1]:.4f}")
print(f"QAOA value: {-result.fun:.4f}")

This demonstrates the QAOA optimization loop for a simple MaxCut instance.

QAOA Parameter Setting

For MaxCut on 3-regular graphs with :

These analytical results hold for specific graph classes. For general problems, parameter optimization is required.

Parameter concentration: for large graphs, optimal QAOA parameters concentrate around specific values, reducing the optimization landscape complexity.

QAOA Performance Analysis

The QAOA approximation ratio depends on:

1. Graph structure: regular graphs perform better than random graphs
2. QAOA depth : deeper circuits give better solutions
3. Parameter optimization: better parameters improve quality
4. Initial state: is standard, but other initial states may help

For MaxCut on 3-regular graphs:

• : ratio
• : ratio
• : ratio
• Classical best (GW):