Span programs are equivalent to quantum query algorithms

DOI10.1137/100792640MaRDI QIDQ3190697zbMATH OpenOpenAlexFDO

Authors Ben Reichardt

Publication date 18 September 2014

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/100792640

zbMATH Keywords

adversary methodfunction compositionquantum computingquery complexityspan program

Mathematics Subject Classification ID

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

Recommendations

• Approximate span programs
• Approximate span programs
• Reflections for quantum query algorithms
• Span-program-based quantum algorithm for evaluating formulas
• Span programs for functions with constant-sized 1-certificates (extended abstract)

Cited in

(10)

• Quantum query as a state decomposition
• Approximate span programs
• Span programs and quantum algorithms for st-connectivity and claw detection
• Span-program-based quantum algorithm for evaluating formulas
• Approximate span programs
• Span programs and quantum space complexity
• Reflections for quantum query algorithms
• Span programs for functions with constant-sized 1-certificates (extended abstract)
• Span programs and quantum space complexity
• Quantum bounds for 2D-grid and Dyck language

This page was built for publication: Span programs are equivalent to quantum query algorithms

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