Shouvanik Chakrabarti

We introduce new theoretical mechanisms for quantum speedup in the global optimization of nonconvex functions, broadening the scope of quantum advantage beyond traditional tunneling-based explanations. By establishing a rigorous correspondence between the spectral properties of Schrödinger operators and classical Langevin diffusion, we identify regimes where a real-space adiabatic algorithm (RsAA) can significantly outperform classical stochastic gradient-based methods. Leveraging this connection and novel non-asymptotic versions of well-known semi-classical results, we provide polynomial (in the dimension $d$) runtime bounds for RsAA on rotated block-separable functions, and offer theoretical evidence that black-box classical algorithms require exponential time for optimization in these settings, thereby generalizing and formalizing prior work by Leng et al (arXiv:2311.00811). While we can design certain specialized, structure-aware classical algorithms that can efficiently optimize these functions, we further show that the quantum ground state exhibits remarkable robustness to nontrivial perturbations. Leveraging recent advances in the study of the hypercontractivity of Schr\"{o}dinger operators, we construct new families of nonconvex functions for which RsAA achieves polynomial-time optimization, whereas both off-the-shelf and structure-aware classical algorithms incur exponential computational costs. These results provide new insight into quantum-classical separations in nonconvex optimization and highlight tractable and general pathways to advantage in this setting.

This work investigates the possibility of quantum speedups for continuous optimization through quantum Hamiltonian simulation. We establish the first rigorous query complexity bounds for unconstrained convex optimization via a fully-specified instance of digital quantum annealing, based on the non-adiabatic Quantum Hamiltonian Descent (QHD) framework. In the process, we derive the first rigorous resource estimates for digital quantum simulation Schr\"odinger operators that depend only on input simulation parameters, given black-box evaluation access to a separable $G$-Lipschitz potential $b(t)f(x)$. We apply these simulation bounds to assess the complexity of optimization in the high-dimensional regime. Our annealing schedule achieves \emph{arbitrarily fast} convergence rates in the evolution time, with computational time determined solely by the cost of discretization. We show that a $G$-Lipschitz convex function can be optimized to an error of $\epsilon$ with $\widetilde{\Ocal}(d^{1.5} G^2 R^2/\epsilon^2)$ queries, given a starting point that is Euclidean distance $R$ from optimal. Under reasonable assumptions about the query complexity of simulating general Schr\"odinger operators and choice of initial state, we show that $\widetilde{\Omega}(d/\epsilon^2)$ queries are necessary. As a result, QHD does not appear to offer improvements over classical zeroth order methods when $f$ is accessed via exact black-box evaluations. However, we show that the QHD algorithm can tolerate $\widetilde{\Ocal}(\epsilon^3 /d^{1.5} G^2 R^2)$ noise in function evaluation, and as a result, provides a super-quadratic query advantage over the best existing noise-tolerant classical algorithms in the high-dimensional setting. We leverage this to design a quantum algorithm for stochastic convex optimization that offers a super-quadratic speedup over all known classical algorithms in this regime. The algorithms also outperforms existing zeroth-order quantum algorithms for noisy (with the same noise tolerance) and stochastic convex optimization in this setting. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization obtained through a dynamical algorithm.

We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over classical methods. We build upon prior works by Hastings~(\textit{Quantum}, 2020) and Schmidhuber~\textit{et al.}~(\textit{Phys.~Rev.~X.}, 2025), and address key limitations by introducing a native qubit-based encoding for the Kikuchi method, enabling explicit quantum circuit constructions and non-asymptotic resource estimation. Our approach substantially reduces constant overheads through a novel guiding state preparation technique as well as circuit optimizations, reducing the threshold for a quantum advantage. We further extend the algorithmic framework to support recovery in sparse tensor PCA and tensor completion, and generalize detection to asymmetric tensors, demonstrating that the quantum advantage persists in these broader settings. Detailed resource estimates show that 900 logical qubits, $\sim 10^{15}$ gates and $\sim 10^{12}$ gate depth suffice for a problem that classically requires $\sim 10^{23}$ FLOPs. The gate count and depth for the same problem without the improvements presented in this paper would be at least $10^{19}$ and $10^{18}$ respectively. These advances position tensor problems as a candidate for quantum advantage whose resource requirements benefit significantly from algorithmic and compilation improvements; the magnitude of the improvements suggest that further enhancements are possible, which would make the algorithm viable for upcoming fault-tolerant quantum hardware.

Quantum mechanics provides cryptographic primitives whose security is grounded in hardness assumptions independent of those underlying classical cryptography. However, existing proposals require low-noise quantum communication and long-lived quantum memory, capabilities which remain challenging to realize in practice. In this work, we introduce a quantum digital signature scheme that operates with only classical communication, using the classical shadows of states produced by random circuits as public keys. We provide theoretical and numerical evidence supporting the conjectured hardness of learning the private key (the circuit) from the public key (the shadow). A key technical ingredient enabling our scheme is an improved state-certification primitive that achieves higher noise tolerance and lower sample complexity than prior methods. We realize this certification by designing a high-rate error-detecting code tailored to our random-circuit ensemble and experimentally generating shadows for 32-qubit states using circuits with ≥ 80 logical (≥ 582 physical) two-qubit gates, attaining 0.90±0.01 fidelity. With increased number of measurement samples, our hardware-demonstrated primitives realize a proof-of-principle quantum digital signature, demonstrating the near-term feasibility of our scheme.

Achieving computational advantage using NISQ devices on practically useful problems is a long standing challenge. We report two papers that experimentally demonstrate a concrete application, namely certified randomness generation, which could be useful for multi-party cryptographic protocols and improving imperfect physical sources of randomness. Both papers involve substantial theoretical contributions to the protocol. We devise a realistic protocol that maximizes practical hardness. The verifier first asks the server to prepare a quantum state using a random circuit and then sends a random measurement basis right before the result must be received. This is repeated for many rounds. We show complexity theoretic evidence for entropy generation and provide improved entropy bounds against adversaries with oracle access to the random circuits. We also construct an end-to-end application of randomness amplification of imperfect sources into nearly perfect randomness, notably achieving everlasting security which uplifts computational security to information theoretic security.

Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} in general but of great practical importance, and it is valuable to identify algorithmic speedups to expand the domain of problems that can be solved in practice. It has proven challenging to identify super-quadratic quantum speedups for ILPs. A primary difficulty is that most classical algorithms that handle ILPs with many constraints are global and exhaustive, whereas quantum frameworks that offer the potential for super-quadratic speedups leverage the local properties of the objective function and feasible set. We address this difficulty by considering quantum algorithms for Gomory's group relaxation, a relaxation of an ILP that is obtained by removing the nonnegativity constraints from variables that are positive in the optimal solution of the linear programming relaxation, while keeping integrality of the decision variables. We present a classical algorithm that is competitive with known alternatives that solves the group relaxation via a local search, and a corresponding quantum algorithm that under reasonable technical conditions offers a super-quadratic speedup. When the group relaxation satisfies a non-degeneracy condition analogous to (albeit stronger than) that found in linear programming, our approach yields an optimal solution to the original integer program. In other cases, the group relaxation can improve downstream branch-and-cut solvers by reducing the integrality gap, a behavior that we numerically show to be typical for some practically interesting ILPs.