Sagnik Chatterjee

About Me

I am a PhD student in the BraQIIIT lab at IIIT-Delhi, 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: B-513, New Academic block, IIITD
Email: sagnikc [at] iiitd [dot] ac [dot] in


Research

Decision Trees

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 potential-based 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 Goldreich-Levin 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 polynomial-time quantum algorithm for improper agnostic learning of decision trees.

[PDF ]

[Image Credit]
Ensemble Learning

Quantum boosting using domain-partitioning hypotheses.

with Rohan Bhatia, Parmeet Singh-Chani 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 non-binary 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]
Graph Matching

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 #P-hard; 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 2-regular graphs by designing polynomial depth QAOA+ style circuits with novel mixing operators. We also evaluate the advantages of starting with the W-state and empirically demonstrate that for 2-regular graphs, our algorithm has a better lower bound for the expected matching size compared to the uniform distribution over all matchings.

[arXiv] [poster] [slides]

[Image credit]

Talks

IIIT-Delhi Theory Reading Group Talk, 2023

This was the inaugural talk of the bi-weekly IIIT-Delhi Theory Reading GroupIIIT-Delhi Theory Reading Group. I presented the paper "Improved Quantum Query Upper Bounds based on Classical Decision Trees" by Cornelisson, Mande, and Patro.

IIIT-Delhi CSE Seminar, 2023

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.
Social Media: Twitter, Facebook, Instagram.

Refresher Module, 2022

This was a short course I taught at IIIT-Delhi 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 C-compiler 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.

IIT-Delhi 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.

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 fan-in 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.

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 (2019-2020), in which we won the second place prize.

Co-Curriculars

Young Quantum - 2023

I was selected to attend YouQu-2023, which is a meeting for PhD scholars and post-doctoral fellows to be organized by the Quantum Information and Computation group of Harish-Chandra 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 (2019-2020). Check out the Github repo for the course here. We designed an 11-week 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)

Free Courses and Books (Quantum)

Free Courses and Books (Learning Theory)

Expository Resources (TCS)

Expository Resources (Quantum)

Expository Resources (Learning Theory)

Expository Resources (others)

Curated Articles

Others