⇦Chinese Physics Letters, 2021, Vol. 38, No. 3, Article code 030302 Effects of Quantum Noise on Quantum Approximate Optimization Algorithm Cheng Xue (薛程)1, Zhao-Yun Chen (陈昭昀)1,2, Yu-Chun Wu (吴玉椿)1, and Guo-Ping Guo (郭国平)1* Affiliations 1Key Laboratory of Quantum Information, Chinese Academy of Sciences, School of Physics, University of Science and Technology of China, Hefei 230026, China 2Origin Quantum Computing Hefei, Hefei 230026, China Received 24 November 2020; accepted 25 December 2020; published online 2 March 2021 Supported by the National Key Research and Development Program of China (Grant No. 2016YFA0301700), the National Natural Science Foundation of China (Grants No. 11625419), the Strategic Priority Research Program of the Chinese Academy of Sciences (Grant No. XDB24030600), and the Anhui Initiative in Quantum Information Technologies (Grant No. AHY080000).
*Corresponding author. Email: gpguo@ustc.edu.cn Citation Text: Xue C, Chen Z Y, Wu Y C, and Guo G P 2021 Chin. Phys. Lett. 38 030302    Abstract The quantum-classical hybrid algorithm is a promising algorithm with respect to demonstrating the quantum advantage in noisy-intermediate-scale quantum (NISQ) devices. When running such algorithms, effects due to quantum noise are inevitable. In our work, we consider a well-known hybrid algorithm, the quantum approximate optimization algorithm (QAOA). We study the effects on QAOA from typical quantum noise channels, and produce several numerical results. Our research indicates that the output state fidelity, i.e., the cost function obtained from QAOA, decreases exponentially with respect to the number of gates and noise strength. Moreover, we find that when noise is not serious, the optimized parameters will not deviate from their ideal values. Our result provides evidence for the effectiveness of hybrid algorithms running on NISQ devices. DOI:10.1088/0256-307X/38/3/030302 © 2021 Chinese Physics Society Article Text In recent years, there have been rapid developments towards building quantum computers. The expectation is that these will feature a quantum chip containing hundreds of qubits—in essence, a noisy-intermediate-scale quantum (NISQ)[1] device. However, some quantum algorithms will require enormous numbers of qubits, as well as a quantum circuit having a long circuit depth, to realize quantum supremacy.[2] When running complex quantum circuits, quantum error correction codes need to be executed, but this will further increase the required number of qubits and quantum circuit complexity. For example, to factor 2048-bit RSA integers requires 20 billion noisy qubits.[3] This requirement far exceeds the capacity of current quantum chips, and this is likely to remain the case for the near future. One meaningful problem is to find a quantum algorithm capable of realizing quantum supremacy on NISQ devices. A quantum-classical hybrid algorithm shows promise in this regard. In recent years, several quantum-classical hybrid algorithms have been proposed,[4–12] a few of which have been demonstrated experimentally on real quantum chips.[5,13–20] In NISQ devices, quantum noise is inevitable, and quantum algorithms running on NISQ devices need to be noise tolerant. However, little research has been conducted to date to study how quantum noise affects the performance of these quantum-classical hybrid algorithms. In Ref. [21], Sharma at al. studied the effects of quantum noise on variational quantum compiling[22–24] and proposed optimal parameter resilience (OPR). In this Letter, we focus on a specific quantum-classical hybrid algorithm—the quantum approximate optimization algorithm (QAOA).[25–29] There is currently limited research concerning the effects of quantum noise on the QAOA. In our work, we study specifically the effects of quantum noise on its performance. We analyze the effects of quantum noise on various aspects of QAOA, including the fidelity of its output state, its cost function, and its parameter optimization. We find that QAOA is noise tolerant, although the QAOA parameter space is somewhat flattened by noise. To demonstrate our conclusion, we choose three different quantum noise channels, testing the effects of each on the QAOA by means of numerical simulations. In the following, we show describe our work in further detail. In our work, we consider quantum noise, for which the Kraus operators are written as $$ K=\{a_0I,a_1K_1,a_2K_2,\ldots,a_sK_s\},~~ \tag {1} $$ where each $a_i$ represents a real number, and $I$ is the identity operator. In our numerical simulations, we choose three quantum noise channels: dephasing, bit flip, and depolarizing channels. The Kraus operators of each are given as follows. Dephasing noise: $$ K_{\rm dephasing}=\{\sqrt{1-p}I,\sqrt{p}Z\}.~~ \tag {2} $$ Bit flip noise: $$ K_{\rm bitflip}=\{\sqrt{1-p}I,\sqrt{p}X\}.~~ \tag {3} $$ Depolarizing noise: $$ K_{\rm depolarizing}=\Big\{\sqrt{1-\frac{3}{4}p}I,\frac{\sqrt{p}}{2}X,\frac{\sqrt{p}}{2}Y, \frac{\sqrt{p}}{2}Z\Big\}.~~ \tag {4} $$ Here $X,Y,Z$ represent the Pauli $X,Y,Z$ matrices, respectively. These three channels have one parameter, $p$. We choose $p$ to be in the range $[0.0001,0.02]$; more specifically, we focus on a smaller interval, and therefore utilize the exponential interval, $$ p_i=0.0001\times 200^{0.1\times i}, ~i=0,1,\ldots,10.~~ \tag {5} $$
cpl-38-3-030302-fig1.png
Fig. 1. Max-Cut graph.
Table 1. Edge weight table.
Edge Weight Edge Weight
0,4 0.73 2,5 0.88
0,5 0.33 2,6 0.58
0,6 0.50 3,5 0.67
1,4 0.69 3,6 0.43
1,5 0.36
We test the effects of this kind of quantum noise on QAOA performance using a treatment of the maximum cut (Max-Cut) problem in graph theory. The specific Max-Cut problem we treat corresponds to finding the maximum cut in an undirected graph. The undirected graph information of the selected Max-Cut problem is shown in Fig. 1 and Table 1. Firstly, we analyze the effects of quantum noise on the state fidelity of the output state of a QAOA quantum circuit. As shown in the Supplemental Material, for a specific QAOA quantum circuit, $U({\boldsymbol \gamma},{\boldsymbol \beta})$; if there is no quantum noise, the output quantum state is $$ |\phi^{\rm ideal}_{\rm out}\rangle=U({\boldsymbol \gamma},{\boldsymbol \beta})|\phi_{\rm in}\rangle.~~ \tag {6} $$ We use $N$ to denote the number of quantum gates in the QAOA quantum circuit. The noisy output quantum state is expressed as $$\begin{align} \rho_{\rm out}^{\rm noise}={}&\sum_{i_1,i_2,\ldots,i_N}p_{1,i_1}p_{2,i_2}\cdots p_{N,i_N}\\ &\cdot|\phi_{i_1,i_2,\ldots,i_N}\rangle\langle\phi_{i_1,i_2,\ldots,i_N}|,~~ \tag {7} \end{align} $$ where $i_j=0,1,2,\ldots,s$, $p_{k,i_j}$ signifies the probability that the $i_j$th noise Kraus operator acts when the quantum state evolves to the $k$th quantum gate. The fidelity between $|\phi_{\rm out}^{\rm ideal}\rangle$ and $\rho_{\rm out}^{\rm noise}$ is $$ F=\langle \phi_{\rm out}^{\rm ideal}|\rho_{\rm out}^{\rm noise}|\phi_{\rm out}^{\rm ideal}\rangle.~~ \tag {8} $$
cpl-38-3-030302-fig2.png
Fig. 2. Effect of quantum noise on output state fidelity. The horizontal axis gives the noise parameter $\log{(1-p)}$, the vertical axis is the output state fidelity. QAOA step $n=1$–4, and the corresponding quantum gate numbers of the QAOA quantum circuit are $N=[59,111,163,215]$, in which one double quantum gate is regarded as two quantum gates. Panels (a), (b), and (c) represent dephasing noise, bit flip noise, and depolarizing noise, respectively. The simulated $\delta$ and the corresponding variance are shown in Table 2.
Table 2. Parameter $\delta $'s fitting result.
Noise Step $\delta$ Variance
1 0.820929 $ 2.08951 \times 10^{-5}$
Dephasing 2 0.549195 $ 7.22086 \times 10^{-6}$
noise 3 0.692255 $ 5.32020 \times 10^{-6}$
4 0.559736 $ 9.267858 \times 10^{-6}$
1 0.656347 $ 5.06738 \times 10^{-6}$
Bit flip 2 0.212916 $ 8.12004 \times 10^{-6}$
noise 3 0.502418 $ 1.86095 \times 10^{-5}$
4 0.424866 $ 8.76859 \times 10^{-6}$
1 0.783912 $ 4.44939 \times 10^{-6}$
Depolarizing 2 0.819920 $ 6.71699 \times 10^{-6}$
noise 3 0.734511 $ 8.06321 \times 10^{-6}$
4 0.582604 $ 2.22129 \times 10^{-6}$
The proportion of the ideal output in relation to noisy output is $p_{1,0}p_{2,0}\cdots p_{N,0}=(1-p)^N$, where $1-p=a_0^2$. Except for $|\phi_{0,0,\ldots,0}\rangle$, only a small part of $|\phi_{i_1,i_2,\ldots,i_N}\rangle$ has a value for $|\langle \phi^{\rm ideal}_{\rm out}|\phi_{i_1,i_2,\ldots,i_N}\rangle|^2$, which is significantly larger than 0. We then perform a numerical simulation, finding that the output state fidelity can be approximated with the equation $$ F\approx(1-p)^{\delta N},~~ \tag {9} $$ for which $\delta$ is a constant, dependent on the quantum circuit architecture and quantum noise model. The numerical simulation results are shown in Fig. 2. We also consider a further fidelity, i.e., the overlap of QAOA output state, and the exact solution of the Max-Cut problem; here, we use $G$ to represent this fidelity, with $G$ defined as $$ G=\sum_{|\psi\rangle\in \boldsymbol{S}}{\langle\psi|\rho_{\rm out}^{\rm noise}}|\psi\rangle,~~ \tag {10} $$ where $\boldsymbol{S}=\{|0001111\rangle,|1110000\rangle\}$, which is the solution set of the Max-Cut problem we chose. The effects of quantum noise on $G$ are similar to the case of $F$, and $G$ can be expressed approximately via the equation $$ G\approx G_0(1-p)^{\eta N},~~ \tag {11} $$ where $\eta$ is a constant, and $G_0$ represents the overlap of noise-free output state and the exact solution of the Max-Cut problem. The numerical simulation results are shown in Fig. 3.
cpl-38-3-030302-fig3.png
Fig. 3. Effect of quantum noise on $G$. The horizontal axis gives the noise parameter $\log{(1-p)}$, and the vertical axis is $y=\log{(G/G_0)}$. The QAOA step $n=1$–4, and the corresponding $G_0$ is $G_0=[0.206220, 0.503128, 0.710670, 0.858298]$. Panels (a), (b), and (c) represent dephasing noise, bit flip noise, and depolarizing noise, respectively. The simulated $\eta$ and the corresponding variance are shown in Table 3.
Table 3. Parameter $\eta $'s fitting result.
Noise Step $\delta$ Variance
1 0.564126 $ 1.07561 \times 10^{-5}$
Dephasing 2 0.575603 $ 3.85836 \times 10^{-5}$
noise 3 0.547389 $ 8.08784 \times 10^{-5}$
4 0.524444 $ 8.93222 \times 10^{-5}$
1 0.475950 $ 1.16587 \times 10^{-5}$
Bit flip 2 0.549503 $ 3.24104 \times 10^{-5}$
noise 3 0.542246 $ 8.42643 \times 10^{-5}$
4 0.539797 $ 1.29240 \times 10^{-4}$
1 0.537495 $ 8.16338 \times 10^{-6}$
Depolarizing 2 0.635128 $ 1.77014 \times 10^{-5}$
noise 3 0.649509 $ 4.93053 \times 10^{-5}$
4 0.645789 $ 7.22830 \times 10^{-5}$
Secondly, we analyze the effects of quantum noise on the QAOA cost function defined in the following. In the Max-Cut problem, the problem Hamiltonian $H_{\it p}$ is written as $$ H_{\it p}=\sum_{i,j}{-C_{ij}\frac{1-Z_iZ_j}{2}}.~~ \tag {12} $$ In our work, we redefined $H_{\it p}$; specifically, we discarded its constant term and multiplied the result by 2, yielding $$ H_{\it p}=\sum_{i,j}{C_{ij}Z_iZ_j}.~~ \tag {13} $$ The performance and results of the QAOA are not influenced. One feature of the redefined $H_{\it p}$ is that its statistical average $\langle H_{\it p} \rangle$ in the entire space satisfies $$ \langle H_{\it p} \rangle={\rm Tr}\Big(\frac{H_{\it p}}{2^m}\Big)=0,~~ \tag {14} $$ where $m$ denotes the number of qubits. For a specific QAOA quantum circuit $U({\boldsymbol \gamma},{\boldsymbol \beta})$ with $N$ quantum gates, the cost function, if there is no quantum noise, is as follows: $$ f({\boldsymbol \gamma},{\boldsymbol \beta})^{\rm ideal}=\langle\phi_{\rm out}^{\rm ideal}|H_{\it p}|\phi_{\rm out}^{\rm ideal}\rangle.~~ \tag {15} $$ However, when quantum noise $K$ acts on the QAOA quantum circuit, the output state density matrix changes. The noisy cost function is then written as $$\begin{split} &f({\boldsymbol \gamma},{\boldsymbol \beta})^{\rm noise}=\\ &\sum_{i_1,i_2,\ldots,i_N}{p_{1,i_1}p_{2,i_2}\cdots p_{N,i_N} \langle\phi_{i_1,i_2,\ldots,i_N}|H_{\it p}|\phi_{i_1,i_2,\ldots,i_N}\rangle}. \end{split}~~ \tag {16} $$ We then perform further numerical simulations, finding that the noisy cost function can be approximated via the equation $$ f({\boldsymbol \gamma},{\boldsymbol \beta})^{\rm noise}\approx(1-p)^{\alpha N} f({\boldsymbol \gamma},{\boldsymbol \beta})^{\rm ideal},~~ \tag {17} $$ for which $\alpha$ is a constant, dependent on the quantum circuit architecture and quantum noise model. The numerical simulation results are shown in Fig. 4. Finally, we test the effects of quantum noise on the QAOA optimization process. We consider a reasonable assumption: When $(1-p)^{\alpha N}>C$, where $C$ is a constant, the optimal QAOA quantum circuit parameters are not changed. We use the vanilla gradient descent algorithm to optimize the QAOA quantum circuit parameters. In the selected Max-Cut problem, we find that when the initial values of parameters ${\boldsymbol \gamma}$ and ${\boldsymbol \beta}$ are close to 0, we obtain the best results after parameter optimization. As such, in our work, the initial values of ${\boldsymbol \gamma}$ and ${\boldsymbol \beta}$ are randomly chosen in the range $[-0.01,0.01]$.
cpl-38-3-030302-fig4.png
Fig. 4. Data fitting showing the effects of quantum noise on the QAOA cost function in the test. Here, $p$ is the noise parameter, and $y=\frac{f({\boldsymbol \gamma},{\boldsymbol \beta})^{\rm noise}}{f({\boldsymbol \gamma},{\boldsymbol \beta})^{\rm ideal}}$. Panels (a), (b), and (c) correspond to dephasing, bit flip, and depolarizing quantum noise, respectively. The simulated $\alpha$ and the corresponding variance are shown in Table 4.
cpl-38-3-030302-fig5.png
Fig. 5. Distance between noisy optimized parameters and ideal optimized parameters. Here, we select points which satisfy $(1-p)^{\alpha N}>0.9$, where $\alpha$ is listed in Table 4. Panels (a), (b), and (c) correspond to dephasing, bit flip, and depolarizing quantum noise, respectively.
We compute the distance between the ideal optimized parameters and the noisy optimized parameters. We use the root mean square of the Euclidean distance to describe the distance between two parameter sequences. Explicitly, we have the distance $\cal{D}$: $$\begin{alignat}{1} {\cal{D}}=\sqrt{\frac{|{\boldsymbol \gamma}^{\rm noise}-{\boldsymbol \gamma}^{\rm ideal}|^2 +|{\boldsymbol \beta}^{\rm noise}-{\boldsymbol \beta}^{\rm ideal}|^2}{2n}},~~ \tag {18} \end{alignat} $$ where $2n$ represents the parameter number of the QAOA quantum circuit. The results are shown in Fig. 5. The optimized parameters under conditions of quantum noise are close to those of ideal optimized parameters. From this, we infer that if we set sufficiently large execution times for the QAOA quantum circuit, the optimized parameters under conditions of quantum noise will be the same as those with ideal optimized parameters.
Table 4. Parameter $\alpha$'s fitting result.
Noise Step $\alpha$ Variance
1 0.325484 $ 3.61151 \times 10^{-5}$
Dephasing 2 0.305575 $ 4.13948 \times 10^{-6}$
noise 3 0.290244 $ 4.21576 \times 10^{-6}$
4 0.270603 $ 5.36495 \times 10^{-6}$
1 0.277000 $ 2.70421 \times 10^{-5}$
Bitflip 2 0.275399 $ 1.27296 \times 10^{-5}$
noise 3 0.287741 $ 2.57187 \times 10^{-5}$
4 0.293386 $ 4.66970 \times 10^{-5}$
1 0.307477 $ 4.10423 \times 10^{-5}$
Depolarizing 2 0.333806 $ 1.69716 \times 10^{-5}$
noise 3 0.340608 $ 6.17305 \times 10^{-6}$
4 0.346604 $ 2.39438 \times 10^{-5}$
In summary, we have investigated the effects of a class of quantum noise channels on QAOA performance, and arrived at the following conclusions: (1) For a specific QAOA quantum circuit, the relations between quantum noise parameter $p$ and the output state fidelity $F$ and $G$ are $F=(1-p)^{\delta N}$ and $G=G_0(1-p)^{\eta N}$. (2) For a specific QAOA quantum circuit, the relationship between quantum noise parameter $p$ and the cost function is $\frac{f^{\rm noise}}{f^{\rm ideal}}=(1-p)^{\alpha N}$. (3) QAOA is a noise tolerant algorithm, when $(1-p)^{\alpha N}$ is large enough, for both noisy and ideal QAOA cost functions, the optimized QAOA parameters being virtually the same. To support these conclusions, we evaluated the effects of dephasing, bit flip, and depolarizing quantum noise channels on the QAOA output, the test results being consistent with our conclusions. Our conclusions extend to other problems. The QAOA quantum circuit is a kind of multi-layer parameterized quantum circuit, and hence our conclusions apply equally to such circuits. Some unsolved problems remain. However. For example, our method is only suitable for certain low quantum noise channels, and is not applicable to arbitrary types. The effects of quantum noise on other NISQ quantum algorithms are also an open problem. In the future, we will extend our method to account for these considerations, and investigate the effects of quantum noise on other NISQ quantum algorithms. Notes: During the review of our manuscript, Marshall et al.[30] followed our work and offered new conclusions, proposing a more reasonable relationship between quantum noise parameter $p$ and state fidelity and cost function: Eqs. (9) and (17) are special cases of their conclusions. References Quantum Computing in the NISQ era and beyondQuantum computing and the entanglement frontierHow to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubitsQuantum circuit learningSupervised learning with quantum-enhanced feature spacesQuantum Generative Adversarial LearningQuantum generative adversarial networksQuantum autoencoders for efficient compression of quantum dataQuantum Boltzmann MachineClassification with Quantum Neural Networks on Near Term ProcessorsQuantum Machine Learning in Feature Hilbert SpacesImplementing a distance-based classifier with a quantum interference circuitGenerative model benchmarks for superconducting qubitsTraining of quantum circuits on a hybrid quantum computerHierarchical quantum classifiersAn artificial neuron implemented on an actual quantum processorExperimental learning of quantum statesExperimental Implementation of a Quantum Autoencoder via Quantum AddersA generative modeling approach for benchmarking and training shallow quantum circuitsNoise resilience of variational quantum compilingQuantum-assisted quantum compilingQuantum compilation and circuit optimisation via energy dissipationVariational Quantum Gate OptimizationA Quantum Approximate Optimization AlgorithmUnsupervised Machine Learning on a Hybrid Quantum ComputerFrequency of everyday pro-environmental behaviour is explained by baseline activation in lateral prefrontal cortexPerformance of the Quantum Approximate Optimization Algorithm on the Maximum Cut ProblemQuantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term DevicesCharacterizing local noise in QAOA circuits
[1] Preskill J 2018 Quantum 2 79
[2] Preskill J 2012 arXiv:1203.5813[quant-ph]
[3] Gidney C and Ekerå M 2019 arXiv:1905.09749[quant-ph]
[4] Mitarai K, Negoro M, Kitagawa M and Fujii K 2018 Phys. Rev. A 98 032309
[5] Havlíček V, Córcoles A D, Temme K, Harrow A W, Kandala A, Chow J M and Gambetta J M 2019 Nature 567 209
[6] Lloyd S and Weedbrook C 2018 Phys. Rev. Lett. 121 040502
[7] Dallaire-Demers P L and Killoran N 2018 Phys. Rev. A 98 012324
[8] Romero J, Olson J P and Aspuru-Guzik A 2017 Quantum Sci. Technol. 2 045001
[9] Amin M H, Andriyash E, Rolfe J, Kulchytskyy B and Melko R 2018 Phys. Rev. X 8 021050
[10] Farhi E and Neven H 2018 arXiv:1802.06002[quant-ph]
[11] Schuld M and Killoran N 2019 Phys. Rev. Lett. 122 040504
[12]Schuld M, Bocharov A, Svore K M and Wiebe N 2020 Phys. Rev. A 101 032308
[13] Schuld M, Fingerhuth M and Petruccione F 2017 Europhys. Lett. 119 60002
[14] Hamilton K E, Dumitrescu E F and Pooser R C 2019 Phys. Rev. A 99 062323
[15] Zhu D, Linke N M, Benedetti M, Landsman K A, Nguyen N H, Alderete C H, Perdomo-Ortiz A, Korda N, Garfoot A and Brecque C et al. 2019 Sci. Adv. 5 eaaw9918
[16] Grant E, Benedetti M, Cao S, Hallam A, Lockhart J, Stojevic V, Green A G and Severini S 2018 npj Quantum Inf. 4 65
[17] Tacchino F, Macchiavello C, Gerace D and Bajoni D 2019 npj Quantum Inf. 5 26
[18] Rocchetto A, Aaronson S, Severini S, Carvacho G, Poderini D, Agresti I, Bentivegna M and Sciarrino F 2019 Sci. Adv. 5 eaau1946
[19] Ding Y, Lamata L, Sanz M, Chen X and Solano E 2019 Adv. Quantum Technol. 2 1800065
[20] Benedetti M, Garcia-Pintos D, Perdomo O, Leyton-Ortega V, Nam Y and Perdomo-Ortiz A 2019 npj Quantum Inf. 5 45
[21] Sharma K, Khatri S, Cerezo M and Coles P J 2020 New J. Phys. 22 043006
[22] Khatri S, LaRose R, Poremba A, Cincio L, Sornborger A T and Coles P J 2019 Quantum 3 140
[23] Jones T and Benjamin S C 2018 arXiv:1811.03147 [quant-ph]
[24] Heya K, Suzuki Y, Nakamura Y and Fujii K 2018 arXiv:1810.12745 [quant-ph]
[25] Farhi E, Goldstone J and Gutmann S 2014 arXiv:1411.4028 [quant-ph]
[26] Otterbach J S, Manenti R, Alidoust N, Bestwick A, Block M, Bloom B, Caldwell S, Didier N, Fried E S, Hong S, Karalekas P, Osborn C B, Papageorge A, Peterson E C, Prawiroatmodjo G, Rubin N, Ryan C A, Scarabelli D, Scheer M, Sete E A, Sivarajah P, Smith R S, Staley A, Tezak N, Zeng W J, Hudson A, Johnson B R, Reagor M, da Silva M P and Rigetti C 2017 arXiv:1712.05771[quant-ph]
[27] Guerreschi G G and Matsuura A Y 2019 Sci. Rep. 9 9
[28] Crooks G E 2018 arXiv:1811.08419 [quant-ph]
[29] Zhou L, Wang S T, Choi S, Pichler H and Lukin M D 2020 Phys. Rev. X 10 021067
[30] Marshall J, Wudarski F, Hadfield S and Hogg T 2020 IOP SciNotes 1 025208