Sathyawageeswar Subramanian

Senior Research Fellow

I am an 1851 Research Fellow at the Department of Computer Science and a College Research Associate affiliated to Sidney Sussex College. I formerly held positions as an Assistant Professor (Research-focused), Research Fellow, and Postdoctoral Research Associate in the Department of Computer Science at the University of Warwick between September 2020 and August 2023.

Research Interests

Theoretical Computer Science
Quantum Computing
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.

Career

2023- : Senior Research Fellow, 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 (Host: Tom Gur)
2016-2020 : PhD, St. Catharine's College & DAMTP, University of Cambridge. Supervisor: Richard Jozsa.

Teaching

In Lent term 2023-24 and Michaelmas Term 2024-25, I lectured Quantum Computation for Part III (4th year / masters) students in Mathematics. I currently supervise three Part III essays.

Scholarships and Awards

2022-2025 : Royal Commission for the Exhibition of 1851 Research Fellowship in Science and Engineering
Sept. 2024 : Invited as a Young Researcher to the 11^th Heidelberg Laureate Forum
Sept. 2024 : Invited to Dagstuhl Seminar 24381 on Computational Complexity
2023-2025 : College Research Associateship, Sidney Sussex College, Cambridge
2023 : Faculty of Science, Engineering and Medicine PostDoc Prize, University of Warwick
2016-2020 : Cambridge-India Ramanujan Scholarship (Cambridge Trust + SERB, Govt. of India)
2015-2016 : Pemanda-Monappa Scholarship (Cambridge Trust)

Selected Publications

Quantum Circuits surpass Biased Threshold Circuits in Constant-Depth
with Min-Hsiu Hsieh, Leandro Mendes, and Michael Oliveira
Accepted for publication in Nature Communications
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
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)

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)