## 2 Methods
### Transformation to One Equation with Binary Ancillaries  
Let us consider Boolean function \(f(\vec{x})=y\), where \(\vec{x}\in\{0,1\}^{N_{x}}\) and denote \(\vec{z}=(\vec{x},y)\in\{0,1\}^{N_{x}+1}\). Our goal is to find the linear equation with binary ancilla (let \(N_{a}\) be the number of ancillas) and continuous coefficients:  
\[\vec{c_{z}}^{\top}\vec{z}+\vec{c_{a}}^{\top}\vec{a}=b, \tag{1}\]  
such that it satisfies two conditions:  
\[\begin{cases}\forall\vec{z}\in\text{F}\;\exists\vec{a}\in\{0,1\}^{N_{a}}:\vec{ c_{z}}^{\top}\vec{z}+\vec{c_{a}}^{\top}\vec{a}=b\\ \forall\vec{z}\
ot\in\text{F}\;\forall\vec{a}\in\{0,1\}^{N_{a}}:\vec{c_{z}}^{ \top}\vec{z}+\vec{c_{a}}^{\top}\vec{a}\
eq b\end{cases}, \tag{2}\]  
where \(F\) is the feasible region (\(f(x)=y\)). The converting is committed using a constraint programming (CP) solver (e.g., CPLEX). The aim of the CP solver is to find \(\vec{c_{z}},\vec{c_{a}},b\) coefficients; after obtaining them, we can easily build Equation (1). For the running solver, we have to reduce the problem from Equation (2) into a CP problem. For this purpose, we consider each constraint separately. In the beginning, imagine the simplest CP problem, which has no objective function or constraints. In the first property, each feasible pair \((\vec{x},y)\) adds the new constraint with a new ancilla:  
\[\vec{c_{z}}^{\top}\vec{z}+\vec{c_{a}}^{\top}\vec{a_{z}}=b\,. \tag{3}\]  
In the second property, for each pair \((\vec{x},y)\) from unfeasible configurations, we add new \(2^{N_{a}}\) constraints:  
\[\forall\vec{a_{v}}\in\{0,1\}^{N_{a}}:\vec{c_{z}}^{\top}\vec{z}+\vec{c_{a}}^{ \top}\vec{a_{v}}\
eq b\,. \tag{4}\]  
Eventually, we have \(|F|+2^{N_{a}}|F^{*}|\) constraints (\(|F|_{\
u}|F^{*}|-\)number of feasible and unfeasible configurations) and \(N_{x}+N_{a}+1+|F|\cdot N_{a}\) variables. This \"homogeneous\" CP has many solutions (multiplying all the coefficients by the same number also gives a solution). We prefer integer coefficients with a small absolute value; therefore, let \(\vec{c_{z}},\vec{c_{a}},b\) be integers with a range of \(-100\)-\(100\) (as we will see later, it is enough for finding coefficients). For obtaining the small absolute value from the CP solver, we add into the objective function in the minimization problem the following term:  
\[g+=\vec{c_{z}}^{2}\,. \tag{5}\]  
In addition, we would like obtain a positive value for the first element in \(\vec{c_{z}}[0]\), so we add a new term as follows:  
\[g-=\vec{c_{z}}[0]\,. \tag{6}\]  
Moreover, we expand the cost function with a large fine (\(\lambda\gg 1\)) for ancilla coefficients:  
\[g+=\lambda\cdot\vec{c_{a}}^{2}\,. \tag{7}\]  
This term is added because linear Equation (1) with the minimum number of ancillaries is much more preferable. Finally, we can write the full CP problem (with bi-linear equation constraints in \(\vec{c_{a}},\vec{a_{z}}\)) for finding the linear equation:  
\[\begin{split}\vec{c_{z}}^{2}-\vec{c_{z}}[0]+\lambda\cdot\vec{c_{ a}}^{2}\rightarrow\min_{\vec{c_{z}}\vec{a_{z}}}\\ \text{subject to}\\ \vec{c_{z}}^{\top}\vec{z}+\vec{c_{a}}^{\top}\vec{a_{z}}=b\quad(|F| \text{ constraints})\,,\\ \vec{c_{z}}^{\top}\vec{z}+\vec{c_{a}}^{\top}\vec{a_{v}}\
eq b\quad(2^{N_{a}}|F^{*}|\text{ constraints})\,,\end{split} \tag{8}\]  
where \(\vec{a_{v}}\) are the fixed values of variables \(\vec{a_{z}}\). Problem (8) is the mixed-integer CP and CPLEX CP optimizer can handle this problem. However, the problem with the chosennumber of ancillary variables may be infeasible. In this case, we add one more ancilla and try to solve the updated problem again. If the new problem is also infeasible, we add one more ancilla and so on. We continue to increase the number of ancillary variables until a feasible solution is found.  
Consider, for example, AND gate (\(y=x_{1}\) AND \(x_{2}\)) for which we will find the corresponding linear equation. It has the following truth table:  
\[\begin{array}{|c|c|c|c|}\hline{\rm x_{1}}&{\rm x_{2