Counting martingales based on #P, SpanP, and GapP functions yield new intermediate measures showing BPP and BQP are negligible and that nearly all problems in the third level of the exponential hierarchy have near-maximum circuit size.
Quantum Analog of Shannon's Lower Bound Theorem
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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 of quantum circuits of any fixed size that we allow is uncountably infinite. Our main tool is a classical result in real algebraic geometry bounding the number of realizable sign conditions of any finite set of real polynomials in many variables.
citation-role summary
background 1
citation-polarity summary
fields
cs.CC 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
Counting Martingales for Measure and Dimension in Complexity Classes
Counting martingales based on #P, SpanP, and GapP functions yield new intermediate measures showing BPP and BQP are negligible and that nearly all problems in the third level of the exponential hierarchy have near-maximum circuit size.