Span-program-based quantum algorithm for evaluating formulas
supplemental information

The purpose of this Mathematica file is to help the reader verify the span program witness size and adversary bound calculations of Appendix C.  Although adversary bounds on all four-bit functions were computed numerically in Ref. [HLŠ06], we need exact calculations of these bounds in order to claim that our span programs are exactly optimal.  

The provided code for evaluating span program witness size is based on taking pseudoinverses, and is best suited for numerical calculations.  For some of the more complicated span programs and span programs with unbalanced input complexities, we only compute here the span program witness size numerically.  For computing witness size exactly, faster calculations can be run by using the small-eigenvalue spectral analysis of of (Subscript[A, (Subscript[G, P])]); see Appendix A.2 or contact one of the authors.

The code automatically scales the part of the input vectors parallel to the target vector t, i.e., the first row of the matrix of input vectors, in order to balance out the witness szes in the true and false cases.  

The code has been tested in Mathematica 5.2 and Mathematica 6.  Note that the code uses global variables, so it is wise to reset the Mathematica kernel before running these procedures.  

Ben Reichardt and Robert Špalek
9/22/2008

Utility functions

Adversary bound utility functions

Di::usage = "Di[Γ,bit] takes a matrix \
Γ for which the entries of the first row and first column label \
the columns and rows of the remaining submatrix (see below for an example).  \
The labels are expected to be strings.  It outputs a matrix that has \
dimensions of the main block of Γ (i.e., one smaller than \
Γ in each direction) that is full of zeros except where the \
bit'th entry of the row label differs from the bit'th entry of the column, \
where it has a one.  These matrices are useful for computing the adversary \
bound.";
Di[Γ_, bit_] := 
        Module[{cols, rows, di, i, 
            j}, 
cols = Γ[[1, 
              Range[2, Dimensions[Γ][[2]]]]]; 
rows = Γ[[
              Range[2, Dimensions[Γ][[1]]], 1]]; 
{cols, 
              rows} = {Characters /@ cols, 
              Characters /@ rows}; 
{cols, 
              rows} = #[[
                      bit]] & /@ # & /@ {cols, 
                rows}; 
di = 
            ZeroMatrix[Length[rows], Length[cols]]; 
di = 
            Table[If[
                rows[[i]] == 
                  cols[[j]], 0, 
                1], 
{i, 1, Length[rows]}, {j, 1, 
                Length[cols]}]; 
di
];
"Example of Di:"
Clear[a, b, c, d, e, 
        f];
MatrixForm@Di[(({{0, "000", "001", "111"}, {"100", a, b, c}, {"110", d, e, f}})),#]&/@{1, 2, 3}



\(evalAdv::usage = "evalAdv takes an adversary matrix where the first row and first column have the input bit strings labeling the remainder of the matrix.  It outputs the adversary bound for that matrix (i.e., a lower bound on the true adversary bound) with costs specified by the optional second argument.";\)
evalAdv[Γ_, costs_: {}] := 
      Module[{g, n, 
          w}, 
g = Γ[[Range[
              2, Dimensions[Γ][[1]]], 
            Range[2, Dimensions[Γ][[2]]]]]; 

n = 
          StringLength[Γ[[1, 
              2]]]; 
w = 
          If[costs == {}, Table[1, {n}], 
            costs]; 

Norm[g]/Max@Table[(1/w)[[i]] Norm[g Di[Γ, i]], {i, 1, n}] // 
          Simplify
]
?evalAdv

"As an example, the adversary matrix and bound for MAJ3 with costs {1,1,β} is:"
evalAdv[(({{0, "011", "101", "110"}, {"100", 0, β, 1}, {"010", β, 0, 1}, {"001", 1, 1, 0}})),{1, 1, β}]/.{{β -> 1}, {β -> (Sqrt[2])}, {β -> 
              2}}//FullSimplify

Span program witness size utility functions

toTruthTable[d_] := 
        Module[{strings, 
            values}, 
strings = (StringJoin@(ToString /@ IntegerDigits[#, 2, 4])) & /@ (-1 + 
                  Range[16]); 
values = 
            IntegerDigits[d, 2, 16]; 
{strings, values} // 
            Transpose
];
<< DiscreteMath`Combinatorica`;

    
applyPermutation[
          p_] := 
1 + 
              FromDigits[#, 
                2] & /@ (Permute[#, 
                  p] & /@ (IntegerDigits[#, 2, 
                      4] & /@ (Range[(2^4)] - 
                      1)));
"Permuting the input bits permutes the truth table in some way.  This \
is a list of the 24 truth table permutations corresponding to the 4! input \
bit permutations"
inputPermutationPermutations = 
        applyPermutation /@ Permutations[Range[4]];

    
applyFlip[
          p_] := 
1 + 
              FromDigits[#, 
                2] & /@ (Mod[# + p, 
                  2] & /@ (IntegerDigits[#, 2, 
                      4] & /@ (Range[(2^4)] - 
                      1)));
"Flipping the input bits permutes the truth table in some way.  This \
is a list of the 16 truth table permutations corresponding to the 2^4 input \
bit flips"
inputFlipPermutations = 
        applyFlip /@ (IntegerDigits[#, 2, 4] & /@ (Range[16] - 
                  1));

    
"permutations is a list of all the truth table permutations \
corresponding to a composition of input bit flips and input bit \
permutations"
permutations = 
        Table[0, {Length[inputPermutationPermutations] 
              Length[inputFlipPermutations]}];
For[k = 1, 
        k ≤ 
          Length[inputPermutationPermutations], k++, 
For[j = 1, 
            j ≤ 
              Length[inputFlipPermutations], j++, 
permutations[[(k - 1) 
                      Length[inputFlipPermutations] + 
                    j]] = 
                Permute[
inputPermutationPermutations[[k]], 
                  inputFlipPermutations[[j]]
];
];
];

    
minimizeFunction::usage = "minimizeFunction takes the truth table of \
a function on four bits. It tries every possible permutation of the input \
bits, and also tries flipping the output, in order to generate the smallest \
possible equivalent truth table considered as a binary number.  It *does not* \
try flipping the input bits!"
minimizeFunction[tt_, verbose_:  False] := 
        Module[{bestsofar, candidate, candidateflipped, 
            k}, 
bestsofar = 
            FromDigits[tt, 2]; 
For[k = 1, 
            k ≤ 
              Length[permutations], k++, 
candidate = 
              Permute[tt, 
                permutations[[k]]]; 
candidateflipped = 
              1 - candidate; 
candidate = 
              FromDigits[candidate, 2]; 
candidateflipped = 
              FromDigits[candidateflipped, 2]; 
If[
              candidate < 
                bestsofar, bestsofar = candidate;]; 
If[
              candidateflipped < 
                bestsofar, bestsofar = 
                  candidateflipped;]; 
If[verbose, 
              Print[candidate]; 
              Print[candidateflipped];];
]; 
bestsofar
];

Off[Unset::norep];
Clear[A, r, ω, w, w1, w2, w3, w4, w5, w6, w7, w8, a, b, 
        c];
For[k = 1, 
        k ≤ 
          20, k++, 
Unevaluated[
            (Subscript[a, k])] =. ; 
Unevaluated[
            (Subscript[b, k])] =. ; 
Unevaluated[
            (Subscript[c, k])] =. ; 
Unevaluated[
            (Subscript[r, k])] =. ;
];
(Subscript[r, out]) =. ;
On[Unset::norep];

    
clearVariables::usage = "clearVariables[] attempts to clear the \
variables that need to be free.  The way Mathematica works it may not be \
successful clearing variables with subscripts, so it is recommended that you \
start a new session to ensure none of the variables are in use."
clearVariables[] := 
        Module[{k}, 
Off[
            Unset::norep]; 
Clear[A, r, ω, w, w1, 
            w2, w3, w4, w5, w6, w7, w8, a, b, c]; 
For[
            k = 1, k ≤ 
              20, k++, 
Unevaluated[
                (Subscript[a, k])] =. ; 
Unevaluated[
                (Subscript[b, k])] =. ; 
Unevaluated[
                (Subscript[c, k])] =. ; 
Unevaluated[
                (Subscript[r, k])] =. ;
]; 
(Subscript[r, out]) =. ; 
On[
            Unset::norep];
];
clearVariables[];

\(\*""Mathematica doesn't realize that, e.g., Conjugate[I a \!\(E\^\(I\\ b\)\)] = -I a \!\(E\^\(\(-I\)\\ b\)\), because it doesn't know variables are restricted to the reals.  This version of PseudoInverse forces that assumption."";\)
pseudoInverse[m_] := 
          PseudoInverse[m] /. Conjugate -> Identity;

preprocessSpanProgram::usage = "preprocessSpanProgram takes span programs \
in two forms, and outputs a span program in a standardized form that will be \
used for further processing.";
?preprocessSpanProgram

\(preprocessSpanProgram[mIn_] := 
          Module[{m = mIn, inputs, 
              i}, 
\*""If the first row of the matrix is the list of inputs, then separate it out.  Otherwise and if no inputs are specified, then by default set the inputs to {{(Subscript[x, 1])},{(Subscript[x, 2])},…,{(Subscript[x, n])}}.""; 
If[
              Head[m[[1, 1]]] === List || 
                Head[m[[1, 1]]] === 
                  Subscript || 
                Head[m[[1, 1]]] === 
                  OverBar || 
                m[[1, 1]] === 
                  t, 
inputs = 
                m[[1, 
                  All]]; 
m = 
                Rest[m];, 
\(inputs = 
                  Table[{x\_i}, {i, 
                      1, \(Dimensions[
                          m]\)[[2]]}];\)
]; 
preprocessSpanProgram[m, 
              inputs]
];\)

\(preprocessSpanProgram[mIn_, inputsIn_] := 
          Module[{m = mIn, inputs = inputsIn, ta, 
              n}, 
"If the first input is {t}, then the target vector is set to be the first column of m; otherwise, the target vector defaults to being {1,0,…,0}"; 
If[
              inputs[[1]] === {t} || 
                inputs[[1]] === 
                  t, 
ta = 
                m[[All, 
                  1]]; 
inputs = 
                Rest[inputs]; 
m = 
                Transpose[Rest[Transpose[m]]];, 
ta = 
                Table[0, {Length[
                      m]}]; 
ta[[1]] = 
                1;
]; 

\*""We allow for singleton grouped inputs to be entered without the braces, i.e., {(Subscript[x, 1])} and (Subscript[x, 1]) are equally acceptable.""; 
inputs = \(If[
                    Head[#] =!= List, {#}, #] &\) /@ 
                inputs; 

\*""Compute n, the number of variables.  Actually, we just find the largest i such that (Subscript[x, i]) or \!\(\(x\_i\)\&_\) is one of the inputs.""; 
n = 
              Max@\(Union@
                  Flatten[
                    inputs /. {x\_i_Integer -> 
                          i, \(x\_i_Integer\)\&_ -> 
                          i}]\); 

"If there are any empty inputs, vectors that are always true, then project onto the orthogonal subspace to eliminate them"; 
Module[{truecolindices, truecols, orthogtruecols, 
                i}, 
truecolindices = \(Position[
                    Length /@ inputs, 0]\)[[All, 
                  1]]; 
If[
                Length[truecolindices] > 0, 
truecols = 
                  m[[All, 
                    truecolindices]]; 
orthogtruecols = 
                  IdentityMatrix[Length[m]] - 
                      truecols . pseudoInverse[truecols] // 
                    Simplify; 
ta = 
                  orthogtruecols . 
                    ta; 
"Delete the true columns from m, and the empty inputs from inputs"; 
m = 
                  m[[All, 
                    Complement[
                      Range[\(Dimensions[
                            m]\)[[2]]], 
                      truecolindices]]]; 
inputs = 
                  inputs[[Complement[Range[Length[inputs]], 
                      truecolindices]]]; 
For[i = 1, 
                  i ≤ 
                    Length[inputs], \(i++\), 
\(m[[All, i]] = 
                      orthogtruecols . 
                          m[[All, i]] // 
                        Simplify;\)
];
];
]; 

"Finally, output {number of variables, target vector, columns, grouped input literals}"; 
{n, ta, m, inputs}
];\)

prepSP = preprocessSpanProgram;

Clear[
        evaluateInputs];
\(evaluateInputs::usage = "evaluateInputs is a subroutine that takes a list of inputs and a truth table for the variables, and evaluates them…"\)
\(evaluateInputs[inputs_, kd_] := 
        Module[{evals}, 
evals = \(\((\(\((# /. {x\_\(i : _Integer\) -> 
                              Hold[kd[[i]]], \(x\_\(i : _Integer\)\)\&_ -> 
                              1 - Hold[
                                  kd[[i]]]})\) &\) /@ #)\) &\) /@ inputs; 
evals = 
            ReleaseHold[
              evals]; 
"Note Times@@{}=1, so empty sets of literals evaluate to true."; 
evals = \(Times @@ # &\) /@ evals; 
evals
];\)
\(If[
          evaluateInputs[{{x\_1, \(x\_2\)\&_}, {}, {x\_3}}, {1, 0, 
                0}] ≠ {1, 1, 0}, \(Print["Error!"];\)];\)

\(evaluateGroupedInputComplexities::usage = "evaluateGroupedInputComplexities is a subroutine that takes a list of inputs and a truth table for the variables, and outputs the grouped input complexities, assuming that the input complexities are all 1.";\)
Clear[inputComplexities];
\(evaluateGroupedInputComplexities[inputs_, kd_] := 
          Module[{evals}, 
evals = \(\((\(\((# /. {x\_\(i : _Integer\) -> 
                                Hold[kd[[i]]], \(x\_\(i : _Integer\)\)\&_ -> 
                                1 - Hold[
                                    kd[[i]]]})\) &\) /@ #)\) &\) /@ 
                inputs; 
evals = 
              ReleaseHold[evals]; 

If[
              ValueQ[inputComplexities], 
MapIndexed[\((
eval = Times @@ #1; 
If[
                      eval == 1, 
If[
                        Length[#1] == 0, 1, 
                        Plus @@ 
                          inputComplexities[[#2[[1]]]]], 
1/
                        Plus @@ \(inputComplexities[[#2[[1]], \(Position[#1, 
                                    0]\)[[All, 
                                  1]]]]\^\(-1\)\)
]
)\) &, 
                evals], 
 (*\ 
                this\ is\ the\ old\ version, \ 
                called\ when\ the\ global\ variable\ inputComplexities\ is\ not\ defined\ *) 
\(\((eval = 
                      Times @@ #1; 
If[eval == 1, 
                      Max[Length[#1], 1], 
1/
                        Count[#1, 
                          0]
]
)\) &\) /@ 
                evals
]
];\)

evaluateSpanProgram::usage = "If the first input is {t}, then the target \
vector is set to be the first column of m; otherwise, the target vector \
defaults to being {1,0,…,0}"
\(evaluateSpanProgram[{n_, ta_, m_, inputs_}] := 
        Module[{k, kd, evals, tt, md, mdproj, w}, 
tt = 
            Table[0, {2\^n}]; 
For[k = 0, 
            k ≤ 2\^n - 1, \(k++\), 
kd = 
              IntegerDigits[k, 2, 
                n]; 

evals = 
              evaluateInputs[inputs, 
                kd]; 
"Zero out all false columns of m"; 
md = 
              Transpose[evals\ Transpose[m]]; 
mdproj = 
              md . pseudoInverse[md] // 
                Simplify; 

"Does the target lie in the span of the remaining (true) columns?  Note that if the span program is specified numerically, we use Chop to determine whether the final number is 0 or nonzero"; 
w = 
              ta - mdproj . ta // Simplify; 
w = 
              w . Conjugate[w] // Simplify; 
w = 
              Chop[w]; 
If[
              Abs@\(N@w\) < 
                10\^\(-6\), 
"If it is numerically close to zero, then simplify to see if it is exactly zero."; 
w = FullSimplify@
                  w;
]; 
tt[[k + 1]] = 
              If[w == 0, 1, 0, 
                0]; 

 (*"Verbose output:"; 
Print["kd= ", kd, ", mdproj= ", 
                mdproj, ", evals= ", evals, ", md= ", 
                md, ", w= ", w]; 
Print["tt= ", 
                tt[[k + 
                    1]]]; 
Print[
                Simplify@\((ta - 
                      md . pseudoInverse[md] . 
                        ta)\)];*) 
]; 
tt
];\)
evalSP = evaluateSpanProgram;

"Testing…"
p=prepSP[(({{{(Subscript[x, 1])}, {(Subscript[x, 2])}, {(Subscript[x, 3])}}, {1, 1, 1}, {1, ω, (ω^2)}}))/.ω -> (E^(2  π I/3))];
evalSP[
      p]
p=prepSP[(({{{(Subscript[x, 1])}, {(Subscript[x, 2])}, {(Subscript[x, 3])}}, {1, 1, 1}, {w1, w2, w3}}))];
evalSP[p]

Clear[
        evaluateSpanProgramComplexity, 
        evalSPC];
evaluateSpanProgramComplexity::usage = "Call evalSPC[prepSP[m]] or \
pevalSPC[m], for short."
\(evaluateSpanProgramComplexity[{n_, ta_, m_, inputs_}, verbose_:  True, 
          doSimplify_:  True] := 
        Module[{simplify, dim, size, tt, spc, k, kd, evals, 
            S, Π, Πc, Δ, Δc, w, mSi}, 
simplify = 
            If[doSimplify, Simplify, 
              Identity]; 

tt = 
            evaluateSpanProgram[{n, ta, m, inputs}]; 
{dim, 
              size} = Dimensions[m]; 

If[
            n ≤ 
              4, 
"Expand the truth table so it has length 2^4=16, and then call minimizeFunction[]"; 
Print["Function computed is #", 
              minimizeFunction[
Switch[
                  n, 
4, tt, 
3, 
                  Flatten@{tt, tt}, 
2, 
                  Flatten@{tt, tt, tt, tt}, 
1, 
                  Flatten@{tt, tt, tt, tt, tt, tt, tt, 
                      tt}
]]];, 
\(Print["Function computed has truth table ", 
                tt];\)
]; 

spc = Table[0, {2\^n}]; 
For[k = 0, 
            k ≤ 2\^n - 1, \(k++\), 
kd = 
              IntegerDigits[k, 2, n]; 
If[
              verbose, \(Print[" ", 
                  kd];\)]; 

evals = 
              evaluateInputs[inputs, kd]; 
Π = 
              DiagonalMatrix[evals]; 
Πc = 
              DiagonalMatrix[
                1 - evals]; 

S = 
              DiagonalMatrix[\@evaluateGroupedInputComplexities[inputs, kd]]; 

If[
              tt[[k + 1]] == 
                1, 
w = 
                pseudoInverse[m . Π . Inverse[S]] . 
                  ta; 
w = 
                w . Conjugate[w] // 
                  simplify; 
"Throw away any leftover Conjugates, because Mathematica isn't smart enough to know that variables are real-valued.  CAUTION: using this code on span programs with complex weights."; 
w = 
                w /. Conjugate -> 
                    Identity; 
spc[[k + 
                    1]] = 
                w;
]; 

If[
              tt[[k + 1]] == 
                0, 
mSi = 
                pseudoInverse[m . S] // simplify; 
w = 
                mSi . ta // 
                  simplify; 
"Computing the PseudoInverse below is very slow if there are any free variables, since each entry of mSi is already a polynomial…"; 
w = \((IdentityMatrix[size] + \((pseudoInverse[Πc . mSi . m . S - 
                                  IdentityMatrix[size]] // 
                              simplify)\) . Π)\) . w // 
                  simplify; 
w = 
                w . Conjugate[w] // 
                  simplify; 
"See above comment"; 
w = 
                w /. Conjugate -> 
                    Identity; 
spc[[
                  k + 1]] = 
                1/w;
];
]; 

"Chop sets small numbers to zero if the span program is given numerically.  This should be avoided."; 
spc = Chop@spc; 
spc = 
            FullSimplify@
              spc; 

"Now determine the maximum spc for a false input and the maximum spc for a true input"; 
{
√\((Max[
                    spc[[\(Position[tt, 
                          0]\)[[All, 
                        1]]]]] 
                  Max[spc[[\(Position[tt, 
                          1]\)[[All, 
                        1]]]]])\), 
{\(StringJoin[ToString /@ IntegerDigits[#, 2, n]] &\) /@ 
                  Range[0, 
                    2\^n - 1], 
tt, 
spc} // MatrixForm
}
];\)
evalSPC = evaluateSpanProgramComplexity;

\(pevalSPC::usage = "pevalSPC is short for 'prepare and evaluate span program complexity.'  pevalSPC[m] is the same as evalSPC[prepSP[m]]"\)
pevalSPC[a_] := evalSPC@prepSP[a];

Function #831, (Subscript[MAJ, 3]), with partly unbalanced inputs—numerically

Adversary matrix:

Clear[β];
evalAdv[(({{0, "011", "101", "110"}, {"100", 0, β, 1}, {"010", β, 0, 1}, {"001", 1, 1, 0}})),{1, 1, β}]/.{{β -> 1}, {β -> (Sqrt[2])}, {β -> 
              2}}//FullSimplify

Span programs: 
(Note that the pevalSPC function sets the target vector to (1,0,…,0) by default, and by default assigns literal (Subscript[X, j]) = {(Subscript[x, j])} to column j.)

pevalSPC[(({{(1/(Sqrt[3])), (1/(Sqrt[3])), (1/(Sqrt[3]))}, {1, ω, (ω^2)}}))/.{ω -> (E^(2  π I/3))}]

Clear[β];
α = (1/(2 (Sqrt[ 2]))) (Sqrt[(Sqrt[8 + (β^2)]) - β]);
m=(({{α, α, (Sqrt[(1/2) + β (α^2)])}, {I, -I, 2  α}}));
inputComplexities = {{1}, {1}, {β}};

β = 1;
pevalSPC[m]
Clear[β];

β = (Sqrt[2]) // N[#, 32] &;
pevalSPC[m]
Clear[β];

β = 2;
pevalSPC[m]
Clear[β];

Clear[inputComplexities];

Function #975 with partly unbalanced inputs

Adversary matrix:

Clear[β];
evalAdv[(({{0, "010", "101"}, {"100", 1, β}, {"011", β, 1}})),{1, 1, β}]/.{{β -> 1}, {β -> (Sqrt[2])}, {β -> 
              2}}//FullSimplify

Span programs:

m=(({{(Subscript[x, 1]), (Subscript[x, 3]), \(\(x\_3\)\&_\), (Subscript[x, 2])}, {0, 1, 1, 0}, {1, 1, 0, 0}, {0, 0, 1, 1}}));
Clear[β];
inputComplexities = {{1}, {β}, {β}, {1}};

β = 1;
pevalSPC[m]
Clear[β];

β = (Sqrt[2]);
pevalSPC[m]
Clear[β];

β = 2;
pevalSPC[m]
Clear[β];

Clear[inputComplexities];

Function #960, (Subscript[EQUAL, 3]), with partly unbalanced inputs

Adversary matrix:

Clear[α, β];
evalAdv[(({{0, "000", "111"}, {"100", 2  α, α}, {"010", 2  α, α}, {"001", 2, 1}, {"011", α, 2  α}, {"101", α, 2  α}, {"110", 1, 2}}))/.α -> (Sqrt[((4 - (β^2))/(5  (β^2) - 2))]),{1, 1, β}]/.{{β -> 1}, {β -> (Sqrt[2])}, {β -> 
              2}}//FullSimplify

Span programs:

Clear[β];
w = 
        (1/(Sqrt[β]));
m=(({{{(Subscript[x, 3])}, {(Subscript[x, 1]), 
                  (Subscript[x, 2])}, \({\(x\_1\)\&_, \(x\_2\)\&_}\), \({\(x\_3\)\&_}\)}, {0, 1, 1, 0}, {w, 1, 0, 0}, {0, 0, 1, w}}));
inputComplexities = {{β}, {1, 
            1}, {1, 1}, {β}};

β = 1;
pevalSPC[m]
Clear[β];

β = (Sqrt[2]);
pevalSPC[m]
Clear[β];

β = 2;
pevalSPC[m]
Clear[β];

Clear[inputComplexities];

Function #963 with partly unbalanced inputs—numerically

Adversary matrix:

Clear[β];
evalAdv[(({{0, "000", "001", "111"}, {"011", 0, 1, 1}, {"101", 0, 1, 1}, {"110", 1, 0, β}})),{1, 1, β}]/.{{β -> 1}, {β -> (Sqrt[2])}, {β -> 
              2}}//FullSimplify

Span programs:

Clear[β];
{w1, 
          w2} = {(1/2) (((1 + (β^2) + (Sqrt[9 + 2  (β^2) + (β^4)])))^((1/2))), (1/(Sqrt[2  β])) (((-3 + (β^2) + (Sqrt[9 + 2  (β^2) + (β^4)])))^((1/2)))};
m=(({{{(Subscript[x, 1])}, {(Subscript[x, 2]), (Subscript[x, 3])}, \({\(x\_2\)\&_, \(x\_3\)\&_}\)}, {0, w1, 1}, {1, w2, 0}}));
inputComplexities = {{β}, {1, 
            1}, {1, 1}};

β = 1;
pevalSPC[m]
Clear[β];

β = (Sqrt[2]) // N;
pevalSPC[m]
Clear[β];

β = 2 // N;
pevalSPC[m]
Clear[β];

Clear[inputComplexities];

Function #828, (Subscript[EXACT, 2 of 3]), with partly unbalanced inputs—numerically

Adversary matrix:

Clear[β];
evalAdv[(({{0, "110", "101", "011"}, {"001", 0, 1, 1}, {"010", 1, 0, β}, {"100", 1, β, 0}, {"111", β, 1, 1}})),{1, 1, β}]/.{{β -> 1}, {β -> (Sqrt[2])}, {β -> 
              2}}//FullSimplify
% // 
      N[#, 32] &

Span programs:

Clear[β];
{w1, 
          w2} = {(Sqrt[(((Sqrt[8  (β^2) + 1]) - 1)/(2  β))]), 
          (1/(Sqrt[(Sqrt[8  (β^2) + 1]) + 3]))};
m=(({{\({\(x\_1\)\&_, \(x\_2\)\&_}\), \({\(x\_3\)\&_}\), {(Subscript[x, 1])}, {(Subscript[x, 2])}, {(Subscript[x, 3])}}, {1, 0, w2, w2, w1/(Sqrt[2])}, {0, 0, I, -I, w1}, {w1, 1, 0, 0, 0}}));
inputComplexities = {{1, 
            1}, {β}, {1}, {1}, {1}};

β = 1;
pevalSPC[m]
Clear[β];

β = (Sqrt[2]) // N[#, 32] &;
pevalSPC[m]
Clear[β];

β = 2 // N[#, 32] &;
pevalSPC[m]
Clear[β];

Clear[inputComplexities];

Function #393

Adversary matrix:

evalAdv@(({{0, "0010", "1101", "0111", "1011"}, {"0001", 1, 3, 0, 0}, {"1110", 3, 1, 0, 0}, {"0011", 2 (Sqrt[ 2]), 0, 3, 3}, {"1111", 0, 2 (Sqrt[ 2]), 3, 3}}))

Span program:

pevalSPC@(({{{(Subscript[x, 1]), 
                (Subscript[x, 2])}, {(Subscript[x, 3])}, \({\(x\_1\)\&_, \(x\_2\)\&_}\), {(Subscript[x, 4])}}, {1, 0, 1, 0}, {1, (Sqrt[3/2]), 0, 0}, {0, 0, 1, (Sqrt[3/2])}}))

Function #989—numerically

Function #989 is equivalent to the formula (x1 & x2 & x3) v (!x1 & (!x2 v x4)).

Adversary matrix:

evalAdv@(({{0, "0010", "0111", "1100"}, {"0011", 1, 1, 0}, {"0110", 1, 1, 1}, {"1101", 0, 1, 1}}))//FullSimplify

pevalSPC@(({{\({\(x\_1\)\&_, 
                x\_2}\), {}, \({\(x\_2\)\&_}\), \({\(x\_3\)\&_}\), {(Subscript[x, 4])}, \({\(x\_4\)\&_}\)}, {0, 1, 1, 1, (2^(1/4)), 1}, {0, 1, (2^(-1/4)), (2^(-1/4)), 1, 1}, {(2^(1/4)) // N, 1, 0, 0, 0, 0}}))

Function #1968

Function #1968 is equivalent to the formula (x1 & x2 & (x3 v x4)) v (!x1 & !x2 & (!x3 v x4)).  
Note that complementing the first three input bits, or switching the first two input bits, does not affect the evaluation.

Adversary matrix:

evalAdv@(({{0, "0000", "1110", "0011", "1101"}, {"0010", 3 (Sqrt[ 7]), 2 (Sqrt[ 7]), 3 (Sqrt[ 7]), 0}, {"1100", 2 (Sqrt[ 7]), 3 (Sqrt[ 7]), 0, 3 (Sqrt[ 7])}, {"1001", 5, 0, 2, 7}, {"0101", 5, 0, 2, 7}, {"0111", 0, 5, 7, 2}, {"1011", 0, 5, 7, 2}}))

Span program:

pevalSPC@(({{{(Subscript[x, 1]), 
                (Subscript[x, 2])}, {(Subscript[x, 3])}, {(Subscript[x, 4])}, \({\(x\_1\)\&_, \(x\_2\)\&_}\), \({\(x\_3\)\&_}\), {(Subscript[x, 4])}}, {1, 0, 0, 1, 0, 0}, {1, ((Sqrt[3])/2), ((Sqrt[3])/2), 0, 0, 0}, {0, 0, 0, 1, ((Sqrt[3])/2), ((Sqrt[3])/2)}}))

Function #1910

Function #1910 is equivalent to the formula (x1 & x2 & x3 & x4) v (!x1 & !x2) v (!x3 & !x4).  
Note the symmetries.

Adversary matrix:

evalAdv@(({{0, "0001", "0010", "0100", "1000", "0011", "1100", "1111"}, {"0111", 0, 0, 1, 0, 1, 0, 1}, {"1011", 0, 0, 0, 1, 1, 0, 1}, {"1101", 1, 0, 0, 0, 0, 1, 1}, {"1110", 0, 1, 0, 0, 0, 1, 1}}))

Span program:

pevalSPC@(({{{(Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3]), 
                (Subscript[x, 4])}, \({\(x\_1\)\&_, \(x\_2\)\&_}\), \({\(x\_3\)\&_, \(x\_4\)\&_}\)}, {(Sqrt[2]), 1, 1}}))

Function #317

Function #1910 is equivalent to the formula (x1 & x2 & x3) v MAJ3(!x2, !x3, x4).

Adversary matrix:

evalAdv@(({{0, "0111", "1010", "1100"}, {"1000", 0, 1, 1}, {"0011", 1, 1, 0}, {"0101", 1, 0, 1}, {"1110", 1, 1, 1}}))

Function #5790

Adversary matrix:

evalAdv@(({{0, "0011", "0100", "1000", "1111"}, {"0000", 1, 1, 1, 0}, {"0111", 1, 1, 0, 1}, {"1011", 1, 0, 1, 1}, {"1100", 0, 1, 1, 1}}))

Span program:

pevalSPC[(({{{(Subscript[x, 1])}, \({x\_2, \(x\_3\)\&_}\), \({\(x\_2\)\&_, 
                x\_3}\), \({\(x\_1\)\&_}\), {(Subscript[x, 2]), 
                (Subscript[x, 4])}, \({\(x\_2\)\&_, \(x\_3\)\&_}\)}, {1, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 0, 0}, {0, 0, 0, 1, 1, 1}}))]

Function #385—numerically

Function #385 is equivalent to the formula (x2 & x3 & x4) v (x1 & !x2 & !x3 & !x4)).  Note the symmetries.

Adversary matrix:

evalAdv@(({{0, "0111", "1000", "1111"}, {"0000", (Sqrt[2]), (Sqrt[2]), 0}, {"1001", 0, (Sqrt[2]), 1}, {"1010", 0, (Sqrt[2]), 1}, {"1100", 0, (Sqrt[2]), 1}}))

Span program:

pevalSPC[(({{{(Subscript[x, 2]), (Subscript[x, 3]), 
                (Subscript[x, 4])}, {(Subscript[x, 1])}, \({\(x\_2\)\&_, \(x\_3\)\&_, \(x\_4\)\&_}\)}, {1 // N, 0, ((((61 + 7 (Sqrt[ 73])))^(1/4))/((2^(3/4)) (Sqrt[3])))}, {0, ((((49 + 5 (Sqrt[ 73])))^(1/4))/((2^(3/4)) (Sqrt[3]))), 1}}))]

Function #279, (Subscript[Threshold, 2 of 4])

Adversary matrix:

evalAdv@(({{0, "0111", "1011", "1101", "1110"}, {"0011", 1, 1, 0, 0}, {"0101", 1, 0, 1, 0}, {"0110", 1, 0, 0, 1}, {"1100", 0, 0, 1, 1}, {"1010", 0, 1, 0, 1}, {"1001", 0, 1, 1, 0}}))

Span program:

pevalSPC@(({{{(Subscript[x, 1])}, {(Subscript[x, 1])}, {(Subscript[x, 2])}, {(Subscript[x, 2])}, {(Subscript[x, 3])}, {(Subscript[x, 3])}, {(Subscript[x, 4])}, {(Subscript[x, 4])}}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 1, 1, -1, I, -I, I, I}, {I, -I, I, I, 1, 1, 1, -1}}))

Function #1639

Function #1639 is equivalent to the formula (x1 & x2) v MAJ3(!x1 & !x2, x3, x4).  Note the symmetries.

Adversary matrix:

evalAdv@(({{0, "0000", "0101", "1001", "0110", "1010"}, {"0001", 1, 1, 1, 0, 0}, {"0010", 1, 0, 0, 1, 1}, {"0111", 0, 1, 0, 1, 0}, {"1011", 0, 0, 1, 0, 1}, {"1100", 1, 0, 0, 0, 0}, {"1101", 0, 1, 1, 0, 0}, {"1110", 0, 0, 0, 1, 1}}))

Span program:

pevalSPC[(({{{(Subscript[x, 1]), 
                (Subscript[x, 2])}, \({\(x\_1\)\&_, \(x\_2\)\&_}\), {(Subscript[x, 3])}, {(Subscript[x, 4])}}, {1, (Sqrt[5])/2, 1/2, 1/2}, {0, 1, I, -I}}))]

Function #6014, (Subscript[EXACT, 2 or 3 of 4])—numerically

Adversary matrix:

evalAdv@(({{0, "1000", "0100", "0010", "0001", "1111"}, {"0011", 0, 0, 1, 1, (1/(Sqrt[3]))}, {"0101", 0, 1, 0, 1, (1/(Sqrt[3]))}, {"0110", 0, 1, 1, 0, (1/(Sqrt[3]))}, {"1100", 1, 1, 0, 0, (1/(Sqrt[3]))}, {"1010", 1, 0, 1, 0, (1/(Sqrt[3]))}, {"1001", 1, 0, 0, 1, (1/(Sqrt[3]))}}))

Span program:

pevalSPC@(({{{(Subscript[x, 1])}, {(Subscript[x, 1])}, {(Subscript[x, 2])}, {(Subscript[x, 2])}, {(Subscript[x, 3])}, {(Subscript[x, 3])}, {(Subscript[x, 4])}, {(Subscript[x, 4])}, \({\(x\_1\)\&_}\), \({\(x\_2\)\&_}\), \({\(x\_3\)\&_}\), \({\(x\_4\)\&_}\)}, {0, 0, 0, 0, 0, 0, 0, 0, (2^(-1/4)), (2^(-1/4)), (2^(-1/
                    4)), (2^(-1/4))}, {1, 1, 1, 1, 1, 1, 1, 1, (Sqrt[3]) // N, (Sqrt[3]), (Sqrt[3]), (Sqrt[3])}, {1, 1, 1, -1, I, -I, I, I, 0, 0, 0, 0}, {I, -1, I, I, 1, 1, 1, -1, 0, 0, 0, 0}}))

Function #278, (Subscript[EXACT, 1 of 4])

Adversary matrix:

evalAdv@(({{0, "0111", "1011", "1101", "1110"}, {"0011", 1, 1, 0, 0}, {"0101", 1, 0, 1, 0}, {"0110", 1, 0, 0, 1}, {"1100", 0, 0, 1, 1}, {"1010", 0, 1, 0, 1}, {"1001", 0, 1, 1, 0}, {"1111", 1, 1, 1, 1}}))

Function #5736, (Subscript[EXACT, 2 of 4])

Adversary matrix:

evalAdv@(({{0, "1000", "0100", "0010", "0001", "0111", "1011", "1101", "1110"}, {"0011", 0, 0, 1, 1, 1, 1, 0, 0}, {"0101", 0, 1, 0, 1, 1, 0, 1, 0}, {"0110", 0, 1, 1, 0, 1, 0, 0, 1}, {"1100", 1, 1, 0, 0, 0, 0, 1, 1}, {"1010", 1, 0, 1, 0, 0, 1, 0, 1}, {"1001", 1, 0, 0, 1, 0, 1, 1, 0}}))