Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis
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.
- Published in:
International Conference on Machine Learning and Applications - Type:
Inproceedings - Authors:
Biesner, David; Gerlach, Thore; Bauckhage, Christian; Kliem, Bernd; Sifa, Rafet - Year:
2022
Citation information
Biesner, David; Gerlach, Thore; Bauckhage, Christian; Kliem, Bernd; Sifa, Rafet: Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis, International Conference on Machine Learning and Applications, 2022, https://ieeexplore.ieee.org/document/10068999, Biesner.etal.2022a,
@Inproceedings{Biesner.etal.2022a,
author={Biesner, David; Gerlach, Thore; Bauckhage, Christian; Kliem, Bernd; Sifa, Rafet},
title={Solving Subset Sum Problems using Quantum Inspired Optimization Algorithms with Applications in Auditing and Financial Data Analysis},
booktitle={International Conference on Machine Learning and Applications},
url={https://ieeexplore.ieee.org/document/10068999},
year={2022},
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...}}
