The problem of computing the distance of classical error-correcting codes was shown to be NP-hard by Alexander Vardy in 1997. Recently, Kapshikar and Kundu extended this result by proving the hardness of computing distances of quantum codes. In this talk, I will prove the hardness of computing the minimum distance of a specific class of quantum codes defined using graphs, referred to as graph states. Graph states play a key role in various quantum applications, including cryptography and communication. As a further application of our techniques, we also prove the hardness of computing the distance of classical codes with constant rate in the interval (0,1/2].
This work is in collaboration with Elena Grigorescu (University of Waterloo) and Eric Samperton (Purdue University).
Short Bio:
I am currently a PhD student in the Department of Computer Science at Purdue University, jointly advised by Elena Grigorescu and Eric Samperton. My research interests lie in Coding Theory (both classical and quantum) and the Analysis of Boolean Functions.
