Towards solving large QUBO problems using quantum algorithms: improving the LogQ scheme

• URL: http://arxiv.org/abs/2507.08489v1
• Date: Fri, 11 Jul 2025 11:07:56 GMT
• Title: Towards solving large QUBO problems using quantum algorithms: improving the LogQ scheme
• Authors: Yagnik Chatterjee, Jérémie Messud,
• Abstract summary: We propose a new LogQ parameterization that can be optimized with a gradient-inspired method.<n>We illustrate the features of our method on an analytical model and present larger scale numerical results on MaxCut problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The LogQ algorithm encodes Quadratic Unconstrained Binary Optimization (QUBO) problems with exponentially fewer qubits than the Quantum Approximate Optimization Algorithm (QAOA). The advantages of conventional LogQ are accompanied by a challenge related to the optimization of its free parameters, which requires the usage of resource intensive evolutionary or even global optimization algorithms. We propose a new LogQ parameterization that can be optimized with a gradient-inspired method, which is less resource-intensive and thus strengthens the advantage of LogQ over QAOA for large/industrial problems. We illustrate the features of our method on an analytical model and present larger scale numerical results on MaxCut problems.

Related papers

• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods.<n>We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
  Finding ground state solutions of diagonal Hamiltonians is relevant for both theoretical as well as practical problems of interest in many domains such as finance, physics and computer science. Here we use imaginary time evolution through a new block encoding scheme to obtain the ground state of such problems and apply our method to MaxCut as an illustration.
  arXiv  Detail & Related papers  (2024-11-16T08:17:36Z)
• Application of Langevin Dynamics to Advance the Quantum Natural Gradient Optimization Algorithm [47.47843839099175]
  A Quantum Natural Gradient (QNG) algorithm for optimization of variational quantum circuits has been proposed recently.<n>Momentum-QNG is more effective to escape local minima and plateaus in the variational parameter space.
  arXiv  Detail & Related papers  (2024-09-03T15:21:16Z)
• Feedback-Based Quantum Algorithm for Constrained Optimization Problems [0.6554326244334868]
  We introduce a new operator that encodes the problem's solution as its ground state. We show that our proposed algorithm saves computational resources by reducing the depth of the quantum circuit.
  arXiv  Detail & Related papers  (2024-06-12T12:58:43Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• A Comparative Study On Solving Optimization Problems With Exponentially Fewer Qubits [0.0]
  We evaluate and improve an algorithm based on Variational Quantum Eigensolver (VQE) We highlight the numerical instabilities generated by encoding the problem into the variational ansatz. We propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better objective.
  arXiv  Detail & Related papers  (2022-10-21T08:54:12Z)
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs [0.0]
  Current quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device.<n>We propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits.<n>We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max-$K$-Cut and obtain circuits that are near-optimal with respect to all relevant cost measures.
  arXiv  Detail & Related papers  (2022-09-07T18:01:01Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• 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)
• Quantum variational optimization: The role of entanglement and problem hardness [0.0]
  We study the role of entanglement, the structure of the variational quantum circuit, and the structure of the optimization problem. Our numerical results indicate an advantage in adapting the distribution of entangling gates to the problem's topology. We find evidence that applying conditional value at risk type cost functions improves the optimization, increasing the probability of overlap with the optimal solutions.
  arXiv  Detail & Related papers  (2021-03-26T14:06:54Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.