  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.
