Algorithms · Quantum query algorithm
Effective resistance of an electrical network
Given oracle access to a weighted graph on N vertices of maximum degree d whose edge weights are conductances, so that an edge of weight w carries resistance 1/w, estimate the effective resistance between a chosen pair of vertices s and t to within a factor of 1 + ε. Wang poses it as ENA-ER: for a network with |V| = N, deg(G) ≤ d, edge conductances normalized to 1 ≤ w_e ≤ c for every edge — equivalently edge resistances in [1/c, 1] — and spectral gap λ2(L_G) ≥ λ > 0, estimate R_eff(s, t) up to multiplicative error ε, succeeding with probability at least 2/3, given a procedure Pv that on input a vertex index and a number k returns the k-th edge incident to that vertex and a procedure Pe that on input an edge index returns that edge's two endpoints and its weight, both of which Wang assumes can be implemented in time poly(log(N)).
Attested & literatureUpdated
- Record typeLiterature reference
- Speedup class (secondary source)Exponential
- Primary source on the speedupStated by the primary source: "In particular, their dependence on N is exponentially better than that of known classical algorithms."
- Reported costWang's abstract states a running time of poly(d, c, log(N), 1/λ, 1/ε) for computing voltages, currents, dissipated powers and effective resistances, where N is the number of vertices, d the maximum unweighted degree, c the ratio of largest to smallest edge resistance, λ the spectral gap of the normalized Laplacian and ε the accuracy; that this is a time bound and not only a query count rests on his assumption that the graph-access procedures can themselves be implemented in time poly(log(N)). For the resistance problem alone the paper gives two counts, both in uses of the two graph-access procedures Pv and Pe and both gate-efficient in its own sense: the linear-systems route is O((c d^2/(λ ε)) · poly log(c d/(λ ε))), and the quantum-walk route is O(min{c^0.5 d^1.5/(ε λ), c d^0.5/(ε λ^1.5)} · poly log(c d/(ε λ))). Wang also proves a lower bound of Ω(1/√λ) queries for any of his four electrical-network problems, and reads it as saying his algorithms are optimal up to polynomial factors. Ito and Jeffery report bounds of a different kind in a different query model: Õ(n √(R_st(G)) / ε^(3/2)) for estimating R_st(G) to relative accuracy ε, and Õ(n √(R_st(G)/µ) / ε) when µ is a lower bound on λ2(G), both in O(log n) space, and both linear rather than logarithmic in n.
- Papers3
A part this method uses, worked through
This page says 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 StudioA part this method uses, worked through
This page says phase estimation
— here is a concrete, runnable instance of it.
Phase estimation of P(3*pi/4)
3 counting qubits estimating the phase of P(3π/4), which is 2π·3/8 exactly: a phase 3-bit QPE can represent exactly.
Where it ends up
- 1011100%
The counting register reads 011 = 3 with probability 1: angle/(2π) = 3/8, recovered exactly.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioGiven oracle access to a weighted graph on N vertices of maximum degree d whose edge weights are conductances, so that an edge of weight w carries resistance 1/w, estimate the effective resistance between a chosen pair of vertices s and t to within a factor of 1 + ε. Wang poses it as ENA-ER: for a network with |V| = N, deg(G) ≤ d, edge conductances normalized to 1 ≤ w_e ≤ c for every edge — equivalently edge resistances in [1/c, 1] — and spectral gap λ2(L_G) ≥ λ > 0, estimate R_eff(s, t) up to multiplicative error ε, succeeding with probability at least 2/3, given a procedure Pv that on input a vertex index and a number k returns the k-th edge incident to that vertex and a procedure Pe that on input an edge index returns that edge's two endpoints and its weight, both of which Wang assumes can be implemented in time poly(log(N)). Wang gives two classes of quantum algorithms for analyzing large sparse electrical networks — networks that might contain exponentially many vertices, but in which each vertex has only a small number of neighbours that can be efficiently found — and reaches the effective resistance as a special case of the dissipated-power problem, because when the external current is the unit current injected at s and extracted at t, the power of the induced flow equals R_eff(s, t). On the current version's own numbering, the first class builds linear systems whose solutions encode the electric potentials and the electric currents and extracts a number from them rather than a state, which is what makes the output an estimate of a physical quantity instead of a state proportional to the solution. The second class instead takes advantage of the graph structure: Wang first establishes a relationship between the kernel of the signed weighted incidence matrix of a network and the electrical flow in that network, then obtains a state encoding that flow by performing a boosted version of phase estimation on the quantum walk corresponding to that matrix, and reads the resistance off it. He reports this walk-based class as beating the first class in computing dissipated powers and effective resistances, though his own side-by-side comparison of the two says that holds unconditionally only for one of the two procedures he gives for implementing the walk operator; with the other, the walk-based one has much better dependence on d but slightly worse dependence on 1/λ. Ito and Jeffery arrive at the same quantity from span programs: they relax the requirement that 1-inputs hit some target exactly, so that any span program deciding a function can also approximate its positive witness size, and the st-connectivity span program of Belovs and Reichardt has positive witness size equal to half the effective resistance, which turns witness-size estimation into resistance estimation. The Zoo attributes one of Wang's two algorithms to the Harrow, Hassidim and Lloyd linear-systems algorithm, which is the route the paper's first version takes; the Zoo numbers neither algorithm, and the paper's own numbering of the two is reversed between its first version and its current one, so no ordinal is safe here.
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 →
Wang gives two classes of quantum algorithms for analyzing large sparse electrical networks — networks that might contain exponentially many vertices, but in which each vertex has only a small number of neighbours that can be efficiently found — and reaches the effective resistance as a special case of the dissipated-power problem, because when the external current is the unit current injected at s and extracted at t, the power of the induced flow equals R_eff(s, t). On the current version's own numbering, the first class builds linear systems whose solutions encode the electric potentials and the electric currents and extracts a number from them rather than a state, which is what makes the output an estimate of a physical quantity instead of a state proportional to the solution. The second class instead takes advantage of the graph structure: Wang first establishes a relationship between the kernel of the signed weighted incidence matrix of a network and the electrical flow in that network, then obtains a state encoding that flow by performing a boosted version of phase estimation on the quantum walk corresponding to that matrix, and reads the resistance off it. He reports this walk-based class as beating the first class in computing dissipated powers and effective resistances, though his own side-by-side comparison of the two says that holds unconditionally only for one of the two procedures he gives for implementing the walk operator; with the other, the walk-based one has much better dependence on d but slightly worse dependence on 1/λ. Ito and Jeffery arrive at the same quantity from span programs: they relax the requirement that 1-inputs hit some target exactly, so that any span program deciding a function can also approximate its positive witness size, and the st-connectivity span program of Belovs and Reichardt has positive witness size equal to half the effective resistance, which turns witness-size estimation into resistance estimation. The Zoo attributes one of Wang's two algorithms to the Harrow, Hassidim and Lloyd linear-systems algorithm, which is the route the paper's first version takes; the Zoo numbers neither algorithm, and the paper's own numbering of the two is reversed between its first version and its current one, so no ordinal is safe here. This record's speedup class, "Exponential", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "In particular, their dependence on N is exponentially better than that of known classical algorithms.". Reported cost: Wang's abstract states a running time of poly(d, c, log(N), 1/λ, 1/ε) for computing voltages, currents, dissipated powers and effective resistances, where N is the number of vertices, d the maximum unweighted degree, c the ratio of largest to smallest edge resistance, λ the spectral gap of the normalized Laplacian and ε the accuracy; that this is a time bound and not only a query count rests on his assumption that the graph-access procedures can themselves be implemented in time poly(log(N)). For the resistance problem alone the paper gives two counts, both in uses of the two graph-access procedures Pv and Pe and both gate-efficient in its own sense: the linear-systems route is O((c d^2/(λ ε)) · poly log(c d/(λ ε))), and the quantum-walk route is O(min{c^0.5 d^1.5/(ε λ), c d^0.5/(ε λ^1.5)} · poly log(c d/(ε λ))). Wang also proves a lower bound of Ω(1/√λ) queries for any of his four electrical-network problems, and reads it as saying his algorithms are optimal up to polynomial factors. Ito and Jeffery report bounds of a different kind in a different query model: Õ(n √(R_st(G)) / ε^(3/2)) for estimating R_st(G) to relative accuracy ε, and Õ(n √(R_st(G)/µ) / ε) when µ is a lower bound on λ2(G), both in O(log n) space, and both linear rather than logarithmic in n..
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)
- Exponential
- Primary source on the speedup
- Stated by the primary source: "In particular, their dependence on N is exponentially better than that of known classical algorithms."
- Reported cost
- Wang's abstract states a running time of poly(d, c, log(N), 1/λ, 1/ε) for computing voltages, currents, dissipated powers and effective resistances, where N is the number of vertices, d the maximum unweighted degree, c the ratio of largest to smallest edge resistance, λ the spectral gap of the normalized Laplacian and ε the accuracy; that this is a time bound and not only a query count rests on his assumption that the graph-access procedures can themselves be implemented in time poly(log(N)). For the resistance problem alone the paper gives two counts, both in uses of the two graph-access procedures Pv and Pe and both gate-efficient in its own sense: the linear-systems route is O((c d^2/(λ ε)) · poly log(c d/(λ ε))), and the quantum-walk route is O(min{c^0.5 d^1.5/(ε λ), c d^0.5/(ε λ^1.5)} · poly log(c d/(ε λ))). Wang also proves a lower bound of Ω(1/√λ) queries for any of his four electrical-network problems, and reads it as saying his algorithms are optimal up to polynomial factors. Ito and Jeffery report bounds of a different kind in a different query model: Õ(n √(R_st(G)) / ε^(3/2)) for estimating R_st(G) to relative accuracy ε, and Õ(n √(R_st(G)/µ) / ε) when µ is a lower bound on λ2(G), both in O(log n) space, and both linear rather than logarithmic in n.
- Speedup class
- Exponential (checked against the record's own primary paper, which states it)
- Complexity basis
- Abstract of arXiv:1311.1851 as arxiv.org/abs/1311.1851 serves it today, which is v10 (LaTeX rendered into Unicode): "These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c, log(N), 1/λ, 1/ε), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and ε is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary." The assumption that turns the query counts below into a time bound is section 2.4 of that version, closing the model description: "We assume that Pv, Pe and Pi are all efficient, in the sense that they can be implemented in time poly(log(N))." The two resistance-specific counts are Corollary 2 of that version, "The ENA-ER problem can be solved by a gate-efficient quantum algorithm that makes O(cd^2/(λε) · poly log(cd/(λε))) uses of Pv and Pe", and Corollary 3, "The ENA-ER problem can be solved by a gate-efficient quantum algorithm that makes O(min{c^0.5 d^1.5/(ελ), cd^0.5/(ελ^1.5)} · poly log(cd/(ελ))) uses of Pv and Pe", each with its bound transcribed out of the display equation the corollary sets it in; the lower bound is the opening of section 5, "we prove that in order to solve any of the ENA-V, ENA-C, ENA-P, ENA-ER problems, one has to make Ω(1/√λ) queries to the graph. This lower bound implies that our algorithms are optimal up to polynomial factors and hence cannot be greatly improved." The adjacency-model figures are the abstract of arXiv:1507.00432 as arxiv.org/abs/1507.00432 serves it (LaTeX rendered into Unicode), which is worded differently from the abstract typeset inside the paper's only version: "we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, R_{s,t}(G), of Õ((1/ε^(3/2)) n √(R_{s,t}(G))), and, when µ is a lower bound on λ2(G), by our phase gap lower bound, we can obtain Õ((1/ε) n √(R_{s,t}(G)/µ)), both using O(log n) space." The same two bounds are Theorem 4.2 and Theorem 4.3 of that version, where they are stated as time complexities with space complexity O(log n). The Zoo states the running time in a third parameterisation, "poly( log n, d, 1/φ, 1/ε), where φ is the expansion of the graph", which is the v1 abstract's "Both of them have running time poly(log n, d, c, 1/φ, 1/ε)" with c dropped.
- 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: Effective resistance of an electrical network
PROBLEM: Given oracle access to a weighted graph on N vertices of maximum degree d whose edge weights are conductances, so that an edge of weight w carries resistance 1/w, estimate the effective resistance between a chosen pair of vertices s and t to within a factor of 1 + ε. Wang poses it as ENA-ER: for a network with |V| = N, deg(G) ≤ d, edge conductances normalized to 1 ≤ w_e ≤ c for every edge — equivalently edge resistances in [1/c, 1] — and spectral gap λ2(L_G) ≥ λ > 0, estimate R_eff(s, t) up to multiplicative error ε, succeeding with probability at least 2/3, given a procedure Pv that on input a vertex index and a number k returns the k-th edge incident to that vertex and a procedure Pe that on input an edge index returns that edge's two endpoints and its weight, both of which Wang assumes can be implemented in time poly(log(N)).
IDEA: Wang gives two classes of quantum algorithms for analyzing large sparse electrical networks — networks that might contain exponentially many vertices, but in which each vertex has only a small number of neighbours that can be efficiently found — and reaches the effective resistance as a special case of the dissipated-power problem, because when the external current is the unit current injected at s and extracted at t, the power of the induced flow equals R_eff(s, t). On the current version's own numbering, the first class builds linear systems whose solutions encode the electric potentials and the electric currents and extracts a number from them rather than a state, which is what makes the output an estimate of a physical quantity instead of a state proportional to the solution. The second class instead takes advantage of the graph structure: Wang first establishes a relationship between the kernel of the signed weighted incidence matrix of a network and the electrical flow in that network, then obtains a state encoding that flow by performing a boosted version of phase estimation on the quantum walk corresponding to that matrix, and reads the resistance off it. He reports this walk-based class as beating the first class in computing dissipated powers and effective resistances, though his own side-by-side comparison of the two says that holds unconditionally only for one of the two procedures he gives for implementing the walk operator; with the other, the walk-based one has much better dependence on d but slightly worse dependence on 1/λ. Ito and Jeffery arrive at the same quantity from span programs: they relax the requirement that 1-inputs hit some target exactly, so that any span program deciding a function can also approximate its positive witness size, and the st-connectivity span program of Belovs and Reichardt has positive witness size equal to half the effective resistance, which turns witness-size estimation into resistance estimation. The Zoo attributes one of Wang's two algorithms to the Harrow, Hassidim and Lloyd linear-systems algorithm, which is the route the paper's first version takes; the Zoo numbers neither algorithm, and the paper's own numbering of the two is reversed between its first version and its current one, so no ordinal is safe here.
REPORTED COST: Wang's abstract states a running time of poly(d, c, log(N), 1/λ, 1/ε) for computing voltages, currents, dissipated powers and effective resistances, where N is the number of vertices, d the maximum unweighted degree, c the ratio of largest to smallest edge resistance, λ the spectral gap of the normalized Laplacian and ε the accuracy; that this is a time bound and not only a query count rests on his assumption that the graph-access procedures can themselves be implemented in time poly(log(N)). For the resistance problem alone the paper gives two counts, both in uses of the two graph-access procedures Pv and Pe and both gate-efficient in its own sense: the linear-systems route is O((c d^2/(λ ε)) · poly log(c d/(λ ε))), and the quantum-walk route is O(min{c^0.5 d^1.5/(ε λ), c d^0.5/(ε λ^1.5)} · poly log(c d/(ε λ))). Wang also proves a lower bound of Ω(1/√λ) queries for any of his four electrical-network problems, and reads it as saying his algorithms are optimal up to polynomial factors. Ito and Jeffery report bounds of a different kind in a different query model: Õ(n √(R_st(G)) / ε^(3/2)) for estimating R_st(G) to relative accuracy ε, and Õ(n √(R_st(G)/µ) / ε) when µ is a lower bound on λ2(G), both in O(log n) space, and both linear rather than logarithmic in n.
BASIS: Abstract of arXiv:1311.1851 as arxiv.org/abs/1311.1851 serves it today, which is v10 (LaTeX rendered into Unicode): "These algorithms compute various electrical quantities, including voltages, currents, dissipated powers and effective resistances, in time poly(d, c, log(N), 1/λ, 1/ε), where N is the number of vertices in the network, d is the maximum unweighted degree of the vertices, c is the ratio of largest to smallest edge resistance, λ is the spectral gap of the normalized Laplacian of the network, and ε is the accuracy. Furthermore, we show that the polynomial dependence on 1/λ is necessary." The assumption that turns the query counts below into a time bound is section 2.4 of that version, closing the model description: "We assume that Pv, Pe and Pi are all efficient, in the sense that they can be implemented in time poly(log(N))." The two resistance-specific counts are Corollary 2 of that version, "The ENA-ER problem can be solved by a gate-efficient quantum algorithm that makes O(cd^2/(λε) · poly log(cd/(λε))) uses of Pv and Pe", and Corollary 3, "The ENA-ER problem can be solved by a gate-efficient quantum algorithm that makes O(min{c^0.5 d^1.5/(ελ), cd^0.5/(ελ^1.5)} · poly log(cd/(ελ))) uses of Pv and Pe", each with its bound transcribed out of the display equation the corollary sets it in; the lower bound is the opening of section 5, "we prove that in order to solve any of the ENA-V, ENA-C, ENA-P, ENA-ER problems, one has to make Ω(1/√λ) queries to the graph. This lower bound implies that our algorithms are optimal up to polynomial factors and hence cannot be greatly improved." The adjacency-model figures are the abstract of arXiv:1507.00432 as arxiv.org/abs/1507.00432 serves it (LaTeX rendered into Unicode), which is worded differently from the abstract typeset inside the paper's only version: "we give the first upper bounds in the adjacency query model on the quantum time complexity of estimating the effective resistance between s and t, R_{s,t}(G), of Õ((1/ε^(3/2)) n √(R_{s,t}(G))), and, when µ is a lower bound on λ2(G), by our phase gap lower bound, we can obtain Õ((1/ε) n √(R_{s,t}(G)/µ)), both using O(log n) space." The same two bounds are Theorem 4.2 and Theorem 4.3 of that version, where they are stated as time complexities with space complexity O(log n). The Zoo states the running time in a third parameterisation, "poly( log n, d, 1/φ, 1/ε), where φ is the expansion of the graph", which is the v1 abstract's "Both of them have running time poly(log n, d, c, 1/φ, 1/ε)" with c dropped.
PRIMARY SOURCE: Guoming Wang (2013), Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks — https://arxiv.org/abs/1311.1851
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
- Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
Guoming Wang · 2013
Primary source, and the only one of the three whose own text states an exponential separation for this row's problem. It proposes two classes of quantum algorithms for analyzing large sparse electrical networks, the first based on solving linear systems and the second on using quantum walks, computes voltages, currents, dissipated powers and effective resistances in time poly(d, c, log(N), 1/λ, 1/ε), and states that their dependence on N is exponentially better than that of known classical algorithms. It also shows that the polynomial dependence on 1/λ is necessary, which it reads as its algorithms being optimal up to polynomial factors. Consult it for the graph-access model, since the time bound rests on the assumption that those procedures run in time poly(log(N)), and for its convention that edge weights are conductances and an edge of weight w has resistance 1/w. Note that the title and the parameterisation both changed across versions: the Zoo cites the first version, titled Quantum algorithms for approximating the effective resistances of electrical networks, whose abstract is stated in terms of the expansion φ of the graph and which uses the Harrow, Hassidim and Lloyd algorithm directly.
- Approximate Span Programs
Tsuyoshi Ito, Stacey Jeffery · 2015
Companion source for the span-program bounds the Zoo cites for this row. It shows how any span program that decides a problem can also be used to approximate the span program witness size, and applies that to effective resistance through the st-connectivity span program of Belovs and Reichardt, whose positive witness size is half of R_st(G). It reports the first upper bounds in the adjacency query model on the quantum time complexity of estimating R_st(G), and states that a linear dependence on n is necessary, so its results cannot be significantly improved. Consult it for the comparison it draws itself between the adjacency and edge-list query models, and for the caveats it lists on estimating a witness size through a linear-systems algorithm instead. Note that the abstract arxiv.org/abs/1507.00432 serves is worded differently from the abstract typeset in the paper itself, though the two bounds are the same.
- Quantum algorithm for solving linear systems of equations
Aram W. Harrow, Avinatan Hassidim, Seth Lloyd · 2008
The linear-systems algorithm the Zoo names as the basis of one of Wang's two algorithms. Given a sparse N by N matrix A with condition number kappa and a vector b, it estimates the expectation value of an operator with respect to the solution of Ax = b in poly(log N, kappa) time, which its abstract calls an exponential improvement over the best classical algorithm; that exponential is about solving linear systems, not about estimating a resistance. The first version of Wang's paper applies it to the Laplacian system whose solution encodes the electric potentials; the current version uses a later linear-system algorithm in its place.