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 an Senior Research Associate (Unestablished Assistant Professor) in Cambridge, and as Assistant Professor (Research-focused), Research Fellow, and Postdoctoral Research Associate in Warwick between September 2020 and September 2025.
- 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
Most of my recent work addresses (quantum) Algorithms and Complexity Theory, Learning Theory, Machine Learning, and Property Testing. I am also more broadly interested in Theoretical Physics.
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".
If you are interested in working with me as a masters or DPhil student, or postdoc, feel free to reach out over email to discuss opportunities.
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 Communications16 (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)
Preprints
Unconditional Pseudorandomness against Shallow Quantum Circuits
with Soumik Ghosh and Wei Zhan
arXiv:2507.18796
Quantum Channel Testing in Average-Case Distance
with Greg Rosenthal, Hugo Aaronson, Animesh Datta, and Tom Gur
arXiv:2409.12566
Spectral sparsification of matrix inputs as a preprocessing step for quantum algorithms
with Steven Herbert
arXiv:1910.02861
Thesis
Quantum Algorithms for Matrix Problems and Machine Learning
PhD thesis, 2020
Supervised by Richard Jozsa