Publications
- Mind the Gap? Not for SVP Hardness under ETH! with Divesh Aggarwal, Rishav Gupta, Chuanqi Zhang.
- 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.
ICALP 2026 arXiv
BibTeX
@misc{AGMZ25,
title={Mind the Gap? Not for SVP Hardness under ETH!},
author={Divesh Aggarwal and Rishav Gupta and Aditya Morolia and Chuanqi Zhang},
year={2026},
eprint={2504.02695},
archivePrefix={arXiv},
primaryClass={cs.CC},
url={https://arxiv.org/abs/2504.02695},
}
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 slides
BibTeX
@InProceedings{DGLM24, author="Doriguello, Joao F. and Giapitzakis, George and Luongo, Alessandro and Morolia, Aditya", editor="Bardet, Magali and Niederhagen, Ruben", title="On the Practicality of Quantum Sieving Algorithms for the Shortest Vector Problem", booktitle="Post-Quantum Cryptography", year="2026", publisher="Springer Nature Switzerland", address="Cham", pages="3--36", 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{\}}{\$}{\$}10-5, code cycles of 100 ns, reaction time of 1 {\$}{\$}{\backslash}upmu {\$}{\$}$\mu$s, and using state-of-the-art arithmetic circuits and quantum error-correction protocols, the best sieving algorithms require {\$}{\$}{\backslash}approx 10^{\{}13{\}}{\$}{\$}≈1013physical qubits and {\$}{\$}{\backslash}approx 10^{\{}31{\}}{\$}{\$}≈1031years to solve SVP on a lattice of dimension 400, which is roughly the dimension in which SVP is to be solved in order to break the 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.", isbn="978-3-032-22695-2" }
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
BibTeX
@article{CMP23, doi = {10.22331/q-2023-04-27-988}, url = {https://doi.org/10.22331/q-2023-04-27-988}, title = {Quantum {R}egularized {L}east {S}quares}, author = {Chakraborty, Shantanav and Morolia, Aditya and Peduri, Anurudh}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {988}, month = apr, year = {2023} }
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.
- 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
- Pseudorandom Error-Correcting Codes Divesh's Group Seminars 13 May 2026, 1:30 PM
- LoRA+: Efficient Low Rank Adaptation of Large Models COM3, NUS April 2026 slides
- Gaussian Boson Sampling CQT, NUS March 2026 slides
- Deterministic Hardness of SVP_p for all p > 2 CIFRA, Bocconi University November 2025
- Quantum Computation and Lattice Problems Divesh's Group Seminars Friday, 10th October, 1 PM
- Quantum Singular Value Transformation Divesh's Group Seminars Friday, 5th September, 1 PM
- 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
Pseudorandom error-correcting codes have recently been identified as a new cryptographic primitive, with applications to watermarking large language models and steganography. I present a construction of (zero bit) pseudorandom codes based on the hardness the planted XOR assumption and LPN, and from subexponential LPN (https://arxiv.org/abs/2402.09370).Abstract
I present the LoRA+ algorithm for efficient finetuning of large language models (https://arxiv.org/abs/2402.12354).Abstract
I present the "Jiuzhang" quantum supremacy experiment on Gaussian Boson Sampling (https://www.science.org/doi/10.1126/science.abe8770).Abstract
I will present the recent result on the deterministic hardness of SVP_p for all p > 2 by Hair and Sahai (https://eprint.iacr.org/2025/2181.pdf).Abstract
We present a quantum reduction from the unique shortest vector problem on a lattice to the Dihedral Coset Problem (Regev'03, https://arxiv.org/abs/cs/0304005v1). This is a quantum problem where one is given polynomially many states (samples) of the form (|0, x> + |1, x+d mod N>)/sqrt(2), where d \in [N] is fixed and x \in [N] is arbitrary across the samples; and the goal is to find d. This problem is connected to the classical problem of finding a hidden subgroup of the dihedral group, from its coset samples.Abstract
Wouldn't it be nice if there was only one algorithm for us to study, that could solve all of our problems? We could then spend our time thinking about more useful things, like cryptography against string theory computers. Or perhaps read some nice fiction. In this talk I'll tell you about why this is kinda true with the current state of quantum algorithms. I'll talk about quantum singular value transformation, an algorithm to apply polynomial transformations to the singular values of an input matrix, and possibly some applications. I'll follow "A Grand Unification of Quantum Algorithms", "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics".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.