QUBOs for Sorting Lists and Building Trees

• URL: http://arxiv.org/abs/2203.08815v1
• Date: Tue, 15 Mar 2022 11:58:17 GMT
• Title: QUBOs for Sorting Lists and Building Trees
• Authors: Christian Bauckhage, Thore Gerlach, Nico Piatkowski
• Abstract summary: 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) We discuss how to construct such QUBOs and how to solve them using Hopfield nets or adiabatic) quantum computing.
• Score: 3.0745536448480326
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
  We develop a way to encode several NP-Complete problems in Abstract Argumentation to Quadratic Unconstrained Binary Optimization problems. With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. We performed tests to prove the correctness and applicability of classical problems in Argumentation and enforcement of argument sets.
  arXiv  Detail & Related papers  (2024-09-09T11:29:46Z)
• 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 Search Algorithm for Binary Constant Weight Codes [3.3555130013686014]
  A binary constant weight code is a type of error-correcting code with a wide range of applications. We propose a quantum search algorithm for binary constant weight codes.
  arXiv  Detail & Related papers  (2022-11-09T01:57:11Z)
• QuAnt: Quantum Annealing with Learnt Couplings [18.40480332882025]
  We learn QUBO forms from data through gradient backpropagation instead of deriving them. We demonstrate the advantages of learnt QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation.
  arXiv  Detail & Related papers  (2022-10-13T17:59:46Z)
• Penalty Weights in QUBO Formulations: Permutation Problems [0.0]
  optimisation algorithms designed to work on quantum computers have been of research interest in recent years. Many of these solver can only optimise problems that are in binary and quadratic form. There are many optimisation problems that are naturally represented as permutations. We propose new static methods of calculating penalty weights which lead to more promising results.
  arXiv  Detail & Related papers  (2022-06-20T22:00:38Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Grover's Algorithm for Question Answering [0.0]
  We adapt Grover's algorithm to the problem of finding a correct answer to a natural language question in English. Using a grammar that can be interpreted as tensor contractions, each word is represented as a quantum state that serves as input to the quantum circuit. We show that our construction can deal with certain types of ambiguous phrases by keeping the various different meanings in quantum superposition.
  arXiv  Detail & Related papers  (2021-06-09T18:00:13Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Machine Number Sense: A Dataset of Visual Arithmetic Problems for Abstract and Relational Reasoning [95.18337034090648]
  We propose a dataset, Machine Number Sense (MNS), consisting of visual arithmetic problems automatically generated using a grammar model--And-Or Graph (AOG) These visual arithmetic problems are in the form of geometric figures. We benchmark the MNS dataset using four predominant neural network models as baselines in this visual reasoning task.
  arXiv  Detail & Related papers  (2020-04-25T17:14:58Z)

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.