Sathya Subramanian

Dr Sathyawageeswar Subramanian
Room
213,
Wolfson Building,
Parks Road, Oxford OX1 3QD
United Kingdom
Biography
I am a Royal Society University Research Fellow and Helen Zhang Non-Stipendiary Research Associate at Jesus College.
I have previously held positions as a Senior Research Associate (Unestablished Assistant Professor) in Cambridge, and as Assistant Professor (Research-focused), Research Fellow, and Postdoctoral Research Associate in Warwick.
- 2025-* : Royal Society University Research Fellow, Department of Computer Science, University of Oxford
- 2023-2025 : Senior Research Associate, Department of Computer Science, University of Cambridge
- 2022-2023 : 1851 Research Fellow, Department of Computer Science & DIMAP, University of Warwick
- 2020-2022 : Postdoctoral Research Associate, Department of Computer Science & DIMAP, University of Warwick
- 2016-2020 : PhD, St. Catharine's College & DAMTP, University of Cambridge
Research Interests
- Quantum Computing
- Theoretical Computer Science
- Quantum Information
Broadly, my work addresses challenges in quantum algorithms and complexity theory, learning theory, machine learning, and property testing, and the applications thereof to theoretical physics.
Some recent works include:
- Unconditional Pseudorandomness against Shallow Quantum Circuits
with S Ghosh and W Zhan
arXiv:2507.18796 - Quantum Channel Testing in Average-Case Distance
with G Rosenthal, H Aaronson, A Datta, and T Gur
arXiv:2409.12566
If you are interested in working with me, feel free to reach out over email to discuss opportunities (see Research Opportunities for more details).
Teaching and Supervision
In Lent term 2023-24 and Michaelmas Term 2024-25, I lectured Quantum Computation for Part III of the Mathematical Tripos at the University of Cambridge. I also supervised three Part III essay students, on "Quantum Algorithms for Non-Abelian HSP and StateHSP" and "Fault-Tolerant Quantum Computation".
Awards and Distinctions
- 2025-* : Royal Society University Research Fellowship
- 2025-* : Helen Zhang Non-Stipendiary Research Associate at Jesus College, Oxford
- 2023-2025 : College Research Associateship, Sidney Sussex College, Cambridge
- 2023 : Faculty of Science, Engineering and Medicine PostDoc Prize, University of Warwick
- 2022-2025 : Royal Commission for the Exhibition of 1851 Research Fellowship in Science and Engineering
- 2016-2020 : Cambridge-India Ramanujan Scholarship (Cambridge Trust + SERB, Govt. of India)
- 2015-2016 : Pemanda-Monappa Scholarship (Cambridge Trust)
Professional Activities
- 09/2024 : Invited Young Researcher at the 11th Heidelberg Laureate Forum
- 09/2024 : Dagstuhl Seminar 24381 on Computational Complexity
- Local organiser of CCC 2023 (with Tom Gur and Artur Czumaj)
Selected Publications
Quantum Catalytic Space
with Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, and Quinten Tupker
TQC 2025 Leibniz International Proceedings in Informatics (LIPIcs), Volume 350
Quantum Circuits surpass Biased Threshold Circuits in Constant-Depth
with Min-Hsiu Hsieh, Leandro Mendes, and Michael Oliveira
Nature Communications 16 (2025)
TQC 2024
QPL 2024
Information-theoretic generalization bounds for learning from quantum data
with Matthias Caro, Tom Gur, Cambyse Rouzé, and Daniel Stilck França
COLT 2024
TQC 2024
A remark on the quantum complexity of the Kronecker coefficients
with Christian Ikenmeyer
ACM Transactions on Quantum Computing
QIP 2024
Quantum Ridgelet Transform: Winning the Neural Network Lottery Ticket
with Hayata Yamasaki, Satoshi Hayakawa, and Sho Sonoda
ICML 2023
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
with Vahid R. Asadi, Alexander Golovnev, Tom Gur, and Igor Shinkar
QIP 2023
Sublinear quantum algorithms for estimating von Neumann entropy
with Min-Hsiu Hsieh and Tom Gur
QIP 2022
A quantum search decoder for Natural Language Processing
with Johannes Bausch and Stephen Piddock
Quantum Machine Intelligence 3 16, 2021
Quantum algorithm for estimating Renyi entropies of quantum states
with Min-Hsiu Hsieh
Physical Review A 104, 022428 (2021)
Learning with optimized random features: Exponential Speedup by Quantum ML
with Hayata Yamasaki, Sho Sonoda, and Masato Koashi
NeurIPS 2020
Implementing smooth functions of a Hermitian matrix on a quantum computer
with Steve Brierley and Richard Jozsa
Journal of Physics Communications 3(6), 65002 (2019)
Do black holes store negative entropy?
with Koji Azuma and Go Kato
Progress in Theoretical and Experimental Physics (PTEP)
Stable non-spherical configurations of rotating magnetized white dwarfs
with Banibrata Mukhopadhyay
Monthly Notices of the Royal Astronomical Society 454(1), pp. 752-765 (2015)
(You can find all of my papers and preprints here.)
Thesis: Quantum Algorithms for Matrix Problems and Machine Learning
PhD thesis, 2020
Supervised by Richard Jozsa
Hiring and Research Opportunities
Together with Prof. Sergii Strelchuk, we have several opportunities for young researchers interested in quantum computation, with a focus on computational complexity theory, classical simulation, and the development and application of novel quantum algorithms.
Our work addresses fundamental challenges at the frontiers of quantum computing and its applications (e.g. bioinformatics). Broadly, we are interested in developing sophisticated algorithm design and analysis tools to realise the potential of quantum computers, while generating a deeper understanding of the theoretical limits of quantum computation. In particular, some of our active directions of investigation are:
- Classical simulation of quantum systems and the limits of efficient computation.
- Quantum complexity theory and quantum learning theory.
- Quantum algorithms and their applications, including emerging directions in bioinformatics and pangenomics.
Our research centres on the mathematical theory and techniques that underpin computation and the physical principles of information. We welcome inquiries from outstanding students and postdoctoral researchers with a strong interest in the intersection of algorithms, physics, and mathematics. Candidates with backgrounds in mathematics, theoretical computer science, theoretical physics, or related disciplines are particularly well suited. For more details, see:
We encourage candidates to contact us over email. Please include: (1) Your CV; and (2) a 1–2 paragraph cover letter describing relevant past research (if any), your future interests, and why you would like to work with us. As we receive a high volume of inquiries, we may take at least a week to reply.
I also have DPhil/PhD and postdoc positions, as well as short internships, available to start in October 2026 and funded by the Royal Society through my University Research Fellowship, to work with me on my URF research programme on beyond worst-case analysis of quantum algorithms. We encourage candidates with a strong background in mathematics to reach out—I'd be glad to discuss how your skills could contribute to our current research and future projects. See the pages linked above for more details.