Computational Complexity in Standard Machine Learning and Quantum Machine Learning Algorithms

Office of the Director of National Intelligence (ODNI)
Reference Code
How to Apply

Create and release your Profile on Zintellect – Postdoctoral applicants must create an account and complete a profile in the on-line application system.  Please note: your resume/CV may not exceed 2 pages.

Complete your application – Enter the rest of the information required for the IC Postdoc Program Research Opportunity. The application itself contains detailed instructions for each one of these components: availability, citizenship, transcripts, dissertation abstract, publication and presentation plan, and information about your Research Advisor co-applicant.

Additional information about the IC Postdoctoral Research Fellowship Program is available on the program website located at:

If you have questions, send an email to  Please include the reference code for this opportunity in your email. 

Application Deadline
2/28/2022 6:00:00 PM Eastern Time Zone

Research Topic Description, including Problem Statement:

  • Advances in computer and information technologies will continue to significantly contribute to the massive data explosion and complex problem spaces anticipated in the near future. These problems will require unique algorithms to address a level of complexity in problems not yet successfully achieved. It will be important to examine the capabilities of conventional and quantum computers and how respective algorithms are designed and function to better handle the next tier problems. The computational complexity of a problem is attributed to the resources required to run the most efficient algorithms that are used to solve the problem. Hence, an understanding of the “standard” and quantum algorithms in conjunction with their respective computing resources will be critical to modeling and assessing the computational complexity.
  • Quantum computing has drawn a lot of interest due to the promise it has shown in some cases to reduce computational complexity. In addition, the possibility that quantum computers can use quantum algorithms to solve “intractable” problems using classical (standard) computers has also generated a lot of excitement. However, quantum computing should not be considered a universal solution for all problems. In some cases, quantum algorithms give little to no advantage. It is only in “special” applications that quantum algorithms can provide quantum speedups.
  • When data points are projected into higher and higher dimensions, classical computers can be severely challenged to deal with such large computations. Clearly, classical and quantum computers fundamentally manipulate data differently. Classical computers perform calculations based on the measured position of a physical state, i.e., binary operations which mean a single state can be either on or off. Quantum computers, on the other hand, work off the probability of an object’s state before it is measured. As a result, they have the potential to process data at a level almost exponential to the way that classical computers can process data.
  • The development of a good “translator” between classical algorithms to quantum algorithms could provide great benefits. In particular, determining machine learning algorithms that might be of practical use and are easy to implement within a quantum environment could significantly enhance quantum adoption. A closer examination of the fundamental building blocks of Quantum Machine Learning (QML) could also provide valuable information toward more widespread adoption.

Example Approaches:

There are several important issues that can be considered in the research and approached collaboratively. Research efforts could include:

  • creating quantum algorithms that might be used in classical systems;
  • expanding on IBM work on quantum kernel methods (see: ) for potential speedup over standard machine learning algorithms particular in classification problems;
  • transitioning algorithms from theoretical description to a programming language description;
  • identifying potential standard for converting instructions to quantum code given that different physical quantum computers are likely to have different sets of basic operations.

Relevance to the Intelligence Community:

Key technologies such as mobile and Internet of Things (IoT) technologies are expected to continue to evolve and provide significant contributions to the massive data explosion and complex problems that have to be addressed in the very near future. Evolving requirements will demand more comprehensive and flexible strategies given how quickly situations change on the world stage. As a result, the need for quick and “trusted” intelligence is escalating to better position us for opportunities, as well as, challenges. Establishing better interplay between standard and quantum computing resources and the algorithms that depend on them will be essential to effective management of the intelligence cycle, data collection, data processing, all source analysis and production, and dissemination—each representing an essential component within the intelligence cycle.

Key Words: Algorithms, Computational, Complexity, Standard, Quantum, Machine Learning, QML, ML, Computing, Intelligence, Cycle, Transitioning, Translator, Internet of Things


Postdoc Eligibility

  • U.S. citizens only
  • Ph.D. in a relevant field must be completed before beginning the appointment and within five years of the application deadline
  • Proposal must be associated with an accredited U.S. university, college, or U.S. government laboratory
  • Eligible candidates may only receive one award from the IC Postdoctoral Research Fellowship Program

Research Advisor Eligibility

  • Must be an employee of an accredited U.S. university, college or U.S. government laboratory
  • Are not required to be U.S. citizens
Eligibility Requirements
  • Citizenship: U.S. Citizen Only
  • Degree: Doctoral Degree.
  • Academic Level(s): Postdoctoral.
  • Discipline(s):
    • Chemistry and Materials Sciences (12 )
    • Communications and Graphics Design (2 )
    • Computer, Information, and Data Sciences (16 )
    • Earth and Geosciences (21 )
    • Engineering (27 )
    • Environmental and Marine Sciences (14 )
    • Life Health and Medical Sciences (45 )
    • Mathematics and Statistics (10 )
    • Other Non-Science & Engineering (2 )
    • Physics (16 )
    • Science & Engineering-related (1 )
    • Social and Behavioral Sciences (27 )

The ORISE GO mobile app helps you stay engaged, connected and informed during your ORISE experience – from application, to offer, through your appointment and even as an ORISE alum!