# Sagnik Chatterjee

## About Me

I am a doctoral candidate at IIIT-Delhi, advised by Dr. Debajyoti Bera, affiliated with the BraQIIIT group. Previously, I worked 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. My work involves developing quantum ensembling algorithms under various learning models and proving theoretical bounds for convergence, generalization, and speedups. Scroll down for more details.

I am also interested in variational quantum optimization algorithms for NISQ hardware, algorithms for computational social choice, and a complexity theoretic approach to neural networks.

## Contact

Office: B-513, R&D block, IIITD

Email: sagnikc [at] iiitd [dot] ac [dot]
in

# Papers

## Quantum boosting using domain-partitioning hypotheses.

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.

###
*arXiv*
*poster*
*slides*

## Applying QAOA+ to the graph matching problem.

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*
*video*

# Selected Talks

## Introduction to C.

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.

## Quantum Boosting of Domain Partitioning Hypotheses.

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.

These are the Slides for the talk.

- Quantum Boosting of Domain-Partitioning hypotheses: Chatterjee-Bhatia-Singh Chani-Bera
- Quantum Boosting: Arunachalam-Maity

### Reference papers

## An overview of Quantum Optimization and Quantum Machine Learning

This was an invited talk at the Faculty Development Program at the JNTU, Anantapuram, India. The talk focuses on introductory concepts and serves as a gateway into the field. The total duration of the talk was 3 hours divided over two sessions. These are the Slides for the talk.

## Oracle Separation of BQP and PH

This was a presentation at my Complexity Theory Course in the Fall of 2020. The talk focuses on the paper by
Ran
Raz and Avishay Tal, and explains the main concepts and proof techniques explored in the paper. The total
duration of the talk was 50 minutes with 10 minutes for Q&A.
MySlides.
**Original Paper** Oracle separation of BQP and PH
(Raz-Tal).

- Boaz Barak.
- Scott Aaronson.
- Lance Fortnow.
- Stanford blog post.

## Blog Posts

## The HHL algorithm for solving linear system of equations.

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.

My Notes,
Slides.

- Quantum algorithm for solving linear systems of equations: Harrow-Hassidim-Lloyd'09
- Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations: Ambainis'10
- A quantum linear system algorithm for dense matrices: Wossnig-Zhao-Prakash'17
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision: Childs-Kothari-Somma'17

## Reference papers

## Shallow Quantum Circuits.

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 will be discussing the motivations behind research on SQC’s and some interesting separation results
between SQC’s and strictly local classical circuits, geometrically local classical circuits, and constant
depth classical circuits. We also briefly look at these separations in the noisy case, and under the
interactive model. We also briefly look at these separations in the noisy case, and under the interactive
model.

Slides and
Video
(*Video is internal to IIITD*).

- Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games: Terhal-DiVincenzo'02
- The Computational Complexity of Linear Optics: Aaronson-Arkhipov'11
- Quantum advantage with shallow circuits: Bravyi-Gosset-Koenig'18
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits: Watts-Kothari-Schaeffer-Tal'19
- Average-Case Quantum Advantage with Shallow Circuits: Le Gall'19
- Quantum advantage with noisy shallow circuits in 3D: Bravyi-Gosset-Koenig-Tomamichel'19

## Reference papers

# Co-Curriculars

## The 4th Advanced Winter School by IIAS

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 course covering concepts in quantum physics, quantum chemistry, mathematics, complexity theory, cryptography, ensemble based learning and much more. This is an excellent starting point for people from backgrounds in physics, mathematics, chemistry and computer science with exercise questions tailored specifically towards these domains.

## QISE 2021 Workshop (colocated with FSTTCS 2021)

I was the only grad student to be a part of the 2021 workshop on Quantum Information Science and Engineering organizing committee. My duties consisted mostly of technical logistics since this was an international workshop with overlapping timezones. This is the website for the workshop (desktop browsers recommended).

## Workshop on Boolean Functions at ISI Calcutta

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.

# Miscellaneous

## Courses and Books (Theoretical Computer Science inclined)

- Algorithms book by Jeff Erickson
- Introduction to Theoretical Computer Science by Boaz Barak
- Notes by Tim Roughgarden
- Modern Algorithm Design by Syamantak Das**
- Randomized Algorithms by James Aspnes
- Communication Complexity course by Mark Bun
- Theory of Computation by Debajyoti Bera**
- 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
- Introduction to Quantum Computing by Sevag Gharibian
- Quantum Computing lecture notes by Ronald de Wolf
- Introduction to Quantum Information Theory by Mark M. Wilde
- Quantum Complexity Theory by Scott Aaronson
- Quantum Complexity Theory by Sevag Gharibian
- 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

## Expository Resources

- Probability Cheatsheet by William Chen and Joe Blitzstein
- Inequalities Cheatsheet by László Kozma's
- Notes and visualizations on Linear Algebra by Kenji Hiranabe
- Notes and visualizations on Edmond's Blossom Algorithm by James S. Plank
- Part 1 and Part 2 on the definition of P, NP, NP-complete and NP-hard
- QAOA literature survey byKunal Marwaha
- The We(a)ekly Quiz by Clement Cannone
- Part 1 and Part 2 on Multivariate Gaussians by Chuong B. Do
- Expository Papers by Keith Conrad
- Why is every p-norm convex?
- How is a quantum superposition different from a mixed state?
- Understanding Ladner's Theorem by Sanjoy Das
- Reservoir Sampling: blog by Florian Hartmann, and notes by Stephen N. Pallone
- Morris' algorithm by Gregory Gundersen
- Controlled rotations in HHL: Question 1, and Question 2
- Question regarding prior knowledge of Eigenspectrum in HHL
- The Unique Games Conjecture by Scott Aaronson
- Is there a general method of expressing optimization problem as a Hamiltonian?
- Open quantum problems
- Understanding Diffusion Models by Calvin Luo

## Interesting Articles on Research and Science

- 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
- How to write a ML paper by Jakob Foerster
- The importance of stupidity in scientific research by Martin A. Schwartz
- Statement of Purpose by Abubakar Abid