Fail-safe quantum algorithm for the transport equation

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 Classiq index entry this record covers, applications/CFD/qlbm, gives a directory path and a file list and states no bound of its own.
DEMONSTRATED BY: the Classiq library entry applications/CFD/qlbm
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.