12

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it. Maybe your post will help motivate me to ...


9

Kaveh's answer provides an answer do the question as you have stated it (and this is the usual proof for showing that $\mathsf{TC}^0$ is contained in $\mathsf{NC}^1$). But I was thinking that you might actually have intended to ask a slightly a different question. Namely for an explicit polynomial size monotone formula for majority. Since majority is ...


9

Computing restricted threshold gate ($\sum_i x_i \geq k$) is essentially sorting input bits. If you can sort the bits then it is easy to compare the result to $k$ and compute restricted threshold. On the other hand, assume that we have an circuits to compute restricted threshold. We can do a parallel search to find the number of ones in the input and ...


7

The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in Complexity of Boolean Functions by Ingo Wegener (Theorem 4.1, page 76). The corresponding circuit has linear size. And since the depth is logarithmic it can be turned to a formula of polynomial ...


4

Let $f\colon \{0,1\}^n \to \{0,1\}$, and let $g\colon \{0,1\}^n \to \{0,1\}$ be chosen uniformly. Then $\Pr[f=g] \sim 2^{-n}\mathrm{Bin}(2^n,1/2)$, and so a Chernoff bound shows that $$ \Pr_g[\Pr[f=g] \geq \tfrac{1}{2}+\epsilon] \leq e^{-2\epsilon^2 2^n}. $$ Now suppose that $f$ goes over all $2^{O(n^2s)}$ circuits of size $s$. The probability that one of ...


2

There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$. Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, ...


2

First of all: your definition of $WCS[C_{t,d}]$ does not match the usual one. The common definition asks for a satisfying assignment of Hamming weight exactly $k$, rather than at most $k$, and this can make an important difference. However, regardless of whether you want at most, or exactly, Hamming weight $k$, the weighted circuit-sat problem for constant-...


2

There are two way to see your question : Is unbounded fanout a reasonable approximation for realistic (quantum) circuits ? Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out ? Peter Shor essentially suggested the formulation 1. in his comment above, and I’ll let experimentalists answer ...


Only top voted, non community-wiki answers of a minimum length are eligible