(collaborator: Smelyanskiy)
NP-complete problems are frequently encountered in practice, and particularly in the context of combinatorial optimization, with distinct relevance to many scientific and engineering applications of relevance to all NASA Enterprises. These are computationally intensive problems whose solution by means of even the best classical algorithms known today requires prohibitively (i.e., exponentially) large computing resources in time and/or space, thus essentially rendering them intractable. The emerging field of quantum information theory utilizes the uniquely quantum principles of superposition, interference, and entanglement to achieve an unprecedented new form of computational parallelism. This revolutionary approach to information processing thus offers a qualitatively new perspective for developing efficient (i.e., polynomial-time) algorithms for solving classically intractable (NP-hard) optimization problems.
Algorithms
The ultimate validation for the quantum-computational approach to optimization will come from the design of polynomial-time quantum algorithms. Our goal here is two-fold:
(a) Propose solutions to NASA-related optimization problems based on existing (Grover-type) quantum search algorithms. The aim here is to customize a well-known quantum search approach to particular problems of interest to NASA. These include (i) rapid planning and scheduling for optimized air traffic control, (ii) planning, coordination, and communication of future dense Earth-observing satellite constellations, (iii) real-time and autonomous data interpretation and understanding (e.g., pattern recognition, causality extraction) in large scientific databases, (iv) solution of difficult constraint satisfaction and resource allocation problems for optimal mission planning on intelligent autonomous spacecraft for deep-space and planetary (e.g., Mars, Europa) missions, and (v) solution of scheduling problems on astronomical observatories (e.g., Hubble, Chandra) for maximized efficiency, among others. Although the time-complexity of Grover-type search algorithms remains essentially exponential, drastic practical improvements may still be achieved.
(b) Develop radically new quantum optimization algorithms that promise to outperform existing (quantum) approaches for solving NP-hard problems. Here, we are exploring an optimization approach based on continuous adiabatic quantum evolution with various time-dependent Hamiltonians incorporating knowledge of the energy spectrum of the problem at hand. The quantum register is forced to remain in its ground state as it evolves from an initial (symmetric) state to a final state that encodes the problem solution. We are also investigating the behavior of search algorithms near the phase transition of an NP-hard problem - the most difficult regime of solution - as a suitable control parameter is scaled dynamically to regulate the algorithmic complexity. Finally, we are examining NP-hard problems where the density of states can be computed approximately in closed form and the energy spectrum is quasi-continuous. This allows an optimization approach based on a time-varying quantum oracle (i.e., optimal quantum control) that promises an improved algorithmic complexity over simple Grover-type search.
Holographic Optical Data Storage Systems
The primary benefits offered by holographic optical data storage over current storage technologies include significantly higher storage capacities and faster read-out rates. This research is expected to lead to compact, high-capacity, rapid- and random-access, radiation-resistant, low-power, and low-cost data storage devices necessary for future intelligent spacecraft, as well as to massive-capacity and fast-access terrestrial data archives, with obvious relevance and impact on NASA's Earth- and Space-Science Enterprises.
The Ames effort is aimed at the development of holographic optical data storage systems based on bacteriorhodopsin (BR - particularly the D85N genetic variant), a novel organic material with a strong photochromism in the visible part of the spectrum. Current research is focused on (1) materials issues pertaining to the development of polymer-based BR films with optimized recording sensitivity and storage lifetime, and (2) systems issues concerning optimal data multiplexing schemes and achievable storage capacities and bit-error rates. This work involves (1) BR film characterization in the laboratory, (2) system-level theoretical analysis, simulations, and experiments, and finally (3) quantum-chemical modeling and genetic engineering of the BR molecule. Our collaborators in this effort include researchers from the Computational Chemistry Branch of NASA-Ames as well as research groups in Syracuse University, University of Oregon, and Bend Research, Inc.
 |
 |
 |
 |
Phone: 650-604-1262