Applications of the quantum algorithm for st-connectivity

DOI10.4230/LIPICS.TQC.2019.6MaRDI QIDQ5089153FDOQ5089153

Authors: Kai Delorenzo, Shelby Kimmel, R. Teal Witter 

Publication date: 18 July 2022

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

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

zbMATH Keywords

algorithmsgraphsquery complexityquantum algorithmsspan programs

Mathematics Subject Classification ID

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

Cites Work

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

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)