The quantum query complexity of certification

zbMATH Open1236.81062MaRDI QIDQ3172424FDOQ3172424

Authors: Andrew M. Childs, François Le Gall, Seiichiro Tani, Andris Ambainis 

Publication date: 5 October 2011

Recommendations

• Quantum certificate complexity
• The quantum query complexity of read-many formulas
• Quantum adversary (upper) bound
• Quantum adversary (upper) bound
• On the power of non-adaptive learning graphs

zbMATH Keywords

quantum query complexityformula evaluationcertificates

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cited In (5)

• Span-Program-Based Quantum Algorithm for Evaluating Unbalanced Formulas
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Quantum certificate complexity
• A strong direct product theorem for quantum query complexity
• The query complexity of certification

This page was built for publication: The quantum query complexity of certification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3172424)