Quantum annealers are single purpose machines allowing to solve quadratic unconstrained binary optimization (QUBO) problems. QUBO problems have following objective function: $$ F=-\sum_{i<j}J_{ij}x_ix_j-\sum_{i=1}^N h_ix_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<j}J_{ij}(\sigma^z_i\otimes\sigma^z_j)-\sum_{i=1}^N h_i\sigma^z_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) $$

  1. Your are right about the commutation problem. However, remember that

$$ \lim_{p \to \infty} \big(e^{A/p}e^{B/p} \big)^p = e^{A+B} $$

so in a sense, at infinite limit depth, it is not a problem. So you recover the quantum annealing approach.

  • $\begingroup$ Thank you, now everything is clear. $\endgroup$ – Martin Vesely Oct 7 '20 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.