QUBO Formulation with Penalty Functions Solves Set Splitting with Linear Logical Qubit

The Set Splitting problem, a fundamental challenge in computer science, seeks efficient ways to divide a collection of items into distinct, non-overlapping groups, and has implications for fields ranging from biology to cybersecurity. Sean Borneman from Bloomington High School South presents a novel approach to this problem, utilising quantum annealing to identify optimal solutions. This research demonstrates a method that scales linearly with problem size, offering a potential advantage over traditional computational methods, and achieves high accuracy in finding globally optimal solutions through carefully designed penalty functions. While current quantum hardware presents limitations in qubit requirements, this work establishes a promising pathway towards accelerating solutions for complex problems and opens avenues for further investigation into robust quantum formulations.

Efficiently solving this problem has implications for various fields, including scheduling, resource allocation, and data clustering, motivating the exploration of novel solution techniques. This involves mapping the problem’s constraints and objective function into a form that can be directly processed by the quantum hardware. The core idea is to translate the problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem, which can then be executed on the quantum annealer. The authors concentrate on a specific QUBO construction approach and evaluate its performance in terms of scalability, accuracy, and solution time.

The research highlights the difference between the theoretical number of qubits required and the physical qubits needed due to hardware limitations, observing that the number of physical qubits increases rapidly with problem size. For problems up to a certain size, the solution achieves a very low error rate. Addressing hardware limitations, such as connectivity and qubit count, is crucial to improve the scalability of quantum annealing solutions. Improvements in qubit topology and embedding methods are essential. Quantum annealing is a metaheuristic for finding the global minimum of a given objective function over a set of candidate solutions, leveraging quantum-mechanical effects to explore the solution space more efficiently than classical algorithms.

QUBO is a mathematical model used to represent optimization problems in a form suitable for quantum annealing, involving finding the values of binary variables that minimize a quadratic function. Logical qubits represent the theoretical minimum number of qubits required to represent a problem, while physical qubits are the actual number used on a quantum computer, often higher than the number of logical qubits due to hardware limitations. The research successfully formulates the problem using a quantum annealing approach, specifically leveraging a QUBO formulation with penalty functions. This formulation ensures that valid solutions, which correctly split input subsets, correspond to the lowest energy state of the QUBO Hamiltonian, and importantly, scales linearly with problem size in terms of logical qubits. Empirical tests demonstrate the algorithm’s ability to converge towards globally optimal solutions with high accuracy across repeated trials.

While the theoretical time complexity offers potential advantages over classical algorithms, the current limitations of quantum annealing hardware introduce a rise in required physical qubits. The authors acknowledge this discrepancy between theoretical and practical qubit requirements, noting that improvements in hardware development could mitigate this issue. Future research directions include enhancing the robustness of the formulation, reducing qubit demands for complex problems, and conducting more comprehensive benchmarking to further validate the algorithm’s performance and scalability.