Talk Information 08/15/2025

Abstract: NISQ quantum supremacy aims to demonstrate that shallow (i.e., low-depth) random quantum circuits can generate output distributions that are classically intractable to simulate, even for the world’s most powerful supercomputers. In this work, we explore the problem of quantum circuit verification from both software and hardware perspectives. First, we address the task of determining whether two constant-depth quantum circuits are functionally equivalent—a fundamental challenge in verifying circuit transformations. Next, we investigate the relationship between a quantum state’s complexity—specifically, the time required to generate the state—and the sample complexity of learning it. In the regime of low state complexity, we establish that meaningful information about the state can be extracted efficiently, even from a single copy. The main idea is to focus on the marginals.

Bio: Nengkun Yu is a faculty member in the Department of Computer Science at Stony Brook University. He received both his Bachelor’s and Ph.D. degrees from Tsinghua University. Before joining Stony Brook, he was affiliated with the University of Technology Sydney. His research interests lie in quantum learning and quantum programming. His work has been recognized with two ACM SIGPLAN Distinguished Paper Awards, at OOPSLA and PLDI, respectively.