Despite much work on quantum algorithms, there are few examples of practically relevant computational tasks that are known to admit substantial quantum speedups for practical instance sizes after all hidden costs and caveats are considered. Portfolio optimization (PO) is a practically important problem that can be solved via Quantum Interior Point Methods (QIPMs) via a standard mapping to a Second-Order Cone Programs (SOCP). Preliminary numerical evidence in prior literature was consistent with an asymptotic quantum speedup. But will this solution be practical?

We present a more complete resource estimate of the QIPM, reporting the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm, including constant factors. The resource estimate incorporates several technical improvements to the algorithm, most notably, improved methods for arbitrary state preparation and block-encoding.  The resource counts depend on instance-specific parameters, such as the condition number of certain linear systems within the problem. To determine the size of these parameters, we perform numerical simulations of small PO instances. Our numerical results do not probe large enough instance sizes to make conclusive statements about the asymptotic scaling of the algorithm. However, already at small instance sizes, our analysis suggests that fundamental improvements to the QIPM are required for it to lead to practical quantum advantage. We discuss why this is the case and where this leaves us in the search for end-to-end practical quantum advantages.

Based on joint work with a number of collaborators in arXiv:2206.03505 & arXiv:2211.12489.

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*