A learning graph based quantum query algorithm for finding constant-size subgraphs

Abstract

Let $H$ be a fixed $k$-vertex graph with $m$ edges and minimum degree $d>0$. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an $n$-vertex graph contains $H$ as a subgraph is $O(n^{2-2/k-t})$, where $t=\max \frac{k^2-2(m+1)}{k(k+1)(m+1)},\frac{2k-d-3}{k(d+1)(m-d+2)}$. The previous best algorithm of Magniez et al. had complexity $\tilde{O}(n^{2-2/k})$.

The analysis has been refined and a second algorithm included

References in corpus (3)

• Quantum query complexity of state conversion
• Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
• Quantum Query Complexity of Subgraph Containment with Constant-sized Certificates

Cited by in corpus (4)

• Nested Quantum Walks with Quantum Data Structures
• Applications of the Adversary Method in Quantum Query Algorithms
• Quantum Algorithms for Finding Constant-sized Sub-hypergraphs
• Quantum Query Complexity of Subgraph Isomorphism and Homomorphism