概述

求解线性方程组是科学计算中的一个基础问题，也可利用线性方程组构造复杂的算法，如数值计算中的插值与拟合、大数据中的线性回归、主成分分析等。而正是由于线性求解问题在学科中的基础性作用，其在科学、工程、金融、经济应用、计算机科学等领域也应用广泛，如常见的天气预报，需要通过建立并求解包含百万变量的线性方程组实现对大气中类似温度、气压、湿度等的模拟和预测；如销量预测，需要采用线性回归方式的时序预测方法进行预测。

2009年，Harrow、Hassidim和Lloyd三人基于量子相位估计提出了HHL算法，是线性系统算法的一个典型代表。HHL算法对于大型良态稀疏矩阵A、用量子算法高效制备的量子态b，可以在复杂度O（polylogN）内输出Ax=b的量子态近似解。量子线性系统算法（QLSA）可以用于矩阵求逆，求解特征值、线性回归、插值与拟合等，被广泛应用于量子机器学习等算法中，可以指数级提升求解效率。但HHL算法也有一定的局限性，HHL算法以及系列改进算法的内核都是基于量子傅里叶变换，因需要指数级的量子线路资源难以实现，这也是当前HHL算法在NISQ时代的局限所在。

NISQ即含噪声中等规模量子器件，NISQ计算机是指那些拥有50-100量子比特、以及高保真量子门的设备。Cirq是谷歌一款用于编写、操作和优化量子线路的Python库，支持在量子计算机及量子模拟器上运行cirq编译的量子线路。Cirq为处理NISQ时代量子计算机提供了有效的抽象。类似的量子编程框架软件还有启科量子的QuTrunk产品。QuTrunk 使用 Python 作为宿主语言，利用 Python 的语法特性 实现针对量子程序的 DSL(领域专用语言)。cirq与QuTrunk两款产品都支持连接量子计算机和量子模拟器使用。本文将主要介绍量子线性系统算法中的典型算法HHL的数学原理及使用cirq、QuTrunk实现算法的代码示例。

1.量子线性算法

一般线性算法英文表述为The linear-system Algorithm，简称LSP；量子线性算法英文表述为The Quantum linear-system Algorithm。LSA与QLSA分别需要解决的问题如下：

LSA需要解决的问题是找到一个N维向量x，使得Ax=b。

QLSA需要解决的问题是找到一个n位量子比特，满足和Ax=b。

一般求解线性方程组的问题时会给定一个系统，再寻找对于矩阵和向量的。其中，假设A是厄米矩阵。将的分别表示为量子态｜x〉和｜b〉后，重新缩放为单位向量即。因此可以将传统的向量表示转化为量子态表示，对应的｜x〉求解方法为。

2.量子线性算法子程序——量子相位估计

量子相位估计算法(Quantum Phase Estimation Algorithm，简称QPE)，是HHL算法中的一个子程序。若假设一个幺正算符U，则该幺正算符作用在其本征态｜u〉上会出现一个相位，现在我们假设算符的本征值φ是未知，在已知算符U和本征态情况下，量子相位估计算法可以估计相位φ。以下为使用cirq进行哈密顿量模拟的演示代码：

class HamiltonianSimulation(cirq.EigenGate):

    def __init__(self, A, t, exponent=1.0):
        cirq.EigenGate.__init__(self, exponent=exponent)
        self.A = A
        self.t = t
        ws, vs = np.linalg.eigh(A)
        self.eigen_components = []
        for w, v in zip(ws, vs.T):
            theta = w * t / math.pi
            P = np.outer(v, np.conj(v))
            self.eigen_components.append((theta, P))

    def _num_qubits_(self) -> int:
        return 1

    def _with_exponent(self, exponent):
        return HamiltonianSimulation(self.A, self.t, exponent)

    def _eigen_components(self):
        return self.eigen_components

量子相位估计程序如下：

• 输入：受控单位；n个量子比特输入态，其。

• 输出：。

• 步骤：

步骤1使用t个辅助量子比特进行初始化操作，具体执行为，产生均匀叠加态。

步骤2根据公式创建量子线路

步骤3应用

• 测量测量辅助量子比特得到概率。

量子相位估计.jpg

图为量子相位估计线路图

2.1使用cirq定义量子相位估计

• 使用cirq完成量子线性系统算法，其中需要先进行量子相位估计操作。量子相位估计门操作中最后一个量子比特储存特征向量，剩下的量子比特都作为量子位存储的相位。

class PhaseEstimation(cirq.Gate):
    """
        num_qubits: The number of qubits of the unitary.
        unitary: The unitary gate whose phases will be estimated.
    """
    def __init__(self, num_qubits, unitary):
        self._num_qubits = num_qubits
        self.U = unitary

    def num_qubits(self):
        return self._num_qubits

    def _decompose_(self, qubits):
        qubits = list(qubits)
        yield cirq.H.on_each(*qubits[:-1])
        yield PhaseKickback(self.num_qubits(), self.U)(*qubits)
        yield cirq.qft(*qubits[:-1], without_reverse=True) ** -1

2.2使用QuTrunk进行量子傅里叶变换

量子傅里叶变换是量子相位估计的一个子程序，使用QuTrunk进行量子傅里叶操作示例如下：

首先准备QuTrunk做量子傅里叶变换的环境。numpy是一个Python包，是一个由多维数组对象和用于处理数组的例程集合组成的库。numpy拥有线性代数和随机数生成的内置函数，因此通常在进行数组的算数和逻辑运算、进行傅立叶变换以及与线性代数有关的操作时候都需要使用numpy。在示例代码中，QuTrunk通过qutrunk.circuit模块实现量子逻辑门操作。在以下量子线路中，对所有量子比特进行H门操作以制备初态量子比特时，只需使用All(H) * qureg命令即可。在QuTrunk的量子逻辑门中p门的主要作用是将单个量子位的和 之间的相位移动给定的角度。如，P(np.pi / 4) * qreg[0]表示相位移动角度为。

import numpy as np

from qutrunk.circuit import QCircuit
from qutrunk.circuit.gates import H, All, P


def run_QFT():
    circuit = QCircuit()
    qureg = circuit.allocate(3)

    All(H) * qureg
    circuit.qft([q.index for q in qureg])
    print(circuit.get_all_state())

    circuit.run()


def run_Full_QFT():
    circuit = QCircuit()
    qureg = circuit.allocate(3)

    All(H) * qureg
    circuit.qft()
    print(circuit.get_all_state())

    circuit.run()


def qft_single_wave():
    num_qubits = 4
    circuit = QCircuit()
    qreg = circuit.allocate(num_qubits)
    All(H) * qreg
    P(np.pi / 4) * qreg[0]
    P(np.pi / 2) * qreg[1]
    P(np.pi) | qreg[2]
    circuit.qft()
    print(circuit.get_all_state())
    circuit.run()

    return circuit


if __name__ == "__main__":
    run_QFT()
    run_Full_QFT()
    circuit = qft_single_wave()
    print(circuit.draw())

3.HHL算法

用于反演方程系统的HHL算法是一个基础性的、易于理解的子程序，它是许多量子机器学习算法的基础。该算法试图用量子计算机求解Ax=b。HHL算法已在不同的量子计算机上被证明，HHL算法将求解向量的值转化为求解矩阵M的期望值（M满足）。在量子计算机上求解HHL算法时，可以通常测量的概率得出期望值比如pauli算法X、Y、Z，可以将测量的概率转换为关于这些运算符的期望值。

HHL算法的核心思想如下：分别表示矩阵A的特征向量和特征值，其中。因此，向量可以写成特征向量的线性组合，。HHL算法的目标是获取。以下为HHL算法及其执行的三个步骤（矩阵A可以使用量子相位估计算法得到）：

HHL算法三步骤.jpg

HHL算法具体程序如下：

• 输入：

1.输入态;

2.使用单元执行受控操作的能力

• 输出量子态｜x〉，｜x〉满足。

• 步骤：

步骤1使用幺正变换进行量子相位估计。该操作将特征值映射到以二进制形式输入寄存器以转换系统。

步骤2对每个执行旋转辅助量子比特为。最后该系统演变为

步骤3执行与步骤一相反的操作，此时系统表达式为

• 测量测量辅助量子比特得到。

HHL.png

HHL算法线路图

3.1使用cirq定义HHL算法的量子线路

以下为使用cirq构建HHL量子线路代码示例。示例代码中，cirq实现的是2×2的哈密顿矩阵。HHL算法一般使用三组量子比特，分别为辅助量子比特、用于存储矩阵A的量子比特、用于存储输入量子态和。量子逻辑门操作顺序为首先使用量子相位估计模块提取A的特征值，再对辅助量子比特进行受控旋转，最后进行量子相位估计逆操作。操作的最终结果准确性取决于寄存器大小和量子线路参数。

def hhl_circuit(A, C, t, register_size, *input_prep_gates):

    ancilla = cirq.LineQubit(0)
    # to store eigenvalues of the matrix
    register = [cirq.LineQubit(i + 1) for i in range(register_size)]
    # to store input and output vectors
    memory = cirq.LineQubit(register_size + 1)

    c = cirq.Circuit()
    hs = HamiltonianSimulation(A, t)
    pe = PhaseEstimation(register_size + 1, hs)
    c.append([gate(memory) for gate in input_prep_gates])
    c.append(
        [
            pe(*(register + [memory])),
            EigenRotation(register_size + 1, C, t)(*(register + [ancilla])),
            pe(*(register + [memory])) ** -1,
            cirq.measure(ancilla, key='a'),
        ]
    )

    c.append(
        [
            cirq.PhasedXPowGate(
                exponent=sympy.Symbol('exponent'), phase_exponent=sympy.Symbol('phase_exponent')
            )(memory),
            cirq.measure(memory, key='m'),
        ]
    )

    return c

结尾

HHL算法并非意味着我们已经可以实现HHL算法在真正的量子计算机上运行解决实际问题。目前虽有在量子计算机上实现HHL算法的成功示例，但HHL算法广泛依然在很大程度上取决于有效量子比特数的数目。因此，量子计算机的研发工作还任重道远。如何利用现有的物理设备挖掘量子算法的应用潜力，开发更多高效的量子算法，也成为现阶段量子计算领域的一项重点工作。

参考来源：

https://mp.weixin.qq.com/s/Vhv0oUQj0bBkL3cv9Pe0Ow

https://cloud.tencent.com/developer/article/1069783

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.120.050502

https://github.com/quantumlib/Cirq/blob/master/examples/hhl.py