Sathya Subramanian

Dr Sathyawageeswar Subramanian

Royal Society Research Fellow

E: sathya.subramanian @ cs.ox.ac.uk

Room 213, Wolfson Building, Parks Road, Oxford OX1 3QD
United Kingdom

Themes:

• Quantum
• Algorithms and Complexity Theory

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

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

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.