Quantum query complexity of up to four-bit functions

A Mathematica worksheet computing the so-called witness size of a given span program over complex numbers. An efficient span program gives a bounded-error quantum algorithm for the function computed by the span program, and our worksheet therefore gives a way of evaluating the quantum query complexity of various Boolean gates. The worksheet allows for limited optimization, as you can specify the span program using some free variables, and it then finds their optimal values giving the most efficient span program.

We have compiled a table of all 222 four-bit functions, up to permutations of input bits and negation of input and output bits. Fourteen of these functions depend on only three bits, and 208 of these functions depend on all four input bits. They are numbered by converting their 16-bit truth tables into decimal. They are sorted first by their polynomial degree and then by their ADV± bound. For each function, we have also linked to a minimum-size {AND, OR, NOT} formula computing it. Comments for some functions are in the far right column.

A function f is lit with a color if we have an optimal span program for f, i.e., a span program P with f_P = f and wsize(P) = ADV(f).

• A yellow background means that optimality follows from composing smaller functions using an AND, OR, or Parity gate. A large class of examples are the functions f with {AND, OR, NOT} formulas of size exactly ADV(f)², which are computed optimally by their formulas.
• A pink background means that we have found an optimal span program P, based on one of the minimum-size {AND, OR, NOT} formulas, with optimized weights. (It is not necessarily based on the minimum-size formula listed here.)
• An orange background means that we have found an optimal span program P, which is not based on a formula, i.e. it is in some sense non-trivial.

For details, please see "Span-program-based quantum algorithm for evaluating formulas" (quant-ph/0710.2630, 2007), or contact one of the authors. You can download our Mathematica worksheet for computation of witness size of a span program. You can also download out Matlab/SeDuMi programs for computation of the adversary bound of a function, both for the nonnegative and negative version of the adversary bound.

- Ben Reichardt and Robert Špalek
   Last updated 11/30/2008