Hybrid Quantum Neighborhood Selection: NISQ-Compatible Combinatorial Optimization via Stochastic Frontier Decomposition

• URL: http://arxiv.org/abs/2606.29647v1
• Date: Sun, 28 Jun 2026 23:35:46 GMT
• Title: Hybrid Quantum Neighborhood Selection: NISQ-Compatible Combinatorial Optimization via Stochastic Frontier Decomposition
• Abstract summary: This work introduces Hybrid Quantum Neighborhood Selection (HQNS)<n>HQNS selects a compact frontier of F N active variables per stage, freezing the rest into reduced QUBO coefficients.<n>We evaluate HQNS on the Maximum Diversity Subset Selection Problem (MDSSP) across six scales, N up to 1000.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large-scale combinatorial optimization is a challenge for near-term quantum computing because dense Quadratic Unconstrained Binary Optimization (QUBO) formulations yield interaction graphs that exceed the limits of NISQ processors. This work introduces Hybrid Quantum Neighborhood Selection (HQNS), a hybrid framework mitigating this via stochastic frontier decomposition. Instead of encoding all N variables into a monolithic circuit, HQNS selects a compact frontier of F << N active variables per stage, freezing the rest into reduced QUBO coefficients. A multi-stage crawling procedure rotates these frontiers, letting local quantum subproblems refine a global solution. We evaluate HQNS on the Maximum Diversity Subset Selection Problem (MDSSP) across six scales, N up to 1000. Circuit burden is reduced from the dense QAOA requirement of O(N^2) two-qubit terms per layer to O(F^2) per stage, with total complexity governed by the number of stages and classical overhead. Benchmarks show that HQNS achieves competitive solution quality relative to parallel simulated annealing (SA) while maintaining bounded circuit width and stable QPU time. In the N=1000 benchmark over ten executions, HQNS preserves 99.9908% of the mean diversity score of an 11-restart parallel SA baseline, while reducing wall-clock time by 65.03%, peak CPU usage by 55.97%, and peak memory by 35.21%. Ablation shows performance depends on frontier size, warm-starts, CVaR filtering, and stochastic rotation. These results demonstrate that structured frontier decomposition makes variational optimization executable for dense QUBO instances unsuitable for direct QAOA on present hardware.

Related papers

• A Hybrid Quantum-Classical Coordination Architecture for Portfolio Optimization via Global Context Injection [2.4660652494309936]
  Near-term quantum and quantum-inspired solvers for portfolio optimization rely on local subproblem execution under severe size constraints.<n>We propose Context-Aware Folding (CAF), a lightweight hybrid quantum-classical coordination layer between one-shot static decomposition and full-matrix optimization.<n>CAF injects a compressed global risk state into each local subproblem via a state-dependent linear bias, decouples local candidate generation from global commitment, and retains a sequential acceptance rule.
  arXiv  Detail & Related papers  (2026-09-14T15:12:22Z)
• Resource-Efficient Hybrid Quantum Neighborhood Selection for Large-Scale Molecular Diversity Optimization [0.0]
  Hybrid Quantum Neighborhood Selection (HQNS) is a framework that decomposes large dense QUBO instances into bounded-width quantum subproblems.<n>HQNS preserves 99.9908% of the mean diversity score of an 11-restart parallel Simulated Annealing baseline, while reducing wall-clock time by 94.91%, peak CPU utilization by 64.68%, and peak memory usage by 88.61%.
  arXiv  Detail & Related papers  (2026-07-08T12:25:47Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Quantum Approximate Optimization Algorithm with Fixed Number of Parameters [0.0]
  We introduce a novel quantum optimization paradigm: the Fixed--Count Approximate Quantum Optimization Algorithm (FPC-QAOA)<n>It is a scalable variational framework that maintains a constant number of trainable parameters regardless of the number of qubits, Hamiltonian complexity, or circuit depth.<n>We benchmark FPC-QAOA on random MaxCut instances and the Tail Assignment Problem, achieving performance comparable to or better than standard QAOA.
  arXiv  Detail & Related papers  (2025-12-24T14:02:31Z)
• Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem [0.0]
  We propose a hybrid quantum-classical framework integrating variational quantum eigensolver (VQE) optimisation with classical machine learning.<n>We evaluate the framework on 80 European cities via Qiskit's AerSimulator and ibm_kyiv 127-qubit backend.
  arXiv  Detail & Related papers  (2025-09-30T13:26:12Z)
• A Depth-Independent Linear Chain Ansatz for Large-Scale Quantum Approximate Optimization [19.43182259360486]
  We propose a variant of QAOA (termed linear chain QAOA) and demonstrate its advantages over original QAOA paradigmatic MaxCut problems.<n>In our ansatz, we locate a linear chain from the original MaxCut graph and place entangling gates sequentially along this chain.<n>This linear-chain ansatz is featured by shallow quantum circuits and with the low execution time that scales independently of the problem size.
  arXiv  Detail & Related papers  (2025-09-22T00:33:54Z)
• Scaling Limits of Quantum Repeater Networks [62.75241407271626]
  Quantum networks (QNs) are a promising platform for secure communications, enhanced sensing, and efficient distributed quantum computing. Due to the fragile nature of quantum states, these networks face significant challenges in terms of scalability. In this paper, the scaling limits of quantum repeater networks (QRNs) are analyzed.
  arXiv  Detail & Related papers  (2023-05-15T14:57:01Z)
• Distribution-Flexible Subset Quantization for Post-Quantizing Super-Resolution Networks [68.83451203841624]
  This paper introduces Distribution-Flexible Subset Quantization (DFSQ), a post-training quantization method for super-resolution networks. DFSQ conducts channel-wise normalization of the activations and applies distribution-flexible subset quantization (SQ) It achieves comparable performance to full-precision counterparts on 6- and 8-bit quantization, and incurs only a 0.1 dB PSNR drop on 4-bit quantization.
  arXiv  Detail & Related papers  (2023-05-10T04:19:11Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum-classical algorithm used to approximately solve optimisation problems. While QAOA can be implemented on NISQ devices, physical limitations can limit circuit depth and decrease performance. This work introduces the eXpressive QAOA (XQAOA) that assigns more classical parameters to the ansatz to improve its performance at low depths.
  arXiv  Detail & Related papers  (2023-02-09T07:47:06Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
  We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the challenges for graph maximum cut (MaxCut) problem. DC-QAOA achieves 97.14% approximation ratio (20.32% higher than classical counterpart) It also reduces the time complexity of conventional QAOA from exponential to quadratic.
  arXiv  Detail & Related papers  (2021-02-26T03:10:30Z)

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.