On experimentally relevant quantum speedups

Giuseppe Castagnoli

Adam Bouland, Wim van Dam, Hamed Joorati +2 more

Quantum computers are expected to have substantial impact on the finance industry, as they will be able to solve certain problems considerably faster than the best known classical algorithms. In this article we describe such potential applications of quantum computing to finance, starting with the state-of-the-art and focusing in particular on recent works by the QC Ware team. We consider quantum speedups for Monte Carlo methods, portfolio optimization, and machine learning. For each application we describe the extent of quantum speedup possible and estimate the quantum resources required to achieve a practical speedup. The near-term relevance of these quantum finance algorithms varies widely across applications - some of them are heuristic algorithms designed to be amenable to near-term prototype quantum computers, while others are proven speedups which require larger-scale quantum computers to implement. We also describe powerful ways to bring these speedups closer to experimental feasibility - in particular describing lower depth algorithms for Monte Carlo methods and quantum machine learning, as well as quantum annealing heuristics for portfolio optimization. This article is targeted at financial professionals and no particular background in quantum computation is assumed.

Sepehr Ebadi, Alexander Keesling, Madelyn Cain +21 more

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.

Vlatko Vedral

Haibin Liu, W. L. Yang, Jun‐Hong An +1 more

The quantum speed limit (QSL) time for open system characterizes the most efficient response of the system to the environmental influences. Previous results showed that the non-Markovianity governs the quantum speedup. Via studying the dynamics of a dissipative two-level system, we reveal that the non-Markovian effect is only the dynamical way of the quantum speedup, while the formation of the system-environment bound states is the essential reason for the quantum speedup. Our attribution of the quantum speedup to the energy-spectrum character can supply another vital path for experiments when the quantum speedup shows up without any dynamical calculations. The potential experimental observation of our quantum speedup mechanism in the circuit QED system is discussed. Our results may be of both theoretical and experimental interest in exploring the ultimate QSL in realistic environments, and may open new perspectives for devising active quantum speedup devices.