Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing
arXiv:2409.10301 · doi:10.1103/PhysRevResearch.7.023142
Abstract
Industrially relevant constrained optimization problems, such as portfolio optimization and portfolio rebalancing, are often intractable or difficult to solve exactly. In this work, we propose and benchmark a decomposition pipeline targeting portfolio optimization and rebalancing problems with constraints. The pipeline decomposes the optimization problem into constrained subproblems, which are then solved separately and aggregated to give a final result. Our pipeline includes three main components: preprocessing of correlation matrices based on random matrix theory, modified spectral clustering based on Newman's algorithm, and risk rebalancing. Our empirical results show that our pipeline consistently decomposes real-world portfolio optimization problems into subproblems with a size reduction of approximately 80%. Since subproblems are then solved independently, our pipeline drastically reduces the total computation time for state-of-the-art solvers. Moreover, by decomposing large problems into several smaller subproblems, the pipeline enables the use of near-term quantum devices as solvers, providing a path toward practical utility of quantum computers in portfolio optimization.
References in corpus (20)
- Modularity and community structure in networks
- Quantum algorithm for solving linear systems of equations
- Perspectives of quantum annealing: Methods and implementations
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Nonlinear shrinkage estimation of large-dimensional covariance matrices
- Cleaning large correlation matrices: tools from random matrix theory
- Introduction to Random Matrices - Theory and Practice
- Challenges and Opportunities in Quantum Optimization
- Community detection for correlation matrices
- Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
- Network Community Detection On Small Quantum Computers
- Multilevel Combinatorial Optimization Across Quantum Architectures
- Quantum speedup of branch-and-bound algorithms
- Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
- Constrained Optimization via Quantum Zeno Dynamics
- Parameter Setting in Quantum Approximate Optimization of Weighted Problems
- GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
- End-to-end resource analysis for quantum interior point methods and portfolio optimization