Quantum query complexity of minor-closed graph properties

DOI10.4230/LIPICS.STACS.2011.661MaRDI QIDQ3113728zbMATH OpenFDO

Authors Andrew M. Childs, Robin Kothari

Publication date 23 January 2012

Full work available at URL https://arxiv.org/abs/1011.1443, http://subs.emis.de/LIPIcs/frontdoor_09b3.html

zbMATH Keywords

graph minorsgraph propertieslower boundsquantum algorithmsquatum query complexity

Mathematics Subject Classification ID

Graph minors (05C83) Quantum algorithms and complexity in the theory of computing (68Q12)

Recommendations

• Quantum query complexity of minor-closed graph properties
• Automata, Languages and Programming
• Quantum Query Complexity of Some Graph Problems
• Quantum query complexity of constant-sized subgraph containment
• Learning graph based quantum query algorithms for finding constant-size subgraphs

Cited in

(8)

• Key establishment à la Merkle in a quantum world
• Quantum property testing for bounded-degree graphs
• Quantum query complexity of subgraph isomorphism and homomorphism
• Quantum query complexity of minor-closed graph properties
• Learning graph based quantum query algorithms for finding constant-size subgraphs
• Automata, Languages and Programming
• Quantum Query Complexity of Some Graph Problems
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: Quantum query complexity of minor-closed graph properties

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