Algorithms · Quantum differential equations · linear
Quantum and classical algorithms for the heat equation
Solve the heat equation in a rectangular region of spatial dimension d, in the sense of approximately computing the amount of heat in a given region.
Attested & literatureUpdated
Open on the mapView frozen graph
- Record typeLiterature reference
- Reference implementationheat_eq_qsvt
- Reported costAn at most quadratic quantum speedup for spatial dimension d ≥ 2, from an approach that applies amplitude estimation to an accelerated classical random walk; the alternative approach, based on a quantum algorithm for linear equations, is never faster than the best classical algorithms. The abstract states the comparison only in those terms: it quotes no complexity expression, no dependence on the error or the discretization, and no qubit or gate count, and the complexities of the ten algorithms it compares are given inside the paper.
- Papers1
A part this method uses, worked through
This page says amplitude estimation
— here is a concrete, runnable instance of it.
Canonical amplitude estimation
3 counting qubits estimating a = sin²(θ) for the one-qubit state A|0⟩ = RY(π/4)|0⟩, θ = π/8.
Where it ends up
- 000125%
- 011125%
- 100125%
- 111125%
The counting register reads 001 or 111, each equally likely: these are θ/π = 1/8 and its mirror 1 − 1/8 = 7/8, both exact in 3 bits by construction. Either one gives a = sin²(π/8) = (2 − √2) / 4 exactly, the standard amplitude-estimation formula a = sin²(πλ) applied to the smaller of the two readings.
Open this part in StudioSolve the heat equation in a rectangular region of spatial dimension d, in the sense of approximately computing the amount of heat in a given region. Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially, and this paper puts that prediction against a prototypical PDE: the heat equation in a rectangular region, with the answer taken to be the amount of heat in a given region, computed approximately. It compares in detail the complexities of ten classical and quantum algorithms for that task. The quantum route the abstract reports on applies amplitude estimation to an accelerated classical random walk, and for spatial dimension d ≥ 2 the paper finds that route gives an at most quadratic quantum speedup. An alternative route, built on a quantum algorithm for linear equations, is on the paper's accounting never faster than the best classical algorithms. The abstract reports only those two findings; the complexities of the ten algorithms it compares are inside the paper.
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 →
Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially, and this paper puts that prediction against a prototypical PDE: the heat equation in a rectangular region, with the answer taken to be the amount of heat in a given region, computed approximately. It compares in detail the complexities of ten classical and quantum algorithms for that task. The quantum route the abstract reports on applies amplitude estimation to an accelerated classical random walk, and for spatial dimension d ≥ 2 the paper finds that route gives an at most quadratic quantum speedup. An alternative route, built on a quantum algorithm for linear equations, is on the paper's accounting never faster than the best classical algorithms. The abstract reports only those two findings; the complexities of the ten algorithms it compares are inside the paper. Reported cost: An at most quadratic quantum speedup for spatial dimension d ≥ 2, from an approach that applies amplitude estimation to an accelerated classical random walk; the alternative approach, based on a quantum algorithm for linear equations, is never faster than the best classical algorithms. The abstract states the comparison only in those terms: it quotes no complexity expression, no dependence on the error or the discretization, and no qubit or gate count, and the complexities of the ten algorithms it compares are given inside the paper..
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
- Reference implementation
- heat_eq_qsvt
- Reported cost
- An at most quadratic quantum speedup for spatial dimension d ≥ 2, from an approach that applies amplitude estimation to an accelerated classical random walk; the alternative approach, based on a quantum algorithm for linear equations, is never faster than the best classical algorithms. The abstract states the comparison only in those terms: it quotes no complexity expression, no dependence on the error or the discretization, and no qubit or gate count, and the complexities of the ten algorithms it compares are given inside the paper.
- Complexity basis
- abstract of arXiv:2004.06516 (TeX rendered into Unicode: the abstract writes the inequality in inline math mode, here written d ≥ 2): "We find that, for spatial dimension d ≥ 2, there is an at most quadratic quantum speedup using an approach based on applying amplitude estimation to an accelerated classical random walk. However, an alternative approach based on a quantum algorithm for linear equations is never faster than the best classical algorithms." The same abstract fixes the task — "approximately computing the amount of heat in a given region" — and says the paper compares "the complexities of ten classical and quantum algorithms for solving it". It carries no big-O expression, no constant, and no resource count, which is why none appears above.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum differential equations · linear 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: Quantum and classical algorithms for the heat equation
PROBLEM: Solve the heat equation in a rectangular region of spatial dimension d, in the sense of approximately computing the amount of heat in a given region.
IDEA: Quantum computers are predicted to outperform classical ones for solving partial differential equations, perhaps exponentially, and this paper puts that prediction against a prototypical PDE: the heat equation in a rectangular region, with the answer taken to be the amount of heat in a given region, computed approximately. It compares in detail the complexities of ten classical and quantum algorithms for that task. The quantum route the abstract reports on applies amplitude estimation to an accelerated classical random walk, and for spatial dimension d ≥ 2 the paper finds that route gives an at most quadratic quantum speedup. An alternative route, built on a quantum algorithm for linear equations, is on the paper's accounting never faster than the best classical algorithms. The abstract reports only those two findings; the complexities of the ten algorithms it compares are inside the paper.
REPORTED COST: An at most quadratic quantum speedup for spatial dimension d ≥ 2, from an approach that applies amplitude estimation to an accelerated classical random walk; the alternative approach, based on a quantum algorithm for linear equations, is never faster than the best classical algorithms. The abstract states the comparison only in those terms: it quotes no complexity expression, no dependence on the error or the discretization, and no qubit or gate count, and the complexities of the ten algorithms it compares are given inside the paper.
BASIS: abstract of arXiv:2004.06516 (TeX rendered into Unicode: the abstract writes the inequality in inline math mode, here written d ≥ 2): "We find that, for spatial dimension d ≥ 2, there is an at most quadratic quantum speedup using an approach based on applying amplitude estimation to an accelerated classical random walk. However, an alternative approach based on a quantum algorithm for linear equations is never faster than the best classical algorithms." The same abstract fixes the task — "approximately computing the amount of heat in a given region" — and says the paper compares "the complexities of ten classical and quantum algorithms for solving it". It carries no big-O expression, no constant, and no resource count, which is why none appears above.
PRIMARY SOURCE: Noah Linden, Ashley Montanaro, Changpeng Shao (2020), Quantum vs. classical algorithms for solving the heat equation — https://arxiv.org/abs/2004.06516
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.
Where this sits
This record is named by the layer graph at:
- Forward-time, centre-space (FTCS) Method
Takes A linear PDE with its conditions, a grid over every continuous variable the problem carries, and — where the problem is posed as a boundary-value problem rather than an initial-value one — the boundary treatment that makes the resulting matrix well posed. Returns One matrix and one right-hand side over all the grid unknowns together, with the condition number that the cost of solving it will be measured against, and the discretization error that fixes how fine the grid had to be.
Related entries
- Quantum amplitude estimation
Algorithms
- HHL linear-systems reference
Algorithms
- Quantum algorithms for linear differential equations
Algorithms
- Quantum singular value transformation
Algorithms
References
- Quantum vs. classical algorithms for solving the heat equation
Noah Linden, Ashley Montanaro, Changpeng Shao · 2020
Primary source: the detailed comparison of ten classical and quantum algorithms for the heat equation in a rectangular region, and the origin of both findings quoted here — the at most quadratic speedup for d ≥ 2 from amplitude estimation applied to an accelerated classical random walk, and the finding that the linear-equations route is never faster than the best classical algorithms. Consult it for the complexities themselves, for the assumptions they rest on, and for the other algorithms in the comparison; the abstract states none of that.