Pith. sign in

REVIEW 1 cited by

How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 1206.0717 v2 pith:J2REM3II submitted 2012-06-04 quant-ph

Andris Ambainis (U of Latvia) , Ronald de Wolf (CWI , U of Amsterdam) This is my paper · ORCID
classification quant-ph
keywords quantumboundcomplexitydegreefunctionsqueryachievedapproximate
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Pretty simple bounds on quantum state discrimination

    quant-ph 2019-08 accept novelty 5.0 of 10

    An explicit pretty-good-measurement protocol solves worst-case quantum state discrimination with O(log n) copies for low-fidelity mixed states and with a Gram-matrix-dependent copy count for pure states.

Pith tools