Span-program-based quantum algorithm for evaluating formulas

DOI10.4086/toc.2012.v008a013zbMath1279.68097arXiv0710.2630OpenAlexW2404437241MaRDI QIDQ2913813

Ben W. Reichardt, Robert Špalek

Publication date: 27 September 2012

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0710.2630

zbMATH Keywords

quantum computationquery complexityspan programsformula evaluation

Mathematics Subject Classification ID

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

Related Items

Approximate span programs, On the relationship between continuous- and discrete-time quantum walk, Unnamed Item, Quantum algorithm design: techniques and applications, Unnamed Item, Superlinear Advantage for Exact Quantum Algorithms, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, Quantum algorithms for learning symmetric juntas via the adversary bound

Cites Work

• Size-depth tradeoffs for Boolean formulae
• Superpolynomial lower bounds for monotone span programs
• Unnamed Item