Quantum Computers Now Seek Best Probability, Not Just Single Answers

A new approach to hypergraph partitioning, developed by Cameron Ibrahim at the United States Naval Academy and colleagues from Los Alamos National Laboratory and University of Delaware, treats the problem as requiring a probability distribution over potential solutions rather than a single optimal outcome. This distributional perspective, inspired by objectives like Fair Cut Cover, aligns with the natural output of the Quantum Approximate Optimisation Algorithm (QAOA). They have created QAOA-based solvers capable of natively representing these distributional solutions and introduced a new problem, the Greatest Expected Imbalance, to illustrate the formulation’s utility. Experiments on both real-world and synthetic hypergraphs reveal that low-depth multi-angle QAOA can surpass classical approximation algorithms based on semidefinite programming, suggesting a potential advantage for quantum algorithms in tackling optimisation problems demanding distributional solutions.

Quantum optimisation enhances hypergraph partitioning performance sharply

Low-depth multi-angle QAOA outperforms classical approximation algorithms, achieving a 7-10% improvement in objective function values on real-world and synthetic hypergraphs. This surpasses the limitations of previous methods reliant on semidefinite programming and hyperplane rounding, which struggled to find solutions with comparable quality, particularly for larger, more complex hypergraphs. The research introduces a new approach to hypergraph partitioning by framing it as a problem requiring a probability distribution over potential solutions, rather than a single optimal outcome, enabling the native representation of distributional solutions via quantum algorithms.

Further analysis showed that low-depth multi-angle QAOA could outperform classical approximation algorithms based on semidefinite programming on proposed objectives, highlighting potential benefits for optimisation problems where the solution is a distribution rather than a single partition. For the Greatest Expected Imbalance problem, QAOA natively represented distributional solutions through quantum states, aligning with objectives such as Fair Cut Cover. These formulations connect balanced hypergraph partitioning, polarized community discovery, and distributional fairness within a unified quantum optimisation framework. Experiments utilising real-world and synthetic hypergraphs showed QAOA’s ability to closely mirror solutions found by exact solvers when identifying Pareto fronts, indicating a high degree of solution quality. However, these gains were observed on hypergraphs with a maximum of 20 vertices, and it remains unclear if this advantage will extend to larger, more complex problems demanding substantial computational resources.

Quantum optimisation of hypergraphs for partitioning, community detection and fairness

Professor Cameton and colleagues explore QAOA-based quantum solvers that represent distributional solutions natively through quantum states, together with quadratic hypergraph objectives suitable for standard and multi-objective QAOA. These formulations connect balanced hypergraph partitioning, polarized community discovery, and distributional fairness under a unified quantum optimisation framework. To facilitate reproducibility, the team have made source code and data available at https://github.com/cameton/QuantumHypergraphPartitioning, alongside optimal polynomial-time classical approximation algorithms based on semidefinite programming and hyperplane rounding. Most quantum optimisation workflows treat measurement randomness as a nuisance, repeatedly sampling a circuit only to extract one best solution.

This paper adopts an opposing view, recognising that when the application itself calls for a distribution over partitions, the probabilistic output of a quantum algorithm becomes the solution object rather than a byproduct. Naturally probabilistic quantum computers need not be forced to solve deterministic optimisation problems, unlike most work on quantum algorithms for optimisation which focuses on finding a single high-quality solution. Hypergraphs are an abstract mathematical structure used to model relationships between groups of individuals, generalizing the pairwise relationships more commonly modelled by graphs.

A classical formulation of Hypergraph Partitioning generally aims to find a single assignment of the nodes onto two disjoint sets to minimise the size of the cut, ie, the number of hyperedges which contain at least two vertices assigned to different sets, while maintaining some balance constraint on the size of the two partitions. Maximising the size of the cut is known as the Max Set Splitting problem. Hypergraph Partitioning serves as a generalisation of Graph Partitioning, where an integer label is assigned to each vertex and edges or hyperedges are scored based on label differences.

Distributional optimisation is a branch of optimisation concerned with finding a distribution over solutions to a problem which, in expectation, achieves a desired outcome. These frameworks are often challenging to handle classically, potentially requiring many solutions for the target problem to be found and maintained in memory, but can offer significant benefits such as lower expected cost or fairer outcomes on average. The team provide a distributional perspective on the Hypergraph Partitioning problem, aiming to utilise the probabilistic nature of quantum computing to natively represent distributional solutions.

Specifically, they formalize three different variations of the distributional Hypergraph Partitioning problem, well-suited to a quantum approach. They introduce a distributional formulation of Hypergraph Partitioning, which they call the Greatest Expected Imbalance problem, aiming to find a distribution over partitions that minimizes the greatest expected imbalance across hyperedges, a quadratic measure of the separation of vertices within a given edge. The second formulation examines the total imbalance of edges in the hypergraph, directly generalizing the standard graph partitioning formulation. Finally, they extend this problem to create a multi-objective formulation of the Hypergraph Partitioning problem to generalize the concept of Balanced Hypergraph Partitioning. They also introduce a hybrid quantum-classical approach used to solve these three problems based on QAOA, and provide classical approximation algorithms for each problem based on semidefinite programming and hyperplane rounding.

Quantum partitioning of hypergraphs demonstrates initial success with binary divisions

Scientists are increasingly applying quantum computing to optimisation problems, shifting away from seeking single solutions towards probabilistic distributions. This approach offers potential benefits in areas like fair resource allocation and identifying community structures within complex networks. While the Hypergraph Partitioning is generally defined on k disjoint partitions, this paper limits k to 2, which still keeps the problem NP-hard. By reframing hypergraph partitioning as a search for distributional solutions, rather than single optimal assignments, this work unlocks a new approach to quantum optimisation.

Hypergraphs, generalisations of graphs where edges can connect any number of nodes, are increasingly used to model intricate relationships in areas like social networks and logistics. QAOA can surpass classical methods when seeking a range of potential solutions, aligning with objectives such as fair division and community detection. Current experiments remain limited to partitioning hypergraphs into just two disjoint sets, a simplification that may not translate to real-world scenarios demanding more granular divisions.

Scientists demonstrated that quantum algorithms can effectively find probability distributions over hypergraph partitions, rather than a single best solution. This is significant because it provides a new method for tackling optimisation problems where fairness or a range of possibilities are important, such as resource allocation or identifying groups within networks. The research focused on partitioning hypergraphs into two sets, and QAOA outperformed classical algorithms on the defined objectives. The authors suggest this work establishes a framework connecting balanced hypergraph partitioning, community discovery, and distributional fairness.