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
Here
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
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
Quadratic pseudo Boolean functions
A quadratic pseudo-Boolean function is given as
(5)
where the fraction on the left-hand-side denotes
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
(7)
here
(8)
Terms such as
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
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.