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 $Oleft(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^{**}})$ queries, where $alpha^{**}(G)$ is a graph parameter defined by [alpha^{**}(G):=min_{VCtext{-- vertex cover of}G}{max_{substack{Isubseteq VCItext{-- independent set}}}{sum_{vin I}{deg{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.
Download