Hybrid Quantum-Classical High-Performance Computation

Abstract:
Quantum computing enjoys some proven computational advantage over classical computers, with alluring applications: e.g., quantum system simulation, quantum chemistry, cryptography, machine learning.

However, current implementations of quantum computers are still far from resilient to effects such as dephasing and decoherence, putting them in stark contrast to the classical computing technology developed over the last century. We would like to make use of both these aspects (quantum computational power and classical computing technology), thus motivating the seek for hybrid algorithms: those that combine the two types of computation.

But, this raises the question: when limiting, for example, the maximum coherent depth to the quantum circuits used, is any quantum advantage preserved? If so, how much, and in to what relation to the limits imposed? We analyze this question from a more tractable perspective, namely, by modelling such a limitation as a limitation on the number of calls made coherently to an oracle of the problem.

We establish an interpolation regime for a particular problem (that of Eigenvalue Estimation) as a generalization of existing results in the literature,and by applying a recently developed technique, named Quantum Singular Value Transformation. We then look at prospective following results, by inspecting the classes of problems for which the maximum quantum speedup is known (but an interpolating regime is not).