QUBOs for Sorting Lists and Building Trees
This work connects abstract data structure problems to neurocomputing and quantum computing, but it appears incremental as it applies existing QUBO methods to new tasks.
The authors tackled the problem of modeling sorting and tree-building tasks as quadratic unconstrained binary optimization problems (QUBOs), showing that neurocomputing or quantum computing can solve these data structure problems.
We show that the fundamental tasks of sorting lists and building search trees or heaps can be modeled as quadratic unconstrained binary optimization problems (QUBOs). The idea is to understand these tasks as permutation problems and to devise QUBOs whose solutions represent appropriate permutation matrices. We discuss how to construct such QUBOs and how to solve them using Hopfield nets or adiabatic) quantum computing. In short, we show that neurocomputing methods or quantum computers can solve problems usually associated with abstract data structures.