Quantum Algorithms

Our interest in quantum computing stems primarily from the need to solve hard, supposedly "intractable", computational problems on a routine basis. Detailed mission planning, deep space network communications scheduling, and spacecraft design optimization are just a few examples of the kinds of NP-complete problems that we face. So far, there is no known classical computing technique that can solve such problems using polynomially bounded resources in the worst case. Today we employ a small army of computer scientists to work on developing the very best classical algorithms for performing these computations.

As we move out into the next century, NASA envisions a huge increase in the number of concurrent space missions. In such a climate the computational demands we will face will become significant factors impeding progress. Moreover, as our spacecraft become more remote from Earth, the speed of light limited communication delays force us to place more autonomy on-board. To function autonomously, such as to re-plan a series of observations, and data analyses in real-time during a fly-by of an astronomical body, we need to bring massive computational power to bear under extreme constraints on allowed mass, time and power. Like the ARO, NSA, ARDA, and DARPA (the other U.S. government agencies funding quantum computing) we would like to know if quantum computers could provide any help.