Marco Pistoia

The Sherrington-Kirkpatrick (SK) model serves as a foundational framework for understanding disordered systems. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum optimization algorithm whose performance monotonically improves with its depth $p$. In this work, we introduce a new equivalence between the task of evaluating the energy of QAOA applied to the SK model in the infinite-size limit and the task of simulating a spin-boson system, which we show can be done with modest cost using matrix product states. Using this equivalence, we optimize QAOA parameters and provide numerical evidence that QAOA obtains a $(1-\epsilon)$ approximation to the optimal energy with circuit depth $\mathcal{O}(n/\epsilon^{\infiniteSizeLimitOneOverEta})$ in the average case, with $\varepsilon\lesssim\infiniteSizeLastpError\%$ at $p=\infiniteSizeLastp$. We then use these optimized QAOA parameters to evaluate the QAOA energy for finite-sized instances with up to $30$ qubits and find convergence to the ground state consistent with the infinite-size limit prediction. Our results provide strong numerical evidence that QAOA can efficiently approximate the ground state of the SK model in the average case.

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.

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.

Client authentication (CA) is a cryptographic protocol where a server tries to validate the identity of a client. Fehr et. al. proposed a CA protocol with pre-shared basis information between the client and server which has a nice key recycling property, where secrets including the pre-shared basis can be securely reused after each successful round. We extend the protocol to a practical setting by including decoy state and error correction, but the leakage of pre-shared basis information via multi-photon events limits the performance of such a protocol. As such, we propose the use of a pseudorandom number generator (PRNG), assumed to be secure only during each run of the protocol, to perform basis selection to reduce information leakage. A formal proof of the protocol security is provided by modifying the entropic uncertainty relation to account for basis generated by a PRNG, which could be of independent interest as it may be applicable to other protocols such as quantum key distribution. An experimental implementation of the protocol, with appropriate post-selection, was performed to demonstrate its feasibility. We also designed a CA protocol secure in the practical setting with only two rounds of communication: a challenge by the server and a response by the client.