Source-linked AI summary
Reverse Quantum Annealing Approach to Portfolio Optimization Problems
Davide Venturelli, Alexei Kondratyev
TL;DR
The paper asks how hybrid quantum-classical methods can solve discrete portfolio optimization problems represented as QUBOs on a D-Wave quantum annealer. It constructs and embeds financially motivated instances, benchmarks quantum annealing against a Genetic Algorithm, and finds that greedy-seeded reverse annealing is especially promising. The optimized reverse protocol achieves more than 100 times the average speed of corresponding forward annealing, while full machine overhead brings TTS results on par with the classical benchmark.
Problem
Discrete portfolio optimization is a hard finance problem, and prior D-Wave studies used portfolios too small to assess scaling with problem size.
Method
The paper constructs financially motivated QUBO instances, embeds them on the D-Wave Chimera architecture, and evaluates forward and greedy-seeded reverse annealing against a Genetic Algorithm.
Results
More than 100 times faster on average, optimized reverse quantum annealing outperforms corresponding forward quantum annealing in annealing-time TTS comparisons.
Takeaways & Limitations
Reverse quantum annealing appears promising for portfolio optimization as quantum-annealing technology and theory progress.
Takeaways & Limitations
Including the D-Wave machine’s full setup and iteration overhead removes the apparent advantage, leaving TTS results on par with the classical benchmark.
Abstract
from arXiv · showhide
We investigate a hybrid quantum-classical solution method to the mean-variance portfolio optimization problems. Starting from real financial data statistics and following the principles of the Modern Portfolio Theory, we generate parametrized samples of portfolio optimization problems that can be related to quadratic binary optimization forms programmable in the analog D-Wave Quantum Annealer 2000Q. The instances are also solvable by an industry-established Genetic Algorithm approach, which we use as a classical benchmark. We investigate several options to run the quantum computation optimally, ultimately discovering that the best results in terms of expected time-to-solution as a function of number of variables for the hardest instances set are obtained by seeding the quantum annealer with a solution candidate found by a greedy local search and then performing a reverse annealing protocol. The optimized reverse annealing protocol is found to be more than 100 times faster than the corresponding forward quantum annealing on average.
1 Introduction
The paper studies portfolio optimization as a difficult discrete finance problem and develops a hybrid quantum-classical approach using D-Wave quantum annealing alongside a Genetic Algorithm benchmark.
- Quantum computing is investigated for delivering high-quality discrete-optimization solutions faster than state-of-the-art classical methods.
- Portfolio optimization is a hard financial problem that also underlies many supervised and reinforcement learning tools used in finance.
- Discrete portfolio optimization can be formulated as a QUBO suitable for quantum annealers, but is harder than continuous mean-variance optimization and is NP-complete.
- The study extends mean-variance optimization to general dependence structures and discretionary views on asset and asset-combination attractiveness.
- The experiments construct instances from real market data, solve them with a hybrid quantum annealing solver, and compare results with a classical Genetic Algorithm benchmark.
2 Portfolio Optimization Beyond Markowitz
The paper formulates fund selection beyond Markowitz by encoding asset attractiveness and diversification into bucketed QUBO coefficients, while addressing cardinality and data constraints through hybrid design choices.
- The target problem selects M assets from N investible assets to maximize risk-adjusted returns for a Fund of Funds portfolio manager.
- QUBO variables encode asset selection, with linear coefficients representing standalone attractiveness and quadratic coefficients representing diversification penalties or rewards.
- The objective uses Sharpe ratios for individual asset scores and correlations for pairwise diversification coefficients.
- The instances coarse-grain Sharpe ratios and correlations into integer buckets, creating an adjustable scorecard that can incorporate portfolio-manager views.
- Large cardinality penalties can create analog-machine precision issues, motivating a hybrid adjustment of desirability values until the selected-asset count matches M.
- The benchmark uses unconstrained instances designed to have ground states selecting about N/2 assets, targeting the model’s largest combinatorial search space.
3 Quantum Annealing Hybrid Solver
The solver maps portfolio QUBOs to embedded Ising problems on the D-Wave Chimera architecture and compares forward annealing with reverse annealing initialized by greedy classical solutions.
- Chimera embedding: Because the DW2000Q Chimera graph is not fully connected, the solver uses minor embedding to represent logical variables as ferromagnetically coupled chains.
- Forward Quantum Annealing: Forward annealing drives the system from an easy initial quantum ground state toward low-energy states of the problem Hamiltonian, ending with computational-basis measurement.
- Hardware considerations: The DW2000Q is only loosely captured by the ideal Schrödinger model because open-system dynamics, parameter misspecification, and cross-talk affect its behavior.
- Reverse Quantum Annealing: Reverse annealing initializes the system with a classical bitstring, reverses the schedule to a pause point, and then resumes forward annealing.
- Reverse Quantum Annealing: The reverse protocol is motivated by escaping local minima through quantum and thermal fluctuations, followed by relaxation and local exploration during the pause.
- Hybrid initialization: Initial reverse-annealing states are generated with a classical greedy algorithm because their quality can strongly influence the process.
4 Experimental Results
The experiments benchmark greedy search, a Genetic Algorithm, forward quantum annealing, and reverse quantum annealing on parametrized portfolio instances. Reverse annealing, initialized by greedy search, provides the strongest reported time-to-solution performance, although benchmark timings exclude initialization and hardware overheads.
- Benchmark setup: 30 randomly generated instances were evaluated for each portfolio size in the benchmark set, targeting problems near the DW2000Q’s programmability limit.The largest embedded problem uses 60 assets, with approximately 60!/(30!)^2 possible portfolios when the optimal portfolio contains N/2 assets.
- Initialization: Greedy search progressively accounts for correlations and supplies the initial state S used by reverse annealing.The study also reports the percentage of instances solved directly by this heuristic as problem size changes.
- Classical benchmark: The classical benchmark uses a Genetic Algorithm that evolves binary portfolio chromosomes through selection and mutation, without crossover for these relatively short gene strings.Its parameter settings are tuned by trial and error to reach target convergence with as few objective-function calls as possible.
- Results: Reverse annealing parameter selection is simplified because forward annealing predicts a good optimal JF, while larger ρ consistently places the optimal pause later in the anneal.These observations concern operational parameter setting for new, unknown instances.
- Results: Reverse annealing is the best solver in the comparisons, achieving a median speed-up of one to three orders of magnitude over quantum annealing at minimum annealing and pause times.The comparison includes GA, forward QA, and reverse QA; GA can also be initialized with greedy search, reducing its TTS.
5 Conclusion and Next Steps
The paper presents a quantum-annealing portfolio-optimization workflow compatible with current D-Wave hardware, while emphasizing substantial measurement and hardware-scaling limitations. It concludes that reverse annealing is promising but not yet clearly the most compelling solver.
- Contribution: The resulting QUBO has integer coefficients and is densely connected, requiring compilation onto the D-Wave Chimera architecture.The authors use state-of-the-art methods for fully connected graphs.
- Instance difficulty: Greedy preprocessing solves a large part of the randomly generated instances, while typical greedy and classical heuristics are expected to fail as N increases.The instances were not filtered by difficulty because portfolio problems are not necessarily hard beforehand.
- Limitations: Reported DW2000Q times omit setup and iteration overhead; including those overheads makes reverse-annealing TTS results comparable to the classical benchmark.The omitted times include programming, thermalization, and readout.
- Future improvements: More than an order of magnitude of performance may be gained by further tuning quench and pause times, although the analysis explores only a limited parameter range.Longer pauses than 100 microseconds may benefit hard problems.
- Future improvements: Pegasus could embed almost 400 logical variables and reduce embedding overhead by at least a factor of 3, with further gains possible from additional hardware techniques.The authors conservatively expect at least an order-of-magnitude improvement from the architecture transition.
- Conclusion: The results indicate that reverse quantum annealing could become a viable portfolio-optimization choice as quantum-annealing technology and theory progress.The conclusion remains cautious about whether quantum annealing will be the most compelling solver.
Disclaimer and Declaration of Interest
The authors disclose no conflicts of interest and state that the paper is for information and discussion rather than an investment recommendation.
- Declaration of interest: The authors report no conflict of interest and accept responsibility for the paper’s content and writing.They also distinguish their opinions from those of affiliated organizations.
- Disclaimer: The paper does not constitute an offer, solicitation, or recommendation involving securities, financial instruments, or investment transactions.It is explicitly limited to information and discussion purposes.
A Geometric Brownian Motion
The appendix describes Geometric Brownian Motion as a model for asset prices and explains its discretized simulation for correlated assets. The scheme uses positive-price dynamics with monthly steps and correlated normal innovations.
- Definition: Geometric Brownian Motion is a stochastic process used to model asset prices.Its drift controls the deterministic component, while volatility represents annualized log-return variability.
- Simulation method: The integrated GBM solution is used for simulation because it prevents simulated asset prices from becoming negative at sufficiently large time steps.The portfolio example uses a one-month time step.
- Correlation: For multiple assets, the simulation uses correlated standard normal variables constructed through Cholesky decomposition of the correlation matrix.The same discretization scheme is applied jointly across the N-asset portfolio.
B Chimera Graph of DW2000Q and Embedding
Figure 4 shows the chip layout used in the experiments: the D-Wave 2000Q hosted at NASA Ames Research Center.
- Hardware layout: Figure 4 identifies the experimental chip layout as belonging to the D-Wave 2000Q at NASA Ames Research Center.The passage provides the hardware identity and location but no additional figure comparison.
C More details on parameter setting for Reverse Annealing
Parameter selection for reverse annealing is evaluated using time-to-solution across annealing times and parameter scans. The reported results identify τ = 1 μs as the most advantageous choice, while parameter optimization is performed instance by instance.
- τ = 1 μs is the most advantageous annealing time in the median TTS comparison.Figure 5 compares τ = 1 μs and 10 μs across the first 10 benchmark instances.
- Figure 5 reports median TTS over 10 instances for the mapping schemes and annealing times tested.The runs use a 99% confidence-level time-to-solution metric.
- The Figure 5 runs produced faster median TTS than the main-paper results, possibly because of finite statistics or machine-performance drift.These runs occurred more than a month earlier under lower machine utilization.
- Parameter scans vary JF and sp, selecting the lowest TTS separately for each instance.The scan procedure determines the best parameter setting used to generate the reported data.