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.

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.