Prateek P. Kulkarni

Research Interests

I am broadly interested in what quantum computers can and cannot do efficiently — both in terms of query and computational complexity. On the algorithms side, I think about quantum speedups for combinatorial and algebraic problems, and how structural properties of inputs (such as entanglement or symmetry) govern the cost of simulation and compilation. On the learning and testing side, I am drawn to questions about how efficiently a quantum learner can recover or test properties of unknown Boolean functions and quantum states, and what separates quantum from classical sample complexity. I also have a growing interest in the interplay between coding theory and complexity — particularly how list-decoding and local testability ideas inform hardness and pseudorandomness in the quantum setting.

Papers

1. Quantum Algorithms for Approximate Graph Isomorphism Testing Prateek P. Kulkarni Quantum Computing Theory in Practice (QCTiP 2026) [arXiv]
2. Entanglement-Dependent Error Bounds for Hamiltonian Simulation Prateek P. Kulkarni Theory of Quantum Computation, Communication and Cryptography (TQC 2026) [arXiv]

Talks

Service

Contact

Education