Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
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. 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.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
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 →
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.
How it works
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. The Classiq library carries this subject under applications · CFD. 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..
Implementation
Unsupported
heat-equation-solver.txt
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.
DEMONSTRATED BY: the Classiq library entry applications/CFD/heat_eq_qsvt
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.
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.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Quantum vs. classical algorithms for solving the heat equation2020 · Noah Linden, Ashley Montanaro, Changpeng Shao
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.