! The results of this competition will not be benchmarked automatically. Each submission will be reviewed manually by a jury of experts.
Goals
- Create a novel and useful application for the Vehicle Routing Problem (VRP).
- Translate the VRP to an instance of the Max Cut Problem.
- Implement QAOA on a GPU using CUDA-Q to solve a small Max Cut Problem.
- Investigate options including circuit cutting and distributed computing to scale QAOA to handle larger Max Cut problems.
- Relate your solution to the Max Cut problem back to the original VRP and communicate your work effectively.
Context
The Vehicle Routing Problem (VRP) addresses the question: "What is the optimal set of routes for a fleet of vehicles to deliver to a given set of customers?" One can think of the VRP as a generalization of the Traveling Salesman Problem (TSP). VRP has applications in many sectors, especially in logistics and transportation.
The Max Cut Problem is a combinatorial optimization problem that asks for the maximum number of edges that can be cut by partitioning the nodes of a graph into two disjoint subsets.
CUDA-Q
NVIDIA CUDA-Q is a unified programming model designed for a hybrid setting, which allows integrating and programming quantum processing units (QPUs), GPUs, and CPUs in one system. It is an open-source platform consisting of language extensions for Python and C++, and a system-level toolchain that enables application acceleration.
CUDA-Q enables GPU-accelerated system scalability and performance across heterogeneous QPU, CPU, GPU, and emulated quantum system elements.
Tasks
Task 1: Choose Your Application
Describe your chosen application:
- State the problem you want to solve.
- Explain how it relates to the VRP problem.
- Declare the variables you will use.
- Discuss the relevance and industries/sectors that could benefit from the application.
Task 2: Formulate the Solution
Explain your reasoning for your solution. Be clear and organized, writing equations when needed. Don't forget to declare the variables you are using. Diagrams, graphics, and drawings are encouraged.
You may opt to apply the clustering techniques described in
Feld et al. and
Herzog et al. to translate the Capacitated Vehicle Routing Problem (CVRP) to a Max Cut Problem.
Task 3: Implement QAOA to Solve a Small Problem Using CUDA-Q
Develop the code to implement your solution using CUDA-Q, the platform for hybrid quantum-classical computing. Here are some useful online resources:
Task 4: Run and Scale Your Problem to Larger Sizes Using Techniques Such as Circuit Cutting and Distributed Computing
- Use GPUs to run your solution.
- Determine which is the largest graph that you can solve.
- Verify your solutions classically.
- The CUDA-Q documentation describes different options for simulating circuits on GPUs.
Task 5: Present Your Results
Summarize your results in a document (.pdf or .md file) and include:
- A description of the problem you want to solve and its relationship to Max-Cut.
- Your solution.
- Your implementation and the results.
