Sagnik Chatterjee

About Me

I am a Visiting Fellow (Postodoctoral researcher) at STCS, TIFR Mumbai, hosted by Prof. Jatin Batra.

I obtained my Ph.D. in 2025, under the guidance of Prof. Debajyoti Bera at the BraQIIIT lab in IIIT-Delhi.

My research lies at the intersection of quantum computing and computational learning theory.

Reach out!

If my research interests you, please drop me an email at chatsagnik [at] gmail [dot] com. I am also (unreliably) reachable at Xitter / Bluesky / LinkedIn.

I am on the academic job market for faculty/postdoc positions starting in Fall 2027.

News

Dec'25: Joined TIFR Mumbai as a Visiting Fellow (Postodoctoral researcher).
Oct'25: Invited talk on Generalization Bounds for Dependent Data using Online-to-Batch Conversion at the STCS seminar, TIFR Mumbai.
May'25: Defended my Ph.D. Thesis.
May'25: Invited talk on Efficient Quantum Agnostic Improper Learning of Decision Trees at the CS Colloquium, Ashoka University.
Mar'25: Invited to give a full day workshop on qunatum computing by Edunautic at IIT Delhi.
Jan'25: Invited to give a talk at the QAC 2025 Symposium.
Jan'25: Generalization Bounds for Dependent Data using Online-to-Batch Conversion accepted at AISTATS'25.
Oct'24: Invited talk on Generalization Bounds for Dependent Data using Online-to-Batch Conversion at the ACMU seminar, ISI Kolkata.
Aug-Oct'24: Visiting Prof. Sourav Chakraborty at ISI Kolkata for a research internship.
Jul'24: Efficient Quantum Agnostic Improper Learning of Decision Trees presented at the RTA'24 .
Jun'24: Invited talk on Efficient Quantum Agnostic Improper Learning of Decision Trees at the ACMU seminar series, ISI Kolkata.
Feb'24: Gave 3 invited lectures on advanced quantum algorithms in the Quantum Computing school organized by CMI, India.
Jan'24: Efficient Quantum Agnostic Improper Learning of Decision Trees accepted at AISTATS'24.
Jan'24: Poster on Efficient Quantum Agnostic Improper Learning of Decision Trees at QIP'24.
Jan'24: Teaching Assistant for Theory of Computaton.
Sep'23: Invited talk at the IDA seminar on Efficient Quantum Agnostic Improper Learning of Decision Trees in Czech Technical University, Prague.
Sep'23: Invited talk on Efficient Quantum Agnostic Improper Learning of Decision Trees at the University of Latvia, Riga.
Jul-Sep'23: Visiting Czech Technical University, Prague for a research internship.
Jun'23: Quantum boosting using domain-partitioning hypotheses accepted at Quantum Machine Intelligence.
Jun'23: Attended the JTG Summer School at IISc Bangalore.
Feb'23: Invited talk on Quantum boosting using domain-partitioning hypotheses at the IIITD CSE Department seminar.
Jan'23: Teaching Assistant for Introduction to Quantum Computing.
Nov'22: Short talk on Quantum boosting using domain-partitioning hypotheses accepted at QTML'22.
Apr'22: Qualified my Ph.D. Comprehensive Exam.
Mar'22: Teaching Assistant for Data Structures and Algorithms.
Mar'22: Invited talk on Quantum boosting using domain-partitioning hypotheses at the IITD Theoretical CS seminar.
Mar'22: Poster on Quantum boosting using domain-partitioning hypotheses presented at QIP'22.
Dec'21: Organized and conducted the QISE'21 online workshop at FSTTCS'21.
Aug'21: Teaching Assistant for Modern Algorithm Design.
Jan'21: Teaching Assistant for Theory of Computation.
Jan'21: Poster on Applying QAOA+ to the graph matching problem presented at QIP'21.
Dec'20: Conducted an online FDP on Quantum Machine Learning for JNTU, Anantapur.
Nov'20: Extended Abstract on Applying QAOA+ to the graph matching problem accepted at AQIS'20.
Aug'20: Teaching Assistant for Modern Algorithm Design.
Feb'20: Attended the Boolean Functions workshop at ISI-Kolkata.
Jan'20: Runners-Up IBMQ 2019 Awards [Teach Me Quantum Category].
Jan'20: Teaching Assistant for Theory of Computation.
Dec'19: Attended the 4th CS Winter School at IIAS, HUJI.
Jul'19: Joined IIIT-Delhi as a Ph.D. student.

Research (selected)

Generalization Bounds for Dependent Data using Online-to-Batch Conversion.

with Manuj Mukherjee and Alhad Sethi.

Accepted at AISTATS 2025.

We give error bounds for statistical learning algorithms trained on non-i.i.d. data in the Online-to-Batch setting.

[proceedings | arXiv | slides]

Abstract Citation

In this work, we give generalization bounds of statistical learning algorithms trained on samples drawn from a dependent data source both in expectation and with high probability, using the Online-to-Batch conversion paradigm. We show that the generalization error of statistical learners in the dependent data setting is equivalent to the generalization error of statistical learners in the i.i.d. setting up to a term that depends on the decay rate of the underlying mixing stochastic process, and is independent of the complexity of the statistical learner. Our proof techniques involve defining a new notion of stability of online learning algorithms based on Wasserstein distances, and employing ”near-martingale” concentration bounds for dependent random variables to arrive at appropriate upper bounds for the generalization error of statistical learners trained on dependent data.

@InProceedings{chatterjee2025Generalization,
title = {Generalization Bounds for Dependent Data using Online-to-Batch Conversion.},
author = {Chatterjee, Sagnik and Mukherjee, Manuj and Sethi, Alhad},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
pages = {2152--2160},
year = {2025},
editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz},
volume = {258},
series = {Proceedings of Machine Learning Research},
month = {03--05 May},
publisher = {PMLR},
url = {https://proceedings.mlr.press/v258/chatterjee25b.html},
}

Efficient Quantum Agnostic Improper Learning of Decision Trees.

with Tharrmashastha SAPV and Debajyoti Bera.

Accepted at AISTATS 2024.
Poster at QIP 2024.

We give the first time and sample efficient quantum algorithm for agnostically learning Boolean functions with bounded decision trees representations, w/o membership queries.

[proceedings | arXiv | slides | poster]

Abstract Citation

The agnostic setting is the hardest generalization of the PAC model since it is akin to learning with adversarial noise. In this paper, we give a \(\mathrm{poly}\left(n,{t},{\frac{1}{\varepsilon}}\right)\) time quantum algorithm for learning size \(t\) decision trees with uniform marginal over instances, in the agnostic setting, without membership queries. Our algorithm is the first algorithm (classical or quantum) for learning decision trees in polynomial time without membership queries. We show how to construct a quantum agnostic weak learner by designing a quantum version of the classical Goldreich-Levin algorithm that works with strongly biased function oracles. We show how to quantize the agnostic boosting algorithm by Kalai and Kanade (NIPS'09) to obtain the first efficient quantum agnostic boosting algorithm. Our quantum boosting algorithm has a polynomial improvement in the dependence of the bias of the weak learner over all adaptive quantum boosting algorithms while retaining the standard speedup in the VC dimension over classical boosting algorithms. We then use our quantum boosting algorithm to boost the weak quantum learner we obtained in the previous step to obtain a quantum agnostic learner for decision trees. Using the above framework, we also give quantum decision tree learning algorithms for both the realizable setting and random classification noise model, again without membership queries.

@InProceedings{chatterjee2024Efficient,
title = { Efficient Quantum Agnostic Improper Learning of Decision Trees },
author = {Chatterjee, Sagnik and SAPV, Tharrmashastha and Bera, Debajyoti},
booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics},
pages = {514--522},
year = {2024},
editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen},
volume = {238},
series = {Proceedings of Machine Learning Research},
month = {02--04 May},
publisher = {PMLR},
url = {https://proceedings.mlr.press/v238/chatterjee24a.html} }

Quantum boosting using domain-partitioning hypotheses.

with Rohan Bhatia, Parmeet Singh-Chani, and Debajyoti Bera.

Published in Quantum Machine Intelligence.
Short talk at QTML 2022.
Poster at QIP 2022.

We answer an open question on the existence of quantum boosting algorithms for weak learners with non-binary hypotheses.

[journal | arXiv | code | poster | slides]

Abstract Citation

Boosting is an ensemble learning method that converts a weak learner into a strong learner in the PAC learning framework. The \(\mathrm{AdaBoost}\) algorithm is a well-known classical boosting algorithm for weak learners with binary hypotheses. Recently, Arunachalam and Maity (ICML'20) presented the first quantum boosting algorithm by quantizing \(\mathrm{AdaBoost}\). Their algorithm, which we refer to as \(\mathrm{QAdaBoost}\) hereafter, is a quantum adaptation of \(\mathrm{AdaBoost}\) and only works for the binary hypothesis case. \(\mathrm{QAdaBoost}\) is quadratically faster than \(\mathrm{AdaBoost}\) in terms of the VC dimension of the hypothesis class of the weak learner while it is polynomially worse in the bias of the weak learner.
In this work, we address an open question by Izdebski et al. on the existence of boosting algorithms for quantum weak learners with non-binary hypotheses. We answer this question in the affirmative by developing the \(\mathrm{QRealBoost}\) algorithm motivated by the classical \(\mathrm{RealBoost}\) algorithm. The main technical challenge was to provide provable guarantees for convergence, generalization bounds, and quantum speedup, given that quantum subroutines are noisy and probabilistic. We prove that \(\mathrm{QRealBoost}\) retains the quadratic speedup of \(\mathrm{QAdaBoost}\) over \(\mathrm{AdaBoost}\) and further achieves a polynomial speedup over \(\mathrm{QAdaBoost}\) in terms of both the bias \(\gamma\) of the learner and the time taken by the learner to learn the target concept class.
Finally, we perform empirical evaluations on \(\mathrm{QRealBoost}\) and report encouraging observations on quantum simulators by benchmarking the convergence performance of \(\mathrm{QRealBoost}\) against \(\mathrm{QAdaBoost}\), \(\mathrm{AdaBoost}\), \(\mathrm{RealBoost}\), and \(\mathrm{SmoothBoost}\) on a subset of the \(\mathrm{MNIST}\) dataset and \(\mathrm{Breast Cancer Wisconsin}\) dataset.

@Article{chatterjee2023Quantum,
author={Chatterjee, Sagnik and Bhatia, Rohan and Singh Chani, Parmeet and Bera, Debajyoti},
title={Quantum boosting using domain-partitioning hypotheses},
journal={Quantum Machine Intelligence},
year={2023},
month={Jul},
day={27},
volume={5},
number={2},
pages={33},
issn={2524-4914},
doi={10.1007/s42484-023-00122-3},
url={https://doi.org/10.1007/s42484-023-00122-3}
}

Applying QAOA+ to the graph matching problem.

with Debajyoti Bera.

Extended Abstract at AQIS'20.
Poster at QIP'21.

We show how to design linear depth \(\mathrm{QAOA}+\) style circuits to obtain distributions over all distinct matchings and all maximal matchings for \(2\)-regular graphs through novel mixing operators. We also empirically evaluate the effect of different ansatzes on our QAOA+ circuit.

[arXiv | poster | slides]

Abstract Citation

The Quantum Alternating Operator Ansatz (QAOA+) framework has recently gained attention due to its ability to solve discrete optimization problems on noisy intermediate-scale quantum (NISQ) devices in a manner that is amenable to derivation of worst-case guarantees. We design a technique in this framework to tackle a few problems over maximal matchings in graphs. Even though maximum matching is polynomial-time solvable, most counting and sampling versions are #P-hard. We design a few algorithms that generates superpositions over matchings allowing us to sample from them. In particular, we get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the \(W\)-states as input. Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a \(2\)-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings. This algorithm uses a \(W\)-state as input and we prove that this input state is better compared to using the empty matching as the input state.

@article{chatterjee2020Applying,
title={Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem},
author={Chatterjee, Sagnik and Bera, Debajyoti},
journal={arXiv preprint arXiv:2011.11918},
year={2020}
}

For a complete list please see my CV.