End-to-end resource analysis for quantum interior point methods and portfolio optimization

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/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 pre-factors, 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.

40 pages, 15 figures. v2: minor corrections and updates to match journal version

References in corpus (28)

• Quantum algorithm for solving linear systems of equations
• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Surface code quantum computing by lattice surgery
• Quantum Data Fitting
• Quantum machine learning: a classical perspective
• A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
• Even more efficient quantum computations of chemistry through tensor hypercontraction
• Preconditioned quantum linear system algorithm
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Efficient phase-factor evaluation in quantum signal processing
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Lattice Surgery with a Twist: Simplifying Clifford Gates of Surface Codes
• Universal quantum computing with twist-free and temporally encoded lattice surgery
• Quantum SDP-Solvers: Better upper and lower bounds
• Product Decomposition of Periodic Functions in Quantum Signal Processing
• Resilience of quantum random access memory to generic noise
• Experimental realization of 105-qubit random access quantum memory
• Quantum algorithms and lower bounds for convex optimization
• Quantum algorithms for Second-Order Cone Programming and Support Vector Machines
• Scalable and High-Fidelity Quantum Random Access Memory in Spin-Photon Networks
• Faster quantum and classical SDP approximations for quadratic binary optimization

Cited by in corpus (6)

• Quantum computing for finance
• Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications
• Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
• Quantum state preparation via piecewise QSVT
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs