Learning Cut Distributions with Quantum Optimization

1. Problem Definition

The paper addresses a specific class of combinatorial optimization problems known as maximin fairness problems. Unlike standard optimization, which seeks a single solution maximizing an average objective (e.g., MaxCut), this problem seeks a probability distribution over solutions that maximizes the worst-case outcome.

• Core Problem: The Fair Cut Cover problem.
  • Given a graph $G=(V, E)$, the goal is to find a probability distribution $p$ over all possible cuts such that the minimum edge-cut probability is maximized.
  • Mathematically: $\bar{\eta}(G) = \max_p \min_{e \in E} P_e(p)$, where $P_e(p)$ is the probability that edge $e$ is cut under distribution $p$.
  • This is the probabilistic dual of the Fractional Cut Cover problem (minimizing the total weight of cuts to cover every edge at least once).
• The Challenge: The support of an optimal distribution can be exponential in size, making it intractable to represent explicitly using classical methods. Classical approaches typically rely on Semidefinite Programming (SDP) relaxations followed by randomized hyperplane rounding. However, the paper argues that the space of distributions generated by SDP + rounding is strictly limited and cannot capture the optimal distribution for certain graph structures (e.g., complete graphs).

2. Methodology

The authors propose a Quantum Variational Algorithm based on the Quantum Approximate Optimization Algorithm (QAOA) to learn these distributions directly.

A. Quantum Formulation

• Native Distribution: A quantum state $|\psi(\theta)\rangle$ naturally induces a probability distribution over bitstrings (cuts) upon measurement in the computational basis.
• Objective Function: The goal is to maximize the minimum edge cut probability. For an edge $e=(u,v)$, the cut probability is $P_e = \frac{1 - \langle \psi | Z_u Z_v | \psi \rangle}{2}$.
• Optimization: The problem is framed as a variational optimization:
  $$\max_{\theta} \min_{e \in E} \frac{1 - \langle \psi(\theta) | Z_u Z_v | \psi(\theta) \rangle}{2}$$
• Smooth Approximation: Since the $\min$ function creates a non-smooth loss landscape (hindering gradient-based optimization), the authors employ a LogSumExp (SoftMin) approximation to smooth the objective, enabling the use of gradient-based optimizers (like Adam) and parameter-shift rules for gradient estimation on quantum hardware.

B. The D-QAOA Ansatz

To ensure the quantum circuit can represent any relevant distribution, the authors introduce Distributional QAOA (D-QAOA), a modification of the Multi-angle QAOA (ma-QAOA):

• Expressibility: Standard QAOA may fail to reach the full space of distributions for certain graph topologies (e.g., paths or cycles).
• Modification: D-QAOA adds ancilla qubits and specific coupling terms (e.g., $Z_v Z_A$) to the phase separator and mixer unitaries if the graph is disconnected, a path, or a cycle.
• Theoretical Guarantee: This modification ensures that the circuit's reachable unitary group acts transitively on the relevant subspace, allowing the circuit to approximate any $Z_2$-symmetric cut distribution to arbitrary precision given sufficient layers.

3. Key Contributions

1. Quantum-Classical Separation in Distribution Space:

   • The paper proves that the space of distributions achievable by SDP + Hyperplane Rounding ($D_{hr}$) is a strict subset of the space of all $Z_2$-symmetric cut distributions ($D$).
   • Specifically, for complete graphs $K_n$ ($n \geq 4$), the optimal Fair Cut Cover distribution cannot be reproduced by SDP rounding.
   • Theorem 2: For complete graphs, even a 1-layer standard QAOA ($Q^1_{std}$) achieves a strictly better approximation ratio than the best possible SDP + rounding ($SDP_{HR}$).

2. Universality of D-QAOA:

   • The authors establish a universality result (Corollary 1) analogous to the Universal Approximation Theorem for neural networks. They prove that with a sufficient number of layers, D-QAOA can approximate any $Z_2$-symmetric cut distribution on any graph $G$.

3. Monotonicity Properties:

   • The paper analyzes the monotonicity of the objective. While SDP solutions are monotonic with respect to subgraphs, standard QAOA is not guaranteed to be so unless the circuit depth is sufficient to capture the full distribution space. D-QAOA restores this property for deep enough circuits.

4. Handling Non-Smoothness:

   • The introduction of the LogSumExp objective function allows for effective training of the QAOA parameters, overcoming the "barren plateau" and non-differentiability issues associated with the raw min-function.

4. Results

Theoretical Results

• Separation Gap: Proven that for $K_n$ ($n \geq 4$), $Q^1_{std}(K_n) > SDP_{HR}(K_n)$.
• Upper Bounds: Derived new upper bounds for the SDP value based on the size of the maximum clique $\omega(G)$ and the number of vertices $|V|$.

Numerical Simulations

• Graphs Tested: Random graphs (Erdos-Renyi) with max clique sizes 4 and 5, and highly symmetric graphs (Petersen, Clebsh, Paley, Shrikhande).
• Performance:
  • 2-3 layers of D-QAOA consistently outperformed the SDP + Hyperplane Rounding baseline.
  • On the Petersen Graph, the optimal value is $0.8$. SDP+HR achieved $\approx 0.732$, while 2-layer D-QAOA reached $\geq 0.740$, and 5-layer reached $\geq 0.798$.
  • Similar improvements were observed on Clebsh and Paley graphs.

Hardware Experiments

• Devices: Experiments were run on Quantinuum H2-2 (56 ions) and Helios-1 (98 ions) trapped-ion devices.
• Instances: 60-node complete graph and smaller graphs (10-15 nodes).
• Findings:
  • Real hardware results showed a degradation of up to 4.1% compared to noiseless simulations.
  • Crucially, the authors attribute this degradation primarily to insufficient sampling (shot noise) rather than device noise, as the approximation ratio improved with more shots.
  • The 60-node complete graph experiment demonstrated the scalability of the approach, though the optimal cut distribution requires an astronomical number of cuts ($10^{16.772}$), highlighting the necessity of learning the distribution rather than enumerating it.

5. Significance and Impact

• Beyond Scalar Optimization: This work shifts the paradigm of quantum optimization from finding a single "best" solution to learning structured probability distributions. This is crucial for applications requiring fairness, robustness, or coverage, where the worst-case performance matters more than the average.
• Provable Quantum Advantage: The paper provides one of the first rigorous proofs of a quantum advantage in optimization that is not just about the objective value, but about the expressibility of the solution space. It demonstrates that quantum circuits can access regions of the solution space (cut distributions) that are fundamentally inaccessible to classical SDP relaxations.
• Near-Term Applicability: By showing that shallow circuits (2-3 layers) can beat classical state-of-the-art approximations on specific graph families, the paper suggests that Noisy Intermediate-Scale Quantum (NISQ) devices can already provide value in distributional optimization tasks.
• Inductive Biases: The authors draw a parallel between D-QAOA and Convolutional Neural Networks (CNNs), suggesting that future research should focus on encoding better inductive biases into QAOA ansatzes to mitigate barren plateaus and improve trainability, much like CNNs revolutionized image processing.

In summary, the paper establishes that quantum variational algorithms are not merely heuristic solvers for scalar objectives but are powerful generative models capable of learning optimal distributions for fairness-critical combinatorial problems, offering a provable advantage over classical relaxation techniques.