求圖中點度數的量子算法*

郎健翔， 李綠周

中山大學計算機學院，廣東 廣州 510006

1 引言

屬性測試是一個重要且廣泛研究的領域，受到經典計算和量子計算社區的廣泛關注（Goldreich，2017； Montanaro et al.，2016）.其目的是確定給定對象是否具有預先確定的屬性.研究對象包括函數、概率分布、圖等.本文關注圖的屬性.

對于一個N個頂點的圖，如果任何經典算法在最壞情況下都需要探查鄰接矩陣中的所有條目，以確定某個屬性，則該屬性被稱為難以捉摸的（Rosenberg，1973）.也就是說，在鄰接矩陣模型下的經典查詢復雜度為Ω(N2).著名的Aanderaa-Karp-Rosenberg 猜想（也稱為難以捉摸猜想）認為，任何非平凡的單調圖屬性都是難以捉摸的.然而，這個猜想目前還沒有被證明.令人驚訝的是，在一系列工作（Buhrman et al.，1999； Magniez et al.，2007； Kulkarni et al.，2015）之后，所有非平凡單調圖屬性的量子查詢復雜度的下界被證明為Ω(N)（Aaronson et al.，2021）.這個下界是最優的，因為非平凡單調圖屬性“至少包含一條邊”可以使用Grover算法在O(N)次查詢內確定.雖然量子計算領域的大部分關注點都集中在單調圖屬性上，但非單調圖屬性在量子模型中的理解還不夠充分（一些非單調圖屬性在（Sun et al.，2004）中被研究）.

在本文中，我們考慮的問題是確定一個圖是否具有特定度數的頂點，這是一個難以捉摸且非單調的圖屬性.更具體的問題描述如下.

問題給定一個N個頂點的無向圖G=(V，E)和一個非負整數k，目標是確定圖G是否具有度數為k的頂點.如果存在這樣的頂點，則找出它.

假設一個圖G=(V，E) 可以通過鄰接矩陣查詢模型進行訪問.它的量子版本用OG表示：

1.1 結果和技術

本文旨在探討使用最少的查詢次數來解決上述問題的量子算法.我們的主要結果如下.

定理1對于一個由N個頂點組成的無向圖G=(V，E)，可以通過鄰接矩陣OracleOG訪問該圖，同時給定一個正整數k＞0.存在一個量子算法，使用次對OG的查詢，如果圖中存在度數為k的頂點，則該算法能夠找到這樣的頂點；否則，算法輸出“不存在這樣的頂點”.

一種直接解決上述問題的方法是首先使用精確量子計數算法（Brassard et al.，2002）以O(N)的查詢次數獲取每個頂點的度數，并且借助Grover 搜索在次查詢中找到度數為k的頂點.這種方法的開銷為).需要注意的是，我們僅需要知道目標頂點是否具有度數k，而不需要知道該頂點的確切度數.因此，我們將提出一種量子算法來確定一個頂點是否具有度數k，然后將上述問題規約為此問題.更一般地，我們可以得到一個有效的量子算法來解決精確計數的判定問題，具體方法如下.

定理2給定一個函數g： [N]→{0，1}，以及滿足1 ≤k≤N的整數k，令M=|{x：g(x) = 1} |.則存在一個量子算法，使用次對g的查詢，并以至少為1 -δ的概率判斷M=k或M≠k.

為了證明定理2，我們將使用量子奇異值轉換（QSⅤT）技術（Gilyén et al.，2019）.此外，基于定理2和有限誤差輸入的量子搜索（H?yer et al.，2003），我們將證明定理1.

1.2 相關工作

尋找頂點度數的經典算法.Goyal et al.（2020）證明了判斷一個n個頂點的無向圖是否有度為0 或1 或2的頂點是難以捉摸的性質，對于k＞2 的情況下的下界是0.42n2，這改進了之前的下界0.25n2（Balasubra‐manian et al.，1997）.此外，他們還證明了判斷一個有向圖是否有出度為k（對于非負整數k≤(n+ 1)/2）的頂點是難以捉摸的問題.這改進了之前k＞1 時n(n- 1 -k)/2 的下界（Balasubramanian et al.，1997）.一個非常相關的問題是在查詢模型中尋找圖中最大度數的頂點.在無向圖（Balasubramanian et al.，1997； Goyal et al.，2020）、有向圖（Balasubramanian et al.，1997； Goyal et al.，2020）和競賽圖（Balasubramanian et al.，1997； Gutin et al.，2018； Goyal et al.，2020； Beretta et al.，2019）方面取得了一些進展.競賽圖就是將完全無向圖的邊給定了方向，是社會學、投票等領域中使用的一個非常有用的模型.此外，Dey（2017）給出了在競賽圖中尋找一些明確定義的頂點集的難以捉摸的下界.

圖問題上的量子算法.目前大多數解決圖問題的量子算法都基于兩種查詢模型：鄰接矩陣和鄰接表.其中，鄰接矩陣查詢模型被用于許多圖問題，如最短路徑、連通性、最小生成樹等等，而鄰接表查詢模型則被用于某些需要實現全局變換的問題，如判定二分圖、判定可遍歷性等等.最近，一些新的查詢模型也被研究了，如割問題和獨立集問題.另外，在量子模型中，也有一些出色的工作涉及到圖的性質檢測，包括二分圖性檢測、擴展性檢測等等.目前還沒有關于量子算法來判斷一個圖是否有一個特定度數頂點的工作.

2 預備知識

在本文中，定義[N]?0，1，…，N- 1.我們將使用兩個函數：一個是誤差函數

另一個是符號函數

接下來，簡要介紹兩個稍后將會用到的工具.

2.1 量子奇異值變換

量子奇異值變換（QSⅤT，quantum singular value transformation）技術最初在Gilyén et al.（2019）中被提出，為我們設計量子算法提供了一種新方法.然后，參考Martyn et al.（2021）利用 QSⅤT 技術提出了一個統一的框架，解釋了大部分已有算法.本文中的算法也將基于 QSⅤT，特別是以下結果.

定理3給定一個酉矩陣U、它的逆U?以及算符如果一個多項式 Poly(a) 滿足以下條件：i） deg(Poly(a)) ≤d；ii） 當x∈[-1，1 ]時，|Poly(a)|≤1；iii） Poly(a) 是奇函數，那么我們可以利用 QSⅤT 技術構建一個電路，使得

這個定理類似于Martyn et al.（2021）的定理2，但方向相反.其正確性在Gilyén et al.（2019）中已經暗示.

2.2 有界誤差輸入上的量子搜索

普通的 Grover 搜索只能在正確定義的oracle 上生效，當對帶有誤差的oracle 進行查詢時，將會失敗.于是H?yer et al.（2003）提出了以下有界誤差輸入的量子搜索技術.

定理4（H?yer et al.， 2003； Ambainis et al.， 2020） 給定n個算法（無論是量子還是經典的），每個算法都以有界的出錯概率給出一個布爾值，并且給定一個整數T≥1.那么存在一個量子算法，它使用次查詢，并且以常數的概率：如果n個值中至少有T個值為 1，則返回一個對應值為1 的索引；如果沒有值為 1，則返回NULL.(當解的數量 [T] 未知時，期望查詢次數也為.

3 量子算法

我們將本文考慮的問題規約為確定給定頂點的度數是否為k的問題，這進一步推廣為在第 3.1 節中的精確計數判定問題.

3.1 精確計數問題的判定問題

定理2是本文中至關重要的技術結果.

定理2 的證明該證明包括兩個步驟：（i）首先構造一個多項式Ploy(x)來近似刻畫問題的函數f(x)，（ii）然后針對多項式Ploy(x)，根據定理3構造一個量子電路來實現它.

首先我們定義以下函數：

注意到該函數滿足以下條件：

是一個區別M=k還是M≠k的指示器.然后，我們可以構造一個多項式Poly(x)，滿足以下條件：

用當前態作為輸入查詢g的結果為0以1 -δ的概率成立，當M≠k時：

用當前態作為輸入查詢g的結果為1以1 -δ的概率成立.因此，構造的量子電路可以以至少1 -δ的概率判斷M=k是否成立.

3.2 關鍵引理的證明

本文的目的是證明引理3，該引理說明存在一個期望的多項式Ploy(x)來逼近式（1）中的函數f(x).在此之前，需要使用Low et al.（2017）中的兩個引理.

引理1（關于符號函數sgn(x) 的整體逼近（Low et al.，2017）Lemma10） 對任意Δ＞0，x∈R，則函數fΔ，?(x) ?erf(lx) 滿足

引理2（誤差函數erf(lx)的多項式逼近（Low et al.，2017）Corollary4） 對任意l＞0，?∈(0，O(1)]，可定義奇次冪的多項式perf，l，n：

使得

① 在Low et al.(2017)中, x ∈[-1,1 ], 但是當x ∈[-2,2 ]時引理也成立.

其中Ij(x)表示第一類修正貝塞爾函數，Tj(x)表示第一類切比雪夫多項式，

現在我們將證明一個引用在定理2證明中的引理.

引理3我們可以高效地構造一個多項式Poly(x)來逼近以下函數

使得

存在fΔ，?(x)和perf，l，n.現在，我們定義以下多項式

當x∈[0，1]時，注意到x±c∈[-2，2 ]，因此有

上述第一個小于號是由引理2得出的；第二個小于號是由

推導出來的，這可以通過引理1中給出的fΔ，?的表達式進行解析驗證；第三個小于號成立是因為根據引理1，|fΔ，?(x±c)|≤1.類似地，有

因此，有

第二個小于號成立是因為：i）|Poly(x)|≤1，ii） |perf，l，n(x) - sgn(x)|≤|perf，l，n(x) -fΔ，?(x)|+|fΔ，?(x) -sgn(x)|≤2?.令δ/2 = 6?，因此，性質（iv）得到證明.

最后，容易發現Poly(x)是奇函數，這可以通過perf，l，n是奇多項式這一事實直接驗證.因此，證明了性質（i）.

3.3 判斷一個圖中是否存在度數為 k 的頂點

現在我們可以展示用于確定給定圖是否存在度數為k的頂點的量子算法.

推論1給定一個由N個頂點組成的無向圖G=(V，E)，可以通過鄰接矩陣OracleOG訪問該圖，同時給定一個正整數k＞0.則對于每個頂點vi∈V，存在一個量子算法Ai，使用次對OG的查詢，以至少1 -δ的概率決定vi的度數是否為k.其中δ是給定的概率誤差限.

證明設g(x) =OG(vi，x)，其中x∈V.根據定理2，存在一個量子算法，可以決定vi的度數是否為k.

這時，定理1可以由定理4和推論1推導得出.

注1在上述定理中，要求k＞0.當k= 0時，我們也可以構造一個消耗O(N)次查詢的量子算法.實際上，如果將式（1）替換為f(x) = sgn(x)，則可以通過類似的思路得到k= 0的算法.

4 結 論