QAOA

Quantum Approximate Optimization Algorithm (QAOA)

Problem Setting

Let be a string of bits, where each bit . We define a cost function that assigns a real value to each bit string. The goal is to find the bit string that maximizes the cost function: where are indicator functions .

Hamiltonian Representation

We can represent the cost function as a Hamiltonian operator acting on a quantum state. The Hamiltonian corresponding to the cost function is given by: where each is a diagonal operator in the computational basis defined as: Each is Hermitian, so is and .

We now seek to find the maximum eigenvalue of and the corresponding eigenstate .

What we can learn from Score Based Model (SBM)

In EBM, we define a probability distribution via the energy function (Hamiltonian):

consider a parameterized model , we can learn the parameters by learning the score function .

where is the score function parameterized by .

---

In QAOA’s scenario, the energy function is fixed and we want to find the state that maximizes the energy.

Let’s define a quantum state parameterized by .

We can measure: We want to maximize: where is the probability of measuring the state given the parameter .

In the first glance, we try to estimiate the log gradient: This is similar to the REINFORCE learning gradient method with reward . However, this gradient is not calculable directly on quantum computer since cannot be computed efficiently. ( terms). And it does not use the result of measure directly.

On the other hand, if we sampling through This suffers from high variance issue. The high variance is due to the high dimensionality of the output space.

Parameter Shift Rule

Remember that in Denoising Score Matching, we can avoid calculating the score function directly by introducing noise and learning to denoise, then the score function can be computed directly. And under Gaussian noise, the score function has a closed form.

This inspires us to introduce a particular parameterization of in QAOA such that we can compute the gradient of directly.

For , where is a Hermitian operator (generator), we have: this uses the property that commutes with .

Thus, where is the commutator of and , .

Now, note that Thus, Therefore, we have: This means we can compute the gradient of by evaluating at two shifted parameter values, avoiding the need to compute the score function directly.

Parameterized Quantum Circuit in QAOA

In QAOA, the parameterized quantum circuit is constructed using two types of unitary operators: the cost unitary and the mixing unitary . The overall circuit for layers is given by:

The cost unitary is defined as: and the mixing unitary is defined as: where with being the Pauli-X operator acting on qubit .

The initial state is typically chosen as the uniform superposition state: which is the ground state of the mixing Hamiltonian .

Reason (Can be omitted, I don’t know very well about this quantum physics part):

The Adiabatic Theorem suggests that if we vary the parameters and slowly enough, the system will remain in its ground state, allowing us to approximate the optimal solution to the original combinatorial optimization problem. The time evolution operator can be approximated using the Trotter-Suzuki decomposition:

Algorithm Summary

1. Initialize the quantum state as the uniform superposition state.
2. Choose the number of layers and initialize the parameters .
3. Construct the parameterized quantum circuit .
4. Measure the expectation value .
5. Use the parameter shift rule to compute the gradients and .
6. Update the parameters using a classical optimization algorithm (e.g., gradient descent).
7. Repeat steps 3-6 until convergence or a stopping criterion is met.
8. Measure the final state to obtain a bit string that approximates the optimal solution to the original problem.