Quantum algorithms for scientific discovery – Call for proposals

This call for proposals is now closed. The deadline to apply was November 10, 2023. Contact us at NRC.Quantum Computing- Informatique quantique .CNRC@nrc-cnrc.gc.ca if you have any questions.

1. Program overview

The National Research Council of Canada's Applied Quantum Computing (AQC) Challenge program is launching a call for proposals to support Canada's National Quantum Strategy. The call aims to enable collaboration between thought leaders in Canada's quantum computing community to develop novel use cases for fault-tolerant quantum computers of the future, to solve hard problems with the potential for exponential improvements in efficiency over the best classical techniques.

The AQC Challenge program focuses on quantum applications and software that will enable scientific discovery and deliver new technologies for human health, climate change and advanced materials with far-reaching benefits to society.

The NRC is Canada's federal research and development organization. Our mission is to have an impact by advancing knowledge, applying leading-edge technologies and working with other innovators to find creative, relevant and sustainable solutions to Canada's current and future economic, social and environmental challenges.

AQC is enabled by the Collaborative Science, Technology and Innovation program with the goal of supporting collaborative research to stimulate early and creative R∓D ideas. Hosted by the Digital Technologies Research Centre, AQC leverages the expertise of NRC science professionals. As a result, this call requires collaboration between NRC researchers and external applicants.

2. Scope and objectives of the call

This call encompasses 3 funding streams, all of which require collaboration with an NRC partner:

  1. Quantum algorithms for Hamiltonian simulation
  2. Quantum algorithms for linear algebra
  3. Quantum algorithms for differential equations

2.1. Stream 1: Quantum algorithms for Hamiltonian simulation

Background

Among the most promising potential applications of large-scale fault-tolerant quantum computers is the simulation and modelling of the quantum properties of particles that are highly relevant to materials science, high-energy physics and quantum chemistry Footnote 1 Footnote 2 Footnote 3.

The complexity of simulating the behaviour of electrons in materials or in large molecules on a classical computer can grow exponentially in the number of particles being modelled. A fully programmable and scalable fault-tolerant quantum computer could, in principle, realize any desired Hamiltonian of the system and efficiently simulate its dynamics.

In practice, very efficient and highly accurate simulations can be achieved by classical methods, and so the question of where one might realize significant quantum speed-ups is very problem-specific. Another challenge is the necessity to prepare an initial state of the Hamiltonian. Common useful initial states are low-energy states (ground states or thermal averages), and computing these states is not known, in general, to be efficiently solvable even on a quantum computer.

Given the current limitations in what can be proven about the quantum computational complexity of these simulation problems in general, we must turn to experiments on specific problems of interest. For specific simulation problems of interest, to understand the potential for exponential quantum advantage, a detailed quantification of the quantum computing resources required to achieve the desired accuracy accounting for fault-tolerance overhead and hardware-specific characteristics is needed.

We need to characterize the performance and resource requirements of the best classical methods available for the problem of interest. If we believe that a quantum simulation may provide an exponential speed-up over classical methods for a particular problem of interest, we also need a way of quantifying and validating the accuracy of quantum simulation when it is operating beyond the capabilities of classical simulation.

Objectives

  • Identify specific simulation problems for which there is a clear potential for a universal fault-tolerant quantum computer to achieve exponential resource advantages over known classical methods
  • Characterize and quantify the quantum computing resources required, accounting for initial state preparation, system dynamics, and measurement and readout
  • Identify additional structures (e.g., spectral gaps, special features of molecular Hamiltonians) that could be exploited by gate-model quantum algorithms for Hamiltonian simulation problems

2.2. Stream 2: Quantum algorithms for linear algebra

Background

It is generally believed that the most influential applications of quantum computers will use scalable fault-tolerant quantum computers of the future and will run algorithms that exhibit exponential speed-up over the best classical techniques for solving specific hard problems.

The first such algorithm, developed by Peter Shor in 1994, allowed for integer factorization at a rate exponentially faster than the best-known classical methods Footnote 4. In 2009, a quantum algorithm for systems of linear equations was proposed by Aram Harrow, Avinatan Hassidim and Seth Lloyd Footnote 5. The algorithm, known as HHL, tackles a fundamental problem in science—solving systems of linear equations. The algorithm runs in time logarithmic in n and offers the hope that we might find a broad class of use cases where quantum computing could bring exponential speed-ups.

HHL has given rise to a flurry of research under the banner of "quantum machine learning." Unfortunately, HHL is burdened with many caveats and subtleties that significantly restrict its potential applicability. In 2015, Scott Aaronson authored an article Footnote 6 in which he enumerated 4 caveats to the applicability of HHL for solving a system Ax = b, where A is an n × n matrix.

The caveats in brief:

  1. The coefficient vector b needs to be efficiently encoded into the quantum computer. This could be achieved in principle by using a quantum random access memory (QRAM), provided b is relatively uniform. Alternatively, in certain cases, b can be described by an explicit formula that could be efficiently run on the quantum computer.
  2. The quantum computer needs to be able to apply unitary transformations of the form e-iAt for various values of t. This may be possible when the matrix A is sparse or for other special classes of matrices.
  3. The matrix A must be well conditioned, meaning that the condition number κ = |λmax / λmin| (ratio of the largest to smallest eigenvalues) must not be exponential in the size of b.
  4. The output of the algorithm is a quantum state whose amplitudes contain the solution vector x. Determining specific elements of the solution will, in general, require repeating the algorithm at least n times, and we lose the exponential advantage of HHL. Thus, the algorithm provides exponential speed-up only if we are interested in some specific statistical information about the solution vector that can be efficiently revealed by some quantum measurement of the output state.

Any proposed use case for HHL requires working out a detailed analysis of the above 4 caveats. This has been done only for relatively few potential applications Footnote 7.

While improvements and extensions to HHL have appeared in the years since it was developed, there are relatively few known uses cases. In the years since HHL, related new quantum algorithms achieving exponential speed-ups have appeared (e.g., k-means clustering Footnote 8, support vector machines Footnote 9, data fitting Footnote 10), and these algorithms have many of the same caveats associated with HHL.

Objectives

  1. Identify use cases for HHL or related gate-model quantum algorithms offering exponential speed-up over the best classical methods, including a detailed analysis of any relevant caveats (including those described above for HHL) and a detailed costing of all the quantum computing resources required
  2. Establish "no-go" results that contribute to a framework for identifying contexts in which these quantum algorithms are unlikely or unable to provide exponential speed-ups. One direction, for example, would be efficient techniques for determining if a matrix is well conditioned
  3. Develop extensions or improvements to HHL and/or related gate-model quantum algorithms offering exponential speed-ups that reduce the caveats or the restrictions limiting the algorithms' applicability
  4. Discover new gate-model quantum algorithms, or algorithmic tools, that can be shown to provide the potential for exponential advantage over the best classical methods for problems in algebra and/or machine learning.

2.3. Stream 3: Quantum algorithms for differential equations

Background

Among the most promising potential applications for large-scale fault-tolerant quantum computers are the simulations of physical systems that are hard for classical computers. Much of the focus has been on the simulation of quantum systems, for which classical computer simulations suffer exponential scaling. However, there are classical physical systems that are also hard for classical computers to simulate.

One example is the flow of incompressible viscous fluids. These flows are described by the Navier–Stokes equations. These are nonlinear partial differential equations (PDEs) that are the sum of the gravitational, pressure and viscous forces. The solutions to Navier–Stokes equations underlie problems in aircraft design, weather forecasting, magneto-hydrodynamics of plasmas and more. Complete solutions are available only for the case of simple 2-dimensional flows.

More general and complicated 3-dimensional flows are intractable for classical computers beyond approximate numerical methods. Further, it is not yet known that smooth solutions always exist. In May 2000, the Clay Mathematics Institute designated the problem of whether smooth, reasonable solutions to the Navier–Stokes equation in 3 dimensions exist, a million-dollar millennium problem.

Recent research has appeared exploring the use of quantum algorithms running on fault-tolerant quantum computers for solving these problems. One method, known as quantum Carleman linearization Footnote 11, works by transforming the PDE into a linear system and then using a quantum algorithm to solve the linear system Footnote 12. Another technique Footnote 13 performs a reduction from the PDEs to an ordinary differential equation (ODE) and then employs the quantum amplitude estimation algorithm Footnote 14 to solve the ODE.

Relatively little research has appeared until very recently that explores the potential for fault-tolerant quantum computers to bring computational advantage to solving partial differential equations like the Navier–Stokes equations. Because of the importance of this problem to a range of applications, this call aims to support new work in this direction.

Objectives

  1. Build on previous research towards quantum algorithms for the Navier–Stokes equations, including establishing complexity bounds, more efficient equation transformations, new ways of applying known quantum algorithms and benchmarking quantum resources for a complete implementation.
  2. Discover new gate-model quantum algorithmic techniques that have the potential to yield new quantum speed-ups for solving the Navier–Stokes equations and other nonlinear differential equations.

3. Eligible projects and teams

Project must demonstrate the potential to achieve 1 or more of the objectives listed above and must be a collaboration between the NRC and at least 1 other eligible recipient.

Eligible recipients under this call:

  • Not-for-profit organizations
  • Small and medium-sized enterprises (those with fewer than 500 employees)
  • Indigenous groups, governments and representative organizations
  • Academic institutions

Requirements for projects and teams:

  • Must clearly align with AQC's mandate and priority areas
  • Must include at least 1 NRC collaborator
  • Must include at least 1 collaborator who is eligible for funding (see above, "Eligible recipients under this call")
  • Must be feasible within 2 or 3 years
  • Must complete an expression of interest (EOI) document

Note: Unfunded collaborators from across the technology ecosystem may also collaborate on projects.

3.1. Commitment to EDI and GBA+

Project teams must clearly demonstrate their commitment to equity, diversity and inclusion (EDI) and gender-based analysis plus (GBA+) in their research applications, including composition of their project teams, research methods, analysis and knowledge-mobilization plans. Undertaking GBA+ and critically considering factors related to EDI adds valuable dimensions in research and improves the quality, social relevance and impact of the research. In addition, it may contribute to taking the research in a new direction. EDI and GBA+ considerations should influence all stages of research or development processes, from establishing priorities and building theory to formulating questions, designing methodologies and interpreting data. Applicants are invited to consult the guide to best practices in equity, diversity and inclusion in research practice and design.

4. Costs

Eligible costs:

  • Salaries for high quality personnel (HQP) working on the project activities
  • Research support costs: Direct costs incurred in the project implementation phase, which can include consumable materials, supplies, equipment rentals and rent and facility or equipment rental costs required for the execution of the project
  • Reasonable costs (relative to price paid) for research equipment, including testing tools, instruments, computer equipment, secure equipment and information technology costs such as high-performance computers and secure servers
  • Costs for on-duty travel required to execute the project and limited conference travel (for HQP only)
  • Indirect costs not directly applicable to carrying out the project but necessary for conducting the recipient's general business, up to a maximum of 10% of total eligible costs
  • Amounts invoiced to the applicant by a contractor for services rendered related directly to the project (e.g., professional services fees)

Ineligible costs:

  • Purchase of land, leasehold interest in land and property taxes
  • Any portion of costs subject to refunds, rebates or credits, including HST, GST and PST
  • Costs paid by the NRC

5. Funding and support

Funding provided by the National Program Office follows the terms and conditions of the Collaborative Science, Technology and Innovation program. This program is intended to position the NRC as a collaborative platform that uses science excellence to respond to Canada's most pressing challenges.

As such, projects supported under this initiative benefit from NRC assets in place (special-purpose research facilities, scientific expertise and networks) and financial assistance in the form of non-repayable grants or contributions.

For more information on available funding, consult the grant and contribution funding for collaborators webpage.

The program is planning to make available up to $7,000,000 in non-repayable funding to support projects under this call. Project funding is expected to be between $100,000 and $300,000 per year, per eligible recipient. Project duration is expected to be between 2 and 3 years.

Determination of financial assistance will be made on the basis of a preliminary risk assessment of proposed projects, including intended recipients, project duration and maximum funding allocations.

5.1. Cost share and stacking provisions

The cost share and stacking provisions for projects are as follows:

  • For academic institutions and not-for-profit organizations, the maximum NRC cost share for grants will not exceed 100% of total eligible project costs.
  • For small and medium-sized enterprises, the maximum NRC cost share for contributions will not exceed 75% of total eligible project costs.
  • The maximum limit of total Canadian government assistance (federal, provincial, territorial and municipal assistance for the same eligible costs) cannot exceed 100% of the total eligible project costs.

6. Application process and timelines

The NRC is committed to a consistent, fair and transparent selection process to identify, select and approve the allocation of funding to projects that best fit the objectives of the collaborative call.

Expressions of interest will be assessed on the basis of the criteria in Annex A, with only the most promising projects moving on to full project proposal (FPP). Applicants may be asked to provide supplementary information at various points in the review process. FPPs will undergo a peer review process.

Applicants invited to submit an FPP will be notified with the information required and templates to be completed. Applicants must provide all mandatory information in order to be considered for funding. Note that an invitation to submit an FPP is not a funding commitment from the AQC program.

6.1. Key dates, deadlines and steps

  • November 10, 2023: Expression of interest (EOI) submission deadline
  • November 20, 2023: NRC sends out invitations for a full project proposal (FPP)
  • January 9, 2024: FPP submission deadline
  • February 2024: Notification of results
  • February to May 2024: Funding disbursed and project starts

Steps of the project development and approval process

  • Step 1: Assemble the project team, including an NRC collaborator. If you have an idea for a project but no NRC collaborator, send an email to NRC.QuantumComputing-Informatiquequantique.CNRC@nrc-cnrc.gc.ca and we will try to make a match for projects aligned with the scope of the call.
  • Step 2: Request an expression of interest (EOI) form by sending an email to NRC.QuantumComputing-Informatiquequantique.CNRC@nrc-cnrc.gc.ca and submit completed EOIs to same email address.
  • Step 3: The AQC program team reviews the EOIs and evaluates the eligibility of the project, potential recipients and project fit.
  • Step 4: The NRC sends a notice to the research teams of the results.
  • Step 5: The National Program Office sends full project proposal (FPP) templates to the selected research teams.
  • Step 6: Research teams work together to develop FPP.
  • Step 7: The principal investigator submits the FPP to the National Program Office by email to Rebecca.Trueman@nrc-cnrc.gc.ca with the program team in CC at NRC.QuantumComputing-Informatiquequantique.CNRC@nrc-cnrc.gc.ca.
  • Step 8: The NRC principal investigator submits internal project documents to the Applied Quantum Computing Challenge program.
  • Step 9: Peer review committee reviews FPPs.
  • Step 10: The NRC sends a notice to the research teams of the results.
  • Step 11: The NRC completes due diligence process.
  • Step 12: Funding and collaboration agreements signed with collaborators of successful proposals.
  • Step 13: Projects begin.

6.2. Expression of interest

Submit your completed expression of interest (EOI) by email no later than 11:59 pm ET on November 10, 2023 to the Applied Quantum Computing Challenge program at NRC.QuantumComputing-Informatiquequantique.CNRC@nrc-cnrc.gc.ca. Use the subject line "AQC EOI" in your email.

If you wish to withdraw your EOI at any stage of the evaluation, you must do so via email. To be eligible to submit an FPP and be considered for funding for the same project in the future, you must resubmit an EOI.

6.3. Full project proposal stage

The most promising projects from the EOI stage will be invited to submit a full project proposal (FPP), which will be evaluated by peer reviewers.

The FPP form and further guidance will be made available to the selected project teams.

7. Projects and funding agreements

After receiving the notice of project approval, applicants must enter into a collaborative research agreement with all project collaborators or a funding agreement (non-repayable transfer payment) with the NRC. If an agreement cannot be finalized within a reasonable time frame, funding may be reallocated to other projects.

8. Contact information

Direct any enquiries to NRC.QuantumComputing-Informatiquequantique.CNRC@nrc-cnrc.gc.ca.

Submit your completed EOI by email no later than 11:59 pm ET on November 10, 2023 to the Applied Quantum Computing Challenge program at NRC.QuantumComputing-Informatiquequantique.CNRC@nrc-cnrc.gc.ca.

Annex A. Selection criteria for expressions of interest

The below 6 criteria will be used to evaluate EOI applications. While each criterion will be equally weighted in the evaluation process, consideration will also be given to regional diversity and distribution across streams and strategic areas.

  1. Methodology

    Describe how the project will be carried out, including a high-level description of the tasks and methodology.

    When answering this question, consider the following:

    • Does the project have a well-developed methodology?
    • Does your response describe how the project will be carried out, including a high-level description of the tasks and methodology?
    • Is the methodology logical and viable?
  2. Project team and resources

    Detail the roles, ability and capacity of your researchers or organization and any collaborators to undertake the work over the duration of the project and to provide continued support upon completion.

    When answering this question, consider the following:

    • Do the project manager, technical/scientific team and partner organizations have the ability and capacity to deliver the project over its lifetime?
    • Does the team have the required expertise to perform this project?
    • Does the team have a history of collaboration?
    • Is there a clear distribution of roles and the input required from the different partners?
    • What is the percent of work distribution among the different actors on the team?
  3. Alignment with scope

    Provide a clear statement of how the project addresses the objective and the priorities of the scope.

    When answering this question, consider the following:

    • Does the project align with the scope?
  4. Addressing a gap

    Provide a clear statement of the technology and knowledge gap(s) that the project will address and explain how the project will address the gap(s).

    When answering this question, consider the following:

    • Does the project address a significant gap that could potentially lead to further advancements, demonstrations or commercial deployment (provide a rationale in statement)?
  5. Innovativeness

    How is the proposed project innovative or novel? Provide context on similar projects already being undertaken in Canada and elsewhere and describe how this project is different.

    When answering this question, consider the following:

    • Is the project sufficiently novel/innovative?
    • Will the project produce a clear advancement of the proposed technology?
  6. Economic and social impacts

    Describe the project's potential economic and social impact(s) (e.g., reduced costs, new revenue streams, job creation, increased public confidence).

    When answering this question, consider the following:

    • Are the proposed economic or social impacts of the project significant and do they address the economic goals of the program?

Annex B. General terms and conditions

Ethics and the responsible conduct of research

Any individual or organization that receives funding must demonstrate the highest standards of research ethics and scientific integrity. This includes a declaration by the principal investigator or project administrator on behalf of the research team and their organizations that there are no real or apparent conflicts of interest that could influence the application and evaluation processes. It also includes the commitment to comply with any other ethics and integrity rules that may be applicable to the location where the research will be conducted. Each research team member must respect the NRC's research and scientific integrity policy and the conflict of interest policy.

Other government co-funders

To facilitate co-funding, the NRC may work with federal, provincial or territorial funding organizations across Canada. By giving the NRC the authority to share your proposal with other government funders, you are authorizing the NRC to explore possible co-funding opportunities. The NRC will not share proposals without your formal consent.

Proactive disclosure

The applicant acknowledges that the NRC must comply with the Government of Canada's Guidelines on the Reporting of Grants and Contributions Awards, which require that the NRC publish information about the EOIs it receives. This information can include, but is not limited to, identity of the applicant, project title, summary description of the project and project objectives. The applicant acknowledges that the NRC may elect to publish the required information on its website.