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