Quantum approximated optimization algorithm (QAOA)
Adiabatic quantum computing (AQC)
Rydberg atom system intrinsically contains information about the solution of the MIS problem, one of the NP-complete optimization problems.
Maximum independent set (MIS) problem
Rydberg blockade is distance dependent feature, so that the interaction is local. To generate controllable and all-to-all connected system, three auxiliary atom-assisted methods are proposed:
The optimization problem is mapped to the logical qubits, and these logical qubit space is embedded by physical qubits, which are supported by auxiliary atoms.
$$ \hat{H}{\rm logical}= \sum_j J_j \hat{\sigma}^z_j + \sum{(j,k)} J_{jk} \hat{\sigma}^z_j\hat{\sigma}^z_k \quad \rightarrow \quad\hat{H}_{\rm physical} $$
$$ \left| G(\hat{H}{\rm physical}) \right> \quad \rightarrow \quad\left| G(\hat{H}{\rm logical}) \right> $$