Algorithms · Quantum query algorithm
Graph collision on a known graph
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.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot stated by the primary source — the abstract of arXiv:quant-ph/0310134 and its section 4.2 (Graph Collision Problem), where Theorem 3 and its proof state the graph collision bound. The abstract reports only the triangle bounds Õ(n^(10/7)) and Õ(n^(13/10)) and does not mention graph collision at all; neither it nor section 4.2 states a classical query cost for graph collision, and neither compares the Õ(n^(2/3)) bound against one. The word classical occurs six times in the body of the paper and twice more in its bibliography, never in section 4.2; the nearest it comes to this problem is the remark opening section 4.1 that the algorithm of Ambainis is somewhat similar to the brand of classical algorithms, where a database is used, which states no cost. was read and makes no such claim
- 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).
- Papers5
A part this method uses, worked through
This page says Ambainis's quantum walk
— here is a concrete, runnable instance of it.
A discrete-time quantum walk on a 4-cycle
One coin qubit, two position qubits (4 positions on a cycle), 3 steps starting at position 0.
Where it ends up
- 11050%
- 11150%
The position always reads 3, for either value of the coin: constructive interference on this small cycle concentrates the walk onto a single position after exactly 3 steps.
Open this part in StudioWe 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. 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.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
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. This record's speedup class, "Polynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Not stated by the primary source — the abstract of arXiv:quant-ph/0310134 and its section 4.2 (Graph Collision Problem), where Theorem 3 and its proof state the graph collision bound. The abstract reports only the triangle bounds Õ(n^(10/7)) and Õ(n^(13/10)) and does not mention graph collision at all; neither it nor section 4.2 states a classical query cost for graph collision, and neither compares the Õ(n^(2/3)) bound against one. The word classical occurs six times in the body of the paper and twice more in its bibliography, never in section 4.2; the nearest it comes to this problem is the remark opening section 4.1 that the algorithm of Ambainis is somewhat similar to the brand of classical algorithms, where a database is used, which states no cost. was read and makes no such claim. 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)..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not stated by the primary source — the abstract of arXiv:quant-ph/0310134 and its section 4.2 (Graph Collision Problem), where Theorem 3 and its proof state the graph collision bound. The abstract reports only the triangle bounds Õ(n^(10/7)) and Õ(n^(13/10)) and does not mention graph collision at all; neither it nor section 4.2 states a classical query cost for graph collision, and neither compares the Õ(n^(2/3)) bound against one. The word classical occurs six times in the body of the paper and twice more in its bibliography, never in section 4.2; the nearest it comes to this problem is the remark opening section 4.1 that the algorithm of Ambainis is somewhat similar to the brand of classical algorithms, where a database is used, which states no cost. was read and makes no such claim
- 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).
- Speedup class
- Polynomial (checked against the record's own primary paper, which does not state it)
- Complexity 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)".
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum query algorithm with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
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.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Element distinctness by quantum walk
Algorithms
- Grover unstructured search
Algorithms
- Subset finding by quantum walk
Algorithms
- Matrix products over semirings
Algorithms
References
- Quantum Algorithms for the Triangle Problem
Frederic Magniez, Miklos Santha, Mario Szegedy · 2003
Primary reference for graph collision on a known graph; the source of this record's cost claim.
- Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
Stacey Jeffery, Robin Kothari, Frédéric Magniez · 2011
Sharpens the bound by counting non-edges, and does it without a quantum walk. The authors reduce Boolean matrix multiplication to instances of graph collision and note that those instances have at most as many non-edges as there are 1s in the output matrix, the quantity their abstract writes as the number of 1s in the output and their section 3.3 calls an upper bound on the non-edge count m. They say outright that they do not use the graph collision algorithm the triangle-finding line depends on: their algorithm does not have any quantum walks. Theorem 3.1 gives Õ(√n + √m) for deciding and Õ(√(nλ) + √m) for finding all λ collisions, which is the form the matrix-multiplication application needs. Consult it for the model in section 3.1, a balanced bipartite graph on 2n vertices, which is narrower than graph collision as the Zoo states it, and for the same section's remark that the best known lower bound is Ω(√n) and closing the gap is an important open problem — the same section that records Magniez, Santha and Szegedy as the origin of the problem.
- Learning-Graph-Based Quantum Algorithm for k-distinctness
Aleksandrs Belovs · 2012
Sharpens the bound in the independence number. The paper's subject is a k-distinctness algorithm built on a modified learning graph approach, and its section 4, headed as a warm-up for that algorithm, proves in Theorem 7 that graph collision on a graph G can be solved in O(√n α^(1/6)) quantum queries with bounded error, where α is the independence number of G — the parameter the Zoo describes as the size of the largest independent set. The theorem carries no condition the abstract omits. The same section fixes how the bound should be read: it interpolates between the complete graph, where α = 1 and two Grover searches suffice, and the general case, where α = O(n) and the bound coincides with the general O(n^(2/3)). Consult it for the learning-graph construction the bound rests on, and note that graph collision is a preparatory result there rather than the subject.
- A quantum query algorithm for the graph collision problem
Dmitry Gavinsky, Tsuyoshi Ito · 2012
The one paper in this row whose subject is graph collision itself. Its Theorem 1 parameterizes by α*(G), the maximum total degree of the vertices in an independent set of G, for a query complexity of O(√n + √(α*(G))) on any graph on n vertices, reached by an approximate count of degrees followed by a span program. The abstract adds that if G is a random graph where every edge is present with a fixed probability independently of other edges then the algorithm requires O(sqrt(n log n)) queries on most graphs, which the authors call optimal up to the sqrt(log n) factor on most graphs; Corollary 2 is the quantitative form of that statement. Consult it for the sense in which the random-graph bound holds, since it quantifies over most graphs rather than over a worst case, and for its related-work section, which restates the Jeffery-Kothari-Magniez m as the number of missing edges compared to the complete bipartite graph.
- Parameterized Quantum Query Complexity of Graph Collision
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Raitis Ozols, Juris Smotrovs · 2013
Three further upper bounds, and the summary the Zoo points readers to. Theorem 1 gives a tree-decomposition algorithm using O(√n t^(1/6)) queries in the treewidth t, Theorem 4 a span-program algorithm using O(√n + √(α**(G))) queries that improves the Gavinsky-Ito result, with α**(G) the minimum over vertex covers of G of the maximum, over independent subsets of that cover, of the sum of the degrees, and Theorem 5 an algorithm for the circulant graphs CI(n, a, b) using O(√n) queries. None of the three carries a condition its abstract omits. Section 5 then gives what the authors call, possibly, the first example of an explicit graph for which none of the existing quantum algorithms finds graph collision with substantially less than O(n^(2/3)) queries; the abstract states the same example against the weaker threshold O(√n log^c n) and, in the authors' own wording, says that all the known graphs fail — evidently a slip for all the known algorithms. Consult it for that graph and for the two additional classes the Zoo declines to describe.