Gadget design - towards embedding computational hard problems to physical devices.

by Prof. Jinguo Liu

Wednesday 25 Dec 2024, 09:00 → 11:00 Asia/Taipei

Abstract:
This talk is about embedding computational hard problems to physical devices, with a focus on the independent set problem. The physical devices usually feature low-dimensional structures. In the first part of the talk, we will discuss the solution space properties of computational hardness of problems with low-dimensional structures (SIAM J. Sci. Comput. 45, A1239–A1270). In the second part, we will discuss how to design gadgets for embedding a set of computational hard problems to physical devices (PRX Quantum 4, 010316). Finally, I want to introduce a work in progress on a unified framework for problem reductions.