郎健翔， 李綠周

中山大學(xué)計算機(jī)學(xué)院，廣東 廣州 510006

1 引言

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

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

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

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

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

1.1 結(jié)果和技術(shù)

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

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

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

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

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

1.2 相關(guān)工作

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

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

2 預(yù)備知識

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

另一個是符號函數(shù)

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

2.1 量子奇異值變換

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

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

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

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

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

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

3 量子算法

我們將本文考慮的問題規(guī)約為確定給定頂點(diǎn)的度數(shù)是否為k的問題，這進(jìn)一步推廣為在第 3.1 節(jié)中的精確計數(shù)判定問題.

3.1 精確計數(shù)問題的判定問題

定理2是本文中至關(guān)重要的技術(shù)結(jié)果.

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

首先我們定義以下函數(shù)：

注意到該函數(shù)滿足以下條件：

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

用當(dāng)前態(tài)作為輸入查詢g的結(jié)果為0以1 -δ的概率成立，當(dāng)M≠k時：

用當(dāng)前態(tài)作為輸入查詢g的結(jié)果為1以1 -δ的概率成立.因此，構(gòu)造的量子電路可以以至少1 -δ的概率判斷M=k是否成立.

3.2 關(guān)鍵引理的證明

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

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

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

使得

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

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

現(xiàn)在我們將證明一個引用在定理2證明中的引理.

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

使得

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

當(dāng)x∈[0，1]時，注意到x±c∈[-2，2 ]，因此有

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

推導(dǎo)出來的，這可以通過引理1中給出的fΔ，?的表達(dá)式進(jìn)行解析驗證；第三個小于號成立是因為根據(jù)引理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?，因此，性質(zhì)（iv）得到證明.

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

3.3 判斷一個圖中是否存在度數(shù)為 k 的頂點(diǎn)

現(xiàn)在我們可以展示用于確定給定圖是否存在度數(shù)為k的頂點(diǎn)的量子算法.

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

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

這時，定理1可以由定理4和推論1推導(dǎo)得出.

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

4 結(jié) 論