Guest Post by Jordan Makansi
As the quantum computing community awaits the advent of fault-tolerant hardware, a class of techniques has emerged that harnesses the noise inherent in near-term quantum devices. These methods, referred to as Noise-Adaptive Quantum Algorithms (NAQAs), are designed to exploit rather than suppress quantum noise. This article examines the nature of NAQAs, their origins, the key literature driving the field, and potential future directions.
What Are Noise-Adaptive Quantum Algorithms?
Quantum Processing Units (QPUs) currently operate in noisy environments. In a hypothetical noise-free setting, the solution with the lowest energy would unequivocally be the best and only one worth keeping. However, real-world quantum systems are subject to noise, complicating this ideal. In practice, multiple low-energy solutions may be produced, and any single bitstring sample might not represent a satisfactory or even feasible solution, particularly when constraints are involved.
Rather than discarding these imperfect samples, NAQAs aggregate information across multiple noisy outputs. Because of quantum correlation, this aggregation can be used to adapt the original optimization problem, thereby guiding the quantum system towards improved solutions before committing to a single sample. This strategic re-use of noisy data defines the essence of NAQAs.
Origins and Classical Analogy
NAQAs bear conceptual resemblance to the classical Cross-Entropy Method (CEM). While CEM does not involve physical noise, it simulates distributions through candidate sampling, followed by iterative refinement. Both CEM and NAQAs seek to guide the search process by adapting to noisy outputs.
| Aspect | Cross-Entropy Method (CEM) | Noise-Adaptive Quantum Algorithms (NAQAs) |
| Output Evaluation | Evaluate sampled candidates via a noisy cost function | Measure quantum bitstrings and compute their cost |
| Optimization Adaptation | Update sampling distribution toward top performers | Identify new attractor state; transform cost Hamiltonian accordingly |
| Optimization Target | Maximize performance over a probability distribution | Minimize cost under transformed Hamiltonian |
| Use of Noise | Noise is averaged over | Noise is exploited to identify attractor states |
It is important to note that this line of work differs fundamentally from the ADAPT family of algorithms, such as ADAPT-VQE [12] and ADAPT-QAOA [11]. These algorithms adapt to problem structure by changing how the search space is explored (i.e. which “mixing” Hamiltonian is used), as the algorithm progresses. These algorithms have thus far only shown success in noise-free simulations, so if implemented as they’ve been originally presented, there is no intent to exploit noise from the QPU. In contrast, the NAQA series is tested on real, noisy quantum hardware.
NAQA Framework
A general pseudocode for NAQAs can be summarized as follows:
- Sample Generation: Obtain a sample set from a quantum program.
- Problem Adaptation: Adjust the optimization problem based on insights from the sampleset. Two techniques are:
- Identifying the attractor state and applying a bit-flip gauge transformation, as in [6-8].
- Fixing the values of certain variables by analyzing correlations across samples, as demonstrated in [5], [9], and [10].
- Re-optimization: Re-solve the modified optimization problem.
- Repeat: Iterate this process until a satisfactory solution quality is reached, or until solution quality stops improving.
This framework applies to both gate-based and annealing-based quantum computers. The most subtle and challenging aspect lies in Step 2: extracting and aggregating information from many noisy samples to adjust the optimization problem. This adjustment steers the algorithm toward promising solutions while avoiding less favorable ones—ideally without overly restricting the solution space. The trade-off is similar to the classical machine learning dilemma of exploration versus exploitation. While this approach introduces additional computational overhead, NAQAs remain practical for near-term devices and often yield significantly higher-quality solutions than standard methods like vanilla QAOA in noisy environments—albeit at the cost of increased runtime (details to follow).
Lineage of NAQA Research
The conceptual roots of NAQAs can be traced to the “Quantum-Assisted Greedy Algorithms” introduced in [5], where variables are fixed based on consensus across multiple sample bitstrings. This methodology was tested on D-Wave’s QPU.
Subsequent developments include:
- Quantum-Enhanced Greedy Combinatorial Optimization Solver [9]
- Extending Relax and Round Combinatorial Optimization Solvers with Quantum Correlations [10]
- Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping [6]
- Enhancing NDAR with Delay-Gate Induced Amplitude Damping [7]
- A Multilevel Approach for Solving Large-Scale QUBO Problems with Noisy Hybrid Quantum Approximate Optimization [8]
Among these, [6] is perhaps the seminal paper, coining the term Noise-Directed Adaptive Remapping, (NDAR) which serves as a cornerstone for subsequent research. Practical applications of these methods are beginning to emerge, such as in [13], which applies NAQAs to real-world optimization problems.
Advantages and Disadvantages of NAQAs
Advantages:
- Simplicity and Modularity: The framework is conceptually straightforward and modular. In fact, the sampling step need not rely exclusively on quantum systems. [6], for example, refers to this stage as “stochastic optimization.”
- Improved Solution Quality: Empirical results suggest that NAQAs outperform baseline techniques such as vanilla QAOA in noisy environments.
Disadvantages:
- Computational Overhead: These algorithms can be computationally intensive. Notably, many key papers omit runtime data, indicating potential performance concerns.
- Cost of Adaptation: Step 2, involving transformation of the optimization problem, can be particularly demanding—especially when requiring operations such as eigenvalue decompositions, which scale cubically with the number of samples, (O(n³)) [9].
Unknowns:
- Transferability: While NAQAs show strong results on Sherrington-Kirkpatrick (SK) Ising models, practical problems often produce Ising models with power-law degree distributions [1, 2], raising questions about generalizability.
- Comparative Benchmarks: There are limited comparisons with alternative noise-aware algorithms. A compelling direction would be to benchmark NAQAs against Q-CTRL’s hardware-agnostic MaxCut solver, which reports high approximation ratios on similar problem instances [4].
Future Directions for NAQAs
NAQAs are inherently flexible and can be enriched through integration with other optimization advancements. For example, the authors of [6] presented a basic version of their NDAR algorithm, and after enhancing their algorithm in [8] showed that it out-performs the original NDAR algorithm while running approximately 3x faster. However, it is not clear how this extended version of NDAR compares to other noise-adaptive techniques like quantum relax-and-round from [10].
There is also potential to incorporate techniques that have shown promise in a noise-free simulation, in Step 1. For instance, techniques like ADAPT-QAOA can be used to obtain the samples that are subsequently processed to steer the algorithm in a more promising direction.
Furthermore, post-processing strategies such as shimming and calibration refinement [3] can be layered onto NAQAs, further enhancing solution quality. NAQA’s modularity points to a rich direction for future work, with more gains expected as noise-aware methods mature.
About the author:
Jordan is an expert in quantum algorithms with a strong background in both academic research and industry applications. He spent several years as a research assistant at the University of Southern California, where he implemented quantum algorithms for optimization. In industry, he has tackled classical optimization problems across diverse sectors, including energy, healthcare, and cybersecurity. Jordan has contributed to several successful startups and holds multiple patents in control optimization for energy systems. He holds a Master’s degree in Systems Engineering from UC Berkeley and a Master’s in Applied Mathematics from the University of Washington, Seattle. He can be reached at makansij (at) gmail (dot) com
References
[1] D. Gamermann, J. Triana-Dopico, R. Jaime. A comprehensive statistical study of metabolic and protein–protein interaction network properties. Physica A, 534:122204, 2019.
[2] K.-I. Goh, E. Oh, H. Jeong, B. Kahng, D. Kim. Classification of scale-free networks. PNAS, 99(20):12583–12588, 2002.
[3] Chern, K., Boothby, K., Raymond, J., Farré, P., & King, A. D. (2023). Tutorial: Calibration refinement in quantum annealing. Frontiers in Computer Science, 5, Article 1238988. https://doi.org/10.3389/fcomp.2023.1238988
[4] N. Sachdeva et al. Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems. arXiv:2406.01743.
[5]. Ayanzadeh, R., Dorband, J. E., Halem, M., & Finin, T. (2022). Quantum-assisted greedy algorithms. arXiv. https://doi.org/10.48550/arXiv.2208.02042
[6] Maciejewski, F. B., Biamonte, J., Hadfield, S., & Venturelli, D. (2024). Improving quantum approximate optimization by noise-directed adaptive remapping. arXiv. https://doi.org/10.48550/arXiv.2404.01412
[7] Tam, W.-H., Matsuyama, H., Sakai, R., & Yamashiro, Y. (2025). Enhancing NDAR with delay-gate-induced amplitude damping. arXiv. https://doi.org/10.48550/arXiv.2504.12628
[8] Maciejewski, F. B., Bach, B. G., Dupont, M., Lott, P. A., Sundar, B., Bernal Neira, D. E., Safro, I., & Venturelli, D. (2024). A multilevel approach for solving large-scale QUBO problems with noisy hybrid quantum approximate optimization. arXiv. https://doi.org/10.48550/arXiv.2408.07793
[9] Dupont, M., Evert, B., Hodson, M. J., Sundar, B., Jeffrey, S., Yamaguchi, Y., Feng, D., Maciejewski, F. B., Hadfield, S., Alam, M. S., Wang, Z., Grabbe, S., Lott, P. A., Rieffel, E. G., Venturelli, D., & Reagor, M. J. (2023). Quantum-enhanced greedy combinatorial optimization solver. arXiv. https://doi.org/10.48550/arXiv.2303.05509
[10] Dupont, M., & Sundar, B. (2024). Extending relax-and-round combinatorial optimization solvers with quantum correlations. arXiv. https://doi.org/10.48550/arXiv.2307.05821
[11] Zhu, L., Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., Broughton, M., Buckley, B. B., Buell, D. A., Burkett, B., Bushnell, N., Chen, Y., Chen, Z., Chiaro, B., Collins, R., … Martinis, J. M. (2020). An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv preprint arXiv:2005.10258.
[12] Grimsley, H. R., Economou, S. E., Barnes, E., & Mayhall, N. J. (2019). An adaptive variational algorithm for exact molecular simulations on a quantum computer. arXiv preprint arXiv:1812.11173
[13] Makansi, J., & Bernal, D. E. (2024). A Greedy Quantum Route-Generation Algorithm. ArXiv.org. https://arxiv.org/abs/2405.03054
