# FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes

arXiv: https://arxiv.org/abs/2210.17037 · HTML: https://mlsanity.com/paper/2210.17037/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 121 references that are in the map.
- First posted on arXiv 31 Oct 2022.

## Builds on (most cited first, 15 of 15)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Epidemic processes in complex networks](https://mlsanity.com/paper/1408.2701/) (2014)
- [Nonnegative/binary matrix factorization with a D-Wave quantum annealer](https://mlsanity.com/paper/1704.01605/) (2017)
- [Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers](https://mlsanity.com/paper/1901.11054/) (2019)
- [Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation](https://mlsanity.com/paper/1903.10963/) (2019)
- [Quantum Computing at the Frontiers of Biological Sciences](https://mlsanity.com/paper/1911.07127/) (2019)
- [Optimized Quantum Compilation for Near-Term Algorithms with OpenPulse](https://mlsanity.com/paper/2004.11205/) (2020)
- [The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model](https://mlsanity.com/paper/2110.14206/) (2021)
- [HAMMER: boosting fidelity of noisy Quantum circuits by exploiting Hamming behavior of erroneous outcomes](https://mlsanity.com/paper/2208.09371/) (2022)
- [Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers](https://mlsanity.com/paper/1902.01474/) (2019)
- [An Ensemble Approach for Compressive Sensing with Quantum](https://mlsanity.com/paper/2006.04682/) (2020)
- [Adaptive job and resource management for the growing quantum cloud](https://mlsanity.com/paper/2203.13260/) (2022)
- [Super-blockers and the effect of network structure on information cascades](https://mlsanity.com/paper/1802.05039/) (2018)
- [Partial Compilation of Variational Algorithms for Noisy Intermediate-Scale Quantum Machines](https://mlsanity.com/paper/1909.07522/) (2019)
- [EQUAL: Improving the Fidelity of Quantum Annealers by Injecting Controlled Perturbations](https://mlsanity.com/paper/2108.10964/) (2021)

## Built on by (most cited first, 4 of 4)

- [Enigma: Application-Layer Privacy for Quantum Optimization on Untrusted Computers](https://mlsanity.com/paper/2311.13546/) (2023)
- [Adversarial Robustness in Distributed Quantum Machine Learning](https://mlsanity.com/paper/2508.11848/) (2025)
- [DyPP: Dynamic Parameter Prediction to Accelerate Convergence of Variational Quantum Algorithms](https://mlsanity.com/paper/2307.12449/) (2023)
- [Skipper: Improving the Reach and Fidelity of Quantum Annealers by Skipping Long Chains](https://mlsanity.com/paper/2312.00264/) (2023)

## Abstract (arXiv)

Quantum Approximate Optimization Algorithm (QAOA) is one of the leading candidates for demonstrating the quantum advantage using near-term quantum computers. Unfortunately, high device error rates limit us from reliably running QAOA circuits for problems with more than a few qubits. In QAOA, the problem graph is translated into a quantum circuit such that every edge corresponds to two 2-qubit CNOT operations in each layer of the circuit. As CNOTs are extremely error-prone, the fidelity of QAOA circuits is dictated by the number of edges in the problem graph. We observe that majority of graphs corresponding to real-world applications follow the ``power-law`` distribution, where some hotspot nodes have significantly higher number of connections. We leverage this insight and propose ``FrozenQubits`` that freezes the hotspot nodes or qubits and intelligently partitions the state-space of the given problem into several smaller sub-spaces which are then solved independently. The corresponding QAOA sub-circuits are significantly less vulnerable to gate and decoherence errors due to the reduced number of CNOT operations in each sub-circuit. Unlike prior circuit-cutting approaches, FrozenQubits does not require any exponentially complex post-processing step. Our evaluations with 5,300 QAOA circuits on eight different quantum computers from IBM shows that FrozenQubits can improve the quality of solutions by 8.73x on average (and by up to 57x), albeit utilizing 2x more quantum resources.