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.

Improve this question
$\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
    Commented Jun 11, 2021 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$
    – Ghost-of-PPPF
    Commented Jun 11, 2021 at 15:17

1 Answer 1

Reset to default
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)}$.

Improve this answer
$\endgroup$

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.