Parameterized Quantum Query Complexity of Graph Collision

Original · EN

We present three new quantum algorithms in the quantum query model for graph-collision problem: itemize an algorithm based on tree decomposition that uses O(√nt16) queries where t is the treewidth of the graph; an algorithm constructed on a span program that improves a result by Gavinsky and Ito. The algorithm uses O(√n+√α**) queries, where α**(G) is a graph parameter defined by α**(G):=-- vertex cover ofGI VC- independent set∑ᵥ∈ ᵢ°v; an algorithm for a subclass of circulant graphs that uses O(√n) queries. 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(√n ᶜ n) queries.