Sagnik Chatterjee

About Me

I am an incoming postdoc at the University of Latvia, Riga, hosted by Prof. Andris Ambainis. I recently defended my thesis (May 2025), advised by Prof. Debajyoti Bera at the BraQIIIT lab in IIIT-Delhi.

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

I am on the academic job market for positions starting in Fall 2026.

Contact

Office: B-513, R&D block, IIITD
Email: sagnikc[at]iiitd[at]ac[at]in

News

May'25: Defended my Ph.D. Thesis titled Designing Quantum Learning Algorithms for Classical Objects.
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: Our paper on Generalization Bounds for Dependent Data using Online-to-Batch Conversion was accepted at AISTATS'25.
October'24: Gave a talk on generalization bounds of statistical learning algorithms at the ACMU seminar series, ISI Kolkata.
Aug-Oct'24: Visiting Prof. Sourav Chakraborty at ISI Kolkata for a research internship.
July'24: Presented our work on Efficient Quantum Agnostic Improper Learning of Decision Trees at the Recent trends in Algorithms (RTA) 2024 workshop in IACS, Kolkata.
June'24: Gave a talk on Quantum Learning of Fourier-sparse Boolean functions at the ACMU seminar series, ISI Kolkata.
May'24: Presented our work on Efficient Quantum Agnostic Improper Learning of Decision Trees at AISTATS'24 in Valencia, Spain.
Feb'24: Gave 3 invited lectures on advanced quantum algorithms at the Quantum Computing Semester organized by the CMI, India.
Jan'24: Our paper on Efficient Quantum Agnostic Improper Learning of Decision Trees was accepted at AISTATS'24.
Jan'24: Presented a poster on Efficient Quantum Agnostic Improper Learning of Decision Trees at QIP'24 in Taipei, Taiwan.
Jan'24: Teaching Assistant for Theory of Computaton.
Sep'23: Gave a Ketchup talk at IIIT-Delhi.
Sep'23: Gave an invited talk at the IDA seminar in Czech Technical University, Prague.
Sep'23: Gave an invited talk at the University of Latvia, Riga.
Jul-Sep'23: Visiting Czech Technical University, Prague for a research internship.
Jun'23: Our paper on Quantum boosting using domain-partitioning hypotheses accepted at Quantum Machine Intelligence.
Jun'23: Attended the JTG Summer School at IISc Bangalore.
Feb'23: Gave an 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: Presented our paper Quantum boosting using domain-partitioning hypotheses at QTML'22 in Naples, Italy.
Aug'22: Quantum boosting using domain-partitioning hypotheses accepted at QTML'22 for a short talk.
Apr'22: Qualified my Ph.D. Comprehensive Exam.
Mar'22: Teaching Assistant for Data Structures and Algorithms.
Mar'22: Gave an invited talk on quantum boosting algorithms at the IITD Theoretical CS seminar.
Mar'22: Poster presented at QIP'22.
Dec'21: Organized and conducted the QISE'21 workshop at FSTTCS'21.
Aug'21: Teaching Assistant for Modern Algorithm Design.
Jan'21: Teaching Assistant for Theory of Computation.
Jan'21: Poster presented at QIP'21.
Dec'20: Gave an invited talk on Quantum Machine Learning at the Faculty Development program hosted by 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 in the IBMQ Awards; Teach Me Quantum Category.
Jan'20: Teaching Assistant for Theory of Computation.
Dec'19: Attended the 4th Winter School in CS organized by the IIAS, HUJI in Jerusalem, Israel.

Research

Realization of maximally-entangling two-qutrit gates using the Cross-Resonance scheme.

with Yash Saxena and Tharrmashastha SAPV

Under Submission.

We introduce the GCR scheme for realizing maximally entangling 2-qutrit gates on fixed-frequency transmons. Unlike previous works, our gates are parametric and directly allow for entanglement on the 1-2 levels.

[arXiv | code]

Abstract Citation

In this letter, we introduce the generalized cross-resonance (GCR) scheme, which is a comprehensive theoretical framework for realizing maximally entangling two-qutrit gates on fixed-frequency transmons that generalize the qubit-centric cross-resonance (CR) interaction beyond the 0-1 subspace. We use the GCR scheme to design parametric two-qutrit gates that act on the 0-1 and 1-2 energy transitions of transmons. Our gates improve upon the existing works in two aspects -
a) Firstly, our gates directly allow for entanglement on the 1-2 levels, unlike previous works.
b) Secondly, our gates are parametric in nature, enabling us to construct multiple entangling gates of interest, whereas the purview of prior works was limited to the construction of specific qutrit gates.
Using our gates we prepare a two-qutrit Bell state with a fidelity of 98.33 ± 0.01%. We note that in our setup, the complete Bell state preparation requires a ∼ 514 ns pulse sequence to prepare the Bell state, which is less than the gate time of cross-Kerr-based entangling gates.

@misc{saxena2025Realization,
title = {Realization of maximally-entangling two-qutrit gates using the Cross-Resonance scheme.},
author = {Saxena, Yash and Chatterjee, Sagnik and {SAPV}, Tharrmashastha},
year = {2025},
eprint={2504.15265},
url={https://arxiv.org/abs/2504.15265},
}

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

with Manuj Mukherjee and Alhad Sethi.

Accepted at AISTATS 2025.

We give generalization 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 polynomial-time and sample quantum algorithm for agnostically learning Boolean functions with size-\(t\) 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, Volume 5. 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}
}