Quantum Annealing for the Set Splitting Problem

Sean Borneman · 2025

Read Quantum Annealing for the Set Splitting Problem by Sean Borneman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06410.txt.

Introduction

Sean Borneman applies quantum annealing to a splitting problem in twenty twenty-five. Set splitting asks for a two-coloring of elements so no given subset is monochromatic. It is a classic hard combinatorial problem. Borneman casts it as a QUBO problem, the native language of quantum annealers.

The contribution lies in the penalty functions. They are built so the QUBO ground state corresponds exactly to valid splits of every subset. Logical qubit needs grow linearly with problem size in the formulation. Empirical tests converged to globally optimal solutions with high accuracy over repeated trials. Current hardware, though, inflates physical qubit counts exponentially when embedding. Readers get a clean formulation whose promise waits on better annealer hardware.

Catalog record

CREATORSean Borneman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06410

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Annealing for the Set Splitting Problem Sean Borneman Abstract 1 Introduction This paper presents a new algorithm for Set Splitting and Max Set Splitting problem (also known as the Hypergraph Coloring Problem). The Set Splitting problem states: Given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. The Optimization version, The Max Set Splitting Problem, is the optimization variant of the problem which asks for the Split which maximizes the number of subsets in F that are split by the partition of S_{1} and S_{2} . There are a few special cases of this problem. If each set in F is restricted to a cardinalityy of k , i.e each subset in F has k elements, it is referred to as the k-Set-Splitting Problem, a special case of this - where k=2 - is know as the Max-Cut problem ( Guruswami 2004a ). This paper attempts to leverage quantum computing which has the potential to dramatically reduce the time and number of operations, required to solve the Set Splitting problem. Conventionally, the k-set-splitting problem has been simplified with kernalization algorithms for a time complexity of O(1.9630^{n}+N) where n is the number of elements and N is the size of the instance ( Lokshtanov & Saurabh 2009a ). Quantum annealing has the potential to out pace such conventional methods, while also providing exact solutions, with it’s low time complexity of O(e^{\sqrt{n}}) where n is the problem size (number of qubits) ( Mukherjee & Chakrabarti 2015a ). Quantum annealing, an adiabatic method of quantum computing, uses quantum fluctuations to find the global minimum of a given function. Quantum annealing is used to solve optimization problems, such as RNA folding, Portfolio Optimization, as well as the Hamiltonian Cycle problem and Shortest Vector Problem ( McGeoch et al. 2019a ). The current largest Quantum Annealer hardware, the D-Wave Advantage, can support up to 5760 qubits. It has already been proven that quantum annealing can solve the Hamiltonian cycle problem ( Mahasinghe et al. 2019a ), and the traveling salesman problem ( Matai et al. 2010a ) with potential to outpace classical solutions, it does however, remain to be seen if a quantum solution to the Set Splitting Problem exists. 2 Background The Set Splitting Problem is an NP-Complete problem meaning that it cannot be solved by a classical computer in polynomial time, however a given answer can be verified in polynomial time (i.e. the time to solve scales polynomially with the number of elements). This work presents a novel quantum algorithm for solving the Set Splitting and Max Set Splitting Problem designed for the adiabatic framework of quantum computation. The adiabatic framework is used because it allows for more qubits to be used for calculations than can currently be used on the best available quantum circuit computers which currently have a maximum of 1000 qubits, meaning that although they allow for more control, since individual logic gates in the form of matrix operations can be placed on each qubit, the size of the problems they can currently solve are much smaller than on a Quantum Annealer. Regarding applications, the Set Splitting problem has a variety of commercial and research applications; most notably in the analysis of Micro-array data, a data set of DNA and gene expression requiring computer analysis ( Chen & Lu 2009a ). When this data is viewed as a matrix of samples, then DNA set splitting can be used to form a rough hypothesis for the genes responsible for the expression of various phenotypes, such as for the emergence of cancer tumors ( Dehne et al. 2003a ). The Set Splitting problem can also have benefits to cybersecurity and network organization when used as a graph coloring algorithm. In the domain of cybersecurity, servers, endpoints, and network nodes can be modelled as graph vertices, with connectivity edges representing attack vectors. Solving a set-splitting problem for such a representation can allow one to partition security controls to isolate risks. Networks of multiple high permission computers leave themselves open to Stuxnet type attacks where a single computer has elevated permissions on a large network. By splitting this network such that susceptible nodes are in separate fire-walled subnets we can improve the security of a organizations network. Quantum annealing uses quantum fluctuation to solve optimization problems. As opposed to simulated annealing (a probabilistic algorithm runnable on a conventional computer) which relies on modeling thermal fluctuations to find the global minimum, Quantum annealing takes advantage of quantum fluctuations such as quantum tunneling to transition between local minima ( Ray et al. 1989a ). Quantum annealing can be more efficient than simulated annealing thermal fluctuations, because conventionally, high energy barriers between local minima are extremely hard to overcome and simulated annealing therefore can only address one possible solution at a time, which leads to an increase in time as the problem space increase. However in quantum annealing the entire problem space is seen at once, leading to much faster ground state (global optimization) calculations ( Das 2005a ). Quantum Annealing relies on finding the energetic ground state of a Hamiltonian where the ground state of that Hamiltonian corresponds to the solution to the computation. Quantum Annealers, the hardware responsible for this process, encode the coefficients of some Ising Hamiltonian or quadratic unconstrained binary optimization (QUBO) onto the qubits of a quantum computer which then returns the solution vector z that minimizes the energy of the Hamiltonian (see equation 1 ): H(z)=\sum_{i=1}^{L}Q_{i,i}z_{i}+\sum_{i<j}^{L}Q_{i,j}z_{i}z_{j} (1) where L is the number of qubits and z is the solution vector where z_{i}\in{-1,1} for Ising Hamiltonian’s, and z_{i}\in{0,1} for QUBO formulations, the latter of which will be used for the remainder of this paper ( McGeoch 2020a ). The largest downsides of the current generation of quantum annealers are mapping, and solution reliability. The mapping issue exists because the modern topologies of quantum annealers do not have perfect connectivity between every possible logical qubit. In the current generation of D-wave Advantage QPU’s the Pegasus architecture allows for qubits to have a nominal length of 12 and a degree of 15 meaning each qubit is connected to 12 orthogonal qubits through internal couplers, and 15 qubits through internal and external couplers.( Boothby et al. 2020a ). In practice, this means that despite some example problem only theoretically requiring 75 logical qubits (ones expressed in the problem Hamiltonian and which directly determine the solution), it may actually require 340 to be encoded onto the QPU, because of the non-perfect inter-connectivity. Separately, the issue of solution reliability is inherent to adiabatic solvers, but it does mean that on any given calculation, the final output may not correspond to the ground state of the problem Hamiltonian ( Boixo et al. 2014a ). 3 Quantum Annealing formulation for Set Splitting problem I present a method of encoding the Set Splitting, and Max Set Split problem as a Hamiltonian H, such that the energetic ground state corresponds to the S_{1} and S_{2} solutions. I also present the results of

Read the complete text