Constrained portfolio selection in drug repurposing (choosing subsets of approved compounds that jointly satisfy interaction avoidance, toxicity ceilings, and target-coverage requirements) remains intractable for classical integer programming beyond ∼10,000 candidates, precisely the regime where combinatorial drug repositioning operates. Existing quantum formulations address pairwise drug-combination scoring but do not account for portfolio-level constraints or the mismatch between problem graph structure and physical qubit connectivity. We introduce a three-stage pipeline: a relational graph convolutional network (RGCN) narrows the candidate pool to ∼5,000 triples, a QUBO encoding extends the Complementary-Exposure framework [6], [36] with budget, diversity, and multitarget coverage penalties, and a topology-aware QAOA compiler maps constraint blocks onto natively connected heavy-hex qubit clusters. The compiler reduces two-qubit SWAP-gate counts by 23-41% relative to Qiskit optimization-level-3 transpilation on sub-problems of 20-100 qubits (Table IV), directly lowering accumulated gate error on IBM Heron r2 hardware. Retrospective validation on ten FDA-approved repurposed drugs yields 82.5% Recall@100 on a noiseless simulator versus 79.3% for ILP/Gurobi; on real IBM Heron hardware, recall drops to 69.8% (approximation ratio 0.64), falling 9.5 percentage points behind ILP and quantifying the noise gap that future errorcorrected processors must close. The central finding is negative: at current NISQ fidelities, classical ILP produces strictly superior solutions in less wall-clock time. The contribution is therefore architectural, not algorithmic; the topology-aware compilation strategy transfers directly to improved processors without redesign, positioning the pipeline for the p ≤ 10 −4 gate-error regime projected for 2028-2030. Code and QUBO encodings will be released upon acceptance.
Constrained portfolio selection in drug repurposing (choosing subsets of approved compounds that jointly satisfy interaction avoidance, toxicity ceilings, and target-coverage requirements) remains intractable for classical integer programming beyond ∼10,000 candidates, precisely the regime where combinatorial drug repositioning operates. Existing quantum formulations address pairwise drug-combination scoring but do not account for portfolio-level constraints or the mismatch between problem graph structure and physical qubit connectivity. We introduce a three-stage pipeline: a relational graph convolutional network (RGCN) narrows the candidate pool to ∼5,000 triples, a QUBO encoding extends the Complementary-Exposure framework [6], [36] with budget, diversity, and multitarget coverage penalties, and a topology-aware QAOA compiler maps constraint blocks onto natively connected heavy-hex qubit clusters. The compiler reduces two-qubit SWAP-gate counts by 23-41% relative to Qiskit optimization-level-3 transpilation on sub-problems of 20-100 qubits (Table IV), directly lowering accumulated gate error on IBM Heron r2 hardware. Retrospective validation on ten FDA-approved repurposed drugs yields 82.5% Recall@100 on a noiseless simulator versus 79.3% for ILP/Gurobi; on real IBM Heron hardware, recall drops to 69.8% (approximation ratio 0.64), falling 9.5 percentage points behind ILP and quantifying the noise gap that future errorcorrected processors must close. The central finding is negative: at current NISQ fidelities, classical ILP produces strictly superior solutions in less wall-clock time. The contribution is therefore architectural, not algorithmic; the topology-aware compilation strategy transfers directly to improved processors without redesign, positioning the pipeline for the p ≤ 10 −4 gate-error regime projected for 2028-2030. Code and QUBO encodings will be released upon acceptance.
Constrained portfolio selection in drug repurposing (choosing subsets of approved compounds that jointly satisfy interaction avoidance, toxicity ceilings, and target-coverage requirements) remains intractable for classical integer programming beyond ∼10,000 candidates, precisely the regime where combinatorial drug repositioning operates. Existing quantum formulations address pairwise drug-combination scoring but do not account for portfolio-level constraints or the mismatch between problem graph structure and physical qubit connectivity. We introduce a three-stage pipeline: a relational graph convolutional network (RGCN) narrows the candidate pool to ∼5,000 triples, a QUBO encoding extends the Complementary-Exposure framework [6], [36] with budget, diversity, and multitarget coverage penalties, and a topology-aware QAOA compiler maps constraint blocks onto natively connected heavy-hex qubit clusters. The compiler reduces two-qubit SWAP-gate counts by 23-41% relative to Qiskit optimization-level-3 transpilation on sub-problems of 20-100 qubits (Table IV), directly lowering accumulated gate error on IBM Heron r2 hardware. Retrospective validation on ten FDA-approved repurposed drugs yields 82.5% Recall@100 on a noiseless simulator versus 79.3% for ILP/Gurobi; on real IBM Heron hardware, recall drops to 69.8% (approximation ratio 0.64), falling 9.5 percentage points behind ILP and quantifying the noise gap that future errorcorrected processors must close. The central finding is negative: at current NISQ fidelities, classical ILP produces strictly superior solutions in less wall-clock time. The contribution is therefore architectural, not algorithmic; the topology-aware compilation strategy transfers directly to improved processors without redesign, positioning the pipeline for the p ≤ 10 −4 gate-error regime projected for 2028-2030. Code and QUBO encodings will be released upon acceptance.
Retrieval-Augmented Generation (RAG) systems typically select context documents using greedy nearest-neighbor search, which optimizes each documentindependently and ignores combinatorial interactions between retrieved items. Wepresent TaxQRAG, the first open-source quantum-hybrid RAG system evaluatedon real quantum hardware for multi-strategy document selection under explicitpairwise interaction constraints. Unlike prior work, our QUBO (Quadratic Unconstrained Binary Optimization) formulation incorporates three novel quadratic terms:domain-specific pairwise synergy rewards, conflict penalties, and audit risk compounding — enabling selection of document subsets that are jointly optimal ratherthan individually relevant. Applied to a tax strategy corpus (87 documents; IRS publications, Internal Revenue Code sections, and structured strategy documents), wecompare four solvers: classical greedy, simulated annealing (SA), QAOA on a localsimulator (Aer), and QAOA on IBM Quantum’s Heron R2 processor (ibm_fez,156 qubits). SA achieves a 173% improvement in combination quality score overclassical greedy with zero conflict selections. QAOA without parameter optimization produces a 66.7% conflict rate, which a λ ablation study confirms is caused byunoptimized variational parameters rather than QUBO encoding deficiency — anegative result that motivates VQE-optimized QAOA as future work. We furtherconduct the first QAOA parameter sensitivity analysis for RAG document selection,finding that combination quality coefficient of variation reaches 88.2% acrossrandom seeds, and that Ising energy and downstream combination score divergesignificantly at shallow circuit depth. Code, benchmark data, and IBM Quantumjob identifiers are released at https://github.com/joerein-iu/taxqrag.
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.
Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery, power grids, logistics, and finance, yet remains computationally demanding for classical algorithms, especially at large scales. The Quantum Approximate Optimization Algorithm (QAOA) offers a promising quantum framework, but conventional penalty-based formulations distort optimization landscapes and demand deep circuits, undermining scalability on near-term hardware. In this work, we introduce Hamming Weight Operators, a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace. Building on this idea, we develop Adaptive Hamming Weight Operator QAOA, which dynamically selects the most effective operators to construct shallow, problem-tailored circuits. We validate our approach on benchmark tasks from both finance and high-energy physics, specifically portfolio optimization and two-jet clustering with energy balance. Across these problems, our method inherently satisfies all constraints by construction, converges faster, and achieves higher Approximation Ratios than penalty-based QAOA, while requiring roughly half as many gates. By embedding constraint-aware operators into an adaptive variational framework, our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.
Despite rapid progress in quantum optimization, broad real-hardware benchmarks comparing multiple algorithmic families across diverse combinatorial problems under a common protocol remain limited. We benchmark gate-based quantum optimization on four NP-hard problems: multi-dimensional knapsack (MDKP), maximum independent set (MIS), quadratic assignment (QAP), and market-share (MSP). We study VQE, CVaR-VQE, standard, multi-angle, and warm-start QAOA, together with qubit-efficient PCE and QRAO, on IBM Heron r1/r2 processors using resilience-level-2 mitigation. To our knowledge, this includes the first real-hardware QRAO results and the first multi-problem PCE hardware benchmark.
Across 247 method-instance combinations, we report transpiled circuit size, hardware outcomes, and an independent-error gate-count fidelity proxy, Fest. For MDKP and MIS, an empirical operating point near Fest≈0.1, corresponding to about 770 two-qubit gates at the median Heron-r2 CZ error rate, marks the onset of noise-dominated execution. QAP exposes a separate bottleneck: dense one-hot encodings and an exponentially sparse feasible manifold, with feasible fraction 10!/2100 at n=10; no tested hardware method produces a feasible assignment. Compiled QAOA-family circuits are generally noise dominated, and a matched uniform-random control shows that most feasible low-fidelity outcomes fall within the random range, apart from one finite-sample MIS warm-start exception. A SWAP-aware, fractional-gate, Nighthawk-topology compilation counterfactual reduces two-qubit counts but leaves all circuits below Fest=10−3. These conclusions apply to the tested implementations rather than QAOA in general. Qubit-efficient methods extend runnable instance sizes, but only within the empirical fidelity budget.
We report the first hardware-executed quantum-classical coordination pipeline on NISQ hardware for a societal coordination problem task-to-member matching in a 500-agent community economy. The three-stage architecture (AI decomposition → 19 qubit quantum semantic scoring on IBM Heron R2 classical QUBO assignment) executes end-to-end on three Heron R2 processors (ibm_fez,ibm_marrakesh, ibm_kingston). We observe a three-tier regret stratification: (i) a noiseless ceiling at 1.48% (five independent simulator controls + ibm_marrakesh), (ii) a classical-kernel tier at 0.86% via the Shin–Teo–Jeong (2024) dequantization kernel K_c, and (iii) a hardware tier at 0.61% reproduced independently on ibm_fez and ibm_kingston with identical θ. Since K_c's RKHS provably contains the quantum kernel's RKHS at logical depth, the hardware tier is a reproducible operating regime outside the dequantized function class. A companion multi-cycle society-model experiment shows pipeline weight choice is a time-horizon-dependent policy decision; the QUBO matcher also acts as a performative Granovetter machine (80% more weak ties than greedy, p = 9.1 × 10⁻⁵, d ≈ 27 at n = 10 runs).