Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction

• URL: http://arxiv.org/abs/2512.18464v1
• Date: Sat, 20 Dec 2025 18:36:10 GMT
• Title: Hierarchical divide and conquer quantum approach to combinatorial optimization problems with tunable reduction
• Authors: Mathias Schmid, Naeimeh Mohseni, Michael J. Hartmann,
• Abstract summary: We introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors.<n>We find that our approach allows us to solve optimization problems on weighted 3-regular graphs with $|mathcalV|=40$ discrete variables on $sim |mathcalV| / 4$ qubits while retaining a possible approximation ratio of $sim99.9%$.
• Score: 0.6117371161379209
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Combinatorial optimization is considered a promising class of problems in which quantum computers can show significant advantages. However, problems of practical relevance typically have more variables than current or foreseeable quantum computers have qubits. Here we introduce a divide and conquer approach that partitions the optimization problem into subgraphs that can be represented on smaller quantum processors. We then find all states of the subgraphs that can possibly be part of the solution to the entire problem by determining the cost or energy ranges in which the local subgraph energies of these states must be contained. This allows us to reduce the problem by only considering the subspace spanned by these states. We then recombine the system using a binary encoding for each subgraph with a local energy ordering. This process can be iterated until no further reduction is possible. We also find that the number of necessary qubits can be reduced further when only retaining states in a fraction of the relevant energy range at very little expense in terms of approximation ratio to the global ground state. In numerical simulations, we find that our approach allows us to solve combinatorial optimization problems on weighted random 3-regular graphs with $|\mathcal{V}|=40$ discrete variables on $\sim |\mathcal{V}| / 4$ qubits while retaining a possible approximation ratio of $\sim99.9\%$. We also observe an increasing reduction with larger system sizes.

Related papers

• Efficient Excited-State Calculations for Molecules Based on Contextual Subspace Method and Symmetry Optimizations [2.2322840607996883]
  Quantum computing methods for excited-state calculations remain underexplored in Noisy Intermediate-Scale Quantum (NISQ) hardware.<n>We propose a resource-efficient framework that integrates the contextual subspace (CS) method with the Variational Quantum Deflation (VQD) algorithm.<n>We show that it is unproblematic to utilize this combination in calculating the excited state to reduce qubits.
  arXiv  Detail & Related papers  (2025-02-25T07:48:04Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• 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)
• Reconstructing the whole from its parts [0.0]
  We analytically determine global quantum states from a wide class of self-consistent marginal reductions in any multipartite scenario. We show that any self-consistent set of multipartite marginal reductions is compatible with the existence of a global quantum state, after passing through a depolarizing channel.
  arXiv  Detail & Related papers  (2022-09-28T15:04:22Z)
• Solving Larger Optimization Problems Using Parallel Quantum Annealing [0.0]
  We show that a hybrid approach combining parallel quantum annealing with graph decomposition allows one to solve larger optimization problem accurately. We apply the approach on the Maximum Clique problem on graphs with up to 120 nodes and 6395 edges.
  arXiv  Detail & Related papers  (2022-05-24T15:56:15Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• 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)
• 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)
• Computational Overhead of Locality Reduction in Binary Optimization Problems [0.0]
  We discuss the effects of locality reduction needed for the majority of solvers that can only accommodate 2-local (quadratic) cost functions. Using a parallel tempering Monte Carlo solver on Microsoft Azure Quantum, we show that post reduction to a corresponding 2-local representation the problems become considerably harder to solve.
  arXiv  Detail & Related papers  (2020-12-17T15:49:55Z)
• Advanced unembedding techniques for quantum annealers [0.0]
  We present tailored unembedding techniques for four important NP-hard problems. Our techniques are simple and yet make use of structural properties of the problem being solved.
  arXiv  Detail & Related papers  (2020-09-10T17:49:43Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)

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.