A Non-Degradation Gate for Near-Term Quantum Optimizers in Medical Edge Scheduling

Noureen Hameed

Published Oct 9, 2026• 0 citations

Abstract

Abstract The quantum approximate optimization algorithm (QAOA) can propose candidate schedules, but a low-cost candidate is not necessarily admissible or better than a trusted baseline. This paper extends our conference work on Policy-Gated Hybrid Quantum Optimization (PHQO) for priority-aware healthcare Internet of Things task offloading. A policy mask removes untrusted or deadline-violating routes, and a lexicographic gate accepts a quantum candidate only when it improves a priority-ordered greedy fallback, guaranteeing non-degradation under the declared key. We test it on 15,000 synthetic tasks without patient data. PHQO completed 98.013% of tasks on time against 97.120% for the greedy scheduler. Gated classical metaheuristics did slightly better, so the gain comes from the gate, not from quantum advantage. The new experiments add finite-shot decoding with depolarizing and readout noise, circuit depths p = 1–3, and windows of up to 16 qubits. In 190,000 gated decisions, no output fell below the fallback. QAOA sampling beat uniform sampling of equal budget by 0.27–0.38 points at 16–256 shots; at 1,024 shots the gap vanished. At p = 3 the feasible probability mass rose from 0.16 to 0.35, but gated success did not change. Gating lets near-term quantum optimizers be trialled at no loss relative to the fallback.

DOI: 10.21203/rs.3.rs-11300282/v1

Related papers

Quantum Supremacy through the Quantum Approximate Optimization Algorithm

Edward Farhi, Aram W. Harrow

The Quantum Approximate Optimization Algorithm (QAOA) is designed to run on a gate model quantum computer and has shallow depth. It takes as input a combinatorial optimization problem and outputs a string that satisfies a high fraction of the maximum number of clauses that can be satisfied. For certain problems the lowest depth version of the QAOA has provable performance guarantees although there exist classical algorithms that have better guarantees. Here we argue that beyond its possible computational value the QAOA can exhibit a form of Quantum Supremacy in that, based on reasonable complexity theoretic assumptions, the output distribution of even the lowest depth version cannot be efficiently simulated on any classical device. We contrast this with the case of sampling from the output of a quantum computer running the Quantum Adiabatic Algorithm (QADI) with the restriction that the Hamiltonian that governs the evolution is gapped and stoquastic. Here we show that there is an oracle that would allow sampling from the QADI but even with this oracle, if one could efficiently classically sample from the output of the QAOA, the Polynomial Hierarchy would collapse. This suggests that the QAOA is an excellent candidate to run on near term quantum computers not only because it may be of use for optimization but also because of its potential as a route to establishing quantum supremacy.

arXiv:1602.07674Bulletin of the American Physical SocietyFeb 24, 2016329 citations

Noise resilient compilation policies for quantum approximate optimization algorithm

Mahabubul Alam, Abdullah Ash Saki, Junde Li +2 more

Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems using noisy quantum devices. The multiqubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA circuit resulting in lower circuit-depth and gate-count. A less number of gates generally indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, near-term quantum devices exhibit significant variations in the gate success probabilities. Variation-aware compilation policies (i.e. putting most gate operations on qubits with higher gate success probabilities) can enhance the probability of successful program execution on the hardware. The greater flexibility of QAOA-circuits offer better scope of optimization with QAOA-tailored compilation policies. This paper presents an argument for compilation policies to exploit the unique characteristics of QAOA-circuits alongside the variation-awareness of the noisy devices. We present two procedures - variation-aware qubit placement (VQP) and variation-aware iterative mapping (VIM) that can improve the circuit success probability quite significantly (≈8.408X on average) for a set of QAOA-MaxCut problems on ibmq_16_melbourne.

Nov 2, 202014 citations

Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.

arXiv:1907.09631Jul 13, 201933 citations

Quantum-Assisted Optimization and Security for Trustworthy AI-Driven Healthcare

Hafiz Muhammad Waseem, Gregory Epiphaniou, Carsten Maple

Digital health increasingly relies on artificial intelligence for clinical decision-making, patient management, and distributed learning, yet two persistent challenges remain: the computational complexity of optimization tasks, such as operating-room scheduling and genomic feature selection, and the need for robust security in federated and Internet-of-Medical-Things (IoMT) systems that are vulnerable to poisoning and spoofing attacks. Existing approaches often address these issues separately and struggle with scalability, interpretability, and resilience to advanced adversaries. This paper introduces a Hybrid Quantum-Classical Architecture (HQCA) that integrates the Quantum Approximate Optimization Algorithm (QAOA) for constrained healthcare decision-making with Quantum Digital Signatures (QDS) for secure authentication. The layered framework combines classical preprocessing with NISQ-era quantum modules and is validated under calibrated IBM Eagle-class noise models. We evaluate four representative tasks, including operating-room scheduling, genomic feature selection, federated-learning integrity, and IoMT firmware authentication, using short-depth QAOA (p≤ 3) and SWAP-test based QDS verification. HQCA reduces operating-room makespan by approximately 7.5% and halves overtime compared to classical baselines, while maintaining over 99.5% scheduling feasibility. In genomic analysis, it improves classification performance while selecting 32% less features. For security, it reduces successful poisoning in federated learning from 20.7% to 3.8%, and no spoofing events were observed in 30 trials for IoMT telemetry, with practical verification latency. These findings indicate that a unified hybrid stack can improve decision quality while providing information-theoretic authenticity guarantees with operationally feasible verification latency, demonstrating a practical pathway toward secure and efficient digital health as quantum hardware matures.

IEEE Transactions on Quantum EngineeringJan 1, 20265 citations

Circuit Compilation Methodologies for Quantum Approximate Optimization Algorithm

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid algorithm to solve hard combinatorial optimization problems. The multi-qubit CPHASE gates used in the quantum circuit for QAOA are commutative i.e., the order of the gates can be altered without changing the output state. This re-ordering leads to the execution of more gates in parallel and a smaller number of additional SWAP gates to compile the QAOA-circuit. Consequently, the circuit-depth and cumulative gate-count become lower which is beneficial for circuit execution time and noise resilience. A less number of gates indicates a lower accumulation of gate-errors, and a reduced circuit-depth means less decoherence time for the qubits. However, finding the best-ordered circuit is a difficult problem and does not scale well with circuit size. This paper presents four generic methodologies to optimize QAOA-circuits by exploiting gate re-ordering. We demonstrate a reduction in gate-count by ≈23.0% and circuit-depth by ≈53.0% on average over a conventional approach without incurring any compilation-time penalty. We also present a variation-aware compilation which enhances the compiled circuit success probability by ≈62.7% for the target hardware over the variation unaware approach. A new metric, Approximation Ratio Gap (ARG), is proposed to validate the quality of the compiled QAOA-circuit instances on actual devices. Hardware implementation of a number of QAOA instances shows ≈25.8% improvement in the proposed metric on average over the conventional approach on ibmq 16 melbourne.

IEEE/ACM International Symposium on Microarchitecture (MICRO)Oct 1, 202071 citations

Evaluation of QAOA based on the approximation ratio of individual samples

Jason M. Larkin, Matías Jonsson, Daniel Justice +1 more

Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.

arXiv:2006.04831Quantum Science and TechnologyApr 22, 202233 citations