Consider Theorem 11 of this paper (S. Aaronson, BQP and the Polynomial Hierarchy), which says:

Any depth $d$ circuit that accepts all $n$ bit strings of Hamming weight $\frac{n}{2} + 1$ and rejects all strings of Hamming weight $\frac{n}{2}$ has size $\exp[\Omega(n^{1/(d-1)})]$.

Is there a matching upper bound to the given lower bound for the same problem?


1 Answer 1


Yes, the bound is essentially tight. The following is a straightforward construction of depth-$d$ Majority circuits of size $$2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}\le2^{n^{1/(d-1)}\log n}=n^{n^{1/(d-1)}}.$$ It works even for nonconstant $d$, up to $d\le\log n$ or so (at which point the bound becomes polynomial in $n$). We will compute more generally the Hamming weight function $h\colon\{0,1\}^n\to\{0,1\}^{\log n}$, with result represented in binary in such a way that the most significant bit gives Majority.

Thinking of $h(x_0,\dots,x_{n-1})$ as $\sum_{i<n}x_i$, we arrange the sum into a depth-$d$ $\lceil n^{1/(d-1)}\rceil$-ary tree (i.e., with $d-1$ layers of inner nodes computing $\lceil n^{1/(d-1)}\rceil$-ary sums, and a bottom layer of leaves attached to the original inputs). The sums computed at each node are functions with $\lceil n^{1/(d-1)}\rceil$ inputs of at most $(1-d^{-1})\log n$ bits each, and at most $\log n$ output bits. Since any function $\{0,1\}^m\to\{0,1\}^k$ has depth-$2$ circuits (CNF or DNF) of size $2^m+k$, we obtain a circuit computing Hamming weight (and Majority) of size $$n^{O(1)}2^{(1-d^{-1})\lceil n^{1/(d-1)}\rceil\log n}=2^{(1-d^{-1})(n^{1/(d-1)}+O(1))\log n}$$ as claimed, of depth $O(d)$.

In order to make the depth exactly $d$, we can use double-rail logic to avoid negations in the depth-$2$ subcircuits (i.e., in parallel with each of the intermediate output nodes, we separately compute its negation), and then express the functions computed on even layers of the tree using CNF, and on odd layers using DNF. This allows us to merge the top gates on each layer (except for the final output) with the bottom gates on the next layer. Thus, we reduce the depth of the resulting circuit from $2(d-1)$ to $(d-2)+2=d$.

Actually, since the question only asks for distinguishing strings of Hamming weight $n/2$ from $n/2+1$, this does not require computing Majority—it can be accomplished with Parity. Then the bound above can be simplified: we only need to compute sums modulo $2$ at each node in the tree, which is a function $\{0,1\}^{n^{1/(d-1)}}\to\{0,1\}$, thus overall the same strategy gives depth-$d$ Parity circuits of size $$n2^{n^{1/(d-1)}},$$ matching even more closely the lower bound. The same argument also gives depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for the $\mathrm{MOD}_k$ functions for any constant $k$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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