Quantum query complexity of up to four-bit functions

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).

If we know a span program P that performs better than √(minimum {AND, OR, NOT} formula size), but that does not match the best known lower bound, then its span-program complexity is filled in under the "Status" heading. We have not yet considered those functions that are not shaded and have a blank "Status" entry.

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

Function Degree ADV ADV± Formula Status Comments
Functions on at most 3 bits
0 0 0 0 constant 0
255 1 1 1 x1
15 2 √2 2 AND2, x1 & x2
3 3 √3 3 AND3, x1 & x2 & x3
63 3 √3 3 x1 v (x2 & x3)
4080 2 2 4 Parity2, x1+x2
975 2 2 4 If-Then-Else, (x3 & x2) v (!x3 & x1)
831 3 2 5 Maj3
960 2 3/√2 6 Equal3
963 3 √(3+√3) 5 (x1 & x2 & x3) v (!x2 & !x3)
60 3 √5 5 x1 v (x2 + x3)
1020 3 1+√2 6 x1 + (x2 v x3)
828 3 √7 8 Exact 2 of 3
15555 3 3 10 Parity3, x1+x2+x3
Polynomial degree up to 3
7128 2 2.5 2.51353 10 2.77394 sorted input bits [Ambainis]
863 3 2 2.07136 5 2.22833 monotone two adjacent 1s
427 3 2.18398 2.20814 5 2.22833 #975(x1 & x2, x3, x4)
27 3 √5 5 x1 & #975(x2, x3, x4)
393 3 4/√3 6
383 3 2.30278 2.34406 7 √(4+√3) (x1 & x2 & x3) v ((x1 v x2 v x3) & x4)
126 3 √5.5 7 x1 & !Equal3(x2, x3, x4)
24 3 √5.5 7 x1 & Equal3(x2, x3, x4)
303 3 2.35829 6 1 + √2 span program size 5
495 3 1+√2 6 #975(x1, x2, x3 & x4)
989 3 1+√2 6
965 3 2.41531 2.42653 7 2.59234
987 3 2.43128 2.44711 7
424 3 √6 8 Equal3(x1, x2, x3 & x4)
2034 3 2.47323 2.48653 7
429 3 2.48837 2.50826 7
490 3 2.52207 2.52326 8
281 3 2.51464 2.54019 8
2022 3 2.55719 2.58189 8
1968 3 2√(5/3) 8
1782 3 2.56155 2.59040 7 2.61804 #975(x1+x2, x3, x4)
984 3 2.58539 2.60282 8
1973 3 2.61704 2.63510 8
1910 3 √7 8
317 3 √7 8 (x1 & x2 & x3) v Maj3(!x2, !x3, x4)
858 3 √7 2.64658 8 √(5 + 2√2)
300 3 2.69932 2.70595 9
6030 3 2.70928 10 3 classical 3 query alg.
894 3 2.70808 2.71982 10
1714 3 2.75018 2.75944 10
1980 3 2.75779 2.77469 9
1719 3 2.76916 2.78319 9
366 3 2.76569 2.80341 10
6042 3 2.84104 2.84923 10
1716 3 2.86854 2.88186 10
1680 3 3 12 Equal3(x1, x2, x3+x4)
1695 3 3 10 #975(x1, x2, x3+x4), tight classical
5790 3 3 10 tight classical
7140 3 3 10 x1+#975(x2, x3, x4), tight classical
1683 3 3.00283 3.01009 11
5766 3 3.02533 3.03595 12
6627 3 3.01470 3.04933 12
5783 3 3.03917 3.07294 12
6375 3 1+√4.5 14 x1 + Equal3(x2, x3, x4)
Polynomial degree 4
1 4 2 4 AND4
127 4 2 4 x1 v AND3(x2, x3, x4)
31 4 2 4
7 4 2 4
855 4 2 4 and-or tree, monotone cyclic two adjacent 1s
319 4 2.17533 2.20453 6 2.27731
431 4 2.20635 2.20721 5 2.22835
23 4 √5 6 x1 & Maj3(x2, x3, x4)
399 4 2.22595 2.25274 6
287 4 √(3+√5) 6 Maj3(x1, x2, x3 & x4)
384 4 4/√3 8 Equal4
447 4 2.30278 2.31707 7
385 4 (1/2)√(13+√73) 7
395 4 2.29062 2.32499 6
2032 4 √((7+√17)/2) 6 #963(x1, x2, x3 v x4)
426 4 √((7+√17)/2) 6 #963(x1, x2, x3 & x4)
967 4 2.36698 2.37004 6
25 4 √(4+√3) 6 x1 & #963(x2, x3, x4)
61 4 √(4+√3) 6 x1 v #963(x2, x3, x4)
981 4 2.39489 2.40490 7
283 4 2.40091 2.42364 7
983 4 2.42266 2.42424 6
409 4 2.39120 2.42693 7
961 4 2.43531 2.43869 7
111 4 √6 6 x1 v #60(x2, x3, x4)
1638 4 √6 6 #60(x1 v x2, x3, x4)
279 4 √6 8 Threshold 2 of 4
6 4 √6 6 x1 & #60(x2, x3, x4)
387 4 2.48662 2.50251 7
859 4 2.49857 2.50575 7
988 4 2.53791 2.53835 7
411 4 2.52192 2.54009 8
1654 4 2.51758 2.54347 7
445 4 2.53019 2.55017 9
425 4 2.55654 7 2.55654 #963(x1 & x2, x3, x4), need exact expr.
494 4 2.55654 7 2.55654 #963(x1 v x2, x3, x4), need exact expr.
2018 4 2.54502 2.55711 8
2016 4 2.55128 2.55874 8
2033 4 2.56155 8 2.59163
491 4 2.56388 2.57901 7 2.64302
879 4 2.57641 2.58289 8
415 4 2.57096 2.58436 8
428 4 2.59386 2.60618 8
430 4 2.60716 2.60975 7
30 4 √(4+2√2) 7 x1 & #1020(x2, x3, x4)
2019 4 2.61439 2.62037 8
488 4 2.62705 10
1639 4 √7 8 (x1 & x2) v Maj3(!x1 & !x2, x3, x4)
1969 4 2.64898 2.65285 9
1778 4 2.66716 2.66873 8
985 4 2.65949 2.67406 8
980 4 2.67345 2.67735 9
1650 4 2.67869 2.68369 8
391 4 2.68828 2.70027 9
878 4 2.68845 2.70057 9
1918 4 2.70131 10 (!x1 & x2 & (x3 v x4)) v (x1 & !Equal3(x2, x3, x4))
386 4 2.67082 2.70300 9
966 4 2.70246 2.70500 8
367 4 2.70387 2.70585 8
1662 4 2.69544 2.70815 9
1776 4 √((9 + √33)/2) 8 #963(x1, x2, x3+x4)
280 4 2.71411 2.71639 10
408 4 2.69951 2.71811 9
301 4 2.71328 2.71856 8
1647 4 1+√3 8 Maj3(x1, x2, x3+x4)
2040 4 1+√3 8 x1 + x2 & (x3 v x4)
510 4 1+√3 8 x1 + (x2 & x3 & x4)
1634 4 2.74013 2.74148 8
856 4 2.73510 2.74171 9
892 4 2.72608 2.74205 9
316 4 2.74228 2.74790 9
862 4 2.74628 2.75157 9
829 4 2.75490 2.76384 9
990 4 2.76066 2.76706 8
1651 4 2.75952 2.76736 8
1715 4 2.76490 2.77389 9
489 4 2.78575 9 2.86182 x2 and x3 are symmetrical
6040 4 2.77499 2.79246 10
1914 4 2.79485 9 2.85539 x3 and x4 are symmetrical
282 4 2.80369 9 2.92535 x2 and x3 are symmetrical
1972 4 2.79678 2.80499 9
893 4 2.79694 2.80607 9
444 4 2.80787 2.81297 10
874 4 2.81477 2.81815 10
107 4 √8 9 x1 & #828(x2, x3, x4)
1632 4 √8 8 (x1 + x2) & (x3 + x4)
22 4 √8 9 x1 & 1-of-3[#828](x2, x3, x4)
6014 4 √8 12 Exact 2-or-3 of 4, Threshold 2 of 4(x1, x2, x3, x4) & !(x1 & x2 & x3 & x4)
854 4 √8 8 (x1 & x2) + (x3 & x4)
6060 4 2.82034 2.83150 10
875 4 2.83428 2.83570 9
2017 4 2.83417 2.83655 10
1712 4 2.84346 2.84354 10
857 4 2.82909 2.85105 9
1718 4 2.84413 2.85900 9
382 4 2.87999 11
362 4 2.88004 2.88205 11
5758 4 2.89586 11
876 4 2.89815 2.90403 10
318 4 2.90163 2.90404 10
407 4 2.89638 2.90417 11
410 4 2.90592 2.91505 10
446 4 2.91254 2.91560 10
1974 4 2.91560 2.91835 10
363 4 2.92040 2.92652 10
1658 4 2.92940 2.93141 10
5774 4 2.92267 2.93717 11
1717 4 2.93360 2.94668 10
1777 4 2.96176 10
982 4 2.96425 2.96696 10
1635 4 2.98641 2.98673 10
6120 4 3 12 x1 + Maj3(x2, x3, x4)
1713 4 2.99622 3.00474 11
1912 4 √(5 + √17) 10 Exact 1 of 3 [#828](x1 v x2, x3, x4)
286 4 √(5 + √17) 10 #828(x1 & x2, x3, x4)
5786 4 3.01265 3.02051 11
1687 4 3.01018 3.02207 11
1681 4 3.02473 3.02629 12
360 4 3.04017 3.04042 12
1659 4 3.04139 3.04288 11
6625 4 3.02185 3.04627 12
5820 4 3.03542 3.04710 11
1725 4 3.04048 3.05100 12
877 4 3.04498 3.05270 11
390 4 3.03755 3.05354 12
872 4 3.06480 3.06823 12
5782 4 3.06111 3.07244 11
5784 4 3.07314 3.07400 12
5742 4 3.09004 3.09058 12
1686 4 3.11060 11 #963(x1+x2, x3, x4)
5804 4 3.11134 3.11717 12
2025 4 3.12714 3.12849 12
6038 4 3.12842 3.12999 12
414 4 3.12805 3.13416 12
5767 4 3.13610 3.13705 13
361 4 3.14864 11
5787 4 3.14761 3.15425 12
105 4 √10 11 x1 & (x2+x3+x4)
278 4 √10 12 Exact 1 of 4, Threshold 3 of 4(x1, x2, x3, x4) & (!x1 v !x2 v !x3 v !x4)
1656 4 3.16284 3.16420 12
6630 4 1+√(3+√3) 12 x1 + #963(x2, x3, x4)
1721 4 3.19509 3.19570 12
1913 4 3.19640 12
5763 4 3.21393 3.21633 13
5771 4 3.21305 3.21888 13
1643 4 3.21930 12
1633 4 3.23607 12 3.33513
1785 4 1+√5 12 x1+#60(x2, x3, x4)
873 4 3.26876 3.27185 12
5785 4 3.27183 3.27189 12
5738 4 3.28207 14
5805 4 3.34542 3.34781 14
5761 4 3.36028 15
406 4 3.36637 3.37384 14
1657 4 3.39009 3.39051 14
5769 4 3.39400 14
7905 4 2+√2 12 x1+x2+(x3 & x4)
5736 4 2√3 16 Exact 2 of 4, Threshold 2 of 4(x1, x2, x3, x4) & Threshold 2 of 4(!x1, !x2, !x3, !x4)
5801 4 3.51041 3.51129 14
5739 4 3.51414 15
1641 4 √(7+√33) 14 Exact 1 of 3 [#828](x1+x2, x3, x4)
5865 4 1+√7 16 x1+#828(x2, x3, x4)
5737 4 3.78478 16 Exact 2-or-4 of 4
27030 4 4 16 Parity4, x1+x2+x3+x4