Email Print Share

This document has been archived.

NSF 20-056

Dear Colleague Letter: Quantum Algorithm Challenge

March 10, 2020

Dear Colleague:

As the age of Moore's law draws to a close, there has been increased interest in new types of computational platforms. Quantum computing in particular has recently seen rapid advances in terms of hardware capabilities, algorithm development, and the availability of software. One of the earliest and most compelling applications for quantum computers, as envisioned by Richard Feynman, is the idea of simulating quantum systems with many degrees of freedom, such as molecules and materials, which is intractable on ordinary classical computers. This and more recently conceived applications of quantum computation related to encryption, search, approximation, optimization, and machine learning promise to have enormous impact in science and technology. With this Dear Colleague Letter (DCL), the National Science Foundation (NSF) aims to challenge the fundamental research community to develop innovative quantum algorithms for many- body systems, develop novel algorithms that expand the applications of quantum computation, or propose new quantum-computing paradigms.

Because quantum computing is very different from classical computing, the best way to obtain a quantum advantage is often quite subtle. It takes creativity and innovation to develop the algorithms required to solve practical problems via quantum computation. Although much progress has been made, there are many open questions and obstacles to overcome before the power of quantum computing can be fully harnessed for application in chemistry, physics, materials science, mathematics, statistics, and computer science.

The National Science Foundation has recently sponsored several workshops that are relevant to this DCL: Mathematical Sciences Challenges in Quantum Information1, Enabling the Quantum Leap: Quantum Algorithms for Quantum Chemistry and Materials2, and Quantum Simulators: Architectures and Opportunities3. These workshops are aligned with the NSF Quantum Leap Big Idea, which aims to exploit quantum mechanical concepts such as superposition and entanglement to develop next-generation technologies for sensing, computing, modeling, and communication.

Stimulated by the recommendations of the workshops, a working group with membership from the Divisions of Chemistry, Materials Research, Physics, and Mathematical Sciences within the Directorate for Mathematical and Physical Sciences; and the Division of Computing and Communication Foundations and Office of Advanced Cyberinfrastructure within the Directorate for Computer and Information Science and Engineering invites the submission of Research Concept Outlines (RCOs) (maximum length three pages) describing research ideas that may lead to EAGER (Early-Concept Grants for Exploratory Research) (EAGER)4 or Research Advanced by Interdisciplinary Science and Engineering (RAISE)5 proposals focused on topics in the following three tracks:

  • QSA: quantum computing simulation algorithms for quantum many-body systems.
  • QIA: quantum information algorithms, which aims to expand the set of known quantum-computing algorithms with application in computer science, mathematics, and statistics; and
  • QCH: quantum computing horizons which explores potentially transformative new paradigms for quantum computation.

QSA

This track focuses on quantum algorithms for the simulation of quantum many-body systems at the atomic or molecular level; systems of interest to chemistry, physics, and materials science2,3. We especially encourage ideas that address simulation challenges that have received less attention to date, such as excited states, large-amplitude vibrational motion, quantum dynamics of realistic chemical or physical systems, excitations in strongly correlated materials, new states of electronic matter, and open problems in quantum statistical physics. These ideas may address long-standing problems that have proven particularly challenging and are computationally prohibitively difficult or intractable under current classical computing paradigms. New mathematical and computational approaches are welcome.

The topical focus of the research may include (but is not limited to) the following: entirely new algorithmic approaches; significant improvements of existing algorithms; novel qubit representations; improved system-specific time evolution methods; state preparation; exploiting structure and avoiding the need to re-prepare initial states; benchmarking and comparison of different approaches in the context of realistic systems; quantum computing software focused on problems in chemistry, physics, and materials. The proposed ideas may be designed for near-term (Noisy Intermediate-Scale Quantum) architectures, mature error-corrected platforms, or other types of computers such as analogue simulators or hybrid platforms. RCOs in this category must display the prefix "QSA:" in the title.

QIA

Since the creation of Shor's algorithm for integer factoring, several algorithms6 in computer science, information science, mathematics, and statistics have been developed for potential implementation on a quantum computer. The full range of quantum-computing capabilities, however, is far from understood. This track calls for research on quantum information algorithms, including work in quantum complexity, communication, and cryptography, that extends the scope of uses for quantum computation. Also, of interest is work that analyzes schemes for quantum computation, such as quantum gate models and error-correction schemes. Additionally, novel potentially-transformative approaches to post-quantum cryptography7 are within the scope of this track. This call aims to promote and facilitate cross-disciplinary exchange and collaboration between mathematical scientists, computer scientists, and scientists from other domains. Mathematicians, statisticians, and theoretical computer scientists are especially encouraged to participate in new collaborative projects in this important interdisciplinary area. RCOs in this category must display the prefix "QIA:" in the title.

QCH

The history of computing is rich with examples in which attempted algorithm development inspired compiler, hardware design, and architecture innovations. For quantum computing it is also reasonable to expect that the focus on algorithms that use existing or envisioned hardware will lead to innovations in hardware. Owing to the fluidity of the ideas underlying quantum computing, there is potential to develop new quantum-computing paradigms, some possibly based on direct analog simulation, that lead to new ways to think about how to perform computation through manipulation of quantum mechanical states, ways that may have a tenuous connection, if any at all, to ideas underlying classical computing. In this track, we encourage more speculative ideas that are not tied to any current model of quantum computing but envision how the problems posed by the simulation of many-body quantum systems or clever ways to utilize or incorporate direct analog quantum simulation could guide the development of new types of quantum or hybrid architectures. RCOs in this category should display the prefix "QCH:" in the title.

A successful Research Concept Outline will describe the following:

  • A challenging scientific problem focus and how the proposed work has the potential to significantly advance our ability to address it.
  • Associated algorithmic or computational challenge(s) being addressed and why current approaches are inadequate. If there are no current approaches, the barriers or challenges that preclude or make them intractable or impractical should be clearly discussed.
  • For each track:
    • QSA: Algorithmic advance(s) being proposed and why the proposed approach offers potential advantages over existing quantum algorithms (if any exist).
    • QIA: How the proposed approach complements or improves upon the existing algorithms and schemes.
    • QCH: The proposed new approach to quantum computing discussed in the context of a challenging existing problem. The RCO should outline what the proposed new way of quantum computing brings over existing paradigms. Will this approach be potentially applicable to other challenging problems?
  • The novelty of the proposed ideas.
  • Specific plans for evaluating or benchmarking the developments.
  • For each track:
    • QSA: The type of hardware being targeted and plans for running on actual machines (or realistic simulators).
    • QIA: The expected speedup (quantum advantage) of the proposed approach, any anticipated improvement in hardware requirements (numbers of qubits/gates), or (for post-quantum cryptographic schemes) the reasons for anticipated resistance to quantum attack.
    • QCH: Prospects for realizing a proof of principle. This track lends itself to interdisciplinary collaboration, if a proof-of-principle is part of the project (RAISE).

The title of the RCO should clearly indicate the funding mode sought through the prefixes EAGER: or RAISE:, followed by QSA: or QIA: or QCH: to label the track. The RCO should also list all the Principal Investigators and their organizational affiliations, as well as anticipated senior personnel. This information should form the first paragraph of the RCO and begin with the first word "Investigators:". Ideas for RAISE proposals should emphasize the interdisciplinary nature of the research and clearly identify the role of each member of the team. RCOs are limited in length to three pages maximum.

The RCOs should be sent to QLQA@nsf.gov by April 15, 2020. The Quantum Algorithms (QLQA) committee will review them and invite submissions by May 1, 2020. Invited EAGER and RAISE proposals will be due on June 15, 2020. The email invitation from an NSF Program Officer serves as documentation and must be uploaded in the Supplementary Documentation section of the proposal.

Sincerely,

Anne Kinney
Assistant Director for Mathematical and Physical Sciences

Margaret Martonosi
Assistant Director for Computer & Information Science & Engineering

  1. Mathematical Sciences Challenges in Quantum Information https://sites.google.com/site/mathqinfo2015/home
  2. Enabling the Quantum Leap: Quantum Algorithms for Quantum Chemistry and Materials https://www.nsf.gov/mps/che/workshops/quantum_algorithms_for_chemistry_and_materials_report_01_21-24_2019.pdf
  3. Quantum Simulators: Architectures and Opportunities https://arxiv.org/abs/1912.06938
  4. Proposal & Award Policies & Procedures Guide (PAPPG) II.E.2 https://nsf.gov/publications/pub_summ.jsp?ods_key=pappg
  5. Proposal & Award Policies & Procedures Guide (PAPPG) II.E.3 https://www.nsf.gov/publications/pub_summ.jsp?ods_key=pappg
  6. Quantum Algorithm Zoo https://quantumalgorithmzoo.org/
  7. National Institute of Standards and Technology (NIST) Post-Quantum Cryptography Standardization Project https://csrc.nist.gov/Projects/Post-Quantum-Cryptography