基于量子计算的投资组合优化算法

Info

该工作为朱学长@11d-beyonder的毕业设计

本文为该工作的阅读笔记

概括总结

1. 将投资组合问题表达为二次优化模型
2. 利用拉格朗日乘子法将二次优化问题转化为方程组求解问题
3. 利用HHL算法求解方程组
4. 通过引入约束缩放系数对算法进行优化

具体内容

标准投资组合选择模型

$$\begin{array}{rlll}\text{minimize}& w^{\mathrm{T}}\mathrm{\Sigma }ws.t.& w^{\mathrm{T}}R=E& w^{\mathrm{T}}\mathrm{\Pi }=\mathrm{\Xi }\end{array}$$ 其中

• $w=[w_1,\cdots ,w_n{]}^{\mathrm{T}},\sum w_i=1$为选择在$n$个标的上投资的比例
• $r_t=[r_1^t,\cdots ,r_n^t{]}^{\mathrm{T}}$为每个标的在交易日$t$的收益
• $R=\mathbb{E}(r_t)={\displaystyle \frac{1}{T}}\sum r_t$为$T$个交易日收益的均值
• $\mathrm{\Sigma }=\mathbb{V}(r_t)={\displaystyle \frac{1}{T-1}}\sum (r_t-R{)}^{\mathrm{T}}(r_t-R)$为收益的协方差矩阵
• $E=w^{\mathrm{T}}R$为期望收益
• $V=w^{\mathrm{T}}\mathrm{\Sigma }w$为风险
• $\mathrm{\Pi }$为当前的价格向量
• $\mathrm{\Xi }$为投资金额限定

  取$\mathrm{\Pi }=[1,\cdots ,1{]}^{\mathrm{T}}$时$w$为各标的投资的份数，$\mathrm{\Xi }$为购买份数限额

故上式表示期望一定时，选取风险最低的投资组合。

拉格朗日乘子法

$$f(w)=w^{\mathrm{T}}\mathrm{\Sigma }w+\eta (w^{\mathrm{T}}R-E)+\rho (w^{\mathrm{T}}\mathrm{\Pi }-\mathrm{\Xi })$$

其中$\eta ,\rho$为拉格朗日乘子。求偏导，得

$$\{\begin{array}{l}{\displaystyle \frac{\partial f}{\partial w}}=2\mathrm{\Sigma }w+\eta R+\rho \mathrm{\Pi }=0\\ {\displaystyle \frac{\partial f}{\partial \eta }}=w^{\mathrm{T}}R-E=0\\ {\displaystyle \frac{\partial f}{\partial \rho }}=w^{\mathrm{T}}\mathrm{\Pi }-\mathrm{\Xi }=0\end{array}$$

即

$$\left[\begin{array}{ccc}0& 0& R^{\mathrm{T}}\\ 0& 0& {\mathrm{\Pi }}^{\mathrm{T}}\\ R& \mathrm{\Pi }& \mathrm{\Sigma }\end{array}\right]\left[\begin{array}{c}\eta \\ \rho \\ w\end{array}\right]=\left[\begin{array}{c}E\\ \mathrm{\Xi }\\ 0\end{array}\right]$$

此处对系数进行了调整

记该方程组为$Ax=b$，利用HHL求解（由于协方差矩阵$\mathrm{\Sigma }$实对称，故$A$自伴）

$$\left[\begin{array}{cc}A& O\\ O& I\end{array}\right]\left[\begin{array}{c}x\\ 0\end{array}\right]=\left[\begin{array}{c}b\\ 0\end{array}\right]$$

---

优化：引入约束缩放系数降低矩阵的条件数

$$\left[\begin{array}{ccc}0& 0& s_1{R}^{\mathrm{T}}\\ 0& 0& s_2{\mathrm{\Pi }}^{\mathrm{T}}\\ s_{1}R& s_2\mathrm{\Pi }& \mathrm{\Sigma }\end{array}\right]\left[\begin{array}{c}\eta \\ \rho \\ w\end{array}\right]=\left[\begin{array}{c}E\\ \mathrm{\Xi }\\ 0\end{array}\right]$$

HHL

概述

求解$Ax=b$，其中$A$自伴（$A$不自伴：构造$\left[\begin{array}{cc}& A\\ A^{†}\end{array}\right]\left[\begin{array}{c}0\\ x\end{array}\right]=\left[\begin{array}{c}b\\ 0\end{array}\right]$）

复杂度：$O({\kappa }^2{ϵ}^{-1}\log N)$，其中$\kappa$为矩阵的条件数，$ϵ$为解的精度（相位估计求特征值时，特征值倒数的相对误差）

表示

$A|x⟩=|b⟩\Rightarrow |x⟩=A^{-1}|b⟩$

谱分解：$A=\sum _{j=0}^{N-1}{\lambda }_j|{\mu }_j⟩⟨{\mu }_j|$

标正基：$|b⟩=\sum _{j=0}^{N-1}{\beta }_j|{\mu }_j⟩$

代入：

$$\begin{array}{rlr}|x⟩& =\left(\sum _{i=0}^{N-1}{\displaystyle \frac{1}{{\lambda }_i}}|{\mu }_i⟩⟨{\mu }_i|\right)\left(\sum _{j=0}^{N-1}{\beta }_j|{\mu }_j⟩\right)& (\text{对角阵})\\ & =\sum _{j=0}^{N-1}{\displaystyle \frac{1}{{\lambda }_j}}{\beta }_j|{\mu }_j⟩& (\text{标正基})\end{array}$$

电路

1. 利用同构电路将$|b⟩=\sum _{j=0}^{N-1}{b}_j|j⟩=\sum _{j=0}^{N-1}{\beta }_j|{\mu }_j⟩$置于$R_v$上（需提前将$|b⟩$归一化）
2. 经过QPE，得$\sum _{j=0}^{N-1}{\beta }_j|{\mu }_j⟩|{\phi }_j⟩$
3. 对于取定的归一化常数$C$，对$R_a$作用$R_Y(\theta )$，得$\sum _{j=0}^{N-1}{\beta }_j|{\phi }_j⟩|{\mu }_j⟩(\cos {\displaystyle \frac{\theta }{2}}|0⟩+\sin {\displaystyle \frac{\theta }{2}}|1⟩)$，其中
   • $\theta =2\arcsin {\displaystyle \frac{C}{{\lambda }_j}}$（由目标方程解的形式决定，$C$用于归一化与成功率控制）
   • ${\lambda }_j$由${\phi }_j$决定
   • $R_p$存储${\phi }_j$ 带入$C$，得$\sum _{j=0}^{N-1}{\beta }_j|{\mu }_j⟩|{\phi }_j⟩(\sqrt{1-{\displaystyle \frac{C^2}{{\lambda }_j^2}}}|0⟩+{\displaystyle \frac{C}{{\lambda }_j}}|1⟩)$
4. 利用QPE${}^{†}$解纠缠，得$\sum _{j=0}^{N-1}{\beta }_j|{\mu }_j⟩{|0⟩}^{\otimes n}(\sqrt{1-{\displaystyle \frac{C^2}{{\lambda }_j^2}}}|0⟩+{\displaystyle \frac{C}{{\lambda }_j}}|1⟩)$
5. 测量辅助比特，测量结果为1时成功求解，得目标态${\displaystyle \frac{1}{\sqrt{\sum _{j=0}^{N-1}{\displaystyle \frac{{\beta }_j^2}{{\lambda }_j^2}}}}}\sum _{j=0}^{N-1}{\displaystyle \frac{{\beta }_j}{{\lambda }_j}}|{\mu }_j⟩{|0⟩}^{\otimes n}|1⟩$，其中${\displaystyle \frac{1}{\sqrt{\sum _{j=0}^{N-1}{\displaystyle \frac{{\beta }_j^2}{{\lambda }_j^2}}}}}\sum _{j=0}^{N-1}{\displaystyle \frac{{\beta }_j}{{\lambda }_j}}|{\mu }_j⟩$为标准化的$|x⟩$
6. 利用量子振幅估计得到基上的系数

细节

参数确定

A

创新：使用A的特征值进行缩放

要求：$|\lambda |⩽1$

缩放：$A:={\displaystyle \frac{l}{|\lambda {|}_{max}}}A(l\in (0,1])$

取$l={\displaystyle \frac{1}{2}}$，此时

• $|\lambda {|}_{min}⩽|\lambda |⩽|\lambda {|}_{max}$，自伴：$A=A^{†}\Rightarrow \kappa ={\displaystyle \frac{max\sigma (\sqrt{A{A}^{†}})}{min\sigma (\sqrt{A{A}^{†}})}}={\displaystyle \frac{|\lambda {|}_{max}}{|\lambda {|}_{min}}}$
• ${\displaystyle \frac{|\lambda {|}_{min}}{2|\lambda {|}_{max}}}⩽{\displaystyle \frac{|\lambda |}{2|\lambda {|}_{max}}}⩽{\displaystyle \frac{|\lambda {|}_{max}}{2|\lambda {|}_{max}}}\Rightarrow |{\lambda }^{\prime }|\in [{\displaystyle \frac{1}{2\kappa }},{\displaystyle \frac{1}{2}}]$

U

利用哈密顿模拟得$U=e^{iAt}$，其中$t$为模拟时间

对角阵：$iAt=\sum _{j=0}^{N-1}i{\lambda }_{j}t|{\mu }_j⟩⟨{\mu }_j|\Rightarrow U=\sum _{j=0}^{N-1}{e}^{i{\lambda }_{j}t}|{\mu }_j⟩⟨{\mu }_j|$

标正基：$U|{\mu }_j⟩=e^{i{\lambda }_{j}t}|{\mu }_j⟩$

$\lambda$

QPE求得的$\phi$满足$U|\mu ⟩=e^{2\pi i\phi }|\mu ⟩(\phi \in [0,1))$

又$U|\mu ⟩=e^{i\lambda t}|\mu ⟩$，故$e^{2\pi i\phi }=e^{i\lambda t}$

$\lambda ⩾0$时，$\phi ={\displaystyle \frac{\lambda t}{2\pi }}$

$\lambda <0$时，$e^{2\pi i}=1\Rightarrow e^{i\lambda t}=e^{2\pi i\frac{\lambda t}{2\pi }}=e^{2\pi i(\frac{\lambda t}{2\pi }+1)}=e^{2\pi i\phi }\Rightarrow \phi =1+{\displaystyle \frac{\lambda t}{2\pi }}$

取$t=\pi$，有$\phi =\{\begin{array}{ll}{\displaystyle \frac{\lambda }{2}},& \lambda ⩾0,\\ 1+{\displaystyle \frac{\lambda }{2}},& \lambda <0.\end{array}$

又$|\lambda |<1$，故$\lambda =\{\begin{array}{ll}2\phi ,& \phi <{\displaystyle \frac{1}{2}},\\ 2(\phi -1),& \phi ⩾{\displaystyle \frac{1}{2}}.\end{array}$

$n_p$

用$n_p$个比特近似$\phi$时绝对误差$|\phi -\tilde{\phi }|<2^{-n_p}$

故$|\lambda -\tilde{\lambda }|<2^{1-n_p}$

由$ϵ$定义（特征值倒数的相对误差）与$|\lambda |$下界${\displaystyle \frac{1}{2\kappa }}$得

$$\left|{\displaystyle \frac{{\displaystyle \frac{1}{\lambda }}-{\displaystyle \frac{1}{\tilde{\lambda }}}}{{\displaystyle \frac{1}{\lambda }}}}\right|\approx \left|{\displaystyle \frac{\tilde{\lambda }-\lambda }{\lambda }}\right|⩽{\displaystyle \frac{\kappa }{2^{n_p-2}}}⩽ϵ\Rightarrow n_p⩾2+{\log }_2{\displaystyle \frac{\kappa }{ϵ}}$$

C

算法成功率$P(|1⟩)=\sum _j{\displaystyle \frac{C^2{\beta }_j^2}{{\lambda }_j^2}}$

约束：$\left|{\displaystyle \frac{C}{{\lambda }_j}}\right|⩽1\Rightarrow |C|⩽|\lambda {|}_{min}$

为提高成功率，取$|C|=|\lambda {|}_{min}$

结果处理

为求得$|x⟩$，需求出$|x⟩$的范数$\sqrt{\sum _{j=0}^{N-1}{\displaystyle \frac{{\beta }_j^2}{{\lambda }_j^2}}}$

又$P(|1⟩)=\sum _{j=0}^{N-1}{\displaystyle \frac{C^2{\beta }_j^2}{{\lambda }_j^2}}$

故$||x||={\displaystyle \frac{\sqrt{P(|1⟩)}}{C}}$

基础知识

协方差矩阵

协方差：用于刻画两个随机变量的相似程度

$$\sigma (x,y)={\displaystyle \frac{1}{n-1}}\sum _{i=1}^n(x_i-\overline{x})(y_i-\overline{y})$$

设有随机变量$\{x_1,\cdots ,x_n\}$，两两之间的协方差为$\sigma (x_m,x_k)={\displaystyle \frac{1}{n-1}}\sum _{i=1}^n(x_{mi}-\overline{x_m})(x_{ki}-\overline{x_k})$ 则协方差矩阵为

$$\mathrm{\Sigma }=\left[\begin{array}{ccc}\sigma (x_1,x_1)& \cdots & \sigma (x_1,x_n)\\ ⋮& & ⋮\\ \sigma (x_n,x_1)& \cdots & \sigma (x_n,x_n)\end{array}\right]$$

为实对称阵

向量&二次型求导

向量对向量求导

分母的每个元素对整个分子求导，求导后的结果按照分母的形状进行组装

二次型求导

$$\begin{array}{l}d(x^{\mathrm{T}}Ax)=(x^{\mathrm{T}}A)dx+d(x^{\mathrm{T}}A)x=x^{\mathrm{T}}Adx+(d(x^{\mathrm{T}}A)x{)}^{\mathrm{T}}\\ =x^{\mathrm{T}}Adx+x^{\mathrm{T}}d(A^{\mathrm{T}}x)=x^{\mathrm{T}}Adx+x^{\mathrm{T}}{A}^{\mathrm{T}}dx=x^{\mathrm{T}}(A+A^{\mathrm{T}})dx\end{array}$$

$A$实对称$\Rightarrow {\displaystyle \frac{d(x^{\mathrm{T}}Ax)}{dx}}=2Ax$

矩阵的条件数

矩阵范数：矩阵对向量的缩放能力

$$||A||=\underset{x}{max}{\displaystyle \frac{||Ax||}{||x||}}$$

由定义知，$||A^{-1}||=\underset{y}{max}{\displaystyle \frac{||A^{-1}y||}{||y||}}={\displaystyle \frac{1}{\underset{y}{min}{\displaystyle \frac{||y||}{||A^{-1}y||}}}}\stackrel{y=Ax}{=}{\displaystyle \frac{1}{\underset{x}{min}{\displaystyle \frac{||Ax||}{||x||}}}}$

条件数：衡量方程的稳定性

$$\kappa (A)=||A||||A^{-1}||$$

易证，当$x$变化$\delta x$时，有${\displaystyle \frac{1}{\kappa (A)}}{\displaystyle \frac{||\delta b||}{||b||}}⩽{\displaystyle \frac{||\delta x||}{||x||}}⩽\kappa (A){\displaystyle \frac{||\delta b||}{||b||}}$

计算：$||A||$为A最大奇异值$max\sigma (\sqrt{A{A}^{†}})$，$||A^{-1}||$为A最小奇异值的倒数${\displaystyle \frac{1}{min\sigma (\sqrt{A{A}^{†}})}}$

QPE

设$U$的特征向量$|\mu ⟩$的特征值为$e^{2\pi i\phi }$，即$U|\mu ⟩=e^{2\pi i\phi }|\mu ⟩$，电路黑盒如下

当$|v⟩=\sum v_j|{\mu }_j⟩$时，结果为$\sum v_j|{\phi }_j⟩$