Aditya Morolia

Publications

Mind the Gap? Not for SVP Hardness under ETH!

with Divesh Aggarwal, Rishav Gupta.
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.

On the practicality of quantum sieving algorithms for the shortest vector problem

with Joao F. Doriguello, George Giapitzakis, Alessandro Luongo.
QCTIP 2025 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 Regularized Least Squares

with Shantanav Chakraborty, Anurudh Peduri.
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.
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, COM1-03-19 - Meeting Rm 1 @ COM1 Friday, 21 March 2025, 2:00 PM

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.

Lower bounds for lattice sieving via approximate nearest neighbour search.

Divesh's Group Seminars, COM3-02-70 02 Feb, 2024, 12 noon.

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.

Lattice sieving via quantum random walks.

Divesh's Group Seminars, COM3-02-70 6 Oct, 2023, 1pm

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.

Lattice sieving for shortest vector problem via nearest neighbour search.

Divesh's Group Seminars, COM3-02-70 29 Sept, 2023, 1pm.

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.

Quantum Computing for Software Engineers

India Developers' Exchange, Goldman Sachs, Hyderabad, Hyderabad, India March 2023

Abstract

Introducing Quantum Computing with the least amount of math possible.

CQT CS Talk on 'Quantum Algorithms for Regularized Least Squares'

Centre for Quantum Technologies, Singapore, Centre for Quantum Technologies, Singapore November 2023

Abstract

Gave a talk based on joint work on variable time quantum algorithms for least squares.

Introduction to Quantum Signal Processing and applications to Linear Systems

Singapore QML Seminar, NUS, Singapore November 2023

Abstract

Gave a talk based on joint work on variable time quantum algorithms for least squares.

Guest Lecture on 'Applications of Linear Algebra'

IIIT Hyderabad, Hyderabad, India May 2022

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.

Quanntum Signal Processing with applications to Linear Systems

IIIT Hyderabad, Hyderabad, India April 2022

Abstract

Introduction to block encodings, quantum signal processing, quantum singular value transformation and least squares optimization at CQST Talks, IIIT Hyderabad.

PCPs and Hardness of Approximation

Theory Reading Group seminar, IIIT Hyderabad, Hyderabad, India January 2021

Abstract

Brief intro to Dinur's proof of the PCP theorem.

Quantum Approximate Counting

Theory Reading Group seminar, IIIT Hyderabad, Hyderabad, India August 2020

Abstract

Started 'Seminar Saturdays', as a part of the 'Theory Reading Group' at IIIT Hyderabad by giving a talk on quantum approximate counting.