Source-linked AI summary
Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
Gili Rosenberg, Poya Haghnegahdar, Phil Goddard, Peter Carr, Kesheng Wu, Marcos López de Prado
TL;DR
The paper addresses discrete multi-period portfolio optimization with transaction costs, a problem harder than its continuous counterpart. It formulates the problem for a D-Wave quantum annealer and reports high success rates, while identifying hardware and experimental limits on problem size and statistical evaluation.
Problem
Discrete multi-period portfolio optimization is difficult because discrete trading creates a non-convex problem, while current quantum-annealing hardware limits the size of problems that can be successfully solved.
Method
The paper formulates multi-period portfolio optimization as a quadratic integer problem for quantum annealing, incorporating transaction costs and using hardware and software techniques to improve solutions.
Results
The limited experiment demonstrates high success rates and considerable improvements after fine-tuning the quantum annealer.
Takeaways & Limitations
The formulation is designed to scale so that larger problems may become solvable as quantum-annealing technology improves.
Takeaways & Limitations
For the small-scale problems studied, time to solution was comparable on classical hardware and the quantum annealer.
Abstract
from arXiv · showhide
We solve a multi-period portfolio optimization problem using D-Wave Systems' quantum annealer. We derive a formulation of the problem, discuss several possible integer encoding schemes, and present numerical examples that show high success rates. The formulation incorporates transaction costs (including permanent and temporary market impact), and, significantly, the solution does not require the inversion of a covariance matrix. The discrete multi-period portfolio optimization problem we solve is significantly harder than the continuous variable problem. We present insight into how results may be improved using suitable software enhancements, and why current quantum annealing technology limits the size of problem that can be successfully solved today. The formulation presented is specifically designed to be scalable, with the expectation that as quantum annealing technology improves, larger problems will be solvable using the same techniques.
I. THE PROBLEM
The paper formulates a multi-period portfolio problem in which an asset manager chooses investments over time while accounting for returns, risk, and transaction costs. Discrete trading constraints make the problem non-convex and harder than continuous optimization, while globally optimal trajectories can outperform independently optimized portfolios.
- The manager chooses investments across N assets and T time steps using return and risk forecasts while accounting for permanent and temporary market impact costs.
- A trajectory that jointly optimizes risk-adjusted returns can outperform the sequence of portfolios optimized independently at each time step.Rebalancing between statically optimal portfolios incurs costs.
- Trading in large or fixed lots makes the portfolio problem inherently discrete, so continuous solutions become approximations.The passage cites institutional even-lot constraints and large-block trading as examples.
- The discrete problem is non-convex and remains difficult when the covariance matrix is ill-conditioned or degenerate.
B. Previous work
Previous work established the computational difficulty of discrete portfolio optimization, developed classical approaches for single-period and continuous multi-period problems, and motivated quantum annealing for the discrete multi-period setting.
- Single-period discrete portfolio optimization is NP-complete, with prior work using branch-and-bound and heuristic algorithms.Reported classical studies include problems involving up to 200 assets.
- Continuous multi-period portfolio optimization has been solved analytically through dynamic programming when the covariance matrix is positive definite.
- Analytical trade-execution work motivates including both temporary and permanent price-impact terms.
- The paper investigates implementing a discrete multi-period portfolio problem on D-Wave’s quantum annealer, following a proposal that such problems are suitable for quantum annealing.
C. Integer formulation
The portfolio problem is expressed as a quadratic integer optimization that maximizes forecast returns while penalizing risk and transaction costs under holdings constraints.
- The formulation maximizes returns while incorporating risk, temporary market impact, permanent market impact, and other transaction costs.
- Holdings must sum to K at every time step.
- Each asset’s holdings are constrained by a maximum allowed level K′.
- The objective’s risk term uses the forecast covariance tensor Σ and risk-aversion parameter γ, while its return term is forecast returns µ multiplied by holdings w.
- Transaction-cost terms penalize changes in holdings and capture temporary costs, direct costs, and permanent price impact.
D. Extensions
The formulation extends to liquidation and offers an alternative trajectory-variance risk measure that avoids covariance-matrix estimation and does not assume normally distributed returns.
- Optimal trade execution can be represented by changing the holdings constraint and extending transaction-cost and permanent-impact terms through time T + 1 with wT +1 = 0.
- Trajectory variance provides an alternative risk measure when covariance estimates are unreliable because of limited data or illiquidity.
- The variance-based formulation avoids covariance-matrix estimation and does not assume a normal return distribution.
- Because variance is quadratic in the returns, it can be included in a quadratic integer formulation.
A. Quantum annealing
Quantum annealing encodes optimization problems as Hamiltonians and probabilistically searches for ground-state solutions. D-Wave’s sparse Chimera hardware requires minor embedding, which limits fully dense problem size and motivates attention to scalable formulations.
- Quantum annealing: Quantum annealing continuously transforms an easy ground-state problem into the target Hamiltonian, with repeated runs increasing the probability of finding the optimum.Because real devices experience external interference, quantum annealers function as heuristic solvers.
- Quantum annealing: Quantum tunnelling has been proposed to improve solution-space search and possibly speed optimization for certain problem classes.
- D-Wave hardware: D-Wave’s annealer minimizes unconstrained binary quadratic functions, using a cryogenic, shielded, high-vacuum environment to reduce disturbances.
- Quantum speedup: Whether D-Wave provides quantum speedup remains an open question, despite a reported 108 speedup over simulated annealing on a specially constructed problem class.
- D-Wave hardware: Chimera hardware contains bipartite eight-qubit unit cells connected in a square lattice, with q = 8s^2 physical qubits.
- Embedding limits: For dense square Chimera embeddings, the largest problem has V = 4s + 1 logical variables; a 1100-qubit annealer embedded approximately Vb ≃ 140 variables at density ≃ 0.1.
B. From integer to binary
The paper converts integer portfolio variables into binary representations using four encodings and incorporates constraints through penalties or encoding choices. These encodings trade variable efficiency, representable integer range, noise sensitivity, redundancy, and embedding cost.
- Encoding schemes: Four encodings—binary, unary, sequential, and partitioning—recast integer holdings into binary variables for quantum annealing.
- Encoding selection: The preferred encoding depends on the optimization problem and annealer, and Table III compares variable counts across example multi-period portfolio problems.
- Encoding trade-offs: Binary, unary, and sequential encodings trade binary-variable efficiency against the largest representable integer because efficient encodings use larger noise-sensitive coefficients.
- Encoding trade-offs: Binary encoding uses the fewest variables but represents the smallest integer range, whereas unary uses more variables but represents the largest range.
- Partition encoding: Partition encoding requires exponentially many variables but can impose complicated constraints by excluding invalid partitions, while embedding may require substantially more physical qubits.
- Encoding trade-offs: Binary and sequential encodings may require penalties for infeasible holdings when the maximum holding is not exactly representable at the chosen bit depth.
- Constraint penalties: Constraints are incorporated by rearranging, squaring, and summing constraint equations into a penalty term weighted by M > 0.
- Constraint penalties: An overly large penalty strength M increases sensitivity to system noise, so the paper selects M empirically by trial and error.
C. Numerical Results
The numerical experiments evaluate success using perturbation-aware optimality, validate solutions against exact or high-confidence solvers, and show improvements from software tuning, gauge averaging, and newer hardware.
- Experimental setup: 200 random instances per problem were tested with one quantum-annealer query using 1000 reads, on hardware with 512 or 1152 qubits.The number of active qubits was slightly smaller than the nominal hardware count.
- Read-count effects: Success rates rise with more reads for fixed problem size, while fixed read counts are expected to reduce success as problem size increases.This read-count dependence helps explain the reported results across problem sizes.
- Evaluation metric: Success S(α) measures the percentage of instances whose annealer result falls within α% of optimality under Gaussian perturbations of the problem matrix.Each instance was perturbed at least 100 times and compared with exhaustive-solver optima.
- Limitation: The variance of the success rate could not be statistically assessed because the required experimental runs exceeded available machine time.This limits uncertainty characterization of the reported success rates.
- Software enhancements: Custom software and parameter tuning produced a large improvement across all problems on the same 512-qubit hardware.The improvements combined an embedding solver, tuned identification coupling strengths, and multiple random gauges.
D. Discussion
The discussion identifies hardware and software factors that constrain quantum-annealer success rates and problem size, while suggesting several routes for improvement. Current small-scale runtime is comparable with classical hardware, and general quantum speedup for this high-precision problem remains un demonstrated.
- Hardware limitations: Intrinsic noise and coefficient-range scaling can reduce success rates, especially for this high-precision portfolio problem.The current chip’s intrinsic noise is estimated at 2%–4% of full scale.
- Hardware limitations: Sparse hardware connectivity requires identifying multiple physical qubits with one binary variable, adding strong couplings and potentially further scaling.This can reduce additional coefficients below ϵ and impact success rates.
- Hardware limitations: More qubits could enable larger problems and less noise-sensitive encodings, while inactive qubits and couplers reduce effective hardware density.Unary encoding is given as an example of an encoding less sensitive to noise than binary encoding.
- Potential improvements: Improved embeddings, calibration, majority voting, and random gauge selection are software or operational enhancements that may improve solutions.The pi-elite metric was used to select scaling, qubit-chain strength, and embeddings; random gauges were combined because success rates vary strongly across gauges.
- Runtime and speedup: For the small-scale problems studied, time to solution is comparable on classical hardware and the quantum annealer.Quantum speedup for the optimal trading trajectory problem is expected only after speedup is demonstrated for general high-precision coupling problems.
III. CONCLUSIONS
The conclusions report promising but limited evidence that D-Wave’s quantum annealer can solve a difficult multi-period portfolio optimization problem with high success rates. Fine-tuning improves success rates, while current problem size remains small and larger instances are expected to be difficult for classical computers.
- III. CONCLUSIONS: D-Wave’s quantum annealer demonstrated potential for high success rates on an important, difficult multi-period portfolio optimization problem.The authors characterize this as a limited experiment.
- III. CONCLUSIONS: Fine-tuning the quantum annealer produced a considerable improvement in success rates.The conclusion attributes this improvement to fine-tuning the annealer’s operation.
- III. CONCLUSIONS: Current quantum annealers solve only small problems, but future technological improvements are expected to support larger problems at higher success rates.The paper notes that larger problems are expected to be intractable on classical computers.
APPENDIX A DEFINITION OF SYMBOLS
The appendix defines notation for time-indexed portfolio quantities, covariance matrices, transaction-cost tensors, and changes in holdings.
- APPENDIX A DEFINITION OF SYMBOLS: The notation defines w_t and µ_t as the t-th columns of their respective matrices, Σ_t as the t-th covariance-matrix page, and Δw_t as the change in holdings.Temporary and permanent transaction costs are represented by tensors Λ and Λ′, respectively.