Posiform Planting: Generating QUBO Instances for Benchmarking

• URL: http://arxiv.org/abs/2308.05859v2
• Date: Sun, 29 Oct 2023 02:04:17 GMT
• Title: Posiform Planting: Generating QUBO Instances for Benchmarking
• Authors: Georg Hahn, Elijah Pelofske, Hristo N. Djidjev
• Abstract summary: We propose a novel method, called posiform planting, for generating random QUBO instances of arbitrary size with known optimal solutions. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of optimization problems with up to $5627$ qubits.
• Score: 2.7624021966289605
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We are interested in benchmarking both quantum annealing and classical algorithms for minimizing Quadratic Unconstrained Binary Optimization (QUBO) problems. Such problems are NP-hard in general, implying that the exact minima of randomly generated instances are hard to find and thus typically unknown. While brute forcing smaller instances is possible, such instances are typically not interesting due to being too easy for both quantum and classical algorithms. In this contribution, we propose a novel method, called posiform planting, for generating random QUBO instances of arbitrary size with known optimal solutions, and use those instances to benchmark the sampling quality of four D-Wave quantum annealers utilizing different interconnection structures (Chimera, Pegasus, and Zephyr hardware graphs) as well as the simulated annealing algorithm. Posiform planting differs from many existing methods in two key ways. It ensures the uniqueness of the planted optimal solution, thus avoiding groundstate degeneracy, and it enables the generation of QUBOs that are tailored to a given hardware connectivity structure, provided that the connectivity is not too sparse. Posiform planted QUBOs are a type of 2-SAT boolean satisfiability combinatorial optimization problems. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of combinatorial optimization problems with up to $5627$ qubits.

Related papers

• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking [1.6385815610837167]
  We investigate making posiform planted QUBOs computationally harder by fusing many smaller random discrete coefficient spin-glass Ising models. We benchmark the capabilities of three D-Wave superconducting qubit quantum annealing processors. We find that the D-Wave QPU ground-state sampling success rate does not change with respect to the size of the random QUBOs we employ.
  arXiv  Detail & Related papers  (2024-11-06T02:46:33Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems [0.0]
  Closest String Problem is an NP-complete problem which appears more commonly in bioinformatics and coding theory. Two QUBO formulations have been proposed, with one being a slight modification over the other. DWave annealers have been used, while providing guidelines for optimality on certain platform-specific concerns.
  arXiv  Detail & Related papers  (2023-10-19T16:03:25Z)
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
  In this work, we integrate the potentials of quantum and classical techniques for optimization. We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. We present numerous computational results from real quantum hardware.
  arXiv  Detail & Related papers  (2023-02-10T20:12:53Z)
• Variational Amplitude Amplification for Solving QUBO Problems [0.0]
  This study focuses on QUBO (quadratic unconstrained binary optimization) problems, which are well-suited for qubit superposition states. We demonstrate circuit designs which encode QUBOs as cost oracle' operations $U_textrmC$, which when combined with the standard Grover diffusion operator $U_textrms$ lead to high probabilities of measurement for states corresponding to the optimal and near optimal solutions.
  arXiv  Detail & Related papers  (2023-01-31T14:33:40Z)
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems [1.0878040851638]
  We report benchmarks across three generations of D-Wave quantum annealers. The Ising, or equivalently QUBO, formulation of these problems do not require auxiliary variables for order reduction.
  arXiv  Detail & Related papers  (2023-01-08T10:02:56Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel Optimization [62.87181271021217]
  We consider non-SBO problems that have many applications in machine learning. This paper proposes fast randomized algorithms for non-SBO problems.
  arXiv  Detail & Related papers  (2021-05-05T18:28:42Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.