Pith. sign in

REVIEW

The quantum query complexity of certification

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 0903.1291 v2 pith:DPF6CKKC submitted 2009-03-06 quant-ph cs.CC

Andris Ambainis , Andrew M. Childs , François Le Gall , Seiichiro Tani This is my paper
classification quant-phcs.CC
keywords complexityquantumquerycertificateslogarithmicthetaadversarybalanced
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced NAND formula. Up to logarithmic factors, we show that the query complexity is Theta(d^{(k+1)/2}) for 0-certificates, and Theta(d^{k/2}) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is O(d^{(k+1)/2}) (again neglecting a logarithmic factor). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

Discussion (0). Sign in to comment.

Pith tools