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 , 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 to represent the set of all -long binary words, where concatenation is juxtaposition. For example,

A Boolean tuple is a placeholder for an element in or a variable over the set .

We say that a Boolean function has type

and a pseudo-Boolean function has type

Here is the set of values on the real number line .

We will abbreviate Boolean tuples in two distinct ways. We say that is a specific string in , whereas is an indeterminate over . We will use non-bold fonts for the case , for example is the -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 is pseudo-Boolean, maps each string to whereas if would be a pseudo-Boolean polynomial over indeterminates .

## Normal forms and gradings

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

(1)

We again use to represent the tuple , and , concatenated variables such as are multiplied with the multiplication symbol omitted and finally, is the logical negation of Boolean variable . We will often replace .

We call two monomials disjoint whenever their product contains a variable and its negation. For example, and are disjoint. The product of such terms vanishes as which is identically zero as Boolean variables are idempotent: .

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

(2)

Here we adopt the convention that and , . In this way, each bit string defines a monomial , and their product

vanishes for disjoint terms.

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

(3)

These forms (1) and (3) each uniquely define any -variable pseudo-Boolean function in terms of real numbers and . If for any input , then is called non-negative. We call

(4)

the affine part of . Any equation that can be entirely expressed in the form (4) is called affine and when the function is called linear.

## Quadratic pseudo Boolean functions

A quadratic pseudo-Boolean function is given as

(5)

where the fraction on the left-hand-side denotes 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 the kernel of the pseudo-Boolean function . 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)

where takes values . There is a simple relationship, where is a Boolean variable. It is also typical in quantum theory to write this in matrix form as:

(7)

here is a matrix:

(8)

Terms such as omit the symbol and also the identity matrix acts on the rest of the space. For example, acting on variables really means , where is the identity matrix. In this setting the vector represents logical zero and represents logical one.

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

(9)

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

(10)

and on all other inputs (in the compliment set ) the function, . 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)

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)

**Exercise**. Use Mathematica to simplify some pseudo Boolean forms considering the relation that . 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

Here is the GitHub link to download the notebook with all examples and solutions to the exercises.