Nengkun Yu, Stony Brook University

Abstract

This paper addresses the problem of checking whether two constant-depth (shallow) quantum circuits are functionally equivalent—a key task in verifying circuit transformations. Since directly simulating quantum states can be exponentially expensive, the paper introduces efficient classical decision procedures for two variants of the equivalence-checking problem. The key idea is to use local projections as constraints that uniquely determine the output state of a shallow circuit. This avoids computing the full state explicitly. The approach also enables sound and complete assertion checking for conjunctions of local projections. Experiments show practical performance: e.g., checking equivalence for 100-qubit, depth-3 circuits takes under 32 seconds.

Speaker 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.