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

Society for Industrial and Applied Mathematics eBooks

Adiabatic Quantum Computing for Max-Sum Diversification

Christian Bauckhage, Rafet Sifa, Stefan Wrobel

Published Jan 1, 2020• 13 citations
Publisher

Abstract

The combinatorial problem of max-sum diversification asks for a maximally diverse subset of a given set of data. Here, we show that it can be expressed as an Ising energy minimization problem. Given this result, max-sum diversification can be solved on adiabatic quantum computers and we present proof of concept simulations which support this claim. This, in turn, suggests that quantum computing might play a role in data mining. We therefore discuss quantum computing in a tutorial like manner and elaborate on its current strengths and weaknesses for data analysis.

DOI
10.1137/1.9781611976236.39

Related papers

Max-Sum Dispersion via Quantum Annealing.

Christian Bauckhage, Rafet Sifa, Dirk Hecker +1 more

We devise an Ising model for the max-sum dispersion problem which occurs in contexts such as Web search or text summarization. Given this Ising model, max-sum dispersion can be solved on adiabatic quantum computers; in proof of concept simulations, we solve the corresponding Schrödinger equations and observe our approach to work well.

LWDA•Jan 1, 2019•0 citations

Adiabatic Quantum Computing for the Subset Sum Problem: Preliminary Studies

Cesar Freitas Bernardes, Pedro Belin Castellucci, Douglas Soares Gonçalves +2 more

The Subset Sum Problem (SSP) is one of those combinatorial problems that are very easy to understand (take a bunch of integer numbers and verify whether there exists a subset of these numbers which sums up to a given target integer), but it can be very difficult to solve.The SSP is actually an NPcomplete problem, but it is "weakly" NP-hard, implying that there are instances of SSP that can be solved in polynomial time.For this particular problem, the instance hardness can be measured by evaluating the so-called "density" index, which basically compares the number of involved integer numbers to the number of bits we need for their binary representation.In our preliminary study on the use of adiabatic quantum computing for the SSP, we investigate the actual feasibility in solving hard instances of the problem.In fact, hard SSP instances are those requiring a large number of bits for the representation of the integers, while the analog nature of the quantum computer does not allow us to ensure highly accurate integer representations.Some preliminary computational experiments performed on D-Wave quantum annealer are presented and compared to standard solvers for classical computers.

Annals of Computer Science and Information Systems•Oct 15, 2025•1 citation

Adiabatic quantum computing solution of the knapsack problem

Mark W. Coffey

We illustrate the adiabatic quantum computing solution of the knapsack problem with both integer profits and weights. For problems with $n$ objects (or items) and integer capacity $c$, we give specific examples using both an Ising class problem Hamiltonian requiring $n+c$ qubits and a much more efficient one using $n+[\log_2 c]+1$ qubits. The discussion includes a brief mention of classical algorithms for knapsack, applications of this commonly occurring problem, and the relevance of further studies both theoretically and numerically of the behavior of the energy gap. Included too is a demonstration and commentary on a version of quantum search using a certain Ising model. Furthermore, an Appendix presents analytic results concerning the boundary for the easy-versus-hard problem-instance phase transition for the special case subset sum problem.

arXiv:1701.05584•Jan 19, 2017•9 citations

Adiabatic Quantum Computing

Sebastian D. Pinski

Adiabatic Quantum Computing (AQC) is a relatively new subject in the world of quantum computing, let alone Physics. Inspiration for this project has come from recent controversy around D-Wave Systems in British Columbia, Canada, who claim to have built a working AQC which is now commercially available and hope to be distributing a 1024 qubit chip by the end of 2008. Their 16 qubit chip was demonstrated online for the Supercomputing 2007 conference within which a few small problems were solved; although the explanations that journalists and critics received were minimal and very little was divulged in the question and answer session. This 'unconvincing' demonstration has caused physicists and computer scientists to hit back at D-Wave. The aim of this project is to give an introduction to the historic advances in classical and quantum computing and to explore the methods of AQC. Through numerical simulations an algorithm for the Max Independent Set problem is empirically obtained.

arXiv:1108.0560•Aug 2, 2011•1 citation

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

David Biesner, Thore Gerlach, Christian Bauckhage +2 more

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.

arXiv:2211.02653•International Conference on Machine Learning and Applications•Dec 1, 2022•7 citations

Problem Solving with Hopfield Networks and Adiabatic Quantum Computing

Christian Bauckhage, Ramsés J. Sánchez, Rafet Sifa

Our goal with this paper is to elucidate the close connection between Hopfield networks and adiabatic quantum computing. Focusing on their use in problem solving, we point out that the energy functions minimized by Hopfield networks are essentially identical to those minimized by adiabatic quantum computers. To practically illustrate this, we consider a simple textbook problem, namely the k-rooks problem, and discuss how to set it up for solution via a Hopfield network or adiabatic quantum computing.

International Joint Conference on Neural Networks (IJCNN)•Jul 1, 2020•18 citations
The combinatorial problem of max-sum diversification asks for a maximally diverse subset of a given set of data. Here, we show that it can be expressed as an Ising energy minimization problem. Given this result, max-sum diversification can be solved on adiabatic quantum computers and we present proof of concept simulations which support this claim. This, in turn, suggests that quantum computing might play a role in data mining. We therefore discuss quantum computing in a tutorial like manner and elaborate on its current strengths and weaknesses for data analysis.
The Subset Sum Problem (SSP) is one of those combinatorial problems that are very easy to understand (take a bunch of integer numbers and verify whether there exists a subset of these numbers which sums up to a given target integer), but it can be very difficult to solve.The SSP is actually an NPcomplete problem, but it is "weakly" NP-hard, implying that there are instances of SSP that can be solved in polynomial time.For this particular problem, the instance hardness can be measured by evaluating the so-called "density" index, which basically compares the number of involved integer numbers to the number of bits we need for their binary representation.In our preliminary study on the use of adiabatic quantum computing for the SSP, we investigate the actual feasibility in solving hard instances of the problem.In fact, hard SSP instances are those requiring a large number of bits for the representation of the integers, while the analog nature of the quantum computer does not allow us to ensure highly accurate integer representations.Some preliminary computational experiments performed on D-Wave quantum annealer are presented and compared to standard solvers for classical computers.
We illustrate the adiabatic quantum computing solution of the knapsack problem with both integer profits and weights. For problems with nnn objects (or items) and integer capacity ccc, we give specific examples using both an Ising class problem Hamiltonian requiring n+cn+cn+c qubits and a much more efficient one using n+[log⁡2c]+1n+[\log_2 c]+1n+[log2​c]+1 qubits. The discussion includes a brief mention of classical algorithms for knapsack, applications of this commonly occurring problem, and the relevance of further studies both theoretically and numerically of the behavior of the energy gap. Included too is a demonstration and commentary on a version of quantum search using a certain Ising model. Furthermore, an Appendix presents analytic results concerning the boundary for the easy-versus-hard problem-instance phase transition for the special case subset sum problem.
Adiabatic Quantum Computing (AQC) is a relatively new subject in the world of quantum computing, let alone Physics. Inspiration for this project has come from recent controversy around D-Wave Systems in British Columbia, Canada, who claim to have built a working AQC which is now commercially available and hope to be distributing a 1024 qubit chip by the end of 2008. Their 16 qubit chip was demonstrated online for the Supercomputing 2007 conference within which a few small problems were solved; although the explanations that journalists and critics received were minimal and very little was divulged in the question and answer session. This 'unconvincing' demonstration has caused physicists and computer scientists to hit back at D-Wave. The aim of this project is to give an introduction to the historic advances in classical and quantum computing and to explore the methods of AQC. Through numerical simulations an algorithm for the Max Independent Set problem is empirically obtained.
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.
Our goal with this paper is to elucidate the close connection between Hopfield networks and adiabatic quantum computing. Focusing on their use in problem solving, we point out that the energy functions minimized by Hopfield networks are essentially identical to those minimized by adiabatic quantum computers. To practically illustrate this, we consider a simple textbook problem, namely the k-rooks problem, and discuss how to set it up for solution via a Hopfield network or adiabatic quantum computing.