Encoding Methods
ToQUBO.Encoding.encode — Function
encode(var, e::VariableEncodingMethod, x::Union{VI,Nothing}, S)ToQUBO.Encoding.encode! — Function
encode!(target, source...)ToQUBO.Encoding.encodes — Function
encodes(f::AbstractPBF, S::Tuple{T,T}, tol::T) where {T}Variables
As you may already know, QUBO models are comprised only of binary variables. So when we are reformulating general optimization problems, one important step is to encode variables into binary ones.
ToQUBO currently implements 6 base encoding techniques. Each method introduces a different number of variables, quadratic terms and linear terms. Also, they differ in the magnitude of their coefficients $\Delta$.
| Encoding | Binary Variables | # Linear terms | # Quadratic terms | $\Delta$ |
|---|---|---|---|---|
| Binary | $O(\log n)$ | $O(\log n)$ | - | $O(n)$ |
| Unary | $O(n)$ | $O(n)$ | - | $O(1)$ |
| One-Hot | $O(n)$ | $O(n)$ | $O(n^2)$ | $O(n)$ |
| Domain-Wall | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Bounded-Coefficient | $O(n)$ | $O(n)$ | - | $O(1)$ |
| Arithmetic Prog | $O(\sqrt{n})$ | $O(\sqrt{n})$ | - | $O(\sqrt{n})$ |
Mirror Encoding
ToQUBO.Encoding.VariableEncodingMethod — Type
VariableEncodingMethodAbstract type for variable encoding methods.
ToQUBO.Encoding.Mirror — Type
Mirror()Simply mirrors a binary variable $x \in \mathbb{B}$ with a twin variable $y \in \mathbb{B}$.
Interval Encoding
ToQUBO.Encoding.IntervalVariableEncodingMethod — Type
IntervalVariableEncodingMethodAbstract type for methods that encode variables using a linear function, e.g.,
\[\xi(\mathbf{y}) = \beta + \sum_{i = 1}^{n} \gamma_{i} y_{i}\]
ToQUBO.Encoding.Unary — Type
Unary{T}()Integer
Let $x \in [a, b] \subset \mathbb{Z}$, $n = b - a$ and $\mathbf{y} \in \mathbb{B}^{n}$.
\[\xi{[a, b]}(\mathbf{y}) = a + \sum_{j = 1}^{b - a} y_{j}\]
Real
Given $n \in \mathbb{N}$ for $x \in [a, b] \subset \mathbb{R}$,
\[\xi{[a, b]}(\mathbf{y}) = a + \frac{b - a}{n} \sum_{j = 1}^{n} y_{j}\]
Representation error
Given $\tau > 0$, for the expected encoding error to be less than or equal to $\tau$, at least
\[n \ge 1 + \frac{b - a}{4 \tau}\]
binary variables become necessary.
When no explicit ToQUBO.Attributes.VariableEncodingBits is set, the compiler uses ToQUBO.Attributes.VariableEncodingATol with this formula. See Representation Error.
ToQUBO.Encoding.Binary — Type
Binary{T}()Integer
Let $x \in [a, b] \subset \mathbb{Z}$, $n = \left\lceil \log_{2}(b - a) + 1 \right\rceil$ and $\mathbf{y} \in \mathbb{B}^{n}$.
\[\xi{[a, b]}(\mathbf{y}) = a + \left(b - a - 2^{n - 1} + 1\right) y_{n} + \sum_{j = 1}^{n - 1} 2^{j - 1} y_{j}\]
Real
Given $n \in \mathbb{N}$ for $x \in [a, b] \subset \mathbb{R}$,
\[\xi{[a, b]}(\mathbf{y}) = a + \frac{b - a}{2^{n} - 1} \sum_{j = 1}^{n} 2^{j - 1} y_{j}\]
Representation error
Given $\tau > 0$, for the expected encoding error to be less than or equal to $\tau$, at least
\[n \ge \log_{2} \left[1 + \frac{b - a}{4 \tau}\right]\]
binary variables become necessary.
When no explicit ToQUBO.Attributes.VariableEncodingBits is set, the compiler uses ToQUBO.Attributes.VariableEncodingATol with this formula. See Representation Error.
ToQUBO.Encoding.Arithmetic — Type
Arithmetic{T}()Integer
Let $x \in [a, b] \subset \mathbb{Z}$, $n = \left\lceil{ \frac{1}{2} {\sqrt{1 + 8 (b - a)}} - \frac{1}{2} }\right\rceil$ and $\mathbf{y} \in \mathbb{B}^{n}$.
\[\xi{[a, b]}(\mathbf{y}) = a + \left( {b - a - \frac{n (n - 1)}{2}} \right) y_{n} + \sum_{j = 1}^{n - 1} j y_{j}\]
Real
Given $n \in \mathbb{N}$ for $x \in [a, b] \subset \mathbb{R}$,
\[\xi{[a, b]}(\mathbf{y}) = a + \frac{b - a}{n (n + 1)} \sum_{j = 1}^{n} j y_{j}\]
Representation error
Given $\tau > 0$, for the expected encoding error to be less than or equal to $\tau$, at least
\[n \ge \frac{1}{2} \left[ 1 + \sqrt{3 + \frac{(b - a)}{2 \tau})} \right]\]
When no explicit ToQUBO.Attributes.VariableEncodingBits is set, the compiler uses ToQUBO.Attributes.VariableEncodingATol with this formula. See Representation Error.
Bounded Coefficients
ToQUBO.Encoding.Bounded — Type
Bounded{E,T}(μ::T) where {E<:Encoding,T}The bounded-coefficient encoding method[Karimi2019] consists in limiting the magnitude of the coefficients in the encoding expansion to a parameter $\mu$. This can be applied to the Unary, Binary and Arithmetic encoding methods.
Let $\xi[a, b] : \mathbb{B}^{n} \to [a, b]$ be an encoding function over the closed interval $[a, b]$. The bounded-coefficient encoding function given $\mu$ is defined as
\[\xi_{\mu}[a, b] = \xi[0, \delta](y_{1}, \dots, y_{k}) + \sum_{j = k + 1}^{r} \mu y{j}\]
```
Arbitrary Set Encoding
ToQUBO.Encoding.SetVariableEncodingMethod — Type
SetVariableEncodingMethodAbstract type for methods that encode variables over an arbitrary set.
ToQUBO.Encoding.OneHot — Type
OneHot{T}()The one-hot encoding is a linear technique used to represent a variable $x \in \set{\gamma_{j}}_{j \in [n]}$.
The associated encoding function is combined with a constraint assuring that only one and exactly one of the expansion's variables $y_{j}$ is activated at a time.
\[\xi[\set{\gamma_{j}}_{j \in [n]}](\mathbf{y}) = \sum_{j = 1}^{n} \gamma_{j} y_{j} ~\textrm{s.t.}~ \sum_{j = 1}^{n} y_{j} = 1\]
When a variable is encoded following this approach, a penalty term of the form
\[\rho \left[ \sum_{j = 1}^{n} y_{j} - 1 \right]^{2}\]
is added to the objective function.
ToQUBO.Encoding.DomainWall — Type
DomainWall{T}()The Domain Wall[Chancellor2019] encoding method is a sequential approach that requires $n - 1$ bits to represent $n$ distinct values.
\[\xi{[\set{\gamma_{j}}_{j \in [n]}]}(\mathbf{y}) = \sum_{j = 1}^{n} \gamma_{j} (y_{j} - y_{j + 1}) ~\textrm{s.t.}~ \sum_{j = 1}^{n} y_{j} \oplus y_{j + 1} = 1, y_{1} = 1, y_{n + 1} = 0\]
where $\mathbf{y} \in \mathbb{B}^{n + 1}$.
Semi-Domain Encoding
ToQUBO.Encoding.Semi — Type
Semi(e::VariableEncodingMethod)Wraps another variable encoding method to represent $x \in \{0\} \cup X$. If the wrapped method encodes $X$ as $\xi[X](y)$, then Semi uses an additional activation bit $z$ and encodes the semi-domain as $z \xi[X](y)$.
Representation Error
ToQUBO.Encoding.encoding_bits — Function
encoding_bits(e::VariableEncodingMethod, S::Tuple{T,T}, tol::T) where {T}Return the number of target binary variables selected by encoding method e for a bounded continuous interval S when no explicit variable bit count is set.
The tolerance tol is the upper bound used by the method's representation error rule. See Representation Error for the derivation and compiler precedence between explicit bit counts and tolerance-based inference.
ToQUBO.Encoding.encoding_points — Function
encoding_points(e::SetVariableEncodingMethod, S::Tuple{T,T}, tol::T) where {T}Return the number of discretization points selected by a set encoding method for a bounded continuous interval S and tolerance tol.
Let $\set{x_{i}}_{i \in [k]}$ be the collection of $k$ evenly spaced samples from the discretization of an interval $[a, b] \subseteq \mathbb{R}$. Its interval length is $L = \left|b - a\right|$.
The representation error for a given point $x$ with respect to $\set{x_{i}}_{i \in [k]}$ is
\[e_{k}(x) = \min_{i \in [k]} \left|x - x_{i}\right|\]
Assuming that $x$ behaves as a uniformly distributed random variable, the expected absolute encoding error is
\[\begin{align*} \mathbb{E}\left[{e_{k}(x)}\right] &= \frac{1}{L} \int_{a}^{b} e_{k}(x) ~\mathrm{d}x \\ &= \frac{1}{4} \frac{L}{k - 1} \end{align*}\]
Thus, for encoding methods that rely on the regular division of an interval, it is possible to define the number of samples $k$ necessary to limit the expected error according to an upper bound $\tau$, that is,
\[\mathbb{E}\left[{e_{k}(x)}\right] \le \tau \implies k \ge 1 + \frac{L}{4 \tau}\]
This allows the compiler to automatically infer the number of bits to allocate for an encoded variable given the tolerance factor. For a bounded continuous variable, an explicit ToQUBO.Attributes.VariableEncodingBits value fixes the bit count directly. When no bit count is set, the compiler reads ToQUBO.Attributes.VariableEncodingATol, falling back to ToQUBO.Attributes.DefaultVariableEncodingATol, and calls ToQUBO.Encoding.encoding_bits for the selected encoding method and the variable bounds.
For the default ToQUBO.Encoding.Binary method, $k = 2^n$ evenly spaced values are represented by $n$ target binary variables. Combining $k = 2^n$ with the tolerance bound gives
\[n \ge \log_{2} \left(1 + \frac{L}{4 \tau}\right),\]
so the compiler uses $\left\lceil \log_{2} \left(1 + L / 4\tau\right) \right\rceil$ bits. Other continuous-variable encoding methods use the same tolerance and bounds inputs with their method-specific ToQUBO.Encoding.encoding_bits or ToQUBO.Encoding.encoding_points rule.
Constraint Reformulation
A QUBO model is unconstrained, so ToQUBO translates each supported source constraint into a penalty term and adds it to the objective. The default reformulations below are nonnegative and are constructed to vanish when the residual and any required slack can be represented exactly. The implementation lives in src/compiler/constraints.jl.
For a scalar affine or quadratic function $f(x)$, the compiler first forms a residual $g(x)$ relative to the set bound. The default reformulations are:
| MOI set | Feasible residual | Penalty before multiplying by $\rho$ |
|---|---|---|
EqualTo(b) | $g(x) = f(x) - b = 0$ | $g(x)^2$ |
LessThan(u) | $g(x) = f(x) - u \leq 0$ | $(g(x) + z)^2$ |
GreaterThan(l) | $g(x) = f(x) - l \geq 0$ | $(g(x) - z)^2$ |
Interval(l, u) | $l \leq f(x) \leq u$ | the sum of the GreaterThan(l) and LessThan(u) penalties |
The EqualTo row shows the default ToQUBO.Attributes.QuadraticPenalty method. Its sign-definite shortcut and the optional ToQUBO.Attributes.LinearPenalty method are described below. Scalar inequalities can instead select the slack-free ToQUBO.Attributes.UnbalancedPenalty method.
The one-sided reformulations introduce a bounded nonnegative slack $z$ so that feasible residuals can be brought to zero. If $L_g$ and $U_g$ are bounds on the residual, LessThan uses $z \in [0, |L_g|]$ and GreaterThan uses $z \in [0, |U_g|]$. Interval constraints are split at their lower and upper bounds and the two generated penalties are added.
The compiler also uses residual bounds to avoid unnecessary slack variables or higher-order terms. A LessThan residual that is already nonnegative over the encoded domain can be used directly as $g(x)$; a GreaterThan residual that is already nonpositive can be used as $-g(x)$. For an EqualTo constraint, a nonnegative residual can be used directly instead of squared. These sign-definite shortcuts preserve zero exactly at feasible assignments. The compiler separately detects always-feasible and infeasible constraints; the corresponding warning, omission, and error behavior is controlled by the constraint feasibility actions.
The generated penalty is multiplied by $\rho$ before it is added to the objective. Automatic inference, fixed hints, and per-constraint overrides for $\rho$ are documented under Automatic Penalty Inference and Changing Penalty Values.
Continuous Slack Resolution
An integer slack can be represented on its integer grid. A continuous slack, however, still needs a finite binary encoding before the QUBO is built. Set ToQUBO.Attributes.SlackVariableEncodingBits to fix its bit count, or use ToQUBO.Attributes.SlackVariableEncodingATol to choose the tolerance used for bit-count inference. The selected encoding method comes from ToQUBO.Attributes.SlackVariableEncodingMethod.
The required real-valued slack can fall between two values on the encoded grid. In that case $g(x) \pm z$ cannot reach zero even though the original continuous inequality is feasible, leaving a positive squared-residual floor. The floor can be zero when the required slack lands exactly on the grid, and grid alignment means it need not decrease strictly at every added bit. Finer resolution generally reduces the representation error but consumes more target binary variables and can change the effective penalty landscape. The bit-count relationship is derived in Representation Error. The user-facing settings and the required feasible/infeasible penalty contrast are summarized under Continuous Variable Resolution and Slack Resolution and Penalty Contrast.
Sampling-feasibility behavior that motivated this documentation is tracked in #205. The issue #208 analysis found that continuous-slack resolution does not explain that model's reported violations. The slack-free method added for #207 addresses the separate target-variable cost of generated inequality slacks.
Equality constraints use a squared residual penalty by default. The compiler can also encode an equality constraint with a signed linear residual through ToQUBO.Attributes.LinearPenalty. This option follows the linear Ising penalty method studied by Mirkarimi et al.[Mirkarimi2024PRR] and demonstrated experimentally for quantum annealing.[Mirkarimi2024NJP] It is a heuristic method: the sign and magnitude of $\rho$ affect whether the residual discourages the intended violations, so ToQUBO requires an explicit ToQUBO.Attributes.ConstraintEncodingPenaltyHint instead of inferring $\rho$ automatically.
For a LessThan residual $g(x) \leq 0$, UnbalancedPenalty() generates $\lambda_1 g(x) + \lambda_2 g(x)^2$; for GreaterThan, it negates the linear term. This quadratic approximation avoids the constraint slack variables for affine inequalities, but it is heuristic: feasible assignments can receive different nonzero energies. It therefore requires an explicit ConstraintEncodingPenaltyHint. Prefer it when target-variable savings justify tuning and validating the altered energy ordering; keep the default slack formulation when a representable feasible slack must give exactly zero penalty. Quadratic source inequalities can still require quadratization variables.
When any reformulation creates terms above quadratic degree, the compiler marks the model for quadratization and reduces those terms before building the target QUBO.
Boolean Logic Gadgets and Indicator Formulations
When an equality constraint uses the default ToQUBO.Attributes.QuadraticPenalty method and every variable involved is a binary variable (MOI.ZeroOne, encoded via ToQUBO.Encoding.Mirror), the compiler recognizes standard Boolean logic residuals (NOT, AND, OR, and XOR, up to overall sign and integer GCD normalization when discretization is enabled) and emits minimal textbook penalty gadgets directly instead of forming a generic squared residual:
| Gate | Constraint / residual $g = 0$ | Emitted PBF penalty (before $\rho$) | Ancillas |
|---|---|---|---|
NOT | $\pm(a + b - 1) = 0$ | $1 - a - b + 2ab$ | $0$ |
AND | $\pm(c - ab) = 0$ | $3c + ab - 2ac - 2bc$ | $0$ |
OR | $\pm(a + b - ab - c) = 0$ | $a + b + c + ab - 2ac - 2bc$ | $0$ |
XOR | $\pm(a + b - 2ab - c) = 0$ | $a + b + c - 2ab - 2ac - 2bc + 4abc$ (quadratized via PTR_BG with 1 ancilla) | $1$ |
Each gadget vanishes on and only on the gate's truth table and has unit minimum positive violation gap ($\epsilon = 1$) over $\{0, 1\}^n$. Non-matching quadratic equalities, or constraints involving any non-binary variable, fall back to the generic squared-residual path $g(x)^2$.
Logical implications can also be modeled directly with MOI.Indicator{MOI.ACTIVATE_ON_ONE} (z => {f(x) in S}) and MOI.Indicator{MOI.ACTIVATE_ON_ZERO} (!z => {f(x) in S}), which multiply the inner constraint's penalty by $z$ or $1 - z$ and quadratize any resulting higher-order terms.
- Karimi2019Karimi, S. & Ronagh, P. Practical integer-to-binary mapping for quantum annealers. Quantum Inf Process 18, 94 (2019). {doi}
- Chancellor2019Nicholas Chancellor, Domain wall encoding of discrete variables for quantum annealing and QAOA, Quantum Science Technology 4, 2019.
- Mirkarimi2024PRRPuya Mirkarimi, Ishaan Shukla, David C. Hoyle, Ross Williams, and Nicholas Chancellor. Quantum optimization with linear Ising penalty functions for customer data science. Physical Review Research 6, 043241 (2024). {doi}
- Mirkarimi2024NJPPuya Mirkarimi, David C. Hoyle, Ross Williams, and Nicholas Chancellor. Experimental demonstration of improved quantum optimization with linear Ising penalties. New Journal of Physics 26, 103005 (2024). {doi}