Parameterized Quantum Query Complexity of Graph Collision

Abstract

We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O\left(\sqrt{n}t^{\sfrac{1}{6}}\right)$ queries where $t$ is the treewidth of the graph; \item an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses $O(\sqrt{n}+\sqrt{{\alpha }^{\ast \ast }})$ queries, where ${\alpha }^{\ast \ast }(G)$ is a graph parameter defined by \[α^{**}(G):=\min_{VC\text{-- vertex cover of}G}{\max_{\substack{I\subseteq VC\\I\text{-- independent set}}}{\sum_{v\in I}{°{v}}}};\] \item an algorithm for a subclass of circulant graphs that uses $O(\sqrt{n})$ queries. \end{itemize} We also present an example of a possibly difficult graph $G$ for which all the known graphs fail to solve graph collision in $O(\sqrt{n}{\log }^{c}n)$ queries.

12 pages, 5 figures, submitted to ICALP workshop "Workshop on Quantum and Classical Complexity" in 5/5/2013

References in corpus (4)

• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
• A quantum query algorithm for the graph collision problem
• Square-Difference-Free Sets of Size Omega(n^{0.7334...})