REVIEW
A note on quantum black-box complexity of almost all Boolean functions
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
classification
quant-phcs.CC
keywords
almostblack-boxbooleanfunctionsquantumboundedcomplexitycompute
read the original abstract
We show that, for almost all N-variable Boolean functions f, at least N/4-O(\sqrt{N} log N) queries are required to compute f in quantum black-box model with bounded error.
Discussion (0). Sign in to comment.