Sparsification and Variable Reduction of Portfolio Optimization QUBOs with QAOA
By Varun, Ethan, Ryan
Our project began with a simple question: if some covariances between stocks are very small, do we need to keep all of them when optimizing a portfolio? In a quantum circuit, retaining a pairwise interaction can add gates. Removing enough interactions might make the calculation easier, but it could also change which stocks are selected. We want to measure that tradeoff and investigate better ways to decide what can be removed. We will study a portfolio that selects a fixed number of stocks and gives them equal weights. Each stock has a binary variable indicating whether it is included. Expected returns, the covariance matrix, and a penalty for selecting the wrong number of stocks can be combined into a quadratic unconstrained binary optimization problem, or QUBO. QAOA, the Quantum Approximate Optimization Algorithm, will be used to search for solutions on small instances. Mr. Hannum suggested starting with a manageable mutual fund and considering whether reduction could go far enough to shrink the matrix itself. That adds a second question to the project. Removing covariance terms makes the matrix sparser, but it does not reduce the number of stock variables. To use fewer qubits in this encoding, we would need to fix or eliminate some of those variables. We will investigate both kinds of reduction and judge the resulting portfolios using the original objective.
We will study how sparsification and asset screening interact in fixed-size portfolio selection with QAOA. In particular, we will test whether their order changes the result: should we remove weak interactions before deciding which assets to exclude, or screen the assets using the full model first? Pruning can alter the portfolios used to rank assets, so the two orders may retain different stocks even when they produce problems of the same size. We will compare both orders with each reduction applied alone and measure the resulting portfolio loss and circuit cost. The proposed contribution is an empirical study of this interaction and its effect on QAOA. Both reductions have precedents, so we will compare the order experiment with the closest existing methods. Exact solutions on small cases and compiled circuit measurements will help distinguish information lost during preprocessing from limitations of QAOA.
Smaller circuits could make portfolio optimization experiments more practical with limited quantum resources. Our code and documented experiments could give later QLab groups a starting point. Identifying which assets or interactions cannot be removed without substantial loss would also help clarify when sparsification is useful.