End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization

Alexander M. Dalzell, B. David Clader, Grant Salton, Mario Berta, Cedric Yen Yu Lin, David A. Bader, Nikitas Stamatopoulos, Martin J.A. Schuetz, Fernando G.S.L. Brandão, Helmut G. Katzgraber, William J. Zeng

Research output: Contribution to journalArticlepeer-review

Abstract

We study quantum interior-point methods (QIPMs) for second-order cone programming (SOCP), guided by the example use case of portfolio optimization (PO). We provide a complete quantum circuit-level description of the algorithm from problem input to problem output, making several improvements to the implementation of the QIPM. We report the number of logical qubits and the quantity and/or depth of non-Clifford T gates needed to run the algorithm, including constant factors. The resource counts we find 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, which lead to concrete resource estimates for the PO use case. 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, due primarily to large constant prefactors, poorly conditioned linear systems, and a fundamental reliance on costly quantum state tomography, fundamental improvements to the QIPM are required for it to lead to practical quantum advantage.

Original languageEnglish (US)
Article number040325
JournalPRX Quantum
Volume4
Issue number4
DOIs
StatePublished - 2023

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Computer Science(all)
  • Mathematical Physics
  • Physics and Astronomy(all)
  • Applied Mathematics
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'End-To-End Resource Analysis for Quantum Interior-Point Methods and Portfolio Optimization'. Together they form a unique fingerprint.

Cite this