Method and system for solving a dynamic programming problem

A non-transitory computer readable storage medium is disclosed for storing computer-executable instructions which, when executed, cause a computer to perform a method for solving a dynamic programming problem using a quantum computer, the method comprising:

• receiving an indication of a dynamic programming problem, the dynamic programming problem comprising a plurality of transition kernels,
• receiving data representative of the dynamic programming problem, generating at least one oracle for the transition kernels of the dynamic programming problem,
• until a stopping criterion is met:
• determining at least one linear programming problem for the dynamic programming problem,
• solving the at least one linear programming problem using a quantum computer comprising the generated at least one oracle to determine at least one solution, and
• providing the determined at least one solution;
• and
• providing a solution to the dynamic programming problem.

A computer comprising:

• a central processing unit;
• a display device;
• a communication port;
• and
• a memory unit comprising an application for solving a dynamic programming problem using a quantum computer, the application comprising,
• instructions for receiving an indication of a dynamic programming problem, the dynamic programming problem comprising a plurality of transition kernels,
• instructions for receiving data representative of the dynamic programming problem,
• instructions for generating at least one oracle for the transition kernels of the dynamic programming problem,
• instructions for until a stopping criterion is met:
• determining at least one linear programming problem for the dynamic programming problem,
• providing the at least one linear programming problem to a quantum computer comprising the generated at least one oracle to determine at least one solution,
• obtaining the determined at least one solution, and
• providing the determined at least one solution;
• and
• instructions for providing a solution to the dynamic programming problem.