Approximate span programs

DOI10.1007/s00453-018-0527-1zbMath1421.68051OpenAlexW2963603598WikidataQ128932636 ScholiaQ128932636MaRDI QIDQ2414858

Tsuyoshi Ito, Stacey Jeffery

Publication date: 17 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/28130

zbMATH Keywords

quantum algorithmseffective resistancequantum query complexityspan programs

Mathematics Subject Classification ID

Related Items (2)

Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The electrical resistance of a graph captures its commute and cover times
• Span Programs and Quantum Algorithms for st-Connectivity and Claw Detection
• Span-program-based quantum algorithm for evaluating formulas
• Quantum algorithms revisited
• Strengths and Weaknesses of Quantum Computing
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Time-Efficient Quantum Walks for 3-Distinctness
• Span programs for functions with constant-sized 1-certificates
• Quantum lower bounds by polynomials
• Quantum Query Complexity of State Conversion

This page was built for publication: Approximate span programs