CJTCS Volume 2012 Article 10

Volume 2012

Article 10

Published by the Department of Computer Science, The University of Chicago.

Learning graph based quantum query algorithms for finding constant-size subgraphs

Troy Lee
Centre for Quantum Technologies
National University of Singapore
Singapore

Frédéric Magniez
CNRS, LIAFA
Université Paris Diderot, Sorbonne Paris Cité
Paris
France

and

Miklos Santha
CNRS, LIAFA
Université Paris Diderot, Sorbonne Paris Cité
Paris
France

December 21st, 2012

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 {A, B} > 0 with
A = [ k^2 -2(m+1)] / [k(k+1)(m+1)]
and
B = [2k -d -3]/[k(d+1)(m-d+2)]

The previous best algorithm of Magniez et al. had complexity Õ(n^[2 - 2/k]).