Suppose we have a set of tasks $T = \{t_1, t_2, \dots, t_n\}$ with durations $\{d(t)| t \in T\}$, that need to be executed on some machine such that their execution times do not overlap. We can represent the start time of task $t$ as $x(t),\, x \in \mathbb{N}$. We don't care about the execution order.
Regardless whether this problem is trivially solved by just exceuting each task after previous ends, I'd like to encode this constraint as minimizing a polynomial $p: X \times \Xi \to \mathbb{R}$ where $X = \{x(t) : t \in T\}$ and $\Xi$ denotes the set of any extra variables one might need to introduce.
Currently my approach is to use the classic double well in combination with slack variables:
For each pair of tasks $(t_i, t_j)$, we want that $x(t_i) + d(t_i) \leq x(t_j)$ or $x(t_j) + d(t_j) \leq x(t_i)$. Introducing the slack variable $\xi \geq 0$, this translates to $$x(t_i) + d(t_i) + \xi - x(t_j) = 0 \quad \text{or} \quad x(t_j) + d(t_j) + \xi - x(t_i) = 0$$ Multiplying both options and squaring gives $$ p_{ij}(x, \xi) = (x(t_i) + d(t_i) + \xi - x(t_j))^2(x(t_j) + d(t_j) + \xi - x(t_i))^2. $$
It is easy to check that $p_{ij}$ is minimized iff tasks $t_i$ and $t_j$ do not overlap and that $0$ is the global minimum value. Thus summing over all combinations of tasks gives the desired constraint energy for all tasks.
My issue now is that each $p_{ij}$ is of degree 4. Having polynomials of degree $\geq$ 2 adds additional variables and constraints when we compile $p$ down to a QUBO.
Can we encode these non-overlapping constraints with polynomials of degree < 4?
For each pair $(t_i, t_j)$ of tasks with $i < j$, introduce a binary variable $z_{ij}\in \lbrace 0,1\rbrace$ which will be 0 if $t_i$ precedes $t_j$ and 1 if $t_j$ precedes $t_i$. The approach is to add a pair of constraints representing those two possibilities, such that for each value of $z_{ij}$ one constraint enforces a particular precedence and the other constraint is vacuous (automatically satisfied). Here you would use the following: $$ x(t_i) + d(t_i) - x(t_j) \le T z_{ij}$$ and $$x(t_j) + d(t_j) - x(t_i) \le T(1-z_{ij}).$$ This is what @RobPratt was getting at.