Data Assimilation on a Quantum Annealing Computer: Feasibility and Scalability

Abstract:

Data assimilation is one of the ubiquitous and computationally hard problems in the Earth Sciences. In particular, ensemble-based methods require a large number of model evaluations to estimate the prior probability density over system states, and variational methods require adjoint calculations and iteration to locate the maximum a posteriori solution in the presence of nonlinear models and observation operators.

Quantum annealing computers (QAC) like the new D-Wave housed at the NASA Ames Research Center can be used for optimization and sampling, and therefore offers a new possibility for efficiently solving hard data assimilation problems. Coding on the QAC is not straightforward: a problem must be posed as a Quadratic Unconstrained Binary Optimization (QUBO) and mapped to a spherical Chimera graph.

We have developed a method for compiling nonlinear 4D-Var problems on the D-Wave that consists of five steps:

1. Emulating the nonlinear model and/or observation function using radial basis functions (RBF) or Chebyshev polynomials.
2. Truncating a Taylor series around each RBF kernel.
3. Reducing the Taylor polynomial to a quadratic using ancilla gadgets.
4. Mapping the real-valued quadratic to a fixed-precision binary quadratic.
5. Mapping the fully coupled binary quadratic to a partially coupled spherical Chimera graph using ancilla gadgets.

At present the D-Wave contains 512 qbits (with 1024 and 2048 qbit machines due in the next two years); this machine size allows us to estimate only 3 state variables at each satellite overpass. However, QAC’s solve optimization problems using a physical (quantum) system, and therefore do not require iterations or calculation of model adjoints. This has the potential to revolutionize our ability to efficiently perform variational data assimilation, as the size of these computers grows in the coming years.