Sagnik

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


Other Interesting Links

News

  • Jun'23 (upcoming): Will attend the JTG Summer School at IISc Bangalore.
  • Feb'23: Gave an invited talk on our QTML paper at the IIITD CSE Department seminar.
  • Jan'23: Teaching Assistant for Introduction to Quantum Computing.
  • Nov'22: Paper on 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 QISE'21 colocated with 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, at the Hebrew University of Jerusalem.

Research

Decision Trees

Efficient Quantum Agnostic Improper Learning of Decision Trees.

with Tharrmashastha SAPV and Debajyoti Bera

Abstract: We give the first polynomial-time and sample quantum algorithm for learning size-t decision trees with uniform marginal over instances, in the agnostic setting, without membership queries.

[Pre-print]

[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.

[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: We obtain non-trivial superpositions over all distinct matchings and all maximal matchings for 2-regular graphs by designing linear depth QAOA+ style circuits with novel mixing operators, and empirically evaluate the expected matching size with different ansatzes.

[arXiv] [poster] [slides]

[Image credit]

Talks

IIIT-Delhi Lattices in Computer Science, Winter 2023

Here are my notes on "Generating Hard Instances for the Short Basis problem" by M. Ajtai (ICALP 1999) for the oral component of the endsem exams for LCS.

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 IIIT-Delhi CSE Seminar 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: We discussed the motivations behind research on Shallow Quantum Circuits and some interesting separation results (noisy as well as noiseless) between SQC’s and various 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. My HHL notes are part of the course we designed for the “Teach Me Quantum” category of the 2019-20 IBMQ awards (2019-2020), in which we won the second place prize.

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

dblp