10 problems

Let $n$ binary spins be arranged on a ring, with the objective of maximizing the number of neighboring pairs pointing in opposite directions. For even $n$, let $r_p^*$ denote the l…

Size-independence conjecture. The approximation of the $k_\sigma=k_t=2$ SDP relaxation to the actual figures is essentially independent of $n$.

Gradient-based QAOA saddle-point conjecture. Gradient-based optimization of QAOA often gets trapped by saddle points of the QAOA loss-function landscape.

The discussion concerns the Sherrington–Kirkpatrick spin glass problem and MaxCut on large random regular graphs, together with their overlap gap property (OGP) and approximate mes…

Let $\alpha^*_3$ denote the threshold appearing in the definition of 2-independent-set-typicality. For $\alpha \in \left(0,\alpha^*_3\right)$ and $\varepsilon>0$, a 3-regular graph…

A $2$-regular graph is a graph in which every vertex has degree $2$, and standard QAOA at depth $p$ is evaluated by its expected approximation ratio for the Max-Cut objective. QAOA…

Consider the quantum approximate optimization method applied to sufficiently large instances, together with distant and unrelated shadow defects that can affect the efficacy of low…

Consider low-depth quantum approximate optimization algorithms (QAOA) applied to random problem instances, and the phenomenon described in the surrounding text, in which distant en…

Consider computational problems, with instances or problems equipped with an appropriate measure-theoretic notion of majority, and distinguish problems possessing exploitable struc…

Hardware-level energy-gap conjecture. When the parameters are autoscaled in these ranges, the resulting hardware-level energy gaps between different solutions become small compared…