Atithi Acharya

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.