Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates
arXiv:1109.4165 · doi:10.1142/S0219749912500190
Abstract
We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether an -vertex graph contains a triangle, clique or star of some size. For a general subgraph with vertices, we show that containment can be solved with quantum query complexity , with a strictly positive function of . This is better than $ \tilde{O}\s{n^{2-2/k}} $ by Magniez et al. These results are obtained in the learning graph model of Belovs.
arXiv comment14 pages, 1 figure, published under title:"Quantum Query Complexity of Constant-sized Subgraph Containment"
References in corpus (5)
Cited by in corpus (5)
- Nested Quantum Walks with Quantum Data Structures
- A learning graph based quantum query algorithm for finding constant-size subgraphs
- Applications of the Adversary Method in Quantum Query Algorithms
- Span-program-based quantum algorithm for tree detection
- Quantum Algorithms for Finding Constant-sized Sub-hypergraphs