Dans un article récent, Herrman et al. \cite{mindepth} proposent une méthode permettant de reformuler des problèmes 3-SAT sous forme de QUBO (Quadratic Unconstrained Binary Optimization) de façon à minimiser la profondeur du circuit quantique nécessaire pour encoder le problème. Ce travail est motivé par la corrélation entre la profondeur d'un circuit quantique et le niveau de bruit.

Nous proposons une approche similaire, consistant à reformuler un problème polynomial de degré trois en un QUBO de façon à minimiser le nombre de qubits nécessaires à l'implémentation de QAOA. Nous proposons également une alternative à la méthode de Herman et al., ainsi qu'une réflexion sur l'extension de tous ces travaux au degré 4 et au-delà.