# Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?

Quantum annealers are single purpose machines allowing to solve quadratic unconstrained binary optimization (QUBO) problems. QUBO problems have following objective function: $$F=-\sum_{i where $$x_i$$ is a binary varibale and $$h_i$$ and $$J_{ij}$$ are coefficients. Such objective function is equivalent to Ising Hamiltonian $$H_{\text{ISING}}=-\sum_{i where $$\sigma^z_i$$ is Pauli Z gate acting on $$i$$th qubit and there are identity operators on other qubits, tensor product $$\sigma^z_i\otimes\sigma^z_j$$ means that Z gates act on $$i$$th and $$j$$th qubits and there are identity operators on other qubits.

Quantum annealers physically implements simulation of Hamiltonian $$H(t)=\Big(1-\frac{t}{T}\Big)\sum_{i=1}^N h_i\sigma^x_i+\frac{t}{T}H_{\text{ISING}},$$ where $$t$$ is a time, $$T$$ total time of simulation and $$\sigma^x_i$$ is Pauli X gate acting on $$i$$th qubit. Initial state of a quantum annealer is equal superposition of all qubits which is ground state of the Hamiltonian $$H(0)$$.

Quantum Approximate Optimization Algorithm (QAOA) is described by an operator $$U(\beta, \gamma) = \prod_{i=1}^{p}U_B(\beta_i)U_C(\gamma_i),$$ where $$p$$ is number of iteration of QAOA, $$U_B(\beta) = \mathrm{e}^{-i\beta\sum_{i=1}^N \sigma^x_i},$$ and $$U_C(\gamma) = \mathrm{e}^{-i\gamma(\sum_{i,j=1}J_{ij}(\sigma^z_i\otimes\sigma^z_j)+\sum_{i=1}^N h_i\sigma^z_i)}.$$ Initial state for QAOA is $$H^{\otimes n}|0\rangle ^{\otimes n}$$, i.e. equally distributed superposition as in case of the quantum annealer.

Since time evolution of quantum system described by Hamiltonian $$H$$ from state $$|\psi(0)\rangle$$ to state $$|\psi(t)\rangle$$ is expressed by $$|\psi(t)\rangle = \mathrm{e}^{-iHt}|\psi(0)\rangle,$$ it seems that operator $$U(\beta, \gamma)$$ from QAOA is simply simulation of Hamiltonian $$H(t)$$ describing quantum annealer beacause exponents of $$\mathrm{e}$$ are sums in Hamiltonian $$H(t)$$.

However, $$H(t)$$ is composed of two term containing Pauli matrices X and Z and $$\mathrm{e}^{A+B}=\mathrm{e}^A\mathrm{e}^B$$ is valid only for commuting matrices $$[A,B]=O$$. But Pauli matrices X and Z fulfil anti-commutation relation $$\{X,Z\}=O$$, not the commutation one.

So my questions are these:

1. Can QAOA be realy considered as a simulation of quantum annealer on gate-based universal quantum computer?
2. What I am missing in discussion above concerning commutation of Pauli matrices? Or is there any condition for matrices $$A$$ and $$B$$ allowing equality $$\mathrm{e}^{A+B}=\mathrm{e}^A\mathrm{e}^B$$?

1. If you use infinite depth then QAOA can be consider as quantum annealer on gate-based. The authors of QAOA original paper probably deduce it from quantum annealing. What I mean by infinite depth is you take $$p \to \infty$$ in the operator
$$U(\beta, \gamma) = \Pi_{i=1}^p U_B(\beta_i)U_C(\gamma_i)$$
$$\lim_{p \to \infty} \big(e^{A/p}e^{B/p} \big)^p = e^{A+B}$$