Algorithms · Quantum differential equations · linear
Fail-safe quantum algorithm for the transport equation
Solve the transport equation — for variable grid sizes and discrete particle velocities, in two and three spatial dimensions — on a fault-tolerant universal quantum computer, including the reflection of particles at the walls, edges and corners of obstacles.
Attested & literatureUpdated
- Record typeLiterature reference
- Reference implementationqlbm
- Reported costQuadratic scaling, per the paper's own comparison, in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities, stated for a single spatial dimension; the abstract calls this scaling superior to state-of-the-art approaches in the literature. Three further findings in the same abstract are each attached to a different subroutine and are qualitative rather than numeric: the streaming approach is said to reduce the number of CNOT gates against state-of-the-art quantum streaming methods; the object-encoding method for walls is said to make the CNOT-gate cost of encoding a wall independent of the wall's size; and the velocity encoding is said to give a linear speed-up in the cost of reflecting a particle's velocity and to make that cost independent of the number of velocities encoded. None of the four is accompanied by an explicit formula, a constant, or an error dependence in the abstract.
- Papers1
Solve the transport equation — for variable grid sizes and discrete particle velocities, in two and three spatial dimensions — on a fault-tolerant universal quantum computer, including the reflection of particles at the walls, edges and corners of obstacles. Schalkers and Möller present a scalable algorithm for solving the transport equation in two and three spatial dimensions, for variable grid sizes and discrete velocities, on a fault-tolerant universal quantum computer. As a proof of concept of their quantum transport method (QTM), they describe a full-circuit start-to-end implementation in Qiskit and present numerical results for 2D flows. The QTM rests on a novel streaming approach that the authors say reduces the number of CNOT gates needed compared with state-of-the-art quantum streaming methods, a novel object-encoding method that makes the CNOT-gate cost of encoding a wall independent of the wall's size, and a novel encoding of the particles' discrete velocities that gives a linear speed-up in the cost of reflecting a particle's velocity and makes that cost independent of the number of velocities encoded. The paper's main contribution, by the authors' own description, is a detailed, fail-safe implementation of the reflection step that can be readily implemented on a physical quantum computer, handles a variety of initial conditions and particle velocities, and produces physically correct behavior around the walls, edges and corners of obstacles. Combining these pieces, the authors present a fail-safe, start-to-end quantum algorithm for the transport equation usable for a multitude of flow configurations, and report that it scales quadratically in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities in a single spatial dimension, which they call superior to state-of-the-art approaches in the literature.
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 →
Schalkers and Möller present a scalable algorithm for solving the transport equation in two and three spatial dimensions, for variable grid sizes and discrete velocities, on a fault-tolerant universal quantum computer. As a proof of concept of their quantum transport method (QTM), they describe a full-circuit start-to-end implementation in Qiskit and present numerical results for 2D flows. The QTM rests on a novel streaming approach that the authors say reduces the number of CNOT gates needed compared with state-of-the-art quantum streaming methods, a novel object-encoding method that makes the CNOT-gate cost of encoding a wall independent of the wall's size, and a novel encoding of the particles' discrete velocities that gives a linear speed-up in the cost of reflecting a particle's velocity and makes that cost independent of the number of velocities encoded. The paper's main contribution, by the authors' own description, is a detailed, fail-safe implementation of the reflection step that can be readily implemented on a physical quantum computer, handles a variety of initial conditions and particle velocities, and produces physically correct behavior around the walls, edges and corners of obstacles. Combining these pieces, the authors present a fail-safe, start-to-end quantum algorithm for the transport equation usable for a multitude of flow configurations, and report that it scales quadratically in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities in a single spatial dimension, which they call superior to state-of-the-art approaches in the literature. Reported cost: Quadratic scaling, per the paper's own comparison, in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities, stated for a single spatial dimension; the abstract calls this scaling superior to state-of-the-art approaches in the literature. Three further findings in the same abstract are each attached to a different subroutine and are qualitative rather than numeric: the streaming approach is said to reduce the number of CNOT gates against state-of-the-art quantum streaming methods; the object-encoding method for walls is said to make the CNOT-gate cost of encoding a wall independent of the wall's size; and the velocity encoding is said to give a linear speed-up in the cost of reflecting a particle's velocity and to make that cost independent of the number of velocities encoded. None of the four is accompanied by an explicit formula, a constant, or an error dependence in the abstract..
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
- qlbm
- Reported cost
- Quadratic scaling, per the paper's own comparison, in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities, stated for a single spatial dimension; the abstract calls this scaling superior to state-of-the-art approaches in the literature. Three further findings in the same abstract are each attached to a different subroutine and are qualitative rather than numeric: the streaming approach is said to reduce the number of CNOT gates against state-of-the-art quantum streaming methods; the object-encoding method for walls is said to make the CNOT-gate cost of encoding a wall independent of the wall's size; and the velocity encoding is said to give a linear speed-up in the cost of reflecting a particle's velocity and to make that cost independent of the number of velocities encoded. None of the four is accompanied by an explicit formula, a constant, or an error dependence in the abstract.
- Complexity basis
- The abstract of arXiv:2211.14269 states four separate scaling claims, each attached by the abstract to a different piece of the algorithm; this record keeps them separate rather than merging them into one figure. The qubit-count claim: "We finally show that our approach is quadratic in the amount of qubits necessary to encode the grid and the amount of qubits necessary to encode the discrete velocities in a single spatial dimension, which makes our approach superior to state-of-the-art approaches known in the literature." On the streaming approach: "Our QTM is based on a novel streaming approach which leads to a reduction in the amount of CNOT gates required in comparison to state-of-the-art quantum streaming methods." On wall encoding: "As a second highlight we present a novel object encoding method, that reduces the complexity of the amount of CNOT gates required to encode walls, which now becomes independent of the size of the wall." On velocity encoding: "Finally we present a novel quantum encoding of the particles' discrete velocities that enables a linear speed-up in the costs of reflecting the velocity of a particle, which now becomes independent of the amount of velocities encoded." None of the four is a big-O expression with an explicit exponent or constant beyond the words "quadratic" and "linear" themselves, and none carries an error or precision dependence. The demonstration this record covers states no complexity bound of its own.
- 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: Fail-safe quantum algorithm for the transport equation
PROBLEM: Solve the transport equation — for variable grid sizes and discrete particle velocities, in two and three spatial dimensions — on a fault-tolerant universal quantum computer, including the reflection of particles at the walls, edges and corners of obstacles.
IDEA: Schalkers and Möller present a scalable algorithm for solving the transport equation in two and three spatial dimensions, for variable grid sizes and discrete velocities, on a fault-tolerant universal quantum computer. As a proof of concept of their quantum transport method (QTM), they describe a full-circuit start-to-end implementation in Qiskit and present numerical results for 2D flows. The QTM rests on a novel streaming approach that the authors say reduces the number of CNOT gates needed compared with state-of-the-art quantum streaming methods, a novel object-encoding method that makes the CNOT-gate cost of encoding a wall independent of the wall's size, and a novel encoding of the particles' discrete velocities that gives a linear speed-up in the cost of reflecting a particle's velocity and makes that cost independent of the number of velocities encoded. The paper's main contribution, by the authors' own description, is a detailed, fail-safe implementation of the reflection step that can be readily implemented on a physical quantum computer, handles a variety of initial conditions and particle velocities, and produces physically correct behavior around the walls, edges and corners of obstacles. Combining these pieces, the authors present a fail-safe, start-to-end quantum algorithm for the transport equation usable for a multitude of flow configurations, and report that it scales quadratically in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities in a single spatial dimension, which they call superior to state-of-the-art approaches in the literature.
REPORTED COST: Quadratic scaling, per the paper's own comparison, in the number of qubits needed to encode the grid and the number needed to encode the discrete velocities, stated for a single spatial dimension; the abstract calls this scaling superior to state-of-the-art approaches in the literature. Three further findings in the same abstract are each attached to a different subroutine and are qualitative rather than numeric: the streaming approach is said to reduce the number of CNOT gates against state-of-the-art quantum streaming methods; the object-encoding method for walls is said to make the CNOT-gate cost of encoding a wall independent of the wall's size; and the velocity encoding is said to give a linear speed-up in the cost of reflecting a particle's velocity and to make that cost independent of the number of velocities encoded. None of the four is accompanied by an explicit formula, a constant, or an error dependence in the abstract.
BASIS: The abstract of arXiv:2211.14269 states four separate scaling claims, each attached by the abstract to a different piece of the algorithm; this record keeps them separate rather than merging them into one figure. The qubit-count claim: "We finally show that our approach is quadratic in the amount of qubits necessary to encode the grid and the amount of qubits necessary to encode the discrete velocities in a single spatial dimension, which makes our approach superior to state-of-the-art approaches known in the literature." On the streaming approach: "Our QTM is based on a novel streaming approach which leads to a reduction in the amount of CNOT gates required in comparison to state-of-the-art quantum streaming methods." On wall encoding: "As a second highlight we present a novel object encoding method, that reduces the complexity of the amount of CNOT gates required to encode walls, which now becomes independent of the size of the wall." On velocity encoding: "Finally we present a novel quantum encoding of the particles' discrete velocities that enables a linear speed-up in the costs of reflecting the velocity of a particle, which now becomes independent of the amount of velocities encoded." None of the four is a big-O expression with an explicit exponent or constant beyond the words "quadratic" and "linear" themselves, and none carries an error or precision dependence. The demonstration this record covers states no complexity bound of its own.
PRIMARY SOURCE: Merel A. Schalkers, Matthias Möller (2022), Efficient and fail-safe quantum algorithm for the transport equation — https://arxiv.org/abs/2211.14269
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 and fail-safe quantum algorithm for the transport equation
Merel A. Schalkers, Matthias Möller · 2022
Primary source: it presents the quantum transport method (QTM), a fail-safe, start-to-end algorithm for the transport equation, and reports that the approach is quadratic in the qubits needed to encode the grid and the discrete velocities in a single spatial dimension, that its streaming approach reduces CNOT gates against state-of-the-art quantum streaming methods, that its wall-encoding method makes CNOT cost independent of wall size, and that its velocity encoding gives a linear speed-up in reflection cost independent of the number of velocities. Consult it for the two- and three-dimensional scaling, the constants involved, and the Qiskit implementation and its 2D numerical results, none of which the abstract itself states in detail.