Quantum Analog of Shannon's Lower Bound Theorem

Saugata Basu, Laxmi Parida

Shannon proved that almost all Boolean functions require a circuit of size $\Theta (2^n/n)$. We prove a quantum analog of this classical result. Unlike in the classical case the number o…