Deep Quantum Blog

May 04, 2023

A Boolean function takes one or more Boolean inputs and produces a single Boolean output.

Unlike Boolean functions that produce binary outputs restricted to the set $\{0, 1\}$ , the outputs of pseudo-Boolean functions take real-values.

These functions have a surprising number of applications in areas related to quantum computing and beyond. This blog post explains some of their elementary properties and demonstrates some scripts I’ve made to manipulate these functions using Mathematica. The notebook used in this post is free to download from GitHub.

Terminology and Notation

We use the standard notation $\{0, 1\}^{\times n}$ to represent the set of all $n$ -long binary words, where concatenation is juxtaposition. For example,

$\{0, 1\}^{\times 3} = \{000, 001, 010, 011, 100, 101, 110, 111\}$

A Boolean tuple $(x_1, \dots, x_n)$ is a placeholder for an element in or a variable over the set $\mathbb{B}^n$ .

We say that a Boolean function $g$ has type

$g:\mathbb{B}^n\rightarrow \mathbb{B}$

and a pseudo-Boolean function $f$ has type

$f:\mathbb{B}^n\rightarrow \mathbb{R}.$

Here $\mathbb{R}$ is the set of values on the real number line $(-\infty, \infty)$ .

We will abbreviate Boolean tuples in two distinct ways. We say that $\underline {\bf x}$ is a specific string in $\mathbb{B}^n$ , whereas $\mathbf{x}$ is an indeterminate over $\mathbb{B}^n$ . We will use non-bold fonts for the case $n=1$ , for example $x_k$ is the $k$ -th Boolean variable.

Variables are usually associated with equations and finding their values, while indeterminates are used to represent general elements within an expression without specifying their actual values. We make this distinction as a way to discuss the specific assignment of Boolean strings. Using this convention, if $f(\mathbf{x})$ is pseudo-Boolean, $f$ maps each string $\underline{{\bf x}}\in \{0, 1\}^{\times n}$ to $f(\underline {\bf x})$ whereas if $f(\mathbf{x})$ would be a pseudo-Boolean polynomial over indeterminates $x_1, \dots, x_n$ .

Normal forms and gradings

The pseudo-Boolean functions can be expressed as sums of disjoint variable products:

(1) $\begin{align*}f({ \bf x}) &= a_0 x_1' \cdots x_n' + a_1 x_1 x_2'\cdots x_n'+\dots \\&\dots + a_{N} x_1 \cdots x_n.\end{align*}$

We again use ${\bf x}$ to represent the tuple $(x_1, x_2, \dots, x_n)$ , and $\forall 1\leq l\leq 2^n-1, a_l\in \mathbb{R}$ , concatenated variables such as $x_k x_m$ are multiplied with the multiplication symbol omitted and finally, $x'$ is the logical negation of Boolean variable $x$ . We will often replace $x'\mapsto 1-x$ .

We call two monomials disjoint whenever their product contains a variable and its negation. For example, $x_lx_m$ and $x'_m$ are disjoint. The product of such terms vanishes as $x_lx_m x'_m = x_lx_m(1-x_m) = x_l x_m-x_l x_mx_m$ which is identically zero as Boolean variables are idempotent: $x_mx_m = x_m$ .

We sometimes make use of a variant of falling powers notation. We can instead express (1) as

(2) $\begin{equation*}f({ \bf x}) = \sum_{{\underline y}\in \mathbb{B}^n} a_{\underline y}{\bf x}^{\underline y}.\end{equation*}$

Here we adopt the convention that ${\bf x}^{\underline y} = x_1^{y_1}\cdots x_n^{y_n}$ and $x^1 \mapsto x$ , $x^0 \mapsto x'$ . In this way, each bit string $\underline{\bf y}, \underline{\bf z}\in \mathbb{B}^n$ defines a monomial ${\bf x}^{\underline{\bf y}}$ , ${\bf x}^{\underline{\bf z}}$ and their product

${\bf x}^{\underline{\bf y}}\cdot {\bf x}^{\underline{\bf z}} = \delta_{\underline{\bf y}, \underline{\bf z}} {\bf x}^{\underline{\bf y}} = \delta_{\underline{\bf y}, \underline{\bf z}} {\bf x}^{\underline{\bf z}}$

vanishes for disjoint terms.

After some calculation, from (1) one arrives at the canonical form,

(3) $\begin{align*}f({\bf x}) &= c_0 + c_1 x_1 + c_2x_2 +\dots +c_n x_n +\\&\quad c_{1,2}x_1x_2+\dots +c_{n-1, n}x_{n-1}x_n + \nonumber \\&\quad \dots +c_{1, 2,\dots, n}x_1x_2\cdots x_n\end{align*}$

These forms (1) and (3) each uniquely define any $n$ -variable pseudo-Boolean function in terms of $N=2^n$ real numbers $\bf a$ and $\bf c$ . If for any input $\underline{\bf y}\in \mathbb{B}^n$ , $f(\underline{\bf y})\geq 0$ then $f(\bf x)$ is called non-negative. We call

(4) $\begin{equation*}c_0 + c_1 x_1 + c_2x_2 +\dots + c_n x_n\end{equation*}$

the affine part of $f({\bf x})$ . Any equation that can be entirely expressed in the form (4) is called affine and when $c_0=0$ the function is called linear.

Quadratic pseudo Boolean functions

A quadratic pseudo-Boolean function is given as

(5) $\begin{align*}f({\bf x}) &= c_0 + c_1 x_1 + c_2x_2 +\dots +c_n x_n +\\&\quad \dots+ c_{12}x_1x_2+\dots +c_{n-1, n}x_{n-1}x_n,\end{align*}$

where the fraction on the left-hand-side denotes $f(\bf x)$ modulo the constraint in the denominator. In other words the quadratic pseudo-Boolean function is a non-homogeneous polynomial of degree two. The minimisation of pseudo-Boolean functions is NP-hard. We call the set of inputs such that $f({\bf x})=0$ the kernel of the pseudo-Boolean function $f$ . Deciding if a (quadratic) pseudo-Boolean function has a non-trivial kernel is NP-complete.

There are a few things worth mentioning for those who are new to pseudo Boolean functions. It is rather common for these to appear in slightly different forms. For example, in physics they are written as:

(6) $\begin{equation*}H = \sum_{q<r}J_{q,r} s_q s_r + \sum_q h_q s_q\end{equation*}$

where $s$ takes values $\pm 1$ . There is a simple relationship, $s = 1-2x = (-1)^x$ where $x$ is a Boolean variable. It is also typical in quantum theory to write this in matrix form as:

(7) $\begin{equation*}H = \sum_{q<r}J_{q,r} \sigma_q^z \sigma_r^z + \sum_q h_q \sigma_q^z\end{equation*}$

here $\sigma^z$ is a matrix:

(8) $\begin{equation*}\sigma^z =\begin{pmatrix}1 & 0 \\0 & -1\end{pmatrix}\end{equation*}$

Terms such as $\sigma_q^z \sigma_r^z$ omit the $\otimes$ symbol and also the identity matrix acts on the rest of the space. For example, $\sigma_1^z \sigma_4^z$ acting on $5$ variables really means $\sigma_1^z\otimes \one \otimes \one \otimes \sigma_4^z\otimes \one$ , where $\one$ is the $2\times 2$ identity matrix. In this setting the vector $(1, 0)^\top$ represents logical zero and $(0,1)^\top$ represents logical one.

In our case, we consider $f\geq 0$ which means that $f$ is non-negative on all its inputs. We are concerned with what we call, the kernel of $f$ :

(9) $\begin{equation*}\ker f({\bf x}) = \{ {\bf x}| f({\bf x}) = 0, {\bf x}\in \mathbb B^n\}. \end{equation*}$

For example, we want to find assignments for the coefficients in (5) so that

(10) $\begin{equation*}\ker f({\bf x}) = \{ (0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 1)\}\end{equation*}$

and on all other inputs (in the compliment set $[\ker f({\bf x})]^\bot$ ) the function, $f\geq 1$ . We will use Mathematica to easily find these coefficients.

Mathematica for Pseudo Boolean functions

Just a reminder that, the notebook used in this post is free to download from GitHub. As an example consider a function that outputs 1 only on the inputs [0, 0, 1], [0, 1, 0], [1, 0, 0]:

In[*]=  W[x_, y_, z_] := (1 - x) (1 - y) z + (1 - x) y (1 - z) + x (1 - y) (1 - z);
In[*]= Outer[W, {0, 1}, {0, 1}, {0, 1}] // Flatten 
Out[*]= {0, 1, 1, 0, 1, 0, 0, 0}

Here the function Outer applies W to all combinations of 0 and 1 for each of the three variables. This results in an array which is only 1 on the desired points, as seen from counting in lexicographical order. Now expanding W:

In[*]= W[x, y, z] // Expand 
Out[*]= x + y - 2 x y + z - 2 x z - 2 y z + 3 x y z

There is an alternative to Outer which I make use of often.

In[*]= Tuples[{0, 1}, 3]
Out[*]= {{0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1}}

Now we will index to the second level using @:

In[*]= W@@@Tuples[{0, 1}, 3]
Out[*]= {0, 1, 1, 0, 1, 0, 0, 0}

Which again produces the desired result. Those unfamiliar should try the following:

Exercise. Try W@Tuples[{0, 1}, 3] and W@@Tuples[{0, 1}, 3]. W@Tuples[{0, 1}, 3] tries to apply W to the entire output of Tuples[{0, 1}, 3], which doesn’t match W‘s definition. When you use W@@Tuples[{0, 1}, 3], the @@ operator (Apply) replaces the outermost level of brackets with W, again treating the entire set of tuples as arguments for a single call to W. This results in a mismatch between the number of arguments W expects (three) and the number it receives (eight).

Now let’s find the coefficients for the AND penalty described before. There are other ways to define the constraints, but this is simple.

In[*]= f[a_, b_, c_, d_, e_, f_, x_, y_, z_] := a x + b y + c z + d x y + e x z + f y z; 

In[*]= constraints = {f[a, b, c, d, e, f, 0, 0, 0] == 0, 
   f[a, b, c, d, e, f, 0, 1, 0] == 0, 
   f[a, b, c, d, e, f, 1, 0, 0] == 0, 
   f[a, b, c, d, e, f, 1, 1, 1] == 0, 
   f[a, b, c, d, e, f, 0, 0, 1] >= 1, 
   f[a, b, c, d, e, f, 0, 1, 1] >= 1, 
   f[a, b, c, d, e, f, 1, 0, 1] >= 1, 
   f[a, b, c, d, e, f, 1, 1, 0] >= 1};

In[*]= minimizationProblem = NMinimize[{Total[(f[a, b, c, d, e, f, ##] - 1)^2 & @@@Tuples[{0, 1}, 3]], constraints}, {a, b, c, d, e, f}]

Out[*]= {8., {a -> 0., b -> 0., c -> 3., d -> 1., e -> -2., f -> -2.}}

NMinimize is trying to minimize the sum of squared differences between the function f (evaluated at all combinations of 0 and 1 for three variables) and 1, subject to specified constraints. The output shows the minimum value obtained (8) and the values of a, b, c, d, e, and f that achieve this minimum. To recover the penalty we do this:

In[*]= Fand[x_, y_, z_] = f[0, 0, 3, 1, -2, -2, x, y, z]
Out[*]= x y + 3 z - 2 x z - 2 y z 

In[*]= Fand[##] & @@@ Tuples[{0, 1}, 3]
Out[*]= {0, 3, 0, 1, 0, 1, 1, 0}

Exercise. Use Mathematica to show that there is no quadratic form of the W function. You can ask ChatGPT for the constraints or use this:

Wconstraints = {f[a, b, c, d, e, f, 0, 1, 0] == 0,
f[a, b, c, d, e, f, 1, 0, 0] == 0,
f[a, b, c, d, e, f, 0, 0, 1] == 0,
f[a, b, c, d, e, f, 0, 0, 0] >= 1,
f[a, b, c, d, e, f, 1, 1, 1] >= 1,
f[a, b, c, d, e, f, 0, 0, 1] >= 1,
f[a, b, c, d, e, f, 0, 1, 1] >= 1,
f[a, b, c, d, e, f, 1, 0, 1] >= 1,
f[a, b, c, d, e, f, 1, 1, 0] >= 1};

Exercise. Use Mathematica to find the GHZ penalty function which outputs 1 only on inputs [0, 0, 0], [1, 1, 1]. You can explain what you are after and ChatGPT will give you the constraints, or you can use this:

GHZconstraints = {f[a, b, c, d, e, f, 0, 0, 0] == 0, 
   f[a, b, c, d, e, f, 1, 1, 1] == 0, 
   f[a, b, c, d, e, f, 0, 0, 1] >= 1, 
   f[a, b, c, d, e, f, 0, 1, 0] >= 1, 
   f[a, b, c, d, e, f, 0, 1, 1] >= 1, 
   f[a, b, c, d, e, f, 1, 0, 0] >= 1, 
   f[a, b, c, d, e, f, 1, 0, 1] >= 1, 
   f[a, b, c, d, e, f, 1, 1, 0] >= 1};

For those familiar with quantum mechanics, it is fun to consider the linear extension of set functions. Mathematica can do this:

In[*]= expansion = Sum[W[x, y, z] TensorProduct[Ket[x], Ket[y], Ket[z]], {x, 0, 1}, {y, 0, 1}, {z, 0, 1}]
Out[*]= |0> ⊗ |0> ⊗ |1> + |0> ⊗ |1> ⊗ |0> + |1> ⊗ |0> ⊗ |0>

If you think that looks ugly, just send this over to your favourite chatbot:

ChatGPT, please rewrite this |0> ⊗ |0> ⊗ |1> + |0> ⊗ |1> ⊗ |0> + |1> ⊗ |0> ⊗ |0> into LaTeX.

The output displays as

(11) $\begin{equation*}\ket{0} \otimes \ket{0} \otimes \ket{1} + \ket{0} \otimes \ket{1} \otimes \ket{0} + \ket{1} \otimes \ket{0} \otimes \ket{0},\end{equation*}$

as expected.

You can also use commas instead of putting a tensor product between each ket vector:

In[*]= expansion = Sum[W@@l TensorProduct[Ket@@l], {l, inputCombinations}]
Out[*]= |0, 0, 1⟩ + |0, 1, 0⟩ + |1, 0, 0⟩

Exercise. Use Mathematica to show that the Fand penalty corresponds to the following:

(12) $\begin{equation*}3 \ket{0, 0, 1} + \ket{0, 1, 1} + \ket{1, 0, 1} + \ket{1, 1, 0}. \end{equation*}$

Exercise. Use Mathematica to simplify some pseudo Boolean forms considering the relation that $x^2 = x$ . Example:

In[*]= Simplify[a b x^2 + a^2 x y + b^2 x y + a b y^2, Assumptions -> {x^2 == x, y^2 == y}]
Out[*]= a^2xy+b^2xy+ab(x+y)

We will have a lot more to say about pseudo Boolean functions later on. I just wanted to explain a little bit today. Similar material has been used in the practicals for my quantum information processing course a few times over the years. As always, please let me know if you have any comments, of if you spot any typos.

References

On symmetric pseudo-Boolean functions: factorization, kernels and applications
R Sengupta and J Biamonte
Preprint (2022) 10.48550/arXiv.2209.15009

Ground-state spin logic
J Whitfield, M Faccin, and J Biamonte
European Physics Letters 99(5):57004 (2012)
DOI: 10.1209/0295-5075/99/57004

Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
J Biamonte
Physical Review A 77(5):052331 (2008)
DOI: 10.1103/PhysRevA.77.052331

Share this article

Newsletter

Join My Newsletter

Type search term(s) and press enter

Popular Searches

Exploring Pseudo-Boolean Functions in Quantum Computing with Mathematica

Book

Blogs I read

Terminology and Notation

Normal forms and gradings

Quadratic pseudo Boolean functions

Mathematica for Pseudo Boolean functions

References

Related Posts

LaTeX Instructions

1 comment

Leave a comment Cancel reply

Join My Newsletter