Quantum Annealing for the Set Splitting Problem
- URL: http://arxiv.org/abs/2508.06410v1
- Date: Fri, 08 Aug 2025 15:55:30 GMT
- Title: Quantum Annealing for the Set Splitting Problem
- Authors: Sean Borneman,
- Abstract summary: I present a novel use of quantum annealing to solve the Set Splitting Problem using (QUBO) problem formulation.<n>The contribution of the work is in formulating penalty functions that ensure the ground state of the QUBO Hamiltonian corresponds to valid solutions that split the input subsets.<n> Empirical tests of the proposed solution show convergence to globally optimal solutions, with high accuracy rates over repeated trials.
- Score: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: I present a novel use of quantum annealing to solve the Set Splitting Problem using (QUBO) problem formulation. The contribution of the work is in formulating penalty functions that ensure the ground state of the QUBO Hamiltonian corresponds to valid solutions that split the input subsets. This approach scales linearly in terms of the number of logical qubits relative to problem size. Empirical tests of the proposed solution show convergence to globally optimal solutions, with high accuracy rates over repeated trials. Hardware limitations of current quantum annealers lead to an exponential rise in required physical qubits, versus the theoretical linear increase, although this can improve with future developments. Further work is needed to enhance formulation robustness, reduce qubit requirements for embedded problems, and to conduct more extensive bench-marking. Quantum solutions to the Set-Splitting problem lead to reduced time complexity versus classical solutions, and may accelerate research in biology, cybersecurity, and other domains.
Related papers
- Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing [0.0]
Quantum computing offers significant potential for solving NP-hardweighted (optimization) problems that are beyond the reach of classical computers.<n>One way to tap into this potential is by reformulating problems as a quadratic unconstrained binary optimization (QUBO) problem.<n>We present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem.
arXiv Detail & Related papers (2025-11-02T22:49:59Z) - Quantum-Classical Hybrid Quantized Neural Network [7.759760132559044]
We present a novel Quadratic Binary Optimization (QBO) model for quantized neural network training, enabling the use of arbitrary activation and loss functions.<n>We employ the Quantum Gradient Conditional Descent (QCGD) algorithm, which leverages quantum computing to directly solve the QCBO problem.<n> Experimental results using a coherent Ising machine (CIM) demonstrate a 94.95% accuracy on the Fashion MNIST classification task, with only 1.1-bit precision.
arXiv Detail & Related papers (2025-06-23T02:12:36Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
Quantum annealers are suited to solve several logistic optimization problems expressed in the QUBO formulation.
The solutions proposed by the quantum annealers are generally not optimal, as thermal noise and other disturbing effects arise when the number of qubits involved in the calculation is too large.
We propose the use of the classical branch-and-bound algorithm, that divides the problem into sub-problems which are described by a lower number of qubits.
arXiv Detail & Related papers (2023-11-16T09:19:01Z) - Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno
Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints.
The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
arXiv Detail & Related papers (2023-05-14T03:49:10Z) - Efficient MILP Decomposition in Quantum Computing for ReLU Network
Robustness [2.854196251981274]
In this study, we examine two decomposition methods for Mixed-Integer Linear Programming (MILP)
We concentrate on breaking down the original problem into smaller subproblems, which are then solved iteratively using a combined quantum-classical hardware approach.
Our experimental results demonstrate that this approach can save up to 90% of qubits compared to existing methods on quantum annealing and gate-based quantum computers.
arXiv Detail & Related papers (2023-04-30T13:10:56Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms.
We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem.
Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
arXiv Detail & Related papers (2023-02-08T17:09:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
We propose a hybrid quantum-classical algorithm for robust fitting.
Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs.
We present results obtained using an actual quantum computer.
arXiv Detail & Related papers (2022-01-25T05:59:24Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP)
This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm.
Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
arXiv Detail & Related papers (2021-05-06T17:59:38Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.