1
$\begingroup$

What is the counting argument for the following statement (classical)?

"A random function on n bits requires $e^{\Omega(n)}$ elementary operations."

It appears in the introduction of PRL 116, 170502 (2016): Efficient Quantum Pseudorandomness.

Is it that since there are infinitely many n-bit boolean functions, implementing one such randomly chosen function using elementary operations would require an exponentially large number? (I'm assuming that elementary operations here mean two-bit universal gates.)

Also, why $\Omega(n)$ and not $O(n)$?

Thanks in advance.

$\endgroup$
2
  • 1
    $\begingroup$ $\Omega(n)$ generally means lower bound, while $O(n)$ means upper bound, does that answer your question? Also, there are $2^n$ boolean functions, not an infinite number. $\endgroup$
    – Condo
    Jun 11 at 13:52
  • 1
    $\begingroup$ Yes, that makes sense. I somehow missed the Boolean part. So, $2^n=e^{ln 2^n} \approx e^{\Omega(n)}$. Thanks! $\endgroup$ Jun 11 at 15:17
1
$\begingroup$

We say that a function $f(n)$ is $O(n)$ if its bounded above by $n$ asymptotically, which is not to be confused with a function $f(n)$ being $\Omega(n)$ which means that $f(n)$ is bounded below by $n$ asymptotically.

Also, there are $2^n$ boolean functions on $\{0,1\}^n$ since each boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is in one-to-one correspondence with a subset $S$ of $\{1,2,\ldots,n\}$ via the identification $f^{-1}(1)=S$.

So like you said in the comments $2^n=e^{\Omega(n)}$.

$\endgroup$

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.