Skip to main content

Sathya Subramanian

Personal photo - Sathyawageeswar 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

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

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.

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.