Abstract
Although quantum approximate optimization algorithm (QAOA) has demonstrated its quantum supremacy, its performance on Noisy Intermediate-Scale Quantum (NISQ) devices would be influenced by complicated noises, e.g., quantum colored noises. To evaluate the performance of QAOA under these noises, this paper presents a framework for running QAOA on non-Markovian quantum systems which are represented by an augmented system model. In this model, a non-Markovian environment carrying quantum colored noises is modelled as an ancillary system driven by quantum white noises which is directly coupled to the corresponding principal system; i.e., the computational unit for the algorithm. With this model, we mathematically formulate QAOA as piecewise Hamiltonian control of the augmented system, where we also optimize the control depth to fit into the circuit depth of current quantum devices. For efficient simulation of QAOA in non-Markovian quantum systems, a boosted algorithm using quantum trajectory is further presented. Finally, we show that non-Markovianity can be utilized as a quantum resource to achieve a relatively good performance of QAOA, which is characterized by our proposed exploration rate.
Introduction
The Quantum Approximate Optimization Algorithm (QAOA) is a cornerstone of the Noisy Intermediate-Scale Quantum (NISQ) era, designed to solve combinatorial optimization problems. However, most theoretical frameworks assume either a closed system or a Markovian environment characterized by memoryless "white" noise. In practice, quantum hardware is often subject to non-Markovian "colored" noise, where the environment retains a memory of its interactions with the system. This paper introduces a novel framework to model these complex interactions and demonstrates that non-Markovianity can actually be harnessed to improve optimization performance.
Methodology
The researchers propose three primary innovations to adapt QAOA for non-Markovian environments:
Augmented System Model
To avoid the computational complexity of solving non-Markovian master equations directly, the authors utilize an augmented system model. In this approach, the principal quantum system (the computational unit) is coupled to an ancillary system that represents the environment. This ancillary system is driven by standard quantum white noise, effectively transforming the non-Markovian dynamics into a Markovian process in a higher-dimensional space.
Regularized QAOA with Depth Constraints
Recognizing the physical limitations of NISQ devices, the framework incorporates $l_1$ regularization into the optimization objective. This penalizes excessive control durations, ensuring the algorithm stays within the coherence time limits of the hardware by maintaining a manageable circuit depth.
Boosted QAOA via Quantum Trajectories
Simulating high-dimensional augmented systems using density matrices is memory-intensive. The authors introduce a "boosted" simulation technique using quantum trajectories. By evolving stochastic state vectors instead of full density matrices, the method significantly reduces memory overhead and enables parallelized computation, allowing for the simulation of larger quantum systems.
Experimental Evaluation
The framework was evaluated using the Max-Cut problem, a standard benchmark for quantum optimization. The researchers tested the algorithm on weighted graphs ranging from 4 to 11 nodes under various noise profiles, including single- and double-Lorentzian power spectral densities.
Discussion: Non-Markovianity as a Resource
A key insight of this work is that non-Markovianity is not merely a source of error but can serve as a computational resource. The "memory" inherent in the environment allows for more complex system evolution, which can help the optimization process escape local minima.
The authors define an exploration rate ($\bar{\sigma}(\Phi)$) to characterize this effect. Their findings suggest a "Goldilocks zone" for exploration: a rate that is too low results in conservative searches that miss optimal solutions, while a rate that is too high causes the algorithm to skip over high-quality solutions. An intermediate exploration rate (typically between 0.6 and 2.0) was found to yield the highest approximation ratios.
Key Results
- Performance Gains: In a 4-node Max-Cut instance, the non-Markovian QAOA achieved an optimal solution probability of 0.8260, nearly doubling the 0.4760 achieved by standard Markovian QAOA.
- Scalability: The framework maintained stable approximation ratios (0.85–0.90) for graphs up to 11 nodes.
- Efficiency: The boosted trajectory algorithm demonstrated a 90% reduction in computation time and a 94% reduction in memory usage for an 8-node problem compared to standard density matrix approaches.
Conclusion
This research provides a robust framework for implementing QAOA in realistic, noisy environments. By modeling noise through an augmented system and utilizing efficient simulation techniques, the authors show that non-Markovian effects can be exploited to enhance quantum optimization. Future work will focus on the active control of environmental noise and the validation of these results on physical quantum processors.
Summary updated