Graph collision on a known graph

ALGORITHM: Graph collision on a known graph
PROBLEM: We are given an undirected graph G on n vertices, known explicitly in advance, together with oracle access to a labeling of the vertices by 1 and 0; the graph collision problem is to decide, by querying that labeling, whether there exist a pair of vertices, connected by an edge, both of which are labeled 1. Only the labeling is queried and never the graph, which is why Magniez, Santha and Szegedy can restate the task as deciding whether the set of vertices of value 1 forms an independent set in G. It is not either of the two problems it is easily confused with: collision finding asks for two arguments of a two-to-one function that share a value, and element distinctness drops that promise and asks whether any two of N items are equal. Those two share a single other Zoo entry, Collision Finding and Element Distinctness, and a single record here, element-distinctness; neither of them has a graph or an edge relation in it.
IDEA: Magniez, Santha and Szegedy introduced graph collision as a subproblem of triangle finding, as Jeffery, Kothari and Magniez record in section 3.1 of their own paper, and solved it inside the dynamic quantum query framework built in the same paper by generalizing Ambainis's quantum walk for element distinctness. The framework walks over the r-element subsets U of the vertex set, carrying with each subset a database D(U) of the pairs (v, f(v)) for the labels already queried; setting a subset up costs r queries, moving one element in or out costs one, and checking whether U already contains a collision costs no query at all, because the stored labels exhibit it. Theorem 3 takes r = n^(2/3) and gets Õ(n^(2/3)) queries on an arbitrary graph. The tilde comes from Corollary 2, the form of the framework that drops the promise of at most one collision: the paper obtains it by a random reduction using a logarithmic number of randomly chosen relations, and says that hence an additional logarithmic factor appears in the complexity. That general bound has not moved since, so the later papers in this row sharpen it by parameterizing the graph rather than by improving the worst case, and their bounds hold on every graph — Belovs notes that his own collapses to the general O(n^(2/3)) once the parameter is as large as it can be. Jeffery, Kothari and Magniez, who need graph collision as the inner problem of Boolean matrix multiplication, use no quantum walk: their instances are bipartite and close to complete, so they search one side for a marked vertex, read the values of the vertices remaining on that side, and search its neighbours on the other side. Belovs derives a bound in the independence number as a warm-up for the modified learning-graph method he builds for k-distinctness. Gavinsky and Ito put an approximate count of degrees in front of a span program and parameterize by the maximum total degree of the vertices in an independent set, which also gives a near-optimal bound on random graphs; Ambainis, Balodis, Iraids, Ozols and Smotrovs add a tree-decomposition algorithm in the treewidth, a span-program algorithm improving the Gavinsky-Ito parameter, and an algorithm for a subclass of circulant graphs. The Zoo records the observation that fixes the lower end: a star graph with its centre labeled 1 and its leaves labeled by the database entries embeds Grover's unstructured search, so graph collision is at least as hard as search.
REPORTED COST: Õ(n^(2/3)) quantum queries on an arbitrary n-vertex graph, which is Theorem 3 of Magniez, Santha and Szegedy and which the Zoo reports without the tilde as O(N^(2/3)) and calls the best upper bound on quantum query complexity known for this problem on general graphs; against that, the Zoo gives quantum query complexity Ω(√n) and classical query complexity Θ(n), both from embedding Grover's unstructured search in a star graph. The sharper bounds are parameterized rather than restricted to a class of graphs: each holds on every graph and degrades to the general bound as its parameter grows. They are O(√n α^(1/6)) in the independence number α (Belovs, Theorem 7); O(√n + √(α*(G))) where α*(G) is the maximum total degree of the vertices in an independent set of G (Gavinsky and Ito, Theorem 1), with O(√(n log n)) queries on most graphs when every edge is present independently with a fixed probability; and O(√n t^(1/6)) in the treewidth t together with O(√n + √(α**(G))) where α**(G) is the smallest, over the vertex covers of G, of the largest total degree of an independent subset of that cover (Ambainis, Balodis, Iraids, Ozols and Smotrovs, Theorems 1 and 4). Only two of the bounds are genuinely restricted to a class: Õ(√n + √m) for a balanced bipartite graph on 2n vertices, where m counts the pairs of the two sides that are not edges, with Õ(√(nλ) + √m) for finding all λ collisions rather than deciding that one exists (Jeffery, Kothari and Magniez, Theorem 3.1), and O(√n) for a subclass of circulant graphs (Ambainis, Balodis, Iraids, Ozols and Smotrovs, Theorem 5).
BASIS: section 4.2 of arXiv:quant-ph/0310134, Theorem 3: "Graph Collision(G) can be solved with positive constant probability in quantum query complexity Õ(n^(2/3))", with its proof "We solve Unique Graph Collision(G) using Corollary 2, with S = [n] and r = n^(2/3)" and "Observe that s(r) = r, u(r) = 1 and c(r) = 0", and the paragraph before Corollary 2 for the tilde: "The reduction goes in the standard way using a logarithmic number of randomly chosen relations R, and hence an additional logarithmic factor appears in the complexity"; Quantum Algorithm Zoo entry "Graph Collision": "One can embed Grover's unstructured search problem as an instance of graph collision by choosing the star graph, labeling the center 1, and labeling the remaining vertices by the database entries. Hence, this problem has quantum query complexity Ω(√n) and classical query complexity Θ(n)" and "In [70], Magniez, Nayak, and Szegedy gave a O(N^(2/3))-query quantum algorithm for graph collision on general graphs. This remains the best upper bound on quantum query complexity for this problem on general graphs" — the Zoo's prose names Nayak, while its own bibliography entry 70 and the arXiv abs page both give Santha; Theorem 3.1 of arXiv:1112.5855: "For all λ ≥ 1, GC_all(n, m, λ) ∈ Õ(√(nλ) + √m) and GC(n, m) ∈ Õ(√n + √m)", whose graph is fixed in section 3.1 as "Let G = (A, B, E) be a balanced bipartite graph on 2n vertices" and whose m is fixed in section 3.3 as "the query complexity of finding a graph collision in some graph with m non-edges, which we denote GC(n, m)"; Theorem 7 of arXiv:1205.1534: "Graph collision on graph G can be solved in O(√n α^(1/6)) quantum queries with bounded error, where α = α(G) is the independence number of G", with the same section's "In the general case, α(G) = O(n), and the complexity of the algorithm is O(n^(2/3)) that coincides with the complexity of the algorithm for a general graph"; Theorem 1 of arXiv:1204.1527: "For a graph G on n vertices, the quantum query complexity of the graph collision problem on G is O(√n + √(α*(G))), where α*(G) is the maximum total degree of the vertices in an independent set of G", with its abstract "if G is a random graph where every edge is present with a fixed probability independently of other edges, then our algorithm requires O(sqrt(n log n)) queries on most graphs"; and arXiv:1305.1021, Theorem 1: "Graph collision on graph G on n vertices can be solved with a bounded error quantum algorithm with O(√n t^(1/6)) queries where t is the treewidth of the graph", Theorem 4: "Q(COL(G)) = O(√(|V(G)|) + √(α**(G)))", and Theorem 5: "For graphs CI(n, a, b): Q(COL(CI(n, a, b))) = O(√n)".
PRIMARY SOURCE: Frederic Magniez, Miklos Santha, Mario Szegedy (2003), Quantum Algorithms for the Triangle Problem — https://arxiv.org/abs/quant-ph/0310134

This is a literature reference record, not an executable circuit.