Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2404.01412 · Quantum

Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping

Filip B. Maciejewski, Jacob Biamonte, Stuart Hadfield, Davide Venturelli

Published Nov 6, 2025• 31 citations
arXivHTMLPDF

Abstract

We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios 0.9 - 0.96 for random, fully connected graphs on n = 82 qubits, using only depth p = 1 QAOA with NDAR. This compares to 0.34 - 0.51 for standard p = 1 QAOA with the same number of function calls.

DOI
10.22331/q-2025-11-06-1906

Related papers

Noise-Directed Adaptive Remapping for Integer Optimization: from qubits to (encoded) qudits

Stuart Hadfield, Filip B. Maciejewski, Davide Venturelli

We extend Noise-Directed Adaptive Remapping (NDAR), a recently proposed heuristic meta-algorithm that leverages device noise as a computational resource, to optimization problems over discrete (integer) domains. While originally introduced for unconstrained binary optimization, the proposed generalization introduces additional gauge degrees of freedom at the logical level, such that the gauge transformation applied at each iteration is no longer unique, allowing tailoring to particular encodings or quantum hardware. We identify encoding-dependent requirements for NDAR beyond binary domains: feasibility of the noise attractor, existence of compatible gauge transformations that preserve an efficiently implementable circuit family, and a systematic way to select the transform to apply at each step. We analyze these criteria for qudit-native and for binary, one-hot, and domain-wall qubit encodings, using the Max-k-colorable subgraph problem as a running example. We demonstrate that these encodings can exhibit distinct advantages and tradeoffs when integrated within the NDAR framework, particularly in how noise-induced dynamics interact with the solution landscape and choice of encoding. Our results indicate that NDAR-guided noise considerations provide a new criterion for comparing device-level encoding choices for quantum optimization. Finally, we outline directions toward experimental realization in superconducting qudit devices and further algorithmic improvements.

quant-pharXiv:2606.28234•Jun 29, 2026•3 citations

Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting

Filip B. Maciejewski, Stuart Hadfield, Oscar Wallis +5 more

Progress towards a quantum advantage using known heuristic methods for combinatorial optimization is impeded by hardware noise and limited qubit count. Here, we propose a noise-aware adaptive approach to quantum approximate optimization, Noise-Directed Adaptive Warm-Starting (ND-AWS), that builds on recent concepts such as Warm-Start QAOA and Noise-Directed Adaptive Remapping. By leveraging bitflip gauge transformations, our algorithm exploits amplitude-damping-like noise components. We experimentally implement high-performance quantum optimization ansätze on 100-qubit Ising Hamiltonians, showing that ND-AWS generally improves the performance over a non-gauge-transformed iterative Warm-Starting variant, at no additional circuit cost. This places our results among the highest-quality demonstrations of quantum optimization with similar ansätze at this scale. Crucially, the simplicity of the framework opens the door for future enhancements such as adaptive bias schedules, and integration with classical solvers.

quant-pharXiv:2607.09368•Jul 13, 2026•6 citations

Enhancing NDAR with Delay-Gate-Induced Amplitude Damping

Tam, Wai-Hong, Hiromichi Matsuyama, Sakai, Ryo +1 more

The Noise-Directed Adaptive Remapping (NDAR) method utilizes amplitude damping noise to enhance the performance of quantum optimization algorithms. NDAR alternates between exploration by sampling solutions from the quantum circuit and exploitation by transforming the cost Hamiltonian by changing the signs of its terms. Both exploration and exploitation are important components in classical heuristic algorithm design. In this study, we examine how NDAR performance improves by adjusting the balance between these components. We control the degree of exploitation by varying the delay time to 0, 50, and $100~μ\text{s}$, and investigate exploration strategies using two quantum circuits, QAOA and a random circuit, on IBM's Heron processor. Our results show that increasing delay time in NDAR improves the best objective value found in each iteration. In single-layer QAOA and random circuits applied to unweighted Max-Cut problem with low edge density, both exploration strategies yield similar objective value trajectories and provide competitive solution quality to simulated annealing for the 80-node problem. Their similar performance indicates that, in most cases, increasing amplitude damping noise via additional delay time results in information loss. On the other hand, QAOA outperforms random circuits in specific cases, such as positive-negative weighted Max-Cut on a fully connected graph. This suggests potential advantages of QAOA in more complex settings. We further develop a classical NDAR to better understand exploration strategies, demonstrating that controlling the Hamming weight distribution of sampled bitstrings yields higher quality solutions. This suggests that identifying suitable quantum circuits for exploration could enhance NDAR performance.

arXiv:2504.12628•Apr 17, 2025•4 citations

A Multilevel Approach for Solving Large-Scale QUBO Problems with Noisy Hybrid Quantum Approximate Optimization

Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont +5 more

Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing quantum processing units (QPUs) are of relatively small size, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform when used as a sub-solver within such a multilevel strategy. To this aim, we combine and extend (via additional classical processing steps) the recently proposed Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax & Round (QRR) algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's superconducting transmon device Ankaa-2. We find approximate solutions to 10 instances of fully connected 82-qubit Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios (ARs) in the range$\sim 0.98-1.0$, and the same class with real-valued coefficients (ARs$\sim 0.94-1.0)$. Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for 6 large-scale graphs with at most$\sim 27,000$variables. In practice, the QPU (with classical post-processing steps) is used to find approximate solutions to dozens of at most 82-qubit problems, which are iteratively used to construct the global solution. We observe that quantum optimization results are competitive in terms of the quality of solutions when compared to classical heuristics used as subsolvers within the multilevel approach. Reproducibility: source code and data will be available at [1].

arXiv:2408.07793•IEEE High Performance Extreme Computing Conference•Sep 23, 2024•17 citations

Design-Space Exploration of Quantum Approximate Optimization Algorithm under Noise

Mahabubul Alam, Abdullah Ash Saki, Swaroop Ghosh

Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.

Custom Integrated Circuits Conference•Mar 1, 2020•32 citations

Adaptive Bias Fields Quantum Approximate Optimization Algorithm for Molecular Docking

Gang Liu, Jiapei Zhuang

Molecular docking, a critical task in drug discovery, represents a highly promising application domain for quantum computing. While the Quantum Approximate Optimization Algorithm (QAOA) shows potential, its performance on near-term quantum devices is limited by noise susceptibility and optimization challenges such as barren plateaus. To address these limitations, we apply Adaptive Bias Fields QAOA (ABF-QAOA) to solve molecular docking problems mapped to Ising Hamiltonians. Our results demonstrate that ABF-QAOA achieves accelerated convergence and higher solution accuracy compared to standard QAOA. In addition, under simulated quantum noise conditions, ABF-QAOA maintains higher solution quality, showcasing significantly enhanced noise resilience. This work establishes ABF-QAOA as a robust quantum approach for molecular docking on noisy intermediate-scale quantum (NISQ) hardware.

International Conference on Computing, Communication, Perception and Quantum Technology (CCPQT)•Oct 24, 2025•1 citation
We present Noise-Directed Adaptive Remapping (NDAR), a heuristic algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. In a standard setting, such noise can be detrimental to the quantum optimization performance. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions. The transformation effectively changes the attractor into a higher-quality solution of the Hamiltonian based on the results of the previous step. The end result is that noise aids variational optimization, as opposed to hindering it. We present an improved Quantum Approximate Optimization Algorithm (QAOA) runs in experiments on Rigetti's quantum device. We report approximation ratios 0.9 - 0.96 for random, fully connected graphs on n = 82 qubits, using only depth p = 1 QAOA with NDAR. This compares to 0.34 - 0.51 for standard p = 1 QAOA with the same number of function calls.
We extend Noise-Directed Adaptive Remapping (NDAR), a recently proposed heuristic meta-algorithm that leverages device noise as a computational resource, to optimization problems over discrete (integer) domains. While originally introduced for unconstrained binary optimization, the proposed generalization introduces additional gauge degrees of freedom at the logical level, such that the gauge transformation applied at each iteration is no longer unique, allowing tailoring to particular encodings or quantum hardware. We identify encoding-dependent requirements for NDAR beyond binary domains: feasibility of the noise attractor, existence of compatible gauge transformations that preserve an efficiently implementable circuit family, and a systematic way to select the transform to apply at each step. We analyze these criteria for qudit-native and for binary, one-hot, and domain-wall qubit encodings, using the Max-k-colorable subgraph problem as a running example. We demonstrate that these encodings can exhibit distinct advantages and tradeoffs when integrated within the NDAR framework, particularly in how noise-induced dynamics interact with the solution landscape and choice of encoding. Our results indicate that NDAR-guided noise considerations provide a new criterion for comparing device-level encoding choices for quantum optimization. Finally, we outline directions toward experimental realization in superconducting qudit devices and further algorithmic improvements.
Progress towards a quantum advantage using known heuristic methods for combinatorial optimization is impeded by hardware noise and limited qubit count. Here, we propose a noise-aware adaptive approach to quantum approximate optimization, Noise-Directed Adaptive Warm-Starting (ND-AWS), that builds on recent concepts such as Warm-Start QAOA and Noise-Directed Adaptive Remapping. By leveraging bitflip gauge transformations, our algorithm exploits amplitude-damping-like noise components. We experimentally implement high-performance quantum optimization ansätze on 100-qubit Ising Hamiltonians, showing that ND-AWS generally improves the performance over a non-gauge-transformed iterative Warm-Starting variant, at no additional circuit cost. This places our results among the highest-quality demonstrations of quantum optimization with similar ansätze at this scale. Crucially, the simplicity of the framework opens the door for future enhancements such as adaptive bias schedules, and integration with classical solvers.
The Noise-Directed Adaptive Remapping (NDAR) method utilizes amplitude damping noise to enhance the performance of quantum optimization algorithms. NDAR alternates between exploration by sampling solutions from the quantum circuit and exploitation by transforming the cost Hamiltonian by changing the signs of its terms. Both exploration and exploitation are important components in classical heuristic algorithm design. In this study, we examine how NDAR performance improves by adjusting the balance between these components. We control the degree of exploitation by varying the delay time to 0, 50, and 100 μs100~μ\text{s}100 μs, and investigate exploration strategies using two quantum circuits, QAOA and a random circuit, on IBM's Heron processor. Our results show that increasing delay time in NDAR improves the best objective value found in each iteration. In single-layer QAOA and random circuits applied to unweighted Max-Cut problem with low edge density, both exploration strategies yield similar objective value trajectories and provide competitive solution quality to simulated annealing for the 80-node problem. Their similar performance indicates that, in most cases, increasing amplitude damping noise via additional delay time results in information loss. On the other hand, QAOA outperforms random circuits in specific cases, such as positive-negative weighted Max-Cut on a fully connected graph. This suggests potential advantages of QAOA in more complex settings. We further develop a classical NDAR to better understand exploration strategies, demonstrating that controlling the Hamming weight distribution of sampled bitstrings yields higher quality solutions. This suggests that identifying suitable quantum circuits for exploration could enhance NDAR performance.
Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing quantum processing units (QPUs) are of relatively small size, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform when used as a sub-solver within such a multilevel strategy. To this aim, we combine and extend (via additional classical processing steps) the recently proposed Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax & Round (QRR) algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's superconducting transmon device Ankaa-2. We find approximate solutions to 10 instances of fully connected 82-qubit Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios (ARs) in the range∼0.98−1.0\sim 0.98-1.0∼0.98−1.0, and the same class with real-valued coefficients (ARs∼0.94−1.0)\sim 0.94-1.0)∼0.94−1.0). Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for 6 large-scale graphs with at most∼27,000\sim 27,000∼27,000variables. In practice, the QPU (with classical post-processing steps) is used to find approximate solutions to dozens of at most 82-qubit problems, which are iteratively used to construct the global solution. We observe that quantum optimization results are competitive in terms of the quality of solutions when compared to classical heuristics used as subsolvers within the multilevel approach. Reproducibility: source code and data will be available at [1].
Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.
Molecular docking, a critical task in drug discovery, represents a highly promising application domain for quantum computing. While the Quantum Approximate Optimization Algorithm (QAOA) shows potential, its performance on near-term quantum devices is limited by noise susceptibility and optimization challenges such as barren plateaus. To address these limitations, we apply Adaptive Bias Fields QAOA (ABF-QAOA) to solve molecular docking problems mapped to Ising Hamiltonians. Our results demonstrate that ABF-QAOA achieves accelerated convergence and higher solution accuracy compared to standard QAOA. In addition, under simulated quantum noise conditions, ABF-QAOA maintains higher solution quality, showcasing significantly enhanced noise resilience. This work establishes ABF-QAOA as a robust quantum approach for molecular docking on noisy intermediate-scale quantum (NISQ) hardware.