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 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.
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.
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]\]
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}$.
Representation Error
ToQUBO.Encoding.encoding_bits — Function
encoding_bits(e::VariableEncodingMethod, S::Tuple{T,T}, tol::T) where {T}ToQUBO.Encoding.encoding_points — Function
encoding_points(e::SetVariableEncodingMethod, S::Tuple{T,T}, tol::T) where {T}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}$.
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}{b - a} \int_{a}^{b} e_{k}(x) ~\mathrm{d}x \\ &= \frac{1}{4} \frac{b - a}{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{b - a}{4 \tau}\]
This allows the compiler to automatically infer the number of bits to allocate for an encoded variable given the tolerance factor.
Constraints
A QUBO model is unconstrained. So when ToQUBO is reformulating a problem, it needs to encode all constraints into the objective function losing as little information as possible.
As constraints are introduced into the objective function, we need to make sure that they won't be violated. In order to do that, ToQUBO multiplies the encoded constraint by a large penalty $\rho$, so that any violation would result in a sub-optimal solution to the problem.
Sometimes, the encoding process might introduce higher-order terms, demanding ToQUBO to reduce the offending polynomials back to a quadratic form.
- 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.