John Kallaugher Group
John is an Assistant Professor in the Department of Computer Science. He obtained his PhD from the University of Texas at Austin in 2021, where he was advised by Eric Price. He then spent four years as a Senior Member of Technical Staff at Sandia National Laboratories in Albuquerque, New Mexico, USA, before joining NUS in 2025. He is originally from London, UK.
CQT Fellow
Centre for Quantum Technologies
Assistant Professor
Department of Computer Science, National University of Singapore
John Kallaugher Group
We investigate which kinds of problems can be solved with or about quantum computers in extremely resource-constrained settings. Examples include:
What kind of problems can be solved by quantum algorithms with very few qubits? When are those same problems intractable for classical algorithms with few bits? [link, link]
What is the smallest amount of interaction with a quantum object needed to answer interesting questions about it? [link]
We approach these questions from the perspective of theoretical computer science, looking for provable and optimal bounds on what is possible. We are particularly interested in finding properties that tell us something about the difficulty of many problems at the same time. [link, link]
Recent papers
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
A Quantum Advantage for a Natural Streaming Problem
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
How to Design a Quantum Streaming Algorithm Without Knowing Anything About Quantum Computing
Hamiltonian Locality Testing via Trotterized Postselection
