Negative weights makes adversaries stronger

Peter Høyer, Troy Lee, and Robert Špalek

A Matlab program using the SeDuMi optimization package, computing the so-called adversary bound for a given Boolean function. An adversary bound is a lower bound for quantum query complexity of a function. If one manages to get the same adversary bound as the witness size of some span program, then the quantum complexity of the function has been fully characterized. We solve approximately the semidefinite formulation of the problem, and compute both the nonnegative and negative version of the bound.

The numerical results of the paper were obtained using the following software packages:

• Matlab 5.0: general purpose numeric computation package
• SeDuMi 1.1: Matlab package for convex optimization
• ADV and ADV±: our own Matlab modules that use the functions provided by SeDumi to find optimal adversary matrices for Boolean functions. ADV looks for non-negative matrices and ADV± looks for matrices possibly using negative weights. The usage is as follows. Assign the set of 0-inputs of a function into X, and of 1-inputs into Y. The function may be partial, hence you don't have to enter all inputs. The following example is for the majority function on 3 bits. Then run

      X = [ 0, 0, 0; 0, 0, 1; 0, 1, 0; 1, 0, 0]
      Y = [ 0, 1, 1; 1, 0, 1; 1, 1, 0; 1, 1, 1]
      [Gamma, D] = adv(X, Y)

  Gamma contains the optimal adversary matrix, and D contains 0-1 coefficients to obtain the submatrices Gamma_i. You can obtain Gamma_1 by entering

      Gamma1 = Gamma .* mat(D(:,1))

  You can examine the eigenvalues etc. of the adversary matrices using standard Matlab commands eig and svd.

Enclosed you can find definitions of some Boolean functions that achieve good separations:

Finally, a table of all 222 4-bits functions (up to permutations of input bits and negation of input and output bits) follows. They are numbered by 16-bit numbers according to their truth table, and sorted first by their polynomial degree and then by their ADV± bound.