Applications of the quantum algorithm for st-connectivity

DOI10.4230/LIPICS.TQC.2019.6MaRDI QIDQ5089153zbMATH OpenFDO

Authors Kai Delorenzo, Shelby Kimmel, R. Teal Witter

Publication date 18 July 2022

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

zbMATH Keywords

algorithmsgraphsquery complexityquantum algorithmsspan programs

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94)

Recommendations

• Span programs and quantum algorithms for \(st\)-connectivity and claw detection
• Quantum algorithms for connectivity and related problems
• Automata, Languages and Programming
• Quantum Query Complexity of Some Graph Problems
• Quantum algorithms for the triangle problem

Cites work

• scientific article; zbMATH DE number 1263189 (Why is no real title available?)
• scientific article; zbMATH DE number 7378719 (Why is no real title available?)
• A Complexity Measure
• A compendium of problems complete for symmetric logarithmic space
• Algebraic Potential Theory on Graphs
• Finding Even Cycles Even Faster
• On the power of Ambainis lower bounds
• Quantum query complexity of minor-closed graph properties
• Reflections for quantum query algorithms
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Span programs and quantum algorithms for \(st\)-connectivity and claw detection
• Span programs for functions with constant-sized 1-certificates (extended abstract)

Cited in

(1)

• Quantum Algorithms for Matching and Network Flows

This page was built for publication: Applications of the quantum algorithm for st-connectivity

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