Publications
- Mind the Gap? Not for SVP Hardness under ETH! with Divesh Aggarwal, Rishav Gupta.
- On the practicality of quantum sieving algorithms for the shortest vector problem with Joao F. Doriguello, George Giapitzakis, Alessandro Luongo.
- Quantum Regularized Least Squares with Shantanav Chakraborty, Anurudh Peduri.
arXiv
Abstract
We prove new hardness results for fundamental lattice problems under the Exponential Time Hypothesis (ETH). Building on a recent breakthrough by Bitansky et al. [BHIRW24], who gave a polynomial-time reduction from $\mathsf{3SAT}$ to the (gap) $\mathsf{MAXLIN}$ problem-a class of CSPs with linear equations over finite fields-we derive ETH-hardness for several lattice problems. First, we show that for any $p \in [1, \infty)$, there exists an explicit constant $\gamma > 1$ such that $\mathsf{CVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Closest Vector Problem) does not admit a $2^{o(n)}$-time algorithm unless ETH is false. Our reduction is deterministic and proceeds via a direct reduction from (gap) $\mathsf{MAXLIN}$ to $\mathsf{CVP}_{p,\gamma}$. Next, we prove a randomized ETH-hardness result for $\mathsf{SVP}_{p,\gamma}$ (the $\ell_p$-norm approximate Shortest Vector Problem) for all $p > 2$. This result relies on a novel property of the integer lattice $\mathbb{Z}^n$ in the $\ell_p$ norm and a randomized reduction from $\mathsf{CVP}_{p,\gamma}$ to $\mathsf{SVP}_{p,\gamma'}$. Finally, we improve over prior reductions from $\mathsf{3SAT}$ to $\mathsf{BDD}_{p, \alpha}$ (the Bounded Distance Decoding problem), yielding better ETH-hardness results for $\mathsf{BDD}_{p, \alpha}$ for any $p \in [1, \infty)$ and $\alpha > \alpha_p^{\ddagger}$, where $\alpha_p^{\ddagger}$ is an explicit threshold depending on $p$. We additionally observe that prior work implies ETH hardness for the gap minimum distance problem ($\gamma$-$\mathsf{MDP}$) in codes.QCTIP 2025 PQCrypto 2026 arXiv
Abstract
One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of lattice problems like the shortest vector problem (SVP), which asks to find the shortest non-zero vector in an integer lattice. Asymptotic quantum speedups for solving SVP are known and rely on Grover's search. However, to assess the security of lattice-based cryptography against these Grover-like quantum speedups, it is necessary to carry out a precise resource estimation beyond asymptotic scalings. In this work, we perform a careful analysis on the resources required to implement several sieving algorithms aided by Grover's search for dimensions of cryptographic interests. For such, we take into account fixed-point quantum arithmetic operations, non-asymptotic Grover's search, the cost of using quantum random access memory (QRAM), different physical architectures, and quantum error correction. We find that even under very optimistic assumptions like circuit-level noise of $10^{-5}$, code cycles of 100 ns, reaction time of 1 $\mu$s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require $\approx 10^{13}$ physical qubits and $\approx 10^{31}$ years to solve SVP on a lattice of dimension 400, which is roughly the dimension for minimally secure post-quantum cryptographic standards currently being proposed by NIST. We estimate that a 6-GHz-clock-rate single-core classical computer would take roughly the same amount of time to solve the same problem. We conclude that there is currently little to no quantum speedup in the dimensions of cryptographic interest and the possibility of realising a considerable quantum speedup using quantum sieving algorithms would require significant breakthroughs in theoretical protocols and hardware development.Quantum Journal, April 2023 arXiv
Abstract
Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from overfitting, leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general $\ell_2$-regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result. To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.Academic Writings
- Notes on lattices I helped write. This was when I was a teaching assistant for advanced algorithms (lattice algorithms) course taught by Divesh. You probably also wanna look at Oded Regev’s notes.
- Notes on Quantum Pseudoentanglement and pseudorandom quantum states I wrote with my friends from CQT.
- Some notes on Approximate Nearest Neighbour Search I worked on with my friends from NUS.
- My MS thesis, “Quantum Algorithms for Regularized Least Squares”.
- Notes on Adiabatic Quantum Computing and Optimization.
- Some notes on analysing the master equation for qubit systems.
- Some introductory notes on quantum computing for 2018.
- A video introducing PCPs from a hardness of approximation perspective. You should probably watch Ryan O’Donnell’s lecture.
- Modelling the stock market using game theory.
Talks
- Quantum vs. classical complexity of learning total functions from oracles, and formalising learnability. Divesh's Group Seminars Friday, 21 March 2025
- Lower bounds for lattice sieving via approximate nearest neighbour search. Divesh's Group Seminars 02 Feb, 2024
- Lattice sieving via quantum random walks. Divesh's Group Seminars 6 Oct, 2023
- Lattice sieving for shortest vector problem via nearest neighbour search. Divesh's Group Seminars 29 Sept, 2023
- Quantum Computing for Software Engineers India Developers' Exchange, Goldman Sachs, Hyderabad March 2023
- CQT CS Talk on 'Quantum Algorithms for Regularized Least Squares' Centre for Quantum Technologies, Singapore November 2023
- Introduction to Quantum Signal Processing and applications to Linear Systems Singapore QML Seminar November 2023
- Guest Lecture on 'Applications of Linear Algebra' IIIT Hyderabad May 2022
- Quanntum Signal Processing with applications to Linear Systems IIIT Hyderabad April 2022
- PCPs and Hardness of Approximation Theory Reading Group seminar, IIIT Hyderabad January 2021
- Quantum Approximate Counting Theory Reading Group seminar, IIIT Hyderabad August 2020
Abstract
Suppose I give you an arbitrary oracle that encodes a total Boolean function $f$. How many queries would you need to learn the complete truth table of $f$? What about when I give you coherent access to the oracle as well, and you have a large enough quantum computer? We'll start with these questions, and try to learn how learning works, in the exact and PAC models. This talk is roughly based on three papers: https://arxiv.org/abs/quant-ph/9805006 (FOCS'98), https://arxiv.org/abs/1001.0018 (IPL 2010) and https://arxiv.org/abs/quant-ph/0007036 (CCC2001). However, we will probably only see the first one with the gory details.Abstract
The shortest (non-zero) vector problem (SVP) on a lattice forms the basis for a majority of the proposed post quantum cryptosystems. Lattice sieving is currently the best known algorithm to solve SVP. Given the importance of the problem, it has received significant attention in the past two decades, leading to several (largely heuristic) improvements over the initial ASK Sieve (https://dl.acm.org/doi/10.1145/380752.380857). Most improvements rely on locality sensitive hashing to speed up the approximate nearest neighbour search (which forms the core subroutine of lattice sieving.) In this talk, we present lower bounds for lattice sieving (Laarhoven, Crypto 2021), and for the approximate nearest neighbour search problem (Rubinstein, STOC 2018). We highlight the possibility of a stronger lower bound on lattice sieving via Rubinstein'18.Abstract
Building upon the contents of the talk in the previous week, we will first describe a framework for lattice sieving which can then be extended into novel classical and quantum algorithms for the shortest vector problems. We will mainly focus on the quantum algorithm using random walks on a Johnson graph, which achieves a SoTA asymptotic complexity. Ref: https://dl.acm.org/doi/10.5555/2884435.2884437, https://eprint.iacr.org/2021/570.Abstract
The asymptotic complexity of SVP and related problems is important to determine the NIST security standards for various lattice based encryption schemes. Today we will discuss how nearest neighbour search via random product codes and hashing can be used to create new algorithms for SVP. Ref:https://dl.acm.org/doi/10.5555/2884435.2884437, https://eprint.iacr.org/2021/570.Abstract
Introducing Quantum Computing with the least amount of math possible.Abstract
Gave a talk based on joint work on variable time quantum algorithms for least squares.Abstract
Gave a talk based on joint work on variable time quantum algorithms for least squares.Abstract
I took a guest lecture for the Linear Algebra course taught by Prof. Siddhartha Das at IIIT Hyderabad. I covered rank-nullity theorem, eigenvalues and eigenvectors, with applications to toy problems in dynamical systems, graph theory and random walks.Abstract
Introduction to block encodings, quantum signal processing, quantum singular value transformation and least squares optimization at CQST Talks, IIIT Hyderabad.Abstract
Brief intro to Dinur's proof of the PCP theorem.Abstract
Started 'Seminar Saturdays', as a part of the 'Theory Reading Group' at IIIT Hyderabad by giving a talk on quantum approximate counting.Academic Service
- 2025: Sub-reviewer for AQIS 2025; AsiaCrypt 2025; FSTTCS 2025; TCC 2025; Eurocrypt 2025.