概述

求解線性方程組是科學(xué)計(jì)算中的一個(gè)基礎(chǔ)問(wèn)題壮不，也可利用線性方程組構(gòu)造復(fù)雜的算法由缆，如數(shù)值計(jì)算中的插值與擬合注祖、大數(shù)據(jù)中的線性回歸、主成分分析等均唉。而正是由于線性求解問(wèn)題在學(xué)科中的基礎(chǔ)性作用是晨，其在科學(xué)、工程舔箭、金融罩缴、經(jīng)濟(jì)應(yīng)用、計(jì)算機(jī)科學(xué)等領(lǐng)域也應(yīng)用廣泛层扶，如常見的天氣預(yù)報(bào)箫章，需要通過(guò)建立并求解包含百萬(wàn)變量的線性方程組實(shí)現(xiàn)對(duì)大氣中類似溫度、氣壓镜会、濕度等的模擬和預(yù)測(cè)修械；如銷量預(yù)測(cè)降宅，需要采用線性回歸方式的時(shí)序預(yù)測(cè)方法進(jìn)行預(yù)測(cè)。

2009年，Harrow认臊、Hassidim和Lloyd三人基于量子相位估計(jì)提出了HHL算法梯轻，是線性系統(tǒng)算法的一個(gè)典型代表梯刚。HHL算法對(duì)于大型良態(tài)稀疏矩陣A及皂、用量子算法高效制備的量子態(tài)b，可以在復(fù)雜度O（polylogN）內(nèi)輸出Ax=b的量子態(tài)近似解季率。量子線性系統(tǒng)算法（QLSA）可以用于矩陣求逆野瘦，求解特征值、線性回歸、插值與擬合等鞭光，被廣泛應(yīng)用于量子機(jī)器學(xué)習(xí)等算法中吏廉，可以指數(shù)級(jí)提升求解效率。但HHL算法也有一定的局限性惰许，HHL算法以及系列改進(jìn)算法的內(nèi)核都是基于量子傅里葉變換席覆，因需要指數(shù)級(jí)的量子線路資源難以實(shí)現(xiàn)，這也是當(dāng)前HHL算法在NISQ時(shí)代的局限所在汹买。

NISQ即含噪聲中等規(guī)模量子器件佩伤，NISQ計(jì)算機(jī)是指那些擁有50-100量子比特、以及高保真量子門的設(shè)備晦毙。Cirq是谷歌一款用于編寫生巡、操作和優(yōu)化量子線路的Python庫(kù)，支持在量子計(jì)算機(jī)及量子模擬器上運(yùn)行cirq編譯的量子線路见妒。Cirq為處理NISQ時(shí)代量子計(jì)算機(jī)提供了有效的抽象孤荣。類似的量子編程框架軟件還有啟科量子的QuTrunk產(chǎn)品。QuTrunk 使用 Python 作為宿主語(yǔ)言须揣，利用 Python 的語(yǔ)法特性 實(shí)現(xiàn)針對(duì)量子程序的 DSL(領(lǐng)域?qū)Ｓ谜Z(yǔ)言)盐股。cirq與QuTrunk兩款產(chǎn)品都支持連接量子計(jì)算機(jī)和量子模擬器使用。本文將主要介紹量子線性系統(tǒng)算法中的典型算法HHL的數(shù)學(xué)原理及使用cirq耻卡、QuTrunk實(shí)現(xiàn)算法的代碼示例疯汁。

1.量子線性算法

一般線性算法英文表述為The linear-system Algorithm，簡(jiǎn)稱LSP卵酪；量子線性算法英文表述為The Quantum linear-system Algorithm幌蚊。LSA與QLSA分別需要解決的問(wèn)題如下：

LSA需要解決的問(wèn)題是找到一個(gè)N維向量x，使得Ax=b溃卡。

QLSA需要解決的問(wèn)題是找到一個(gè)n位量子比特霹肝，滿足和Ax=b。

一般求解線性方程組的問(wèn)題時(shí)會(huì)給定一個(gè)系統(tǒng)，再尋找對(duì)于矩陣和向量的最铁。其中，假設(shè)A是厄米矩陣垮兑。將的分別表示為量子態(tài)｜x〉和｜b〉后，重新縮放為單位向量即雀哨。因此可以將傳統(tǒng)的向量表示轉(zhuǎn)化為量子態(tài)表示，對(duì)應(yīng)的｜x〉求解方法為雾棺。

2.量子線性算法子程序——量子相位估計(jì)

量子相位估計(jì)算法(Quantum Phase Estimation Algorithm膊夹，簡(jiǎn)稱QPE)，是HHL算法中的一個(gè)子程序捌浩。若假設(shè)一個(gè)幺正算符U放刨，則該幺正算符作用在其本征態(tài)｜u〉上會(huì)出現(xiàn)一個(gè)相位，現(xiàn)在我們假設(shè)算符的本征值φ是未知尸饺，在已知算符U和本征態(tài)情況下进统，量子相位估計(jì)算法可以估計(jì)相位φ。以下為使用cirq進(jìn)行哈密頓量模擬的演示代碼：

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

量子相位估計(jì)程序如下：

• 輸入：受控單位浪听；n個(gè)量子比特輸入態(tài)螟碎，其。

• 輸出：迹栓。

• 步驟：

步驟1使用t個(gè)輔助量子比特進(jìn)行初始化操作掉分，具體執(zhí)行為，產(chǎn)生均勻疊加態(tài)迈螟。

步驟2根據(jù)公式創(chuàng)建量子線路

步驟3應(yīng)用

• 測(cè)量測(cè)量輔助量子比特得到概率叉抡。

量子相位估計(jì).jpg

圖為量子相位估計(jì)線路圖

2.1使用cirq定義量子相位估計(jì)

• 使用cirq完成量子線性系統(tǒng)算法，其中需要先進(jìn)行量子相位估計(jì)操作答毫。量子相位估計(jì)門操作中最后一個(gè)量子比特儲(chǔ)存特征向量褥民，剩下的量子比特都作為量子位存儲(chǔ)的相位。

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進(jìn)行量子傅里葉變換

量子傅里葉變換是量子相位估計(jì)的一個(gè)子程序洗搂，使用QuTrunk進(jìn)行量子傅里葉操作示例如下：

首先準(zhǔn)備QuTrunk做量子傅里葉變換的環(huán)境消返。numpy是一個(gè)Python包，是一個(gè)由多維數(shù)組對(duì)象和用于處理數(shù)組的例程集合組成的庫(kù)耘拇。numpy擁有線性代數(shù)和隨機(jī)數(shù)生成的內(nèi)置函數(shù)撵颊，因此通常在進(jìn)行數(shù)組的算數(shù)和邏輯運(yùn)算、進(jìn)行傅立葉變換以及與線性代數(shù)有關(guān)的操作時(shí)候都需要使用numpy惫叛。在示例代碼中倡勇，QuTrunk通過(guò)qutrunk.circuit模塊實(shí)現(xiàn)量子邏輯門操作。在以下量子線路中嘉涌，對(duì)所有量子比特進(jìn)行H門操作以制備初態(tài)量子比特時(shí)妻熊，只需使用All(H) * qureg命令即可。在QuTrunk的量子邏輯門中p門的主要作用是將單個(gè)量子位的和 之間的相位移動(dòng)給定的角度仑最。如扔役，P(np.pi / 4) * qreg[0]表示相位移動(dòng)角度為。

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算法

用于反演方程系統(tǒng)的HHL算法是一個(gè)基礎(chǔ)性的警医、易于理解的子程序亿胸，它是許多量子機(jī)器學(xué)習(xí)算法的基礎(chǔ)。該算法試圖用量子計(jì)算機(jī)求解Ax=b婉刀。HHL算法已在不同的量子計(jì)算機(jī)上被證明诱桂，HHL算法將求解向量的值轉(zhuǎn)化為求解矩陣M的期望值（M滿足）肝劲。在量子計(jì)算機(jī)上求解HHL算法時(shí)，可以通常測(cè)量的概率得出期望值比如pauli算法X、Y舱殿、Z冈绊，可以將測(cè)量的概率轉(zhuǎn)換為關(guān)于這些運(yùn)算符的期望值霸妹。

HHL算法的核心思想如下：分別表示矩陣A的特征向量和特征值静盅，其中。因此蚣常，向量可以寫成特征向量的線性組合，施绎。HHL算法的目標(biāo)是獲取。以下為HHL算法及其執(zhí)行的三個(gè)步驟（矩陣A可以使用量子相位估計(jì)算法得到）：

HHL算法三步驟.jpg

HHL算法具體程序如下：

• 輸入：

1.輸入態(tài);

2.使用單元執(zhí)行受控操作的能力

• 輸出量子態(tài)｜x〉贞绳，｜x〉滿足。

• 步驟：

步驟1使用幺正變換進(jìn)行量子相位估計(jì)冈闭。該操作將特征值映射到以二進(jìn)制形式輸入寄存器以轉(zhuǎn)換系統(tǒng)俱尼。

步驟2對(duì)每個(gè)執(zhí)行旋轉(zhuǎn)輔助量子比特為。最后該系統(tǒng)演變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%60%5Csum_%7Bj%5Cin%20%5C%7B1%2CN%5C%7D%7D%CE%B2_j%EF%BC%88%5Csqrt%7B1-%7B%5Cfrac%7BC%5E2%7D%7B%7B%CE%BB_j%7D%5E2%7D%7D%7D%7C0%5Crangle_a%2B%5Cfrac%7BC%7D%7B%CE%BB_j%7D%7C1%5Crangle_a%EF%BC%89%7C%CE%BB_j%5Crangle_r%7Cu_j%5Crangle_m%20%60" alt="`\sum_{j\in \{1,N\}}β_j（\sqrt{1-{\frac{C^2}{{λ_j}^2}}}|0\rangle_a+\frac{C}{λ_j}|1\rangle_a）|λ_j\rangle_r|u_j\rangle_m `" mathimg="1">

步驟3執(zhí)行與步驟一相反的操作拒秘，此時(shí)系統(tǒng)表達(dá)式為

• 測(cè)量測(cè)量輔助量子比特得到号显。

HHL.png

HHL算法線路圖

3.1使用cirq定義HHL算法的量子線路

以下為使用cirq構(gòu)建HHL量子線路代碼示例。示例代碼中躺酒，cirq實(shí)現(xiàn)的是2×2的哈密頓矩陣押蚤。HHL算法一般使用三組量子比特，分別為輔助量子比特羹应、用于存儲(chǔ)矩陣A的量子比特揽碘、用于存儲(chǔ)輸入量子態(tài)和。量子邏輯門操作順序?yàn)槭紫仁褂昧孔酉辔还烙?jì)模塊提取A的特征值园匹，再對(duì)輔助量子比特進(jìn)行受控旋轉(zhuǎn)雳刺，最后進(jìn)行量子相位估計(jì)逆操作。操作的最終結(jié)果準(zhǔn)確性取決于寄存器大小和量子線路參數(shù)裸违。

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

結(jié)尾

HHL算法并非意味著我們已經(jīng)可以實(shí)現(xiàn)HHL算法在真正的量子計(jì)算機(jī)上運(yùn)行解決實(shí)際問(wèn)題掖桦。目前雖有在量子計(jì)算機(jī)上實(shí)現(xiàn)HHL算法的成功示例，但HHL算法廣泛依然在很大程度上取決于有效量子比特?cái)?shù)的數(shù)目供汛。因此枪汪，量子計(jì)算機(jī)的研發(fā)工作還任重道遠(yuǎn)涌穆。如何利用現(xiàn)有的物理設(shè)備挖掘量子算法的應(yīng)用潛力，開發(fā)更多高效的量子算法雀久，也成為現(xiàn)階段量子計(jì)算領(lǐng)域的一項(xiàng)重點(diǎn)工作宿稀。

參考來(lái)源：

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