Algorithms · Quantum query algorithm
Property testing of bounded-degree graphs in the adjacency list model
Given only an oracle that, for a vertex of an N-vertex graph of degree d together with an index j in {1, 2, ..., d}, returns that vertex's j-th neighbor or null when the vertex has degree less than d, decide in as few queries as possible whether the graph is bipartite or far from bipartite — far meaning that a constant fraction of the edges would have to be removed to achieve bipartiteness — and, in the same model, whether the graph is an expander or far from being one.
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costÕ(N^(1/3)) quantum complexity, in the Zoo's words, for deciding bipartiteness on an N-vertex bounded-degree graph promised to be either bipartite or far from bipartite, and Õ(N^(1/3)) together with an Ω̃(N^(1/4)) quantum lower bound, the two not meeting, for distinguishing expanders from graphs far from being expanders, against a classical Θ̃(√N); the primary paper states the same upper bound as time O(N^(1/3)) for both problems, its quantum lower bound as Ω(N^(1/4)) and the classical side as an Ω(√N) lower bound holding for both problems, all without tildes. The Zoo adds, from papers outside this record, Θ(√(NM)) quantum query complexity for finding a minimal spanning tree, Θ(N) for deciding connectivity in the undirected case and Θ̃(√(NM)) in the directed case, Θ̃(√(NM)) for computing the lowest weight path from a given source to all other vertices on a weighted graph, and Õ(N√d) running time for st-connectivity, bipartiteness and forest testing using only logarithmically many qubits, where N is the number of vertices, M the number of edges and d the degree.
- Papers1
Given only an oracle that, for a vertex of an N-vertex graph of degree d together with an index j in {1, 2, ..., d}, returns that vertex's j-th neighbor or null when the vertex has degree less than d, decide in as few queries as possible whether the graph is bipartite or far from bipartite — far meaning that a constant fraction of the edges would have to be removed to achieve bipartiteness — and, in the same model, whether the graph is an expander or far from being one. Ambainis, Childs and Liu treat the testing of bipartiteness and of expansion for bounded-degree graphs. Their abstract credits the construction to a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness, and the Zoo likewise names element distinctness as the key quantum algorithmic tool. For expansion testing the paper also proves a quantum query lower bound, obtained by the polynomial method with algebraic techniques and combinatorial analysis that the abstract calls novel and describes as accommodating the graph structure, and it presents that bound as ruling out the possibility of an exponential quantum speedup. The Zoo sets this beside other results in the same adjacency list model — query complexities for a minimal spanning tree, for connectivity in the undirected and directed cases and for the lowest weight path from a given source on a weighted graph, and algorithms for st-connectivity, bipartiteness and forest testing that run in Õ(N√d) time using only logarithmically many qubits — all of which rest on papers outside this record.
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 →
Ambainis, Childs and Liu treat the testing of bipartiteness and of expansion for bounded-degree graphs. Their abstract credits the construction to a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness, and the Zoo likewise names element distinctness as the key quantum algorithmic tool. For expansion testing the paper also proves a quantum query lower bound, obtained by the polynomial method with algebraic techniques and combinatorial analysis that the abstract calls novel and describes as accommodating the graph structure, and it presents that bound as ruling out the possibility of an exponential quantum speedup. The Zoo sets this beside other results in the same adjacency list model — query complexities for a minimal spanning tree, for connectivity in the undirected and directed cases and for the lowest weight path from a given source on a weighted graph, and algorithms for st-connectivity, bipartiteness and forest testing that run in Õ(N√d) time using only logarithmically many qubits — all of which rest on papers outside this record. 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 checked against the primary source yet. Reported cost: Õ(N^(1/3)) quantum complexity, in the Zoo's words, for deciding bipartiteness on an N-vertex bounded-degree graph promised to be either bipartite or far from bipartite, and Õ(N^(1/3)) together with an Ω̃(N^(1/4)) quantum lower bound, the two not meeting, for distinguishing expanders from graphs far from being expanders, against a classical Θ̃(√N); the primary paper states the same upper bound as time O(N^(1/3)) for both problems, its quantum lower bound as Ω(N^(1/4)) and the classical side as an Ω(√N) lower bound holding for both problems, all without tildes. The Zoo adds, from papers outside this record, Θ(√(NM)) quantum query complexity for finding a minimal spanning tree, Θ(N) for deciding connectivity in the undirected case and Θ̃(√(NM)) in the directed case, Θ̃(√(NM)) for computing the lowest weight path from a given source to all other vertices on a weighted graph, and Õ(N√d) running time for st-connectivity, bipartiteness and forest testing using only logarithmically many qubits, where N is the number of vertices, M the number of edges and d the degree..
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 checked against the primary source yet
- Reported cost
- Õ(N^(1/3)) quantum complexity, in the Zoo's words, for deciding bipartiteness on an N-vertex bounded-degree graph promised to be either bipartite or far from bipartite, and Õ(N^(1/3)) together with an Ω̃(N^(1/4)) quantum lower bound, the two not meeting, for distinguishing expanders from graphs far from being expanders, against a classical Θ̃(√N); the primary paper states the same upper bound as time O(N^(1/3)) for both problems, its quantum lower bound as Ω(N^(1/4)) and the classical side as an Ω(√N) lower bound holding for both problems, all without tildes. The Zoo adds, from papers outside this record, Θ(√(NM)) quantum query complexity for finding a minimal spanning tree, Θ(N) for deciding connectivity in the undirected case and Θ̃(√(NM)) in the directed case, Θ̃(√(NM)) for computing the lowest weight path from a given source to all other vertices on a weighted graph, and Õ(N√d) running time for st-connectivity, bipartiteness and forest testing using only logarithmically many qubits, where N is the number of vertices, M the number of edges and d the degree.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:1012.3174, which writes its bounds in plain text without tildes: "We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound", and "For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup." Quantum Algorithm Zoo entry "Graph Properties in the Adjacency List Model", with LaTeX rendered into Unicode and widetilde written as a tilde over the symbol (Õ, Ω̃, Θ̃): "Suppose we are given the promise that G is either bipartite or is far from bipartite in the sense that a constant fraction of the edges would need to be removed to achieve bipartiteness", "the quantum complexity of deciding bipartiteness is Õ(N^(1/3))", "distinguishing expander graphs from graphs that are far from being expanders has quantum complexity Õ(N^(1/3)) and Ω̃(N^(1/4)), whereas the classical complexity is Θ̃(√N)", "finding a minimal spanning tree has quantum query complexity Θ(√(NM)), deciding graph connectivity has quantum query complexity Θ(N) in the undirected case, and Θ̃(√(NM)) in the directed case, and computing the lowest weight path from a given source to all other vertices on a weighted graph has quantum query complexity Θ̃(√(NM))", and "quantum algorithms are given for st-connectivity, deciding bipartiteness, and deciding whether a graph is a forest, which run in Õ(N √d) time and use only logarithmically many qubits". Neither source states a gate count or a constant factor.
- 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: Property testing of bounded-degree graphs in the adjacency list model
PROBLEM: Given only an oracle that, for a vertex of an N-vertex graph of degree d together with an index j in {1, 2, ..., d}, returns that vertex's j-th neighbor or null when the vertex has degree less than d, decide in as few queries as possible whether the graph is bipartite or far from bipartite — far meaning that a constant fraction of the edges would have to be removed to achieve bipartiteness — and, in the same model, whether the graph is an expander or far from being one.
IDEA: Ambainis, Childs and Liu treat the testing of bipartiteness and of expansion for bounded-degree graphs. Their abstract credits the construction to a combination of classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness, and the Zoo likewise names element distinctness as the key quantum algorithmic tool. For expansion testing the paper also proves a quantum query lower bound, obtained by the polynomial method with algebraic techniques and combinatorial analysis that the abstract calls novel and describes as accommodating the graph structure, and it presents that bound as ruling out the possibility of an exponential quantum speedup. The Zoo sets this beside other results in the same adjacency list model — query complexities for a minimal spanning tree, for connectivity in the undirected and directed cases and for the lowest weight path from a given source on a weighted graph, and algorithms for st-connectivity, bipartiteness and forest testing that run in Õ(N√d) time using only logarithmically many qubits — all of which rest on papers outside this record.
REPORTED COST: Õ(N^(1/3)) quantum complexity, in the Zoo's words, for deciding bipartiteness on an N-vertex bounded-degree graph promised to be either bipartite or far from bipartite, and Õ(N^(1/3)) together with an Ω̃(N^(1/4)) quantum lower bound, the two not meeting, for distinguishing expanders from graphs far from being expanders, against a classical Θ̃(√N); the primary paper states the same upper bound as time O(N^(1/3)) for both problems, its quantum lower bound as Ω(N^(1/4)) and the classical side as an Ω(√N) lower bound holding for both problems, all without tildes. The Zoo adds, from papers outside this record, Θ(√(NM)) quantum query complexity for finding a minimal spanning tree, Θ(N) for deciding connectivity in the undirected case and Θ̃(√(NM)) in the directed case, Θ̃(√(NM)) for computing the lowest weight path from a given source to all other vertices on a weighted graph, and Õ(N√d) running time for st-connectivity, bipartiteness and forest testing using only logarithmically many qubits, where N is the number of vertices, M the number of edges and d the degree.
BASIS: abstract of arXiv:1012.3174, which writes its bounds in plain text without tildes: "We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound", and "For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup." Quantum Algorithm Zoo entry "Graph Properties in the Adjacency List Model", with LaTeX rendered into Unicode and widetilde written as a tilde over the symbol (Õ, Ω̃, Θ̃): "Suppose we are given the promise that G is either bipartite or is far from bipartite in the sense that a constant fraction of the edges would need to be removed to achieve bipartiteness", "the quantum complexity of deciding bipartiteness is Õ(N^(1/3))", "distinguishing expander graphs from graphs that are far from being expanders has quantum complexity Õ(N^(1/3)) and Ω̃(N^(1/4)), whereas the classical complexity is Θ̃(√N)", "finding a minimal spanning tree has quantum query complexity Θ(√(NM)), deciding graph connectivity has quantum query complexity Θ(N) in the undirected case, and Θ̃(√(NM)) in the directed case, and computing the lowest weight path from a given source to all other vertices on a weighted graph has quantum query complexity Θ̃(√(NM))", and "quantum algorithms are given for st-connectivity, deciding bipartiteness, and deciding whether a graph is a forest, which run in Õ(N √d) time and use only logarithmically many qubits". Neither source states a gate count or a constant factor.
PRIMARY SOURCE: Andris Ambainis, Andrew M. Childs, Yi-Kai Liu (2010), Quantum property testing for bounded-degree graphs — https://arxiv.org/abs/1012.3174
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
References
- Quantum property testing for bounded-degree graphs
Andris Ambainis, Andrew M. Childs, Yi-Kai Liu · 2010
Primary source for the bipartiteness and expansion figures in this record, and for those only. It gives quantum algorithms for testing bipartiteness and expansion of bounded-degree graphs in time O(N^(1/3)) against an Ω(√N) classical lower bound, proves an Ω(N^(1/4)) quantum query lower bound for testing expansion, and credits the algorithms to classical property testing techniques due to Goldreich and Ron, derandomization, and the quantum algorithm for element distinctness. Consult it for the promise each test assumes, for the degree bound, and for how the polynomial-method lower bound is set up, none of which the abstract spells out.