Quantum Algorithm Zoo全訳 オラクルアルゴリズム
本記事はQuantum Algorithm Zoo全訳シリーズの一部です。
以下のリンクから他の記事に飛べます。
- 前書き
- 代数アルゴリズム、数論アルゴリズム
- オラクルアルゴリズム(本記事)
- 近似アルゴリズム、シミュレーションアルゴリズム
訳者注：この項目では、入力に対してある決まった規則で出力を返すオラクル(神託機械)が与えられたとき、できるだけ少ない回数オラクルに問い合わせ(クエリ)をすることでオラクルに関する何らかの性質を求める問題を考える。この時、問題を解くためにオラクルに何回問い合わせをする必要があるかを、問い合わせ計算量 (query complexity)と呼ぶ。問い合わせ計算量のSpeedupは、必ずしも同じスケールでの時間計算量の改善を意味するわけではないことに注意。
Algorithm: 探索 (Grover Search, グローバー探索)
Speedup: 多項式的
詳細
$N$ 種類の入力を受け付けるオラクルが与えられる。或る入力 $w$ のみが"当たり"であり、これに対応する出力は $1$ である。それ以外の全ての入力に対応する出力は $0$ である。探索問題は、 $w$ を見つける問題である。古典計算では、 $\Omega(N)$ の回数の問い合わせが必要になる。Lov Groverによる量子アルゴリズム(グローバー探索)は $O(\sqrt{N})$ 回の問い合わせで $w$ を見つけることが出来る [48] 。これは最適であることも知られている [216] 。このアルゴリズムは後に「"当たり"が複数個ある場合 [15] 」、「任意の関数の総和を計算する問題 [15, 16, 73] 」、「任意の関数の最小値を求める問題 [35, 75, 255] 」、「異なる初期状態や [100] 、或る非一様な事前確率分布が得られている時 [123] 、これを活用する場合」、「入力に応じてオラクルの応答時間が変化する場合 [138] 」、「定積分の近似 [77] 」、「不動点への収束 [208, 209] 」などに拡張された。一般化されたGroverのアルゴリズムは振幅推定(Amplitude estimation) [17] として知られており、現在の量子アルゴリズムにおいて重要な基本要素となっている。振幅推定は衝突問題とグラフの性質に関する問題に関連する殆どの量子アルゴリズムにおいて中心的な役割を果たしている。グローバー探索の自然な応用の一つは3-SATといったNP完全な問題の既知の最も良い古典アルゴリズムを高速化することである。これが可能かどうかは非自明である。なぜなら、3-SATの既知の最も良い古典アルゴリズムは全探索では無いからだ。しかしながら、参考文献 [133] に示されるように振幅増幅を用いると既知の最も良い3-SATの古典アルゴリズムをルートだけ改善できることが知られている。他の制約充足問題の$2$乗の加速についても参考文献 [134] で得られている。グローバー探索と振幅増幅の他の応用例については参考文献 [261, 262] を参照せよ。グローバー探索に密接に関係しているが、しかしより難しい問題として、空間探索がある。これは、データベースの問い合わせが或るグラフの構造によって制約されている場合の探索問題である。十分密に結合したグラフについては、 $O(\sqrt{N})$ の量子問い合わせ計算量が実現される [274, 275, 303, 304, 305, 306, 330] 。
Algorithm: 可換隠れ部分群
Speedup: 超多項式的
詳細
$G$ を有限な可換群とする。 $H$を剰余群 $G \setminus H$ を有限にする $G$ の部分群とする。 $f$を $G$に関する関数とする。ただし、 $f$は任意の $g_1, g_2 \in G$について、 $g_1$と $g_2$ が$H$の同じ剰余類に属する時に、そしてその時に限り、$f(g_1) = f(g_2)$ を満たす関数であるとする。我々のタスクは、 $f$に問い合わせることで、$H$ を求める (言い換えると、 $H$の生成元の集合を求める)ことである。これは、量子計算機を用いると $O(\log |G|)$ の問い合わせで解ける。一方、古典計算機では $\Omega(|G|)$の問い合わせが必要となる。このアルゴリズムはBonehとLiptonらの参考文献 [14] において、最初に完全に一般化した形で与えられた。しかしながら、このアルゴリズムに対する正確な貢献者を決めることは難しい。なぜなら、参考文献 [76] の五章にあるように、このアルゴリズムは多くの歴史的に重要な量子アルゴリズムを特殊例として包含しているからだ。例えばこの問題はSimonのアルゴリズム [108] を特殊例として含み、SimonのアルゴリズムはShorの周期発見アルゴリズムを発見するきっかけとなっており、周期発見アルゴリズムは彼の因数分解や離散対数問題のアルゴリズムの中核をなしている。可換隠れ部分群のアルゴリズムはペル方程式、主イデアル、単元群、類群のアルゴリズムにおいても重要な役割を果たす。参考文献 [30] に示されるように、幾つかの例については、可換隠れ部分群問題は $\log (|G|)$ のオーダーではなく1回の問い合わせだけで解答を得ることが出来る。
Algorithm: 非可換隠れ部分群
Speedup: 超多項式的
詳細
$G$ を有限な可換群とする。 $H$を有限の左剰余類を持つ $G$ の部分群とする。 $f$を $G$に関する関数とする。ただし、 $f$は任意の $g_1, g_2 \in G$について、 $g_1$と $g_2$ が$H$の同じ左剰余類に属する時に、そしてその時に限り、$f(g_1) = f(g_2)$ を満たす関数であるとする。我々のタスクは、 $f$に問い合わせることで、$H$ を求める (言い換えると、 $H$の生成元の集合を求める)ことである。これは、量子計算機を用いると $O(\log |G|)$ の問い合わせで解ける。一方、古典計算機では $\Omega(|G|)$ の問い合わせが必要となる [37, 51] 。しかしながら、このアルゴリズムは効率的な量子アルゴリズムとはみなせない。なぜならば、一般には問い合わせの結果から得られた量子状態を処理するのに指数的な時間がかかってしまうかもしれないからだ。いくつかの非可換群については、隠れ部分群問題に対する効率的な量子アルゴリズムが知られている [81, 55, 72, 53, 9, 22, 56, 71, 57, 43, 44, 28, 126, 207, 273] 。少し古くなってしまった概説が参考文献 [69] で与えられている。特に重要な意味を持つのが、対称群と二面体群である。対称群に対してこの問題を解決できればグラフ同型問題が解けると考えられる。二面体群に対してこの問題を解決できればいくつかの格子問題が解けると考えられる [78] 。これまでの多くの努力にも関わらず、これらの群に対する多項式時間での解法は、参考文献 [312] の特殊な場合を除いて見つかっていない。しかしながら、Kuperberg [66] は二面体群 $D_N$ の隠れ部分群を $2^{O(\sqrt{\log N})}$ の時間で求めるアルゴリズムを発見した。Regevは後にこのアルゴリズムを改善し、多項式的な空間と準指数的な時間のアルゴリズムを開発した [79] 。必要とされる量子ビットの数に関する漸近的なスケーリングのさらなる改善が 参考文献 [218] で与えられている。(必ずしも量子ゲート操作の数について効率的な量子アルゴリズムであることを意味しないものの）幾分かより一般的な置換集合における関数の同型性のテストについても、量子問い合わせ計算量の改善が得られている [311] 。
Algorithm: Bernstein-Vazirani
Speedup: 多項式的、再帰的には超多項式的
詳細
$n$ ビットを入力として受けとり、 $1$ ビットを出力するオラクルが与えられる。オラクルは$x \in \{0,1\}^n$ の入力に対して、 $x \odot h$ を出力する。ここで、 $h$ は"隠された" $n$ ビット列であり、 $\odot$ はビットごとの内積を2で割った余りである。この問題のタスクは $h$ を求めることである。古典計算機ではこの作業は $n$ 回の問い合わせを要する。BernsteinとVaziraniの結果 [11] で示されているように、この回数は量子計算を用いると1回に減らせる。しかも、量子計算が古典計算に比べ指数的に問い合わせ回数を減らすことが出来る問題を、この問題の再帰的なバージョンを考えることによって構成できる [11] 。この再帰的なバージョンの問題はRecursive Fourier samplingと呼ばれる。関連した研究として、一般的な量子回路における普遍的な量子加速に関しては参考文献 [256, 257] を見よ。また、オラクルの関数と別のフーリエ変換の間の相関の検出における量子問い合わせ回数の改善については、参考文献 [258, 270] を見よ。
Algorithm: Deutsch-Jozsa
Speedup: Pクラスに対して指数的、BPPクラスに対しては改善なし
詳細
$n$ ビットを入力として受けとり、 $1$ ビットを出力するオラクルが与えられる。オラクルの出力は $2^n$ 通りのありうる全ての入力に対して、「全てに0を出力する」、「全てに1を出力する」、「半分に1を、残りに0を出力する」のどれかであることが約束されている。この問題のタスクは、オラクルの出力が均衡している場合（半分に1を出力する場合）か、一定値の場合（全てに０，あるいは全てに１を出力する場合）かを判定することである。Deutsch [32] によって、 $n=1$ の場合は、この問題は決定論的な古典計算では2回の問い合わせを必ず必要とする一方、量子計算機を用いると1回の問い合わせで解くことが出来ることが示された。これは歴史的には古典計算に対する加速を明確に実現した初めての量子アルゴリズムである。（関連した、より最近の教育的な例が参考文献 [259] で与えられている。）1回の問い合わせで任意の $n$ について解くアルゴリズムはDeutschとJozsaによって参考文献 [33] で示された。古典計算ではDeutsch-Jozsaの問題は確率的に $O(1)$ 回の問い合わせで容易に解けてしまうものの、決定論的な古典計算機での問い合わせ計算量においてこの問題は指数的な時間がかかる最悪な場合を持つ。
Algorithm: Formulaの評価
Speedup: 多項式的
詳細
ブール式は各変数がそれぞれ一度ずつしか使われていない時、formulaと呼ばれる。formulaはファンアウトの無い回路に対応し、これは結果として木構造のトポロジーを持つ。Reichardtのspan-program形式によって、$N$ 変数に対する $O(1)$ 個のファンインで構成されるどんなformulaに対しても、量子問い合わせ計算量は $\Theta(\sqrt{N})$であることが知られている [158] 。この結果は、長い研究 [27, 8, 80, 159, 160] の末に得られている。これらの研究はFarhiら [38] による$2^n$変数におけるNAND木が量子計算機で連続時間の量子ウォークを用いると $O(2^{0.5n})$ で評価できるという発見に端を発している。この問題は古典計算機では $\Omega(2^{0.753n})$個の問い合わせを要する。多くの場合において、量子的なformulaの評価アルゴリズムは問い合わせ計算量だけでなく時間計算量についても効率的である。Span-program形式は量子問い合わせ計算量の下界も与える [149] 。当初は異なった観点から発見されたものの、Groverのアルゴリズムはformulaの評価ですべてのゲートがORである特殊例とみなせる。ブール式でないformulaの評価における量子計算量については参考文献 [29] で研究されている。しかし、完全には理解されていない。Childsらはこのアルゴリズムを入力で同じ変数が繰り返されるかもしれない場合(つまり、回路の最初の層がファンアウトを含むかもしれない場合)に一般化した [101] 。彼らは $O(\min \{N,\sqrt{S},N^{1/2} G^{1/4}\})$ 回の問い合わせを要する量子アルゴリズムを得た。ここで、 $N$ は重複を無視した入力変数の数、 $S$ は重複を含んだ入力変数の数、 $G$ はformulaにおけるゲートの数である。参考文献 [164] 、 [165] や [269] は同じでない入力を受けるNANDゲートの数が限られているようなNAND木の問題の特殊な場合を考えている。これらのうちいくつかは、量子と古典問い合わせ計算量の間に超多項式的な差をもたらしている。
Algorithm: 勾配の計算、構造のあるデータの探索、多項式の学習
Speedup: 多項式的
詳細:
なめらかな関数 $f: \mathbb{R}^d \rightarrow \mathbb{R}$ を計算するオラクルが与えられる。 $f$ の入出力は有限の多数のビット精度でオラクルに与えられる。我々のタスクは $x_0 \in \mathbb{R}^d$ における $\nabla f$ を推定することである。参考文献 [61] で示されているように、量子計算機は1回の問い合わせでこれを実現できる。一方で、古典計算機は少なくとも $d+1$ 回の問い合わせが必要となる。参考文献 [20] では、Bulgerは最適化問題に対する潜在的な応用を提案した。参考文献 [62] のappendix Dで示されるように、量子計算は勾配アルゴリズムを $d$ 次元の二次形式の最小値を $O(d)$ 回の問い合わせで計算するのに使える。一方 参考文献 [94] で示されるように古典計算機はこの計算に少なくとも $\Omega(d^2)$ の問い合わせを要する。単一の問い合わせでハミング距離におけるお椀型の最小値を求める量子アルゴリズムは参考文献 [147, 148, 223] で与えられている。参考文献 [62] の量子アルゴリズムは二次形式の行列の $d^2$ 個のすべての行列要素を $O(d)$ 回の問い合わせで得ることができる。より一般的に言えば、 $d$ 変数のなめらかな関数における $d^n$ 個の $n$-階微分を $O(d^{n-1})$ の問い合わせで得ることができる。参考文献 [130, 146] で示されるように、有限体上の $d$ 変数についての二次形式や多重線形多項式は古典計算機で要求される問い合わせの数に対して $d$ 倍少ない回数の量子問い合わせで取り出せるかもしれない。
Algorithm: 隠れシフト
Speedup: 超多項式的
詳細:
$\mathbb{Z}_N$における或る関数 $f$ にアクセスするオラクルを考える。我々は、 $f(x)=g(x+s)$ であることを知っているとする。ただし、 $g$ は既知の関数であり、 $s$ は未知のシフトである。隠れシフト問題は $s$ を求める問題である。 Groverの問題からの帰着により、少なくとも $\sqrt{N}$ のクエリが一般の場合に必要なことが明らかである。しかし、隠れシフト問題の或る特殊な場合においては、量子計算機は $O(1)$ 回の問い合わせで問題を解くことができる。特に、van Damらは $f$ が 有限な環か体の乗法的指標である場合、このケースが実現できることを示した [89] 。以前に発見されたシフトされたルジャンドル記号のアルゴリズム [88, 86] はこの特殊例である。なぜならば、ルジャンドル記号 $(\frac{x}{p})$ は $\mathbb{F}_p$ の乗法的指標だからだ。これらの問題に対して、 $O({\rm polylog}(N))$ で動作する古典アルゴリズムは知られていない。しかも、或る暗号における疑似乱数生成器については、その生成器に量子問い合わせをする能力が与えられたとき、この量子アルゴリズムはその疑似乱数生成器を破ることができる [89] 。差集合の隠れシフト問題における量子加速については 参考文献 [312] で与えられている。さらに、これはルジャンドル記号の問題を特殊例として含む。Roettelerは或る非線形ブール関数において隠れシフトを求める問題に対して、指数的な量子加速が得られることを発見した [105, 130] 。この成果を示すにあたって、Gavinsky、Roetteler、Rolandはランダムブール関数 $f: \mathbb{Z}^n_2 \rightarrow \mathbb{Z}_2$ についての隠れシフト問題は $O(n)$ の平均量子問い合わせ計算量で解けることを示した [142] 。一方で、古典計算機では $\Omega(2^{n/2})$ の問い合わせが必要となる。参考文献 [143] における結果は、彼らは二面体群における隠れ部分群問題について言及しているものの、 $\mathbb{Z}_N$ における 単射関数についての隠れシフト問題の量子 問い合わせ 計算量が $O(\log n)$ であることを示唆している。古典計算機ではこれを解くのに $\Theta(\sqrt{N})$ の問い合わせが必要となる。しかしながら、既知の最良の $\mathbb{Z}_N$ における単射関数の隠れシフト問題についての量子 回路 計算量は $O(2^{C\sqrt{\log N}})$ である。この結果は Kuperbergの篩アルゴリズム(Kuperberg's sieve algorithm) [66] で得られている。
Algorithm: 多項式補間
Speedup: 定数倍
詳細
$p(x) = a_d x^d + \ldots + a_1 x + a_0$ を ${\rm GF}(q)$ における多項式とする。 $x \in {\rm GF}(q)$ が与えられると、 $p(x)$ を返すようなオラクルへのアクセスが与えられる。多項式補間問題とは、オラクルに問い合わせることで $a_d, \ldots, a_0$ の係数を定める問題である。古典的には、これは $d+1$ 回の問い合わせが必要かつ十分である。量子においては、 $d/2+1/2$ 回の問い合わせが必要であり、 $d/2 + 1$ 回の問い合わせが十分である [360, 361] 。
Algorithm: パターンマッチング
Speedup: 超多項式的
詳細
長さ $n$ の文字列 $T$ と、 長さ $m<n$ の文字列 $P$ が与えられる。両方ともに有限の文字種(alphabet)からなる。パターンマッチングの問題とは、 $P$ が $T$ の部分文字列となっている場所を探す、あるいは $P$ が $T$ の部分文字列になっていないことを知らせる問題である。より一般的には、 $T$ と $P$ は一次元配列(文字列)ではなく $d$-次元配列の場合を考えることができる。この場合は、パターンマッチングの問題は $T$ の $n \times n \times \ldots \times n$ の配列において、 $m \times m \times \ldots \times m$ の $P$ と一致するブロックになっている箇所を探す、あるいはそうした箇所が存在しないことを知らせる問題である。構造を持たないデータの探索 [216] では $\Omega(\sqrt{N})$ の問い合わせが下界である。このことはこの問題の最悪の量子問い合わせ計算量は $\Omega(\sqrt{n} + \sqrt{m})$ であることを示唆している。このオーダーを対数係数を無視した上で実現する量子アルゴリズムは [217] で与えられている。この量子アルゴリズムはGroverのアルゴリズムをdeterministic samplingと呼ばれる古典手法と一緒に用いることで機能する。さらに最近、Montanaroはパターンマッチングの平均的なインスタンスについて、もし $m$ が $n$ の対数よりも大きいのであれば、超多項式的な量子加速が実現できることを示した。特に、 参考文献 [215] で与えられている量子アルゴリズムはパターンマッチングの平均的な問題を $\tilde{O}((n/m)^{d/2} 2^{O(d^{3/2} \sqrt{\log m})})$ の時間で解く。この量子アルゴリズムは、Kuperbergの量子篩アルゴリズム [66] を二面体の隠れ部分群問題と隠れシフトの問題に対して$d$次元で機能し小さな量のノイズを許容できるように一般化し、さらにパターンマッチングの問題をノイズのある $d$-次元版の隠れシフト問題に古典的に帰着することで構成されている。
Algorithm: 線形システム
Speedup: 超多項式的
詳細
$n \times n$ の行列Aと、ベクトル $b$ の或る記述にアクセスするオラクルが与えられる。我々は或る効率的に計算可能な関数 $f$ について、 $f(A)b$ の性質を求めたい。$A$ がそれぞれの行に $O({\rm polylog}\, n)$ 個の非零要素を持つエルミート行列とし、 $k$ をその条件数とする。参考文献 [104] で示されるように、量子計算機は $O(k^2 \log n)$ の計算時間でベクトル $f(A)b$ に関し様々な期待値を多項式精度で計算することができる（ただし、 $b$ に比例する量子状態が効率的に構成可能とする）。或る関数に関して、例えば $f(x)=1/x$については、この手続きは非エルミートで正方でさえない行列 $A$ に拡張できる。このアルゴリズムの計算時間はのちに参考文献 [138] で $O(k \log^3k \log n)$ に改善された。参考文献 [263] において、精度に関する指数的な計算時間の改善が得られている。このアルゴリズムを拡張したものは様々な問題に適用されている。例えば電磁散乱断面積の推定 [249] (別のアプローチとしては参考文献 [369] も見よ)、線形微分方程式を解く [156, 296] 、ネットワークの電気抵抗の推定 [210] 、最小二乗法でのフィッティング [169] 、テプリッツ系(Toeplitz systems)を解く [297] 、機械学習 [214, 222, 250, 251, 309] などである。線形システムのアルゴリズムをベースとした量子機械学習のいくつかの制約は 参考文献 [246] によくまとめられている。参考文献 [220] において、量子計算機は良条件の $n \times n$ 行列の逆行列を $O(\log n)$ の量子ビットだけで計算できることが示されている。一方、既知の最良の古典アルゴリズムは $\log^2 n$ のオーダーのビットを必要としている。後にこの量子アルゴリズムについての改善が参考文献 [279] で与えられている。
Algorithm: 順序あり探索
Speedup: 定数
詳細
昇順に並んだ $N$ 個の値のリストにアクセスするオラクルが与えられる。値 $x$ を与えられたときに、我々のタスクはその値が入るべき場所を探すことである。古典的には、最良のアルゴリズムは二分探索であり、 $\log_2 N$ の問い合わせを要する。Farhiらは量子計算機は $0.53 \log_2 N$ の問い合わせでこれを実現できることを示した [39] 。現在では、既知の最良の決定論的量子アルゴリズムはこの問題のために $0.433\log_2 N$ の問い合わせを要する [103] 。この問題に対して、量子問い合わせ回数の下界は $\frac{\ln 2}{\pi} \log_2 N$ であることが示されている [219, 24] 。参考文献 [10] では、問い合わせ回数の期待値が $\frac{1}{3}\log_2 N$ より小さい乱択量子アルゴリズムが与えられている。
Algorithm: 隣接行列モデルでのグラフの性質
Speedup: 多項式的
詳細
$G$ を $n$ 個の頂点からなるグラフとする。我々は、 $\{1,2,\ldots,n\}$ から整数のペアを与えられたときに対応する頂点が辺でつながれているかを答えるオラクルへのアクセスを与えられる。先行研究 [35, 52, 36] に基づき、Dürrら [34] は重み付きグラフの最小全域木を求める量子問い合わせ計算量と、有向および無向グラフの連結度を求める量子問い合わせ計算量は $\Theta(n^{3/2})$ であることを示した。また、最小重み経路を求める問題は $O(n^{3/2} \log^2 n)$ の量子問い合わせ計算量であることも示した。参考文献 [317] で示されたように、参考文献 [13, 272, 318] に基づくことで、グラフが二部グラフであるかの判定、閉路の検知、或る頂点が別の頂点から到達可能かの判定(st-connectivity)に対して量子問い合わせ計算量とゲートの数のどちらも $\tilde{O}(n^{3/2})$ でスケールし、対数個の量子ビットしか要しない量子アルゴリズムを構築することができる。与えられたサイズの木をマイナーとして持つかを検知する、 $\tilde{O}(n)$ の時間を要するspan-programベースの量子アルゴリズムが参考文献 [240] で与えられている。全てのグラフの辺の数が頂点の数の高々 $c$ 倍になるような定数 $c$ が存在するとき、グラフの性質が疎であるという。ChildsとKothariはあらゆる疎なグラフの性質は、もしグラフが禁止された部分グラフのリストで特徴づけられないときに $\Theta(n^{2/3})$ の問い合わせ計算量を持ち、特徴づけられるときは $o(n^{2/3})$ であることを示した [140] ($o$の記号についてはランダウ記法のwikipediaを参照)。前者のアルゴリズムはグローバー探索に基づくアルゴリズムであり、後者のアルゴリズムは参考文献 [141] の量子ウォークの定式化に基づくものである。Maderの定理により、疎なグラフの性質は全ての非自明なminor-closedな性質を含む。例えば平面性やグラフが森(forest)であること、指定された長さのパスを含まないこと、などである。広く信じられているAanderaa-Karp-Rosenbergの予想によれば、上記のすべての問題は $\Omega(n^2)$ の古典問い合わせ計算量を持つ。また別の興味深い計算問題として、与えられたグラフ $G$ から部分グラフ $H$ を探す問題がある。最もシンプルなケースは三角形、すなわち大きさが3のクリークを探す問題である。既知の最良の量子アルゴリズムは三角形を $O(n^{5/4})$ の量子問い合わせで求める [319] 。 これは参考文献 [276, 175, 171, 70, 152, 21] を改善することで得られている。より強い量子問い合わせ計算量の上界が、グラフが十分に疎である場合について与えられている [319, 320] 。古典的には、triangle finding問題は $\Omega(n^2)$ の問い合わせを要する [21] 。より一般的には、量子計算機は任意の $k$ 頂点の部分グラフを探すのに $O(n^{2-2/k-t})$ の問い合わせを要する。ただし、 $t=(2k-d-3)/(k(d+1)(m+2))$ であり、$d$と$m$は $H$の頂点の次数が$d$で辺の数が$m+d$となるような値である [153] 。この結果は参考文献 [70] の先行研究を改善して得られている。いくつかの場合において、この問い合わせ計算量は参考文献 [140] の量子アルゴリズムに劣る。このアルゴリズムは$G$が疎な場合に $H$を $\tilde{O}(n^{\frac{3}{2} - \frac{1}{{\rm vc}(H)+1}})$ の問い合わせで求める。ただし、 ${\rm vc}(H)$は $H$ の最小の頂点被覆の大きさである。定数サイズの部分ハイパーグラフを3-様(3-uniform)なハイパーグラフから探す問題を $O(n^{1.883})$ の問い合わせで求める量子アルゴリズムが参考文献 [241] で与えられている。
Algorithm: 隣接リストモデルにおけるグラフの性質
Speedup: 多項式的
詳細
$G$を$N$個の頂点と$M$個の辺からなる、次数$d$のグラフとする。我々は、頂点のラベルと $j\in \{1,2,\ldots,d\}$ の値の問い合わせに対して、指定された頂点の$j$番目の隣接した頂点、あるいは指定した頂点の次数が$d$未満の場合にはnullを返すようなオラクルが与えられる。与えられるグラフ $G$が二部グラフであるか、二部グラフからはるかに遠いかのどちらかだと約束されているとする。この時、はるかに遠いとは、遠いグラフを二部グラフにするために定数割合の辺を除かなければいけないことを意味する。参考文献 [144] で示されているように、$G$が二部グラフかどうかを決定するのに要する量子計算量は$\tilde{O}(N^{1/3})$である。また、参考文献 [144] では、expanderグラフとexpanderグラフからはるかに遠いグラフを区別するためには$\tilde{O}(N^{1/3})$かつ$\tilde{\Omega}(N^{1/4})$の量子計算量を要することも示されている。一方、この計算には$\tilde{\Theta}(\sqrt{N})$の古典計算量を要する。この量子アルゴリズムのカギとなるのは、element distinctnessに対するAmbainisのアルゴリズムである。参考文献 [34] では、最小全域木を求めるのに必要な量子問い合わせ計算量が $\Theta(\sqrt{NM})$であること、グラフの連結度を決定するのに必要な量子問い合わせ計算量は無向グラフにおいて $\Theta(N)$で有向グラフでは$\tilde{\Theta}(\sqrt{NM})$であること、重み付きグラフに対して与えられた頂点(source)からほかの頂点への最小重み経路を計算するのに必要な量子問い合わせ計算量が$\tilde{\Theta}(\sqrt{NM})$であることが示されている。参考文献 [317] では、st-connectivity、二部グラフかどうかの決定、グラフが森(forest)であるかの決定を行う、$\tilde{O}(N\sqrt{d})$の時間と対数個の量子ビットのみを用いる量子アルゴリズムが与えられている。
Algorithm: 溶接された木(Welded Tree)
Speedup: 超多項式的
詳細
或る計算機の問題は、迷路を通り抜けるための問い合わせ計算量の言葉で言い換えることができる。つまり、オラクルを通してアクセスできるグラフ$G$がある場合だ。与えられたノードのラベルが問い合わされたとき、オラクルはすべての隣接したノードのラベルのリストを返す。我々のタスクは、或るsourceノード(のラベル)からスタートして、或るマークされた終点のノードのラベルに到達することである。Childsらによって示されたように [26] 、量子計算機は少なくとも或るグラフについて、古典計算機よりも指数的に早くこのタスクを達成することができる。特に、二つの深さ$n$の二分木を、二つの根(root)を除きすべてのノードが次数3になるようランダムに"溶接"してつなぎ合わせることで得られるグラフを考えたとき、量子計算機は一方の根から始めてもう一方の根を${\rm poly}(n)$の問い合わせで発見できる。一方、古典問い合わせの場合この問い合わせ計算量はおそらく実現不可能である。
Algorithm: 衝突問題とElement Distinctness
Speedup: 多項式的
詳細
サイズ$N$の定義域を持つ2対1関数 $f$にアクセスするオラクルが与えられたとする。衝突問題とは$f(x)=f(y)$となるペア$x,y \in \{1,2,\ldots,N\}$を発見する問題である。この問題の古典乱択問い合わせ計算量は $\Theta(\sqrt{N})$である。一方、Brassardらによって示されたように、量子計算機はこれを$O(N^{1/3})$の問い合わせを使って実現する [18] 。（参考文献 [315] も見よ。） $f$が2対1関数であるという約束を取り除くと、問題はelement distinctnessと呼ばれる。これは、$\Theta(N)$の古典問い合わせで解かれる。参考文献 [21] の結果を改善することで、Ambainisはelement distinctnessについて $O(N^{2/3})$ の問い合わせ計算量の量子アルゴリズムを与えた。これは最適であることが分かっている [7, 374] 。$k$個の重複した衝突が存在するかどうかを決定する問題は$k$-distinctnessと呼ばれる。参考文献 [7, 154] の改善に基づくと、最も良い量子問い合わせ計算量は$O(n^{3/4 - 1/(4(2^k-1))})$ である [172, 173] 。$k=2,3$の場合については、対数のファクターを無視すればこれは時間計算量になることが参考文献 [7] で示されている。$k>3$については、既知の最も速い量子アルゴリズムは $O(n^{(k-1)/k})$の時間計算量を持つ [363] 。それぞれ$N$,$M$のサイズの定義域を持つ二つの関数$f$と$g$を与えられた時、clawとは$f(x)=g(y)$となるペア$x,y$である。$N=M$の場合、参考文献 [7] のアルゴリズムはclawを求める問題を$O(N^{2/3})$の問い合わせで解く。この結果は、以前に参考文献 [21] で提案されていた$O(N^{3/4}\log N)$の量子アルゴリズムを改善している。さらなる研究結果として、$N\neq M$である様々なパラメータ領域において、改善された量子問い合わせ計算量が与えられている [364, 365] 。より一般的には、element distinctnessに関連する問題として以下のようなものがある。或るシーケンスにアクセスするオラクルが与えられる。この時、$k$次の頻度モーメント $F_k=\sum_j n_j^k$を推定したい。ただし、 $n_j$は$j$がシーケンス内で起きた回数である。この問題については近似的に$2$乗の高速化が参考文献 [277] で得られている。グラフ衝突の項目も見よ。
Algorithm: グラフ衝突
Speedup: 多項式的
詳細
我々は $n$頂点を持つ無向グラフと、1か0でラベル付けされた頂点のラベルにアクセスするオラクルを与えられる。グラフ衝突問題とは、オラクルに問い合わせることで、辺で結合されており、かつ両方ともに1のラベルを持つような頂点のペアがあるかどうかを決定する問題である。スターグラフを用いて、グラフの中心に1をラベル付けし、残りの頂点はデータベースの入力でラベル付けすることで、Groverの構造を持たない探索問題をグラフ衝突のインスタンスに埋め込むことができる。よって、この問題は $\Omega(\sqrt{n})$ の量子問い合わせ計算量と、$\Theta(n)$ の古典問い合わせ計算量を持つ。参考文献 [70] では、Magniez、Nayak、Szegedyが一般のグラフについてのグラフ衝突に関し、$O(N^{2/3})$の問い合わせの量子アルゴリズムを与えた。この結果は一般のグラフに関して、現在も量子問い合わせ計算量の最良の上界である。しかし、より強い上界がいくつかの特殊なグラフのクラスについて与えられている。具体的に言うと、グラフ$G$の問い合わせ計算量は、$G$のnon-edgeの数が$l$の時$\tilde{O}(\sqrt{n}+\sqrt{l})$ [161] 、$G$の最大独立集合の大きさが$\alpha$の時$O(\sqrt{n}\alpha^{1/6})$ [172] 、$G$の或る独立集合の最大総次数が$\alpha^*$の時$O(\sqrt{n},\sqrt{\alpha^*})$ [200] 、$G$のtreewidthが$t$の時$O(\sqrt{n}t^{1/6})$ [201] である。さらに、グラフがそれぞれの頂点のペアについて辺が存在するかどうかを一定の確率で独立に選ばれたランダムグラフ(つまり、Erdős–Rényiグラフ)の場合、高い確率で量子問い合わせ計算量は $\tilde{O}(\sqrt{n})$ である [200] 。これらの結果と、ここに書くには複雑すぎる二つのさらなるグラフのクラスに関する新たな上界についてのまとめに関しては、参考文献 [201] を見よ。
Algorithm: 行列の可換性
Speedup: 多項式的
詳細
我々は、 $n \times n$ の $k$ 個の行列にアクセスするオラクルを与えられる。整数$i,j\in \{1,2,\ldots,n \}$、および$x\in \{1,2,\ldots,k \}$を与えられたとき、オラクルは$x$番目の行列の$ij$成分を返す。
我々のタスクは、$k$個の行列がすべて交換するかどうかを判定することである。Itakuraによって示されたように [54] 、これは量子計算機を用いて$O(k^{4/5}n^{9/5})$の問い合わせで実現できる。一方、古典的にはこれは$\Omega(kn^2)$の問い合わせを要する。
Algorithm: 群の可換性
Speedup: 多項式的
詳細
我々は群$G$の$k$個の生成元のリストと、群の積を計算するブラックボックスへのアクセスが与えられる。このブラックボックスに問い合わせることで、我々はこの群が可換かどうかを知りたい。既知の最良の古典アルゴリズムはPakによって与えられており、$O(k)$の問い合わせを要する。MagniezとNayakは、このタスクについての量子問い合わせ計算量が$\tilde{\Theta}(k^{2/3})$であることを示した [139] 。
Algorithm: 隠れた非線形構造
Speedup: 超多項式的
詳細
どのような可換群$G$も格子として可視化できる。$G$の部分群$H$はその部分格子であり、$H$の剰余類は全てこの部分格子をシフトしたものである。可換隠れ部分群問題は通常は隠れ部分群のランダムな剰余類についての重ね合わせを得、その双対格子からサンプルできるようにフーリエ変換を行うことで解かれる。これを非可換隠れ部分群問題(非可換隠れ部分群問題の項目を見よ)に一般化するのではなく、代わりに格子以外の隠れた部分集合を見出す問題に一般化することができる。Childsらによって示されたように [23] 、この問題は量子計算機を用いれば多項式によって定義される或る部分集合、例えば球、において効率的に解くことができる。Deckerらはこれに関連したいくつかの問題がどのようにして効率的に解けるのかを示した [31, 212] 。
Algorithm: 放射関数の中心
Speedup: 多項式的
詳細
我々は$\mathbb{R}^d$から或る任意の集合$S$への関数$f$を評価するオラクルを与えられる。ただし、$f$は球対称な関数である。我々は或る精度で、対象性の中心を特定したい。(簡単のため、精度は固定とする。)参考文献 [110] において、Liuはcurvelet変換をベースとして、この問題を$d$と独立な定数の量子問い合わせで解く量子アルゴリズムを与えた。このアルゴリズムは古典の下界である$\Omega(d)$に対して多項式的な高速化を実現する。このアルゴリズムは関数$f$が十分小さなスケールで揺らいでも機能する。例えば、$f$の等位集合が十分に細い球殻である場合などだ。この量子アルゴリズムは理想的な連続的モデルにおいても機能することが示されており、また厳密ではないながらも離散化の効果は小さいことを示唆する議論もある。
Algorithm: 群の位数とメンバーシップ
Speedup: 超多項式的
詳細
有限群$G$が以下のようなオラクルを通した形で与えられるとする。それぞれの$G$の元について、対応するラベルが紐づけられる。群の元の順序対が与えられると、オラクルはそれらの積のラベルを返す。そのような群に対応していくつもの古典的に困難な問題がある。一つは、群の生成元の集合のラベルが与えられたときに群の位数を求める問題である。もう一つのタスクは、ビット列が与えられたとき、それが群の元に対応するかどうかを決定する問題である。構造的なバージョンのこのメンバーシップ問題は、もし答えがYESである場合は、与えられた元を群の生成元の積として分解したものを要求する。古典的には、たとえ$G$が可換群だったとしてもこれらの問題は ${\rm polylog(|G|)}$の問い合わせで解くことは出来ない。可換群については、Moscaによって示されたように [74] 、量子計算機はこれらの問題を可換隠れ部分群問題に帰着することで ${\rm polylog(|G|)}$の問い合わせで解くことが出来る。さらに、Watrousによって示されたように [91] 、量子計算機は任意の可解群についてのこれらの問題も ${\rm polylog(|G|)}$の問い合わせで解くことが出来る。オラクルとしてではなく、有限体上の行列として与えられた群については、位数発見と構造的なメンバーシップ問題は離散対数問題や因数分解の量子アルゴリズムを用いて多項式時間で解くことが出来る [124] 。群同型の項も見よ。
Algorithm: 群同型
Speedup: 超多項式的
詳細
$G$を有限群だとする。$G$の全ての元は任意のラベル(ビット列)が割り当てられている。群の元のラベルの順序対が与えられた時、群オラクルはそれらの積のラベルを返す。2つの群$G$と$G'$に対する群オラクルに問い合わせる事が出来、それぞれの群の生成元のリストも与えられているもとで、$G$と$G'$が同型かどうかを決定しなければならない。可換群に対しては、参考文献 [127] で与えられている任意の可換群を巡回群の直積に分解する量子アルゴリズムを適用することで${\rm poly}(\log{|G|}, \log{|G'|})$回のオラクルへの問い合わせでこの問題を解くことが出来る。参考文献 [128] の量子アルゴリズムは、非可換群の或るクラス$\mathscr{S}$に対して群同型問題を${\rm poly}(\log{|G|}, \log{|G'|})$回の問い合わせで解くことが出来る。具体的に言うと、もし$G$が$G=A,y$となるような正規可換部分群$A$と、$|A|$と互いに素な位数の元$y$を持っているならば、$G$は$\mathscr{S}$に属している。最近、Zatloukalによって、群同型に密接に関連した問題、即ち群の拡大の同等性テストのいくつかの例に対して指数的量子加速が与えられた [202] 。
Algorithm: 統計的有意差
Speedup: 多項式的
詳細
定義域が$1$から$T$までの整数で値域が$1$から$N$までの整数であるような2つのブラックボックス$A$と$B$が与えられているとする。許されている入力から一様ランダムに選ぶことで、可能な出力の確率分布を得ることが出来る。行いたいタスクは、$A$と$B$によって決まる出力確率分布間の$L1$距離を定数精度で近似することである。古典的には、必要な問い合わせ回数はどうしても$N$に対して線形に増えてしまう。参考文献 [117] で示されているように、量子計算機はこのタスクを$O(\sqrt{N})$回の問い合わせで達成することが出来る。確率分布の一様性と直交性を近似的に決めるという問題も量子計算機を用いれば$O(N^{1/3})$回の問い合わせで解くことが出来る。主要なツールは参考文献 [16] の量子数え上げアルゴリズム(quantum counting algorithm)である。このタスクに対する量子アルゴリズムは参考文献 [265] においてさらに改良された。
Algorithm: 有限環とイデアル
Speedup: 超多項式的
詳細
有限環$R$上で足し算と掛け算を実行するブラックボックスが$R$の生成元の集合と共に与えられているとする。但し、$R$は必ずしも可換では無い。加法に関して、$R$は有限可換群$(R,+)$になっている。参考文献 [119] で示されている通り、量子計算機を用いれば$(R,+)\simeq\langle h_1\rangle\times\ldots\times\langle h_m\rangle$を満たす加法生成元の集合$\{ h_1,\ldots,h_m \} \subset R$を${\rm poly}(\log{|R|})$の時間で発見することが出来る。ここで、$m$は$|R|$の対数の多項式である。これは$R$に対するmultiplication tensorを効率的な計算を可能にする。参考文献 [118] で示されている通り、$R$の任意のイデアルに対して加法によって生成される集合を同様の方法で発見することが出来る。これは、2つのイデアルの交わりの発見、それらの商の発見、与えられた環の要素が与えられたイデアルに含まれているかどうかの証明、与えられた要素が可逆元かどうかを証明し、そうである場合にはその逆元を発見すること、加法単位元と乗法単位元の発見、イデアルの位数の計算、環上の線型方程式を解くこと、イデアルが最大かどうかの判定、零化イデアルの発見、環準同型の全射性と単射性のテスト、を可能にする。参考文献 [120] で示されている通り、与えられた多項式が与えられた有限ブラックボックス環上で$0$に等しいかどうかを効率良く決定するために量子計算機を使うことも出来る。これらの問題に対する既知の古典アルゴリズムは${\rm poly}(|R|)$でスケールする。
Algorithm: 偽造コイン
Speedup: 多項式的
詳細
$N$個のコインが与えられ、その内$k$個は偽造コインだとする。本物のコインは全て同じ重さで、偽造コイン同士も本物のコインとは異なる等しい重さになっている。そして、コインの部分集合の任意のペアの重さを上皿秤を用いて比較することが出来る。古典的には、全ての偽造コインを見極めるためには$\Omega(k\log (N/k))$回秤に掛ける必要がある。元の個数が同じであるようなコインの部分集合のペアを与えられた時に、重さが同じか違うかを示す1ビットを出力するオラクルを導入することが出来る。TerhalとSmolinの研究 [137] をもとにして、Iwamaらは量子計算機を使えば$O(k^{1/4})$回問い合わせするだけで全ての偽造コインを見極められることを示した [136] 。量子加速の裏にある核となるテクニックは、振幅増幅とBernstein-Vaziraniアルゴリズムである。
Algorithm: 行列の階数
Speedup: 多項式的
詳細
$n\times m$行列$A$の(整数)要素にアクセス出切るオラクルが与えられているとする。行いたいタスクはその行列の階数を求めることである。古典的には、この問題は$nm$のオーダーの問い合わせを必要とする。参考文献 [149] をもとにして、Belovsは行列の階数が少なくとも$r$であるという約束が与えられた時により少ない問い合わせ回数でこの問題を解くことが出来る量子アルゴリズムを提案した [150] 。具体的に言うと、Belovsのアルゴリズムは$O(\sqrt{r(n-r+1)}LT)$回の問い合わせを用いる。ここで、$L$は$A$の$r$個の最大特異値の逆数の二乗平均平方根で、$T$は行列がどれだけ疎であるかに依存した因子である。一般の$A$に対しては、$T=O(\sqrt{nm})$である。$A$が任意の行または列に対して高々$k$個の非零要素しか持っていない場合には、$T=O(k\log{(n+m)})$となる。($k$-sparseの場合に同じ問い合わせ計算量を達成するためには、オラクルが列番号を入力とし、その列の非零行列要素のリストを出力しなければならない。)重要な特殊ケースとして、これらの量子アルゴリズムは、行列式問題(determinant problem)とも呼ばれることがある平方行列が特異行列かどうかを決定する問題を解くために使うことが出来る。一般の$A$に対しては、行列式問題の量子問い合わせ計算量は古典問い合わせ計算量よりも低くない [151] 。しかし、参考文献 [151] は疎であることや小さい特異値が無いなどの約束が$A$に与えられた場合の量子加速の可能性を除外してはいない。
Algorithm: 半環上の行列積
Speedup: 多項式的
詳細
半環とは足し算と掛け算が出来、加法逆元の存在を除いて全ての環の公理に従う集合である。様々な半環上での行列積はグラフに関する問題に対して多くの応用がある。半環上の行列積はスクールブック法(schoolbook multiplication)を率直にグローバー探索のアイデアを使って改良することによって加速することが出来る。具体的には、2つの$n\times n$行列の掛け算を$\tilde{O}(n^{5/2})$の時間で行う量子アルゴリズムを作ることが出来る。いくつかの半環に対してはこの量子アルゴリズムは既知の古典アルゴリズムより性能が優れているが、他のいくつかの半環に対してはそうなっていない [206] 。特に興味深いのは、ORを足し算、ANDを掛け算として取り扱うブール半環である。$n^{2.373}$の計算量を持つ最適な古典アルゴリズムよりも性能が良い量子アルゴリズムは一般の場合におけるブール半環上の行列積に対しては知られていない。しかし、疎な入力と出力に対しては、量子的な加速が知られている。具体的に言うと、$A$と$B$を$n\times n$の二値行列だとする。さらに$C=AB$で、$C$の要素の内$1$と等しい(つまり、TRUEである)要素の個数を$l$とする。参考文献 [19, 155, 157] を改良することで、既知の最良の量子問い合わせ計算量の上界は$\widetilde{O}(n\sqrt{l})$であることが参考文献 [161] で示されている。もし入力の行列が疎ならば、或る領域においては、既知の古典アルゴリズムの中で最善のものに対する量子加速も発見されている [206] 。古典アルゴリズムとの詳細な比較に関しては、参考文献 [155, 206] を見よ。(max,min)半環上の行列積を$\widetilde{O}(n^{2.473})$の時間で、distance dominance半環上の行列積を$\widetilde{O}(n^{2.458})$の時間で実行する量子アルゴリズムが発見された [206] 。これら両方の問題に対して既知の古典アルゴリズムは最速のものでも$\widetilde{O}(n^{2.687})$の時間を要する。
Algorithm: 部分集合の発見
Speedup: 多項式的
詳細
関数$f:D\rightarrow R$にアクセスするオラクルが与えられている。ここで、$D$と$R$は有限集合である。或る性質$P\subset (D\times R)^k$が、例えばリストとして明示されている。我々のタスクは、$P$を満たす$D$のサイズ$k$の部分集合、即ち$((x_1,f(x_1)),\ldots,(x_k,f(x_k))) \in P$を発見する、またそのような部分集合が存在しない場合には棄却することである。大抵の場合、$f$への問い合わせ回数を最小にしてこのタスクを達成したい。参考文献 [7] の結果を一般化することによって、$O\left(|D|^{k/(k+1)}\right)$の量子問い合わせ回数でこのタスクを達成出来ることが参考文献 [162] で示された。注目すべき特別な場合として、このアルゴリズムは、和が或る望みの値になるようにリストから$k$個の数を選ぶ$k$-部分和問題を解くことが出来る。量子問い合わせ計算量に対するタイトな下界は参考文献 [163] で証明されている。
Algorithm: ワイルドカードを伴った探索(Search with Wildcards)
Speedup: 多項式的
詳細
ワイルドカードを伴った探索問題は、オラクル$f$に問い合わせをすることで隠れた$n$ビット列$x$を同定する問題である。$f$は$S\subseteq \{1,2,\ldots,n \}$と$y\in \{0,1 \}^{|S|}$を与えられた時、$S$で明示される$x$の部分列が$y$と等しければ$1$を、その他の場合には$0$を返すオラクルである。古典的には、この問題は$\Theta(n)$の問い合わせを必要とする。参考文献 [167] で示されているように、この問題の量子問い合わせ計算量は$\Theta(\sqrt{n})$である。興味深いことに、この$2$乗の加速は振幅増幅や量子ウォークではなく、所謂Pretty Good Measurmentの使用によって達成されている。参考文献 [167] では、combinatorial group testingという関連した問題に対する量子加速も与えられている。この結果とgroup testingに対するその後のより速い量子アルゴリズムに関しては、Junta testingとGroup testingの項目で議論されている。
Algorithm: ネットワークフロー
Speedup: 多項式的
詳細
ネットワークは、運ぶ容量(capacity)を示す数で辺がラベル付けされており2つの頂点が始点(source)と終点(sink)として指定されるような有向グラフである。ネットワーク上のフローとは、辺の容量を超えるフローが無く、さらに始点と終点に選ばれた頂点以外のそれぞれの頂点に対して流れ込む量と流れ出る量が等しいような辺へのフローの割り当てである。ネットワークフロー問題とは、ネットワークが与えられたもとで始点から終点へのフローの量が最大となるようなフロー(最大フロー)を探す問題である。$n$個の頂点と$m$個の辺から成り、容量が高々$U$以下の整数であるようなネットワークに対して、$O({\rm min} \{n^{7/6}\sqrt{m}U^{1/3},\sqrt{nU}m \}\times\log{n})$の時間で最大フローを探す量子アルゴリズムが参考文献 [168] で与えられた。ネットワークフロー問題はグラフの最大マッチング、すなわちそれぞれの頂点を高々他の1頂点としか接続しないような辺の最大部分集合を見つける問題と密接に関係している。参考文献 [168] では、グラフが二部グラフの場合には$O(n\sqrt{m+n}\log{n})$の時間で、一般の場合には$O(n^2(\sqrt{m/n}+\log{n})\log{n})$の時間で最大マッチングを発見する量子アルゴリズムが与えられている。これらのアルゴリズムの核となっているのはグローバー探索である。ネットワークフロー問題と最大マッチング問題の古典における計算量の既知の上界を述べるのは難しい。何故ならば、パラメータの値に依存して最も好ましい古典アルゴリズムが異なるからである。しかし、一定のパラメータ領域において上記の量子アルゴリズムは全ての既知の古典アルゴリズムよりも良いアルゴリズムとなっている。(詳細は参考文献 [168] を参照せよ。)
Algorithm: 電気抵抗
Speedup: 指数的
詳細
最大次数が$d$で$n$個の頂点からなる重み付きグラフにアクセスするオラクルが与えられる。この重み付きグラフの辺の重みは電気抵抗として解釈される。我々のタスクは選ばれた2頂点間の抵抗を計算することである。Wangは参考文献 [210] でこのタスクに対して${\rm poly}(\log{n},d,1/\phi,1/\epsilon)$の時間で動作する2つの量子アルゴリズムを与えた。ここで、$\phi$は重み付きグラフに対する正規化Laplacianのスペクトルギャップ(expansion of graph)で、答えは$1+\epsilon$倍の誤差の範囲内で与えられる。この問題に対する既知の古典アルゴリズムは$\log{n}$ではなく$n$の多項式時間で動作する。Wangのアルゴリズムの内1つは量子ウォークの新しい使い方をもとにしている。もう一方は連立一次方程式を解くための量子アルゴリズム [104] をもとにしている。隣接クエリモデル(adjucency query model)における電気抵抗問題に対する量子問い合わせ計算量の最初の上界は、approximate span programsを用いることで参考文献 [280] にて与えられている。
Algorithm: 機械学習
Speedup: 様々
詳細
機械学習は多種の計算問題を含んでおり、様々なアルゴリズムのテクニックを用いて取り組むことが出来る。この項目では、機械学習を改良するために使われる量子アルゴリズムのテクニックをまとめる。ここで紹介する量子アルゴリズムの多くは他の項目でも触れられている。参考文献 [214, 222, 250, 251, 309, 338, 339, 359] ではクラスタ発見、主成分分析、2クラス分類、様々な種類の回帰を、或る条件を満たしたデータが与えられたもとで加速するために、連立一次方程式を解くための量子アルゴリズム [104] を適用している。参考文献 [222] では、連立一次方程式を解くためのこれらの量子アルゴリズムが、持続性ホモロジーによるデータの集合の特徴付けを加速するために用いられた。連立一次方程式を解くための量子アルゴリズム [104] に基づかないクラスタ発見の方法は参考文献 [336] で与えられている。参考文献 [192, 195, 344, 345, 346, 347, 348] では、分類器の学習を加速するための断熱的な最適化手法の利用が探求されている。参考文献 [221] では、ボルツマンマシンをボルツマン因子に比例した振幅のコヒーレント状態を操作することで学習させる方法が提案された。グローバー検索と振幅増幅のような関連したテクニックを最新の古典機械学習アルゴリズムのサブルーチンに適用することで多項式的加速を得ることが出来る。例えば、参考文献 [358, 340, 341, 342, 343] を参照せよ。上記のカテゴリに当てはまらないその他の量子機械学習アルゴリズムとしては参考文献 [337, 349] のものがある。量子機械学習アルゴリズムにおけるいくつかの制限に関しては参考文献 [246] に良くまとめられている。ブラックボックスの隠れた構造を抽出する多くのその他の量子オラクルアルゴリズムは機械学習アルゴリズムとして捉えることが出来るだろう。例えば、参考文献 [146, 23, 11, 31, 212] を参照せよ。majority関数と"battleship"関数を学習するためのオラクルアルゴリズムは参考文献 [224] で与えられている。ノイズのあるオラクルから学習することにおける量子計算の大きな利点は参考文献 [236, 237] で与えられている。この分野の現状をまとめた物としては最近のレビュー記事 [299, 332, 333] や本 [331] がある。厳密には量子アルゴリズムの標準的な設定に従ってはいないものの、データそのものが重ね合わせ状態を取り得るような場合における量子学習に関連した一連の論文もある。例えば、参考文献 [350, 334, 335, 351, 352, 353, 354, 355, 356, 357] を参照せよ。
Algorithm: Junta testingとGroup testing
Speedup: 多項式的
詳細
関数$f~:~\{0,1\}^n\rightarrow\{0,1\}$が入力ビットのうち高々$k$ビットにしか依存しない時、その関数は$k$-juntaであると言う。$k$-junta testingとは与えられた関数が$k$-juntaか任意の$k$-juntaから$\epsilon$離れた(訳者注: 或る関数$f,g$が、入力$x$を一様ランダムに選んだ下で${\rm Pr}_x[f(x)\neq g(x)]>\epsilon$を満たす時、$f$は$g$から$\epsilon$離れていると言う。)関数かを判別する問題である。明らかでは無いが、この問題はgroup testingと密接に関係している。group testingは関数$f~:~\{1,2,\ldots,n\}\rightarrow\{0,1\}$によって定義される問題である。この問題では、$\{1,2,\ldots,n\}$の部分集合を入力とする$F$に問い合わせが出来るオラクルが与えられる。$F$は、$f(x)=1$となるような$x\in S$が存在するならば$F(S)=1$となり、その他の場合には$F(S)=0$となる。参考文献 [266] において、$k$-junta問題を$\widetilde{O}(\sqrt{k/\epsilon})$回の問い合わせと$\widetilde{O}(n\sqrt{k/\epsilon})$の時間で解く量子アルゴリズムが与えられた。これは最適な古典アルゴリズムに対して$2$乗の加速を実現しており、参考文献 [267] で与えられている$k$-junta testingのための量子アルゴリズムをより良いものにしている。gap(近似)版のgroup testing (gapped version of the group testing)に対する多項式的加速は参考文献 [266] にて達成されている。この結果は先行する参考文献 [167, 268] の結果を改良することで得られている。
参考文献
7
Andris Ambainis
Quantum walk algorithm for element distinctness.
SIAM Journal on Computing, 37:210-239, 2007.
arXiv:quant-ph/0311001
8
Andris Ambainis, Andrew M. Childs, Ben W.Reichardt, Robert Špalek, and Shengyu Zheng
Every AND-OR formula of size N can be evaluated in time $n^{1/2+o(1)}$ on a quantum computer.
In Proceedings of the 48th IEEE Symposium on the Foundations of Computer Science, pages 363-372, 2007.
arXiv:quant-ph/0703015 and arXiv:0704.3628
9
Dave Bacon, Andrew M. Childs, and Wim van Dam
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.
In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pages 469-478, 2005.
arXiv:quant-ph/0504083
10
Michael Ben-Or and Avinatan Hassidim
Quantum search in an ordered list via adaptive learning.
arXiv:quant-ph/0703231, 2007.
11
Ethan Bernstein and Umesh Vazirani
Quantum complexity theory.
In Proceedings of the 25th ACM Symposium on the Theory of Computing, pages 11-20, 1993.
13
A. Berzina, A. Dubrovsky, R. Frivalds, L. Lace, and O. Scegulnaja
Quantum query complexity for some graph problems.
In Proceedings of the 30th Conference on Current Trends in Theory and Practive of Computer Science, pages 140-150, 2004.
14
D. Boneh and R. J. Lipton
Quantum cryptanalysis of hidden linear functions.
In Don Coppersmith, editor, CRYPTO '95, Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.
15
M. Boyer, G. Brassard, P. Høyer, and A. Tapp
Tight bounds on quantum searching.
Fortschritte der Physik, 46:493-505, 1998.
16
G. Brassard, P. Høyer, and A. Tapp
Quantum counting.
arXiv:quant-ph/9805082, 1998.
17
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp
Quantum amplitude amplification and estimation.
In Samuel J. Lomonaco Jr. and Howard E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series. American Mathematical Society, 2002.
arXiv:quant-ph/0005055
18
Gilles Brassard, Peter Høyer, and Alain Tapp
Quantum algorithm for the collision problem.
ACM SIGACT News, 28:14-19, 1997.
arXiv:quant-ph/9705002
19
Harry Buhrman and Robert Špalek
Quantum verification of matrix products.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 880-889, 2006.
arXiv:quant-ph/0409035
20
David Bulger
Quantum basin hopping with gradient-based local optimisation.
arXiv:quant-ph/0507193, 2005.
21
Harry Burhrman, Christoph Dürr, Mark Heiligman, Peter Høyer, Frédéric Magniez, Miklos Santha, and Ronald de Wolf
Quantum algorithms for element distinctness.
In Proceedings of the 16th IEEE Annual Conference on Computational Complexity, pages 131-137, 2001.
arXiv:quant-ph/0007016
22
Dong Pyo Chi, Jeong San Kim, and Soojoon Lee
Notes on the hidden subgroup problem on some semi-direct product groups.
Phys. Lett. A 359(2):114-116, 2006.
arXiv:quant-ph/0604172
23
A. M. Childs, L. J. Schulman, and U. V. Vazirani
Quantum algorithms for hidden nonlinear structures.
In Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, pages 395-404, 2007.
arXiv:0705.2784
24
Andrew Childs and Troy Lee
Optimal quantum adversary lower bounds for ordered search.
Proceedings of ICALP 2008
arXiv:0708.3396
26
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman
Exponential algorithmic speedup by quantum walk.
In Proceedings of the 35th ACM Symposium on Theory of Computing, pages 59-68, 2003.
arXiv:quant-ph/0209131
27
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung
Discrete-query quantum algorithm for NAND trees.
Theory of Computing, 5:119-123, 2009.
arXiv:quant-ph/0702160
28
Andrew M. Childs and Wim van Dam
Quantum algorithm for a generalized hidden shift problem.
In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1225-1232, 2007.
arXiv:quant-ph/0507190.
29
Richard Cleve, Dmitry Gavinsky, and David L. Yeung
Quantum algorithms for evaluating MIN-MAX trees.
In Theory of Quantum Computation, Communication, andCryptography, pages 11-15,
Springer, 2008. (LNCS Vol. 5106)
arXiv:0710.5794.
30
J. Niel de Beaudrap, Richard Cleve, and John Watrous
Sharp quantum versus classical query complexity separations.
Algorithmica, 34(4):449-461, 2002.
arXiv:quant-ph/0011065v2.
31
Thomas Decker, Jan Draisma, and Pawel Wocjan
Quantum algorithm for identifying hidden polynomials.
Quantum Information and Computation, 9(3):215-230, 2009.
arXiv:0706.1219.
32
David Deutsch
Quantum theory, the Church-Turing principle, and the universal quantum computer.
Proceedings of the Royal Society of London Series A, 400:97-117, 1985.
33
David Deutsch and Richard Jozsa
Rapid solution of problems by quantum computation.
Proceedings of the Royal Society of London Series A, 493:553-558, 1992.
34
Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla
Quantum query complexity of some graph problems.
SIAM Journal on Computing, 35(6):1310-1328, 2006.
arXiv:quant-ph/0401091.
35
Christoph Dürr and Peter Høyer
A quantum algorithm for finding the minimum.
arXiv:quant-ph/9607014, 1996.
36
Christoph Dürr, Mehdi Mhalla, and Yaohui Lei
Quantum query complexity of graph connectivity.
arXiv:quant-ph/0303169, 2003.
37
Mark Ettinger, Peter Høyer, and Emanuel Knill
The quantum query complexity of the hidden subgroup problem is polynomial.
Information Processing Letters, 91(1):43-48, 2004.
arXiv:quant-ph/0401083.
38
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
A quantum algorithm for the Hamiltonian NAND tree.
Theory of Computing 4:169-190, 2008.
arXiv:quant-ph/0702144.
39
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser
Invariant quantum algorithms for insertion into an ordered list.
arXiv:quant-ph/9901059, 1999.
43
K. Friedl, G. Ivanyos, F. Magniez, M. Santha, and P. Sen
Hidden translation and translating coset in quantum computing.
SIAM Journal on Computing Vol. 43, pp. 1-24, 2014.
Appeared earlier in Proceedings of the 35th ACM Symposium on Theory of Computing, pages 1-9, 2003.
arXiv:quant-ph/0211091.
44
D. Gavinsky
Quantum solution to the hidden subgroup problem for poly-near-Hamiltonian-groups.
Quantum Information and Computation, 4:229-235, 2004.
48
Lov K. Grover
Quantum mechanics helps in searching for a needle in a haystack.
Physical Review Letters, 79(2):325-328, 1997.
arXiv:quant-ph/9605043.
51
Sean Hallgren, Alexander Russell, and Amnon Ta-Shma
Normal subgroup reconstruction and quantum computation using group representations.
SIAM Journal on Computing, 32(4):916-934, 2003.
52
Mark Heiligman
Quantum algorithms for lowest weight paths and spanning trees in complete graphs.
arXiv:quant-ph/0303131, 2003.
53
Yoshifumi Inui and François Le Gall
Efficient quantum algorithms for the hidden subgroup problem over a class of semi-direct product groups.
Quantum Information and Computation, 7(5/6):559-570, 2007.
arXiv:quant-ph/0412033.
54
Yuki Kelly Itakura
Quantum algorithm for commutativity testing of a matrix set.
Master's thesis, University of Waterloo, 2005.
arXiv:quant-ph/0509206.
55
Gábor Ivanyos, Frédéric Magniez, and Miklos Santha
Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem.
In Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures, pages 263-270, 2001.
arXiv:quant-ph/0102014.
56
Gábor Ivanyos, Luc Sanselme, and Miklos Santha
An efficient quantum algorithm for the hidden subgroup problem in extraspecial groups.
In Proceedings of the 24th Symposium on Theoretical Aspects of Computer Science, 2007.
arXiv:quant-ph/0701235.
57
Gábor Ivanyos, Luc Sanselme, and Miklos Santha
An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups.
In LATIN 2008: Theoretical Informatics, pg. 759-771,Springer (LNCS 4957).
arXiv:0707.1260.
61
Stephen P. Jordan
Fast quantum algorithm for numerical gradient estimation.
Physical Review Letters, 95:050501, 2005.
arXiv:quant-ph/0405146.
62
Stephen P. Jordan
Quantum Computation Beyond the Circuit Model.
PhD thesis, Massachusetts Institute of Technology, 2008.
arXiv:0809.2307.
66
Greg Kuperberg
A subexponential-time quantum algorithm for the dihedral hidden subgroup problem.
SIAM Journal on Computing, 35(1):170-188, 2005.
arXiv:quant-ph/0302112.
69
Chris Lomont
The hidden subgroup problem - review and open problems.
arXiv:quant-ph/0411037, 2004.
70
Frédéric Magniez, Miklos Santha, and Mario Szegedy
Quantum algorithms for the triangle problem.
SIAM Journal on Computing, 37(2):413-424, 2007.
arXiv:quant-ph/0310134.
71
Carlos Magno, M. Cosme, and Renato Portugal
Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups.
arXiv:quant-ph/0703223, 2007.
72
Cristopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman
The power of basis selection in Fourier sampling: the hidden subgroup problem in affine groups.
In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pages 1113-1122, 2004.
arXiv:quant-ph/0211124.
73
M. Mosca
Quantum searching, counting, and amplitude amplification by eigenvector analysis.
In R. Freivalds, editor, Proceedings of International Workshop on Randomized Algorithms, pages 90-100, 1998.
74
Michele Mosca
Quantum Computer Algorithms.
PhD thesis, University of Oxford, 1999.
75
Ashwin Nayak and Felix Wu
The quantum query complexity of approximating the median and related statistics.
In Proceedings of 31st ACM Symposium on the Theory of Computing, 1999.
arXiv:quant-ph/9804066.
76
Michael A. Nielsen and Isaac L. Chuang.
Quantum Computation and Quantum Information.
Cambridge University Press, Cambridge, UK, 2000.
77
Erich Novak
Quantum complexity of integration.
Journal of Complexity, 17:2-16, 2001.
arXiv:quant-ph/0008124.
78
Oded Regev
Quantum computation and lattice problems.
In Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002.
arXiv:cs/0304005.
79
Oded Regev
A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space.
arXiv:quant-ph/0406151, 2004.
80
Ben Reichardt and Robert Špalek
Span-program-based quantum algorithm for evaluating formulas.
Proceedings of STOC 2008
arXiv:0710.2630.
81
Martin Roetteler and Thomas Beth
Polynomial-time solution to the hidden subgroup problem for a class of non-abelian groups.
arXiv:quant-ph/9812070, 1998.
86
Wim van Dam
Quantum algorithms for weighing matrices and quadratic residues.
Algorithmica, 34(4):413-428, 2002.
arXiv:quant-ph/0008059.
88
Wim van Dam and Sean Hallgren
Efficient quantum algorithms for shifted quadratic character problems.
arXiv:quant-ph/0011067, 2000.
89
Wim van Dam, Sean Hallgren, and Lawrence Ip
Quantum algorithms for some hidden shift problems.
SIAM Journal on Computing, 36(3):763-778, 2006.
arXiv:quant-h/0211140.
91
John Watrous
Quantum algorithms for solvable groups.
In Proceedings of the 33rd ACM Symposium on Theory of Computing, pages 60-67, 2001.
arXiv:quant-ph/0011023.
94
Andrew Yao
On computing the minima of quadratic forms.
In Proceedings of the 7th ACM Symposium on Theory of Computing, pages 23-26, 1975.
100
Eli Biham, Ofer Biham, David Biron, Markus Grassl, and Daniel Lidar
Grover's quantum search algorithm for an arbitrary initialamplitude distribution.
Physical Review A, 60(4):2742, 1999.
arXiv:quant-ph/9807027and arXiv:quant-ph/0010077
101
Andrew Childs, Shelby Kimmel, and Robin Kothari
The quantum query complexity of read-many formulas
In Proceedings of ESA 2012, pg. 337-348, Springer. (LNCS 7501)
arXiv:1112.0548, 2011.
103
A. M. Childs, A. J. Landahl, and P. A. Parrilo
Quantum algorithms for the ordered search problem via semidefiniteprogramming.
Physical Review A, 75 032335, 2007.
arXiv:quant-ph/0608161
104
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd
Quantum algorithm for solving linear systems of equations.
Physical Review Letters 15(103):150502, 2009.
arXiv:0811.3171.
105
Martin Roetteler
Quantum algorithms for highly non-linear Boolean functions.
Proceedings of SODA 2010
arXiv:0811.3208.
108
D. Simon
On the Power of Quantum Computation.
In Proceedings of the 35th Symposium on Foundations of Computer Science, pg. 116-123, 1994.
110
Yi-Kai Liu
Quantum algorithms using the curvelet transform.
Proceedings of STOC 2009, pg. 391-400.
arXiv:0810.4968.
117
Sergey Bravyi, Aram Harrow, and Avinatan Hassidim
Quantum algorithms for testing properties of distributions.
IEEE Transactions on Information Theory 57(6):3971-3981, 2011.
arXiv:0907.3920.
118
Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, and Joseph P. Brennan
Efficient quantum processing of ideals in finite rings.
arXiv:0908.0022, 2009.
119
V. Arvind, Bireswar Das, and Partha Mukhopadhyay
The complexity of black-box ring problems.
In Proceedings of COCCOON 2006, pg 126-145.
120
V. Arvind and Partha Mukhopadhyay
Quantum query complexity of multilinear identity testing.
In Proceedings of STACS 2009, pg. 87-98.
123
Ashley Montanaro
Quantum search with advice.
In Proceedings of the 5th conference on Theory of quantumcomputation, communication, and cryptography (TQC 2010)
arXiv:0908.3066
124
Laszlo Babai, Robert Beals, and Akos Seress
Polynomial-time theory of matrix groups.
In Proceedings of STOC 2009, pg. 55-64.
126
Aaron Denney, Cristopher Moore, and Alex Russell
Finding conjugate stabilizer subgroups in PSL(2;q) and relatedgroups.
Quantum Information and Computation 10(3):282-291, 2010.
arXiv:0809.2445.
127
Kevin K. H. Cheung and Michele Mosca
Decomposing finite Abelian groups.
Quantum Information and Computation 1(2):26-32, 2001.
arXiv:cs/0101004.
128
François Le Gall
An efficient quantum algorithm for some instances of the groupisomorphism problem.
In Proceedings of STACS 2010.
arXiv:1001.0608.
130
Martin Rötteler
Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm.
In Proceedings of MFCS 2009, pg 663-674.
arXiv:0911.4724.
133
Andris Ambainis
Quantum Search Algorithms.
SIGACT News, 35 (2):22-35, 2004.
arXiv:quant-ph/0504012
134
Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams
Nested quantum search and NP-hard problems.
Applicable Algebra in Engineering, Communication and Computing, 10 (4-5):311-338, 2000.
136
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Junichi Teruyama
Quantum Counterfeit Coin Problems.
In Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC2010), LNCS 6506, pp.73-84, 2010.
arXiv:1009.0416
137
Barbara Terhal and John Smolin
Single quantum querying of a database.
Physical Review A 58:1822, 1998.
arXiv:quant-ph/9705041
138
Andris Ambainis
Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations.
arXiv:1010.4458, 2010.
139
Frédéric Magniez and Ashwin Nayak
Quantum complexity of testing group commutativity.
In Proceedings of 32nd International Colloquium on Automata,Languages and Programming. LNCS 3580, pg. 1312-1324, 2005.
arXiv:quant-ph/0506265
140
Andrew Childs and Robin Kothari
Quantum query complexity of minor-closed graph properties.
In Proceedings of the 28th Symposium on Theoretical Aspects of Computer Science (STACS 2011), pg. 661-672
arXiv:1011.1443
141
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha
Search via quantum walk.
In Proceedings STOC 2007, pg. 575-584.
arXiv:quant-ph/0608026
142
Dmitry Gavinsky, Martin Roetteler, and Jérémy Roland
Quantum algorithm for the Boolean hidden shift problem.
In Proceedings of the 17th annual international conferenceon Computing and combinatorics (COCOON '11), 2011.
arXiv:1103.3017
143
Mark Ettinger and Peter Høyer
On quantum algorithms for noncommutative hidden subgroups.
Advances in Applied Mathematics, Vol. 25, No. 3, pg. 239-251, 2000.
arXiv:quant-ph/9807029
144
Andris Ambainis, Andrew Childs, and Yi-Kai Liu
Quantum property testing for bounded-degree graphs.
In Proceedings of RANDOM '11: Lecture Notes in Computer Science 6845, pp. 365-376, 2011.
arXiv:1012.3174
146
Ashley Montanaro
The quantum query complexity of learning multilinearpolynomials.
Information Processing Letters, 112(11):438-442, 2012.
arXiv:1105.3310.
147
Tad Hogg
Highly structured searches with quantum computers.
Physical Review Letters 80: 2473, 1998.
148
Markus Hunziker and David A. Meyer
Quantum algorithms for highly structured search problems.
Quantum Information Processing, Vol. 1, No. 3, pg. 321-341, 2002.
149
Ben Reichardt
Span programs and quantum query complexity: The general adversarybound is nearly tight for every Boolean function.
In Proceedings of the 50th IEEE Symposium on Foundations ofComputer Science (FOCS '09), pg. 544-551, 2009.
arXiv:0904.2759
150
Aleksandrs Belovs
Span-program-based quantum algorithm for the rank problem.
arXiv:1103.0842,2011.
151
Sebastian Dörn and Thomas Thierauf
The quantum query complexity of the determinant.
Information Processing Letters Vol. 109, No. 6, pg. 305-328, 2009.
152
Aleksandrs Belovs
Span programs for functions with constant-sized 1-certificates.
In Proceedings of STOC 2012, pg. 77-84.
arXiv:1105.4024.
153
Troy Lee, Frédéric Magniez, and Mikos Santha
A learning graph based quantum query algorithm for findingconstant-size subgraphs.
Chicago Journal of Theoretical Computer Science,Vol. 2012, Article 10, 2012.
arXiv:1109.5135.
154
Aleksandrs Belovs and Troy Lee
Quantum algorithm for k-distinctness with prior knowledge on the input.
arXiv:1108.3022, 2011.
155
François Le Gall
Improved output-sensitive quantum algorithms for Boolean matrix multiplication.
In Proceedings of the 23rd Annual ACM-SIAM Symposium on DiscreteAlgorithms (SODA '12), 2012.
156
Dominic Berry
Quantum algorithms for solving linear differential equations.
arXiv:1010.2745, 2010.
157
Virginia Vassilevska Williams and Ryan Williams
Subcubic equivalences between path, matrix, and triangle problems.
In 51st IEEE Symposium on Foundations of Computer Science (FOCS '10) pg. 645 - 654, 2010.
158
Ben W. Reichardt
Reflections for quantum query algorithms.
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pg. 560-569, 2011.
arXiv:1005.1601
159
Ben W. Reichardt
Span-program-based quantum algorithm for evaluating unbalanced formulas.
arXiv:0907.1622, 2009.
160
Ben W. Reichardt
Faster quantum algorithm for evaluating game trees.
In Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pg. 546-559, 2011.
arXiv:0907.1623
161
Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Improving quantum query complexity of Boolean matrixmultiplication using graph collision.
In Proceedings of ICALP 2012, pg. 522-532.
arXiv:1112.5855.
162
Andrew M. Childs and Jason M. Eisenberg
Quantum algorithms for subset finding.
Quantum Information and Computation 5(7):593-604, 2005.
arXiv:quant-ph/0311038.
163
Aleksandrs Belovs and Robert Špalek
Adversary lower bound for the k-sum problem.
In Proceedings of ITCS 2013, pg. 323-328.
arXiv:1206.6528.
164
Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim
Super-polynomial quantum speed-ups for Boolean evaluation treeswith hidden structure.
ITCS 2012: Proceedings of the 3rd Innovations in Theoretical Computer Science, ACM, pg. 249-265.
arXiv:1101.0796
165
Shelby Kimmel
Quantum adversary (upper) bound.
39th International Colloquium on Automata, Languages and Programming - ICALP 2012 Volume 7391, p. 557-568.
arXiv:1101.0797
167
Andris Ambainis and Ashley Montanaro
Quantum algorithms for search with wildcards and combinatorialgroup testing.
arXiv:1210.1148, 2012.
168
Andris Ambainis and Robert Špalek
Quantum algorithms for matching and network flows.
Proceedings of STACS 2007, pg. 172-183.
arXiv:quant-ph/0508205
169
Nathan Wiebe, Daniel Braun, and Seth Lloyd
Quantum data-fitting.
Physical Review Letters 109, 050505, 2012.
arXiv:1204.5242
171
Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Nested quantum walks with quantum data structures.
In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA'13), pg. 1474-1485, 2013.
arXiv:1210.1199
172
Aleksandrs Belovs
Learning-graph-based quantum algorithm for k-distinctness.
Proceedings of STOC 2012, pg. 77-84.
arXiv:1205.1534, 2012.
173
Andrew Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
A time-efficient quantum walk for 3-distinctness using nested updates.
arXiv:1302.7316, 2013.
175
Troy Lee, Frédéric Magniez, and Miklos Santha
Improved quantum query algorithms for triangle finding andassociativity testing.
arXiv:1210.1014, 2012.
192
Kristen L. Pudenz and Daniel A. Lidar
Quantum adiabatic machine learning.
Quantum Information Processing, 12:2027, 2013.
arXiv:1109.0325.
195
Hartmut Neven, Vasil S. Denchev, Geordie Rose, and William G. Macready
Training a binary classifier with the quantum adiabatic algorithm.
arXiv:0811.0416,2008.
200
D. Gavinsky and T. Ito
A quantum query algorithm for the graph collision problem.
arXiv:1204.1527,2012.
201
Andris Ambainis, Kaspars Balodis, Jānis Iraids, Raitis Ozols, andJuris Smotrovs
Parameterized quantum query complexity of graph collision.
arXiv:1305.1021,2013.
202
Kevin C. Zatloukal
Classical and quantum algorithms for testing equivalence ofgroup extensions.
arXiv:1305.1327,2013.
206
François Le Gall and Harumichi Nishimura
Quantum algorithms for matrix products over semirings.
arXiv:1310.3898,2013.
207
Nolan Wallach
A quantum polylog algorithm for non-normal maximal cyclic hiddensubgroups in the affine group of a finite field.
arXiv:1308.1415,2013.
208
Lov Grover
Fixed-point quantum search.
Phys. Rev. Lett. 95(15):150501, 2005.
arXiv:quant-ph/0503205
209
Tathagat Tulsi, Lov Grover, and Apoorva Patel
A new algorithm for fixed point quantum search.
Quantum Information and Computation 6(6):483-494, 2005.
arXiv:quant-ph/0505007
210
Guoming Wang
Quantum algorithms for approximating the effective resistances of electrical networks.
arXiv:1311.1851
212
Thomas Decker, Peter Høyer, Gabor Ivanyos, and Miklos Santha
Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
arXiv:1305.1543
214
Seth Lloyd, Masoud Mohseni, and Patrick Robentrost
Quantum algorithms for supervised and unsupervised machine learning
arXiv:1307.0411
215
Ashley Montanaro
Quantum pattern matching fast on average
arXiv:1408.1816
216
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani
Strengths and weaknesses of quantum computing
SIAM J. Comput. 26(5):1524-1540, 1997
arXiv:quant-ph/9701001
217
H. Ramesh and V. Vinay
String matching in $\widetilde{O}(\sqrt{n} + \sqrt{m})$ quantum time
Journal of Discrete Algorithms 1:103-110, 2003
arXiv:quant-ph/0011049
218
Greg Kuperberg
Another subexponential-time quantum algorithm for the dihedralhidden subgroup problem
In Proceedings of TQC pg. 20-34, 2013
arXiv:1112.3333
219
Peter Høyer, Jan Neerbek, and Yaoyun Shi
Quantum complexities of ordered searching, sorting, and elementdistinctness
In Proceedings of ICALP pg. 346-357, 2001
arXiv:quant-ph/0102078
220
Amnon Ta-Shma
Inverting well conditioned matrices in quantum logspace
In Proceedings of STOC 2013 pg. 881-890.
221
Nathan Wiebe, Ashish Kapoor, and Krysta Svore
Quantum deep learning
arXiv:1412.3489
222
Seth Lloyd, Silvano Garnerone, and Paolo Zanardi
Quantum algorithms for topological and geometric analysis of big data
arXiv:1408.3106
223
David A. Meyer and James Pommersheim
Single-query learning from abelian and non-abelian Hammingdistance oracles
arXiv:0912.0583
224
Markus Hunziker, David A. Meyer, Jihun Park, James Pommersheim, andMitch Rothstein
The geometry of quantum learning
Quantum Information Processing 9:321-341, 2010.
arXiv:quant-ph/0309059
236
Andrew W. Cross, Graeme Smith, and John A. Smolin
Quantum learning robust to noise
arXiv:1407.5088
237
Aram W. Harrow and David J. Rosenbaum
Uselessness for an oracle model with internal randomness
Quantum Information and Computation 14(7/8):608-624, 2014
arXiv:1111.1462
240
Guoming Wang
Span-program-based quantum algorithm for tree detection
arXiv:1309.7713, 2013.
241
François Le Gall, Harumichi Nishimura, and Seiichiro Tani
Quantum algorithm for finding constant-sized sub-hypergraphsover 3-uniform hypergraphs
In Proceedings of COCOON, 2014. pg. 429-440
arXiv:1310.4127
246
Scott Aaronson
Read the fine print
Nature Physics 11:291-293, 2015.
[fulltext]
249
B. D. Clader, B. C. Jacobs, and C. R. Sprouse
Preconditioned quantum linear system algorithm
Phys. Rev. Lett. 110:250504, 2013.
arXiv:1301.2340
250
S. Lloyd, M. Mohseni, and P. Rebentrost
Quantum principal component analysis
Nature Physics. 10(9):631, 2014.
arXiv:1307.0401
251
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd
Quantum support vector machine for big data classification
Phys. Rev. Lett. 113, 130503, 2014.
arXiv:1307.0471
255
L. A. B. Kowada, C. Lavor, R. Portugal, and C. M. H. de Figueiredo
A new quantum algorithm for solving the minimum searching problem
International Journal of Quantum Information, Vol. 6, No. 3, pg. 427-436, 2008.
256
Sean Hallgren and Aram Harrow
Superpolynomial speedups based on almost any quantum circuit
Proceedings of ICALP 2008, pg. 782-795.
arXiv:0805.0007
257
Fernando G.S.L. Brandao and Michal Horodecki
Exponential quantum speed-ups are generic
Quantum Information and Computation, Vol. 13, Pg. 0901, 2013
arXiv:1010.3654
258
Scott Aaronson and Andris Ambainis
Forrelation: A problem that optimally separates quantum from classical computing.
arXiv:1411.5729, 2014.
259
Z. Gedik
Computational speedup with a single qutrit
arXiv:1403.5861, 2014.
261
David Cornwell
Amplified Quantum Transforms
arXiv:1406.0190, 2015.
262
T. Laarhoven, M. Mosca, and J. van de Pol
Solving the shortest vector problem in lattices faster using quantum search
Proceedings of PQCrypto13, pp. 83-101, 2013.
arXiv:1301.6176
263
Andrew M. Childs, Robin Kothari, and Rolando D. Somma
Quantum linear systems algorithm with exponentially improveddependence on precision
arXiv:1511.02306, 2015.
265
Ashley Montanaro
Quantum speedup of Monte Carlo methods
arXiv:1504.06987, 2015.
266
Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf
Efficient quantum algorithms for (gapped) group testing andjunta testing
arXiv:1507.03126, 2015.
267
A. Atici and R. A. Servedio
Quantum algorithms for learning and testing juntas
Quantum Information Processing, 6(5):323-348, 2007.
arXiv:0707.3479
268
Aleksandrs Belovs
Quantum algorithms for learning symmetric juntas via theadversary bound
Computational Complexity, 24(2):255-293, 2015.
(Also appears in proceedings of CCC'14).
arXiv:1311.6777
269
Stacey Jeffery and Shelby Kimmel
NAND-trees, average choice complexity, and effective resistance
arXiv:1511.02235, 2015.
270
Scott Aaronson, Shalev Ben-David, and Robin Kothari
Separations in query complexity using cheat sheets
arXiv:1511.01937, 2015.
272
Agnis Āriņš
Span-program-based quantum algorithms for graph bipartitenessand connectivity
arXiv:1510.07825, 2015.
273
Juan Bermejo-Vega and Kevin C. Zatloukal
Abelian hypergroups and quantum computation
arXiv:1509.05806, 2015.
274
Andrew Childs and Jeffrey Goldstone
Spatial search by quantum walk
Physical Review A, 70:022314, 2004.
arXiv:quant-ph/0306054
275
Shantanav Chakraborty, Leonardo Novo, Andris Ambainis, and Yasser Omar
Spatial search by quantum walk is optimal for almost all graphs
arXiv:1508.01327, 2015.
276
François Le Gall
Improved quantum algorithm for triangle finding viacombinatorial arguments
In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pg. 216-225, 2014.
arXiv:1407.0085
277
Ashley Montanaro
The quantum complexity of approximating the frequency moments
arXiv:1505.00113, 2015.
279
Bill Fefferman and Cedric Yen-Yu Lin
A complete characterization of unitary quantum space
arXiv:1604.01384, 2016.
280
Tsuyoshi Ito and Stacey Jeffery
Approximate span programs
arXiv:1507.00432, 2015.
296
Ashley Montanaro and Sam Pallister
Quantum algorithms and the finite element method
arXiv:1512.05903, 2015.
297
Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Fei Gao, and Qiao-Yan Wen
Quantum algorithm for the Toeplitz systems
arXiv:1608.02184, 2016.
299
J. Adcock, E. Allen, M. Day, S. Frick, J. Hinchliff, M. Johnson, S. Morley-Short, S. Pallister, A. Price, and S. Stanisic
Advances in quantum machine learning
arXiv:1512.02900, 2015.
303
Thomas G. Wong
Quantum walk search on Johnson graphs
arXiv:1601.04212, 2016.
304
Jonatan Janmark, David A. Meyer, and Thomas G. Wong
Global symmetry is unnecessary for fast quantum search
Physical Review Letters 112:210502, 2014.
arXiv:1403.2228
305
David A. Meyer and Thomas G. Wong
Connectivity is a poor indicator of fast quantum search
Physical Review Letters 114:110503, 2014.
arXiv:1409.5876
306
Thomas G. Wong
Spatial search by continuous-time quantum walk with multiple marked vertices
Quantum Information Processing 15(4):1411-1443, 2016.
arXiv:1501.07071
309
Iordanis Kerenidis and Anupam Prakash
Quantum recommendation systems
arXiv:1603.08675, 2016.
311
Aram W. Harrow and Ashley Montanaro
Sequential measurements, disturbance, and property testing
arXiv:1607.03236, 2016.
312
Martin Roetteler
Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
arXiv:1608.02005, 2016.
315
Gilles Brassard, Peter Høyer, and Alain Tapp
Quantum cryptanalysis of hash and claw-free functions
In Proceedings of the 3rd Latin American symposium on Theoretical Informatics (LATIN'98), pg. 163-169, 1998.
317
Chris Cade, Ashley Montanaro, and Aleksandrs Belovs
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness
arXiv:1610.00581, 2016.
318
A. Belovs and B. Reichardt
Span programs and quantum algorithms for st-connectivity and claw detection
In European Symposium on Algorithms (ESA'12) , pg. 193-204, 2012.
arXiv:1203.2603
319
Titouan Carette, Mathieu Laurière, and Frédéric Magniez
Extended learning graphs for triangle finding
arXiv:1609.07786, 2016.
320
F. Le Gall and N. Shogo
Quantum algorithm for triangle finding in sparse graphs
In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC'15), pg. 590-600, 2015.
330
Peter Høyer and Mojtaba Komeili
Efficient quantum walk on the grid with multiple marked elements
Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 42, 2016.
arXiv:1612.08958
331
Peter Wittek
Quantum Machine Learning: what quantum computing means to data mining
Academic Press, 2014.
332
Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione
An introduction to quantum machine learning
Contemporary Physics, 56(2):172, 2014.
arXiv:1409.3097
333
J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd
Quantum machine learning
arXiv:1611.09347
334
Esma Aïeur, Gilles Brassard, and Sébastien Gambs
Machine learning in a quantum world
In Advances in Artificial Intelligence: 19th Conference of the Canadian Society for Computational Studies of Intelligencepg. 431-442, Springer, 2006.
335
Vedran Dunjko, Jacob Taylor, and Hans Briegel
Quantum-enhanced machine learning
Phys. Rev. Lett 117:130501, 2016.
336
Nathan Wiebe, Ashish Kapoor, and Krysta Svore
Quantum algorithms for nearest-neighbor methods for supervised and unsupervised learning
Quantum Information and Computation 15(3/4): 0318-0358, 2015.
arXiv:1401.2142
337
Seokwon Yoo, Jeongho Bang, Changhyoup Lee, and Junhyoug Lee
A quantum speedup in machine learning: finding a N-bit Boolean function for a classification
New Journal of Physics 6(10):103014, 2014.
arXiv:1303.6055
338
Maria Schuld, Ilya Sinayskiy, and Frencesco Petruccione
Prediction by linear regression on a quantum computer
Physical Review A 94:022342, 2016.
arXiv:1601.07823
339
Zhikuan Zhao, Jack K. Fitzsimons, and Joseph F. Fitzsimons
Quantum assisted Gaussian process regression
arXiv:1512.03929
340
Esma Aïeur, Gilles Brassard, and Sébastien Gambs
Quantum speed-up for unsupervised learning
Machine Learning, 90(2):261-287, 2013.
341
Nathan Wiebe, Ashish Kapoor, and Krysta Svore
Quantum perceptron models
Advances in Neural Information Processing Systems 29 (NIPS 2016), pg. 3999–4007, 2016.
arXiv:1602.04799
342
G. Paparo, V. Dunjko, A. Makmal, M. Martin-Delgado, and H. Briegel
Quantum speedup for active learning agents
Physical Review X4(3):031002, 2014.
arXiv:1401.4997
343
Daoyi Dong, Chunlin Chen, Hanxiong Li, and Tzyh-Jong Tarn
Quantum reinforcement learning
IEEE Transactions on Systems, Man, and Cybernetics- Part B (Cybernetics)38(5):1207, 2008.
344
Daniel Crawford, Anna Levit, Navid Ghadermarzy, Jaspreet S. Oberoi, and Pooya Ronagh
Reinforcement learning using quantum Boltzmann machines
arXiv:1612.05695, 2016.
345
Steven H. Adachi and Maxwell P. Henderson
Application of Quantum Annealing to Training of Deep Neural Networks
arXiv:1510.06356, 2015.
346
M. Benedetti, J. Realpe-Gómez, R. Biswas, and A. Perdomo-Ortiz
Quantum-assisted learning of graphical models with arbitrary pairwise connectivity
arXiv:1609.02542, 2016.
347
M. Benedetti, J. Realpe-Gómez, R. Biswas, and A. Perdomo-Ortiz
Quantum-assisted learning of graphical models with arbitrary pairwise connectivity
arXiv:1609.02542, 2016.
348
M. H. Amin, E. Andriyash, J. Rolfe, B. Kulchytskyy, and R. Melko
Quantum Boltzmann machine
arXiv:1601.02036, 2016.
349
Peter Wittek and Christian Gogolin
Quantum enhanced inference in Markov logic networks
Scientific Reports7:45672, 2017.
arXiv:1611.08104, 2016.
350
N. H. Bshouty and J. C. Jackson
Learning DNF over the uniform distribution using a quantum example oracle
SIAM Journal on Computing28(3):1136-1153, 1999.
351
Srinivasan Arunachalam and Ronald de Wolf
A survey of quantum learning theory
arXiv:1701.06806, 2017.
352
Rocco A. Servedio and Steven J. Gortler
Equivalences and separations between quantum and classical learnability
SIAM Journal on Computing, 33(5):1067-1092, 2017.
353
Srinivasan Arunachalam and Ronald de Wolf
Optimal quantum sample complexity of learning algorithms
arXiv:1607.00932, 2016.
354
Alex Monràs, Gael Sentís, and Peter Wittek
Inductive quantum learning: why you are doing it almost right
arXiv:1605.07541, 2016.
355
A. Bisio, G. Chiribella, G. M. D'Ariano, S. Facchini, and P. Perinotti
Optimal quantum learning of a unitary transformation
Physical Review A 81:032324, 2010.
arXiv:0903.0543.
356
M. Sasaki, A. Carlini, and R. Jozsa
Quantum template matching
Physical Review A 64:022317, 2001.
arXiv:quant-ph/0102020.
357
Masahide Sasaki and Alberto Carlini
Quantum learning and universal quantum matching machine
Physical Review A 66:022303, 2002.
arXiv:quant-ph/0202173.
358
Esma Aïeur, Gilles Brassard, and Sébastien Gambs
Quantum clustering algorithms
In Proceedings of the 24th International Conference on Machine Learning (ICML), pg. 1-8, 2007.
359
Iordanis Kerenidis and Anupam Prakash
Quantum gradient descent for linear systems and least squares
arXiv:1704.04992, 2017.
360
Dan Boneh and Mark Zhandry
Quantum-secure message authentication codes
In Proceedings of Eurocrypt, pg. 592-608, 2013.
361
A. M. Childs, W. van Dam, S-H Hung, and I. E. Shparlinski
Optimal quantum algorithm for polynomial interpolation
In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pg. 16:1-16:13, 2016.
arXiv:1509.09271
363
Stacey Jeffery
Frameworks for Quantum Algorithms
PhD thesis, U. Waterloo, 2014.
364
Seiichiro Tani
An improved claw finding algorithm using quantum walk
In Mathematical Foundations of Computer Science (MFCS), pg. 536-547, 2007.
arXiv:0708.2584
365
K. Iwama and A. Kawachi
A new quantum claw-finding algorithm for three functions
New Generation Computing, 21(4):319-327, 2003.
369
Pedro C.S. Costa, Stephen Jordan, and Aaron Ostrander
Quantum algorithm for simulating the wave equation
arXiv:1711.05394, 2017.
374
Renato Portugal
Element distinctness revisited
arXiv:1711.11336, 2017.