Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence

• URL: http://arxiv.org/abs/2504.08159v1
• Date: Thu, 10 Apr 2025 23:00:20 GMT
• Title: Optimizing QUBO generation parameters for NP problems and their impact on D-Wave convergence
• Authors: Toru Fujii, Koshi Komuro, Kaito Tomari,
• Abstract summary: In this study, we analyzed QUBO formulas for three coloring-related problems.<n>We identified the need for independent parameters for complex problems and derived relationships between formula characteristics and optimal QUBO parameter values.<n>We demonstrated how independent Ising coefficients enhance convergence to correct states based on optimal parameter adjustments.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: NP problems are closely related to practical optimization challenges but often suffer from exponential increases in computation time as problem sizes grow. Quantum annealing offers a promising approach to solve NP problems faster than classical methods, requiring cost functions and constraints to be expressed in QUBO format. However, setting QUBO coefficients often relies on empirical methods, particularly in scheduling problems where large values and intuition are needed. In this study, we analyzed QUBO formulas for three coloring-related problems: the graph coloring problem, the clique vertex cover problem, and the integer-length job scheduling problem. We identified the need for independent parameters for complex problems and derived relationships between formula characteristics and optimal QUBO parameter values. Using D-Wave quantum annealing, we validated these parameters and visualized the effects of parameter changes on states and eigenvalues in small spin problems. Additionally, we demonstrated how independent Ising coefficients enhance convergence to correct states based on optimal parameter adjustments.

Related papers

• Transferring linearly fixed QAOA angles: performance and real device results [0.0]
  We investigate a simplified approach that combines linear parameterization with parameter transferring, reducing the parameter space to just 4 dimensions regardless of the number of layers. We compare this combined approach with standard QAOA and other parameter setting strategies such as INTERP and FOURIER, which require computationally demanding incremental layer-by-layer optimization. Our experiments extend from classical simulation to actual quantum hardware implementation on IBM's Eagle processor, demonstrating the approach's viability on current NISQ devices.
  arXiv  Detail & Related papers  (2025-04-17T04:17:51Z)
• PINNverse: Accurate parameter estimation in differential equations from noisy data with constrained physics-informed neural networks [0.0]
  Physics-Informed Neural Networks (PINNs) have emerged as effective tools for solving such problems.<n>We introduce PINNverse, a training paradigm that addresses these limitations by reformulating the learning process as a constrained differential optimization problem.<n>We demonstrate robust and accurate parameter estimation from noisy data in four classical ODE and PDE models from physics and biology.
  arXiv  Detail & Related papers  (2025-04-07T16:34:57Z)
• One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
  We present a unified quantum-classical framework for solving NP-complete constrained optimization problems. We show that QCP's parameterized ansatz class always captures the optimum within its generated subcone.
  arXiv  Detail & Related papers  (2024-11-01T08:00:30Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Enhancing Hypergradients Estimation: A Study of Preconditioning and Reparameterization [49.73341101297818]
  Bilevel optimization aims to optimize an outer objective function that depends on the solution to an inner optimization problem. The conventional method to compute the so-called hypergradient of the outer problem is to use the Implicit Function Theorem (IFT) We study the error of the IFT method and analyze two strategies to reduce this error.
  arXiv  Detail & Related papers  (2024-02-26T17:09:18Z)
• Solving Forward and Inverse Problems of Contact Mechanics using Physics-Informed Neural Networks [0.0]
  We deploy PINNs in a mixed-variable formulation enhanced by output transformation to enforce hard and soft constraints. We show that PINNs can serve as pure partial equation (PDE) solver, as data-enhanced forward model, and as fast-to-evaluate surrogate model.
  arXiv  Detail & Related papers  (2023-08-24T11:31:24Z)
• Optimum-Preserving QUBO Parameter Compression [0.9281671380673306]
  We study the implications of solving Quadratic unconstrained binary optimization problems under limited precision. We show that the problem's dynamic range has a crucial impact on the problem's robustness against distortions. We introduce techniques to reduce the dynamic range of a given QUBO instance based on theoretical bounds of the minimal energy value.
  arXiv  Detail & Related papers  (2023-07-05T10:42:05Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  We propose a novel methodology for addressing the hyperspectral image deconvolution problem. A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network. The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
  arXiv  Detail & Related papers  (2023-06-10T08:25:16Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• 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)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• FaDIn: Fast Discretized Inference for Hawkes Processes with General Parametric Kernels [82.53569355337586]
  This work offers an efficient solution to temporal point processes inference using general parametric kernels with finite support. The method's effectiveness is evaluated by modeling the occurrence of stimuli-induced patterns from brain signals recorded with magnetoencephalography (MEG) Results show that the proposed approach leads to an improved estimation of pattern latency than the state-of-the-art.
  arXiv  Detail & Related papers  (2022-10-10T12:35:02Z)
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm [0.0]
  We show that the calculation of the expectation of a problem Hamiltonian under a Grover-driven, QAOA-prepared state can be performed independently of system size. Such calculations can help deliver insights into the performance of and predictability of angles in QAOA in the limit of large problem sizes.
  arXiv  Detail & Related papers  (2022-08-22T17:18:25Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)

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.