Microsoft gives Nasa a lesson in timeshare optimisation

Microsoft’s Azure Quantum team has worked with Nasa’s Jet Propulsion Laboratory (JPL) to apply quantum computing to a classic scheduling problem.

The Deep Space Network (DSN) is a collection of large antennas, based at three facilities spaced equidistant from each other – about 120 degrees apart in longitude – around the world. The DSN is operated by the JPL, which also operates many of Nasa’s interplanetary robotic space missions.

Space mission operations teams use the DSN Command System to control the activities of their spacecraft. Commands are sent to robotic probes as coded computer files that the craft execute as a series of actions.

The DSN also acquires, processes, decodes and distributes science and engineering telemetry data transmitted to Earth via radio signals from spacecraft as they explore the far reaches of our solar system. It also offers capabilities to support science investigations that probe the nature of asteroids and the interiors of planets and moons. 

However, as Nasa launches more frequent and complex missions into space, managing communications with the growing number of spacecraft is increasingly challenging.

In a blog post describing the project, Microsoft said scheduling requests to use the DSN antennas from the space missions come with a large number of constraints and require intensive computing resources. “All missions require access for key communication, resulting in several hundred weekly requests when each spacecraft is visible to the antenna,” wrote Anita Ramanan, senior Azure Quantum software engineer, in the blog post.

According to Ramanan, the scheduling task facing JPL is a multivariate problem. She said the team took quantum-inspired optimisation algorithms from Microsoft’s research in quantum computing and ran them on a classical computing architecture.

By thinking about how to solve the problem using a quantum computer, the team was able to develop a quantum-inspired algorithm that could be run on a classical computing architecture. At the beginning of the project, the Microsoft team said it had recorded run times of two hours or more to produce a schedule for the DSN.

Ramanan said that by applying quantum-inspired optimisation algorithms with Azure Quantum, “we were able to reduce run time to 16 minutes, and a custom solution reduced it to about two minutes”.

She added: “Schedules that are produced in minutes rather than hours enable JPL to create many candidate schedules and allow the organisation to be more agile as space missions and demands increase.”