How can one show that there exist Boolean functions on $n$ inputs which require at least $2^n/\log{n}$ logic gates to compute?

This problem was originally stated in Exercise 3.16 of Nielsen & Chuang's Quantum Computation and Quantum Information.


1 Answer 1


There are only so many circuits using at most $m$ gates, say $f(m)$. If all Boolean functions on $n$ inputs could be computed using at most $m$ gates, then $f(m) \geq 2^{2^n}$, since there are $2^{2^n}$ Boolean functions on $n$ inputs. Hence if $f(m) < 2^{2^n}$ then there must be a function on $n$ inputs which cannot be computed using at most $m$ gates.

A Boolean circuit with $m$ unbounded fan-in gates can be simulated using at most $m^2$ binary gates. We can describe each binary gate by satisfying its inputs and its type (AND, OR, NOT), for a total of $O(m^4)$ possibilities per gate. This leads to a rough bound $f(m) = O(m)^{4m}$. If $m = C 2^n/n$ then $$ f(m) = \exp O(m\log m) = \exp O(C 2^n), $$ and so for an appropriate choice of $C$, we would get $f(m) < 2^{2^n}$. This shows that there are some Boolean functions which require at least $C 2^n/n$ gates to compute. It turns out that (up to the choice of $C$) this bound is tight. (So what you wrote in your post is actually wrong.)

  • 1
    $\begingroup$ As I'm sure you have already guessed, the question came from an exercise in a textbook, so that must be a typo/error. Thank you for clarifying this. $\endgroup$ Commented Oct 10, 2017 at 9:01
  • 1
    $\begingroup$ Shouldn't it be $f(m)=O(m)^{2m^4}$? (Instead of $f(m)=O(m)^{4m}$) Reason: We have at most $m^2$ binary gates, each can be described $O(m^4)$ different ways so: $\left(m^2\right)^{m^4}=m^{2m^4}$ $\endgroup$
    – Attila Kun
    Commented Sep 28, 2020 at 17:43
  • 1
    $\begingroup$ Possibly, though it makes little difference here (unless you care about constants). $\endgroup$ Commented Sep 28, 2020 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.