Sagnik Chatterjee
About Me
I am a PhD student in the BraQIIIT lab at IIITDelhi, where I am very fortunate to be advised by Debajyoti Bera. Previously, I was employed at Oracle Financial Software Services (OFSS) in Bengaluru.
My research
My main area of research lies at the intersection of quantum computing and learning theory, and involves developing algorithms for discriminative and generative tasks under various noise models and proving theoretical bounds for convergence, generalization, and speedups.
Contact
Office: B513, New Academic block, IIITD
Email: sagnikc [at]
iiitd [dot] ac [dot]
in
Research
Efficient Quantum Agnostic Improper Learning of Decision Trees.
with
Tharrmashastha SAPV
and
Debajyoti Bera
We show how to efficiently learn decision
trees in the
agnostic quantum PAC setting,
particularly without membership
queries.
To the best of our knowledge,
this is the first algorithm (quantum or classical) to learn decision trees in
polynomial time without membership queries. We also give quantum decision tree
learning algorithms for both
the realizable setting and random classification noise model,
again without
membership queries.
 We construct the first efficient quantum agnostic boosting algorithms by giving a quantum generalization of the potentialbased boosting algo rithm by Kalai and Kanade. Our algorithm shows the standard quadratic speedup in the VC dimension of the weak learner compared to the classical case. It also has the lowest dependence on the bias of the learner out of all current quantum boosting algorithms.
 Next, we show construct a quantum agnostic weak learner by designing a quantum version of the classical GoldreichLevin algorithm that works with biased function oracles. In general, even coming up with weak learners in the agnostic setting is a challenging task, which makes our construction of independent interest for designing quantum ensemble learning setups.
 Finally, we use our boosting algorithm to convert the agnostic quantum weak learner into a polynomialtime quantum algorithm for improper agnostic learning of decision trees.
[PDF ]
[Image Credit]Quantum boosting using domainpartitioning hypotheses.
with Rohan Bhatia, Parmeet
SinghChani and
Debajyoti Bera
Accepted at QTML'22
for a short talk. Poster accepted at QIP'22.
Abstract:
This work answers an open question
regarding the existence of quantum boosting algorithms for weak learners with
nonbinary hypotheses. Our QRealBoost algorithm has provable theoretical
guarantees for convergence, generalization bounds, and quantum speedup (using noisy
and probabilistic quantum subroutines) versus both classical boosting algorithms and
other quantum adaptive boosting algorithms.
We also perform empirical evaluations and report encouraging observations on quantum
simulators by
benchmarking the convergence performance of QRealBoost against QAdaBoost, AdaBoost,
and RealBoost on a subset of the
MNIST dataset and Breast Cancer Wisconsin dataset.
[QMI version (under review)] [QTML version (arXiv)] [poster] [slides]
[Image Credit]Applying QAOA+ to the graph matching problem.
with
Debajyoti Bera
Extended Abstract accepted at AQIS'20. Poster
accepted at QIP'21.
Abstract:
Counting problems with respect to matchings are #Phard; which precludes the
existence of efficient deterministic
classical algorithms for creating superpositions over all distinct matchings and all
maximal matchings. In this work, we try to achieve these superpositions for
2regular graphs by designing polynomial depth QAOA+ style circuits with novel
mixing operators. We also evaluate the advantages of starting with the Wstate and
empirically demonstrate that for 2regular graphs, our algorithm has a better lower
bound for the expected matching size compared to the uniform
distribution over all matchings.
[arXiv] [poster] [slides]
Talks
IIITDelhi Theory Reading Group Talk, 2023
This was the inaugural talk of the biweekly IIITDelhi Theory Reading GroupIIITDelhi Theory Reading Group. I presented the paper "Improved Quantum Query Upper Bounds based on Classical Decision Trees" by Cornelisson, Mande, and Patro.
 CornelissenMandePatro
 My notes.
Reference papers
Refresher Module, 2022
This was a short course I taught at IIITDelhi as part of a refresher module on
Operating Systems during the Monsoon 2022 semester. The focus of the course was
revising the behaviour of the Ccompiler with respect to the system memory at an
introductory level. The main topics covered were control flow, pointers, arrays,
strings, dynamic memory allocation, intermediate stages of compilation, and using
tools like gdb and valgring for debugging.
Lecture 1,
Lecture 2,
Lecture 3.
IITDelhi Theoretical CS Seminar, 2022
This was a talk at the weekly Theoretical CS seminar at IIT Delhi on the joint work with my advisor, Rohan Bhatia, and Parmeet Singh Chani. See above for details.
 ChatterjeeBhatiaSingh ChaniBera
 ArunachalamMaity
Reference papers
Faculty Development Program, 2020
This was an invited talk at the Faculty Development Program at the JNTU, Anantapuram, India. The talk focuses on giving an overview of Quantum Optimization and Quantum Machine Learning. My Slides.
Evariste Invited Talk, 2020
This was a talk I gave for Evariste – IIITD’s Theory and Math club.
Abstract: Shallow Quantum Circuits are the quantum analogs of
constant depth classical
circuits, which became a focal point of interest following the proof of
unconditional
separation between SQC’s and constant depth bounded fanin classical circuits by
Bravyi et al.
We discussed the motivations behind research on SQC’s and some interesting
separation results (noisy as well as noiseless)
between SQC’s and strictly local classical circuits, geometrically local classical
circuits, and constant
depth classical circuits.
Slides and
Video
(Video is internal to IIITD).
Complexity Theory, 2020
Course Presentation.

Original Paper : Oracle separation of BQP and PH (RazTal).  Blog Posts: Boaz Barak, Scott Aaronson, Lance Fortnow, Stanford blog post.
 My Slides.
References
Gong Show Talk, 2019
This was a Gong Show talk I gave at the 4th Advanced School of CSE, hosted by the Israel Institute of Advanced Studies, Jerusalem. I have linked the slides, and the video below. I have also provided my revised notes which I had contributed towards the “Teach Me Quantum” category of the IBMQ awards (20192020), in which we won the second place prize.
 HarrowHassidimLloyd'09
 Ambainis'10
 WossnigZhaoPrakash'17
 ChildsKothariSomma'17
 My Notes and Slides.
Reference papers
CoCurriculars
Young Quantum  2023
I was selected to attend YouQu2023, which is a meeting for PhD scholars and postdoctoral fellows to be organized by the Quantum Information and Computation group of HarishChandra Research Institute (HRI), Prayagraj (Allahabad), which aims to provide a platform for young researchers working in the broad areas of quantum information theory and related fields to encourage discussions and stimulate new collaborations and interactions.
QISE 2021 Workshop
I was the only grad student to be a part of the 2021 workshop on Quantum Information Science and Engineering (colocated with FSTTCS 2021) organizing committee. This is the website for the workshop (desktop browsers recommended).
2020 Workshop on Boolean Functions
I was selected to attend a workshop on Sensitivity, Query Complexity, Communication Complexity and Fourier Analysis of Boolean Functions organized by the Indian Statistical Institute, Calcutta.
The 4th Advanced Winter School by IIAS 2019
I was one of the two grad students from India to be selected for this prestigious winter school organized by the Israel Institute for Advanced studies, at the Hebrew University of Jerusalem. The school served as brief introductions to the fields of quantum algorithms, quantum error correction, quantum supremacy, delegation and verification, interactive proofs, cryptography, and Hamiltonian complexity along with detailed TA sessions for a week. Check out the youtube video of my Gong Talk on the HHL algorithm (starts around the 6 min mark).
IBMQ Awards 2019
We finished runners up in the “Teach Me Quantum” category of the IBMQ awards (20192020). Check out the Github repo for the course here. We designed an 11week undergraduate course covering concepts in quantum physics, quantum chemistry, mathematics, complexity theory, cryptography, and ensemble based learning and much more. The main goal of this course is to serve as a starting point for people from backgrounds in physics, mathematics, chemistry and computer science with exercises tailored specifically towards these domains.
Miscellaneous
Free Courses and Books (TCS)
 Randomized Algorithms by James Aspnes
 Advanced Complexity Theory by Hamed Hatami
 Computational Complexity by Manoj M. Prabhakaran
 Communication Complexity by Mark Bun
 Computational Social Choice by Rohit Vaish
 Analytical Toolkit in Computer Science by Hemanta K. Maji
 A Theorist's toolkit by Ryan O'Donnell
 Data Stream Algorithms by Amit Chakraborti
 Theory of Metric Embeddings by Harald Räcke
 Lecture notes on metric embeddings by Jiří Matoušek
 Algorithms book by Jeff Erickson
 Introduction to Theoretical Computer Science by Boaz Barak
 Lecture Notes by Tim Roughgarden
 Analysis of Boolean Functions by Ryan O'Donnell
 Probabilistic Method in Combinatorics by Yufei Zhao
Free Courses and Books (Quantum)
 Introduction to Quantum Computing by Sevag Gharibian
 Introduction to Quantum Information Theory by Mark M. Wilde
 Quantum Complexity Theory by Scott Aaronson
 Quantum Complexity Theory by Sevag Gharibian
 Quantum Computing lecture notes by Ronald de Wolf
Free Courses and Books (Learning Theory)
 Sample Complexity and Uniform Convergence Part 1 and Part 2: Eli Upfal
 Machine Learning by Ronald Rivest and Mona Singh
 Machine Learning Theory by Akshay Krishnamurthy
 Foundations of Modern Machine Learning by Nika Haghtalab
 Learning Theory by Ambuj Tewari
 Machine Learning Theory by Maria Florina Balcan
 Understanding ML by Shai ShalevShwartz and Shai BenDavid
 Convex Optimization: Algorithms and Complexity by Sébastien Bubeck
 2019 Mathematics of Machine Learning Graduate Summer School
 Topics and Techniques in Distribution Testing by Clément Canonne
Expository Resources (TCS)
 Metric Embeddings (FOCS22 workshop) by Hung Le
 Five Proofs of Chernoff's Bound with Applications by Wolfgang Mulzer
 Edmond's Blossom Algorithm by James S. Plank
 Tossing a biased coin by Michael Mitzenmacher
 Determining the direction of a coin's bias by William Hoza
 Part 1 and Part 2 on Multivariate Gaussians by Chuong B. Do
 Understanding Ladner's Theorem by Sanjoy Das
 Reservoir Sampling: Florian Hartmann, Stephen N. Pallone
 Morris' algorithm by Gregory Gundersen
 The Unique Games Conjecture by Scott Aaronson
 Hastad's switching lemma by Victor Lecomte
 Plancherel's trick by Victor Lecomte
Expository Resources (Quantum)
 Youtube playlist on Density Matrix and Mixed States by Diego Emilio
 QAOA literature survey by Kunal Marwaha
 A list of Open and Solved quantum problems by IQOQI Vienna
Expository Resources (Learning Theory)
 Website on Algorithms With Predictions
 Diffusion Models : Calvin Luo, Lilian Weng, CVPR 2022 Tutorial
 Generative Flows : Lilian Weng, Yoshua Bengio
 Learning Theory Notes by Gene Li
 Dijkstra's in Disguise by Eric Jang
Expository Resources (others)
 Probability Cheatsheet by William Chen and Joe Blitzstein
 Inequalities Cheatsheet by László Kozma
 Notes and visualizations on Linear Algebra by Kenji Hiranabe
 The We(a)ekly Quiz by Clement Cannone
 Expository Papers on Algebra and Number Theory by Keith Conrad
Curated Articles
 The Value of Science by Richard Feynman
 The Limits of Quantum Computers by Scott Aaronson
 Advice to PhD students by Oded Goldreich
 3 qualities of successful PhD students by Matt Might
 Writing a good introduction by Jim Kurose
 How to write a ML paper by Jakob Foerster
 Writing Technical Articles by Henning Schulzrinne
 The importance of stupidity in scientific research by Martin A. Schwartz
 Presenting a Technical Talk by Nick Feamster
 Top 10 ways to Lose your Audience
Others
 BraQIIIT Lab Reading Group.
 My Feedly Opml File (download)
 Curated StackExchange Links