Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2211.02653 · International Conference on Machine Learning and Applications

Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis

David Biesner, Thore Gerlach, Christian Bauckhage, Bernd Kliem, Rafet Sifa

Published Dec 1, 2022• 7 citations
arXivHTMLPDF

Abstract

Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in many real applications.We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We outline how this algorithm can be applied by adiabatic quantum computers (quantum annealers) and specialized hardware (field programmable gate arrays) for digital annealing and run experiments on quantum annealing hardware.

DOI
10.1109/icmla55696.2022.00150

Related papers

Solving Subset Sum Problems using Binary Optimization with Applications in Auditing and Financial Data Analysis

David Biesner, Rafet Sifa, Christian Bauckhage

Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in real applications. We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We give an outlook for the application of specialized hardware and quantum algorithms.

•Jan 28, 2022•1 citation

Solving Subset Sum Problems using Binary Optimization with Applications in Auditing and Financial Data Analysis

David Biesner, Rafet Sifa, Christian Bauckhage

Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in real applications. We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We give an outlook for the application of specialized hardware and quantum algorithms.

•Jan 28, 2022•0 citations

Solving NP-hard Problems with Quantum Annealing

Jehn‐Ruey Jiang, Chun-Wei Chu

Quadratic unconstrained binary optimization (QUBO) formulas of quantum annealing (QA) algorithms are classified into four categories. QA algorithms using different QUBO formulas solve specific NP-hard problems as examples of the classification. The NP-hard problems solved are the subset sum, the vertex cover, the graph coloring, and the traveling salesperson problems. The QA algorithms are compared with their classical counterparts in terms of the quality of the solution and the time to the solution. Based on the comparison results, observations and suggestions are given for each QUBO formula category, so that proper actions can be adopted to improve the performance of QA algorithms. Compared with classical algorithms, QA algorithms are competitive in the current noisy intermediate-scale quantum (NISQ) era and beyond.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Oct 28, 2022•3 citations

Quadratic Unconstrained Binary Optimization via Quantum-Inspired Annealing

Joseph Bowles, Alexandre Dauphin, Patrick Huembeli +2 more

We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.

Physical Review Applied•Sep 7, 2022•23 citations

Classifying and Benchmarking Quantum Annealing Algorithms Based on Quadratic Unconstrained Binary Optimization for Solving NP-Hard Problems

Jehn‐Ruey Jiang, Chun-Wei Chu

Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related classical algorithms (CAs) running on classical computers in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.

IEEE Access•Jan 1, 2023•46 citations

Dynamic Range Reduction via Branch-and-Bound

Thore Gerlach, Nico Piatkowski

A key strategy to enhance specialized hardware accelerators, such as GPUs and FPGA, is to reduce the numerical precision in arithmetic operations, which increases processing speed and lowers latency-both crucial for real-time AI applications. In this work, we consider NP-hard Quadratic Unconstrained Binary Optimization (QUBO) problems, which arise in machine learning and beyond. We show that these problems often require high numerical precision, posing challenges for hardware solvers. We introduce a principled Branch-andBound algorithm for reducing the precision requirements of QUBO problems by utilizing the dynamic range as measure of complexity. Experiments demonstrate that our method reduces the dynamic range in subset sum, clustering, and vector quantization problems, thereby increasing their solvability on actual quantum annealers and FPGA-based digital annealers.

arXiv:2409.10863•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation
Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in many real applications.We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We outline how this algorithm can be applied by adiabatic quantum computers (quantum annealers) and specialized hardware (field programmable gate arrays) for digital annealing and run experiments on quantum annealing hardware.
Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in real applications. We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We give an outlook for the application of specialized hardware and quantum algorithms.
Many applications in automated auditing and the analysis and consistency check of financial documents can be formulated in part as the subset sum problem: Given a set of numbers and a target sum, find the subset of numbers that sums up to the target. The problem is NP-hard and classical solving algorithms are therefore not practical to use in real applications. We tackle the problem as a QUBO (quadratic unconstrained binary optimization) problem and show how gradient descent on Hopfield Networks reliably finds solutions for both artificial and real data. We give an outlook for the application of specialized hardware and quantum algorithms.
Quadratic unconstrained binary optimization (QUBO) formulas of quantum annealing (QA) algorithms are classified into four categories. QA algorithms using different QUBO formulas solve specific NP-hard problems as examples of the classification. The NP-hard problems solved are the subset sum, the vertex cover, the graph coloring, and the traveling salesperson problems. The QA algorithms are compared with their classical counterparts in terms of the quality of the solution and the time to the solution. Based on the comparison results, observations and suggestions are given for each QUBO formula category, so that proper actions can be adopted to improve the performance of QA algorithms. Compared with classical algorithms, QA algorithms are competitive in the current noisy intermediate-scale quantum (NISQ) era and beyond.
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimization. The algorithm can be seen as an analog of quantum annealing under the restriction of a product-state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent-based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large-scale problem instances with tunable hardness and planted solutions. We find that our algorithm offers a similar performance to current state-of-the-art approaches within a comparably simple gradient-based and nonstochastic setting.
Quantum annealing has the potential to outperform classical transistor-based computer technologies in tackling intricate combinatorial optimization problems. However, ongoing scientific debates cast doubts on whether quantum annealing devices (or quantum annealers) can genuinely provide better problem-solving capabilities than classical computers. The question of whether quantum annealing algorithms (QAAs) running on quantum annealers have computational advantages over classical algorithms (CAs) running on classical computers still remains unclear. This paper aims to clarify the question by classifying and benchmarking QAAs that utilize quadratic unconstrained binary optimization (QUBO) formulas to solve NP-hard problems. It proposes a four-class classification of QUBO formulas and exemplifies each class by QUBO formulas used by QAAs for solving specific NP-hard problems, such as the subset sum, maximum cut, vertex cover, 0/1 knapsack, graph coloring, Hamiltonian cycle, traveling salesperson, and job shop scheduling problems. The classification is based on the following two criteria: (i) Does the number of QUBO variables scale linearly with the problem input size? (ii) Does the QUBO formula have both the constraint term and the optimization term? QAAs are implemented and run on a D-Wave quantum annealer for benchmarking. They are benchmarked against related classical algorithms (CAs) running on classical computers in terms of the quality of the solution and the time to the solution. The benchmarking results reveal which classes of QUBO formulas are likely to provide advantages to QAAs over CAs. Furthermore, based on the benchmarking results, observations and suggestions are given for each class of QUBO formulas, facilitating the adoption of appropriate actions to improve the performance of QAAs.
A key strategy to enhance specialized hardware accelerators, such as GPUs and FPGA, is to reduce the numerical precision in arithmetic operations, which increases processing speed and lowers latency-both crucial for real-time AI applications. In this work, we consider NP-hard Quadratic Unconstrained Binary Optimization (QUBO) problems, which arise in machine learning and beyond. We show that these problems often require high numerical precision, posing challenges for hardware solvers. We introduce a principled Branch-andBound algorithm for reducing the precision requirements of QUBO problems by utilizing the dynamic range as measure of complexity. Experiments demonstrate that our method reduces the dynamic range in subset sum, clustering, and vector quantization problems, thereby increasing their solvability on actual quantum annealers and FPGA-based digital annealers.