REVIEW 1 cited by
Quantum Analog of Shannon's Lower Bound Theorem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 1 Pith paper
-
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-max...
Discussion (0). Continue with ORCID to comment.