Quantum Walks and Variational Algorithms on NP-hard Problems and Biased Dynamics: Graph Topology, Optimization and Condensed Matter Phenomena

• Grant number: 25/24799-5
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: September 01, 2026
• End date: July 31, 2029
• Field of knowledge: Physical Sciences and Mathematics - Physics - Condensed Matter Physics
• Principal Investigator: Marcos César de Oliveira
• Grantee: José Carlos Bellizotti Souza
• Host Institution: Instituto de Física Gleb Wataghin (IFGW). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
• Associated research grant: 24/00998-6 - Center for Research and Innovation on Smart and Quantum Materials (CRISQuaM), AP.CEPID

Abstract

Many science problems can be mapped into optimization problems, where one is required to find the minimum, or maximum, value of a given objective function. This fact led to scientists from different fields to develop optimization algorithms with different approaches on how to find the optimal set of parameters. However, finding global and local optimal parameters typically is a NP-hard problem and most optimizers were developed to be performed by classical computers. With the recent interest rise on quantum computers, physicists working on this field are interested on quantum optimizers, since specific sets of problems can be solved faster by using quantum computers instead of classical computers, and optimization problems are one of such sets. Variational quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA), can be used to find the optimal solution given a cost function mapped into an Ising Hamiltonian. However, the QAOA has a set of parameters that need to be optimized classically, requiring QAOA circuits to run multiple times. Optimization problems can be mapped into graph representations, and by employing Quantum Walks (QWs), one can solve the problem by a quantum walker exploring the problem graph. QWs have different approaches regarding the time domain, with each approach differing by how the quantum walker explores the graph. In this project we propose to use the different QW approaches to solve NP-hard problems, to develop a QAOA-QW hybrid model, and to investigate biased QWs and their correspondence with condensed matter systems. We expect our developed models to be useful on solving practical NP-hard problems, enabling science and industry to progress at faster paces. (AU)