Quantum Algorithm Zoo全訳 近似アルゴリズム、シミュレーションアルゴリズム
本記事はQuantum Algorithm Zoo全訳シリーズの一部です。
以下のリンクから他の記事に飛べます。
- 前書き
- 代数アルゴリズム、数論アルゴリズム
- オラクルアルゴリズム
- 近似アルゴリズム、シミュレーションアルゴリズム(本記事)
Algorithm: 量子シミュレーション
Speedup: 超多項式的
詳細
任意の $n$ 自由度の物理的に実現可能なハミルトニアン $H$ について、対応する時間発展演算子 $e^{-iHt}$ は ${\rm poly}(n,t)$ 個のゲートで実装できると信じられている。BPP=BQPでなければ、この問題は一般に古典計算機では多項式時間で解くことが出来ない。「一般的なハミルトニアンのクラス [25, 95, 92, 5, 12, 170, 205, 211, 244, 245, 278, 293, 294, 295, 372, 382] 」、「量子化学におけるダイナミクス [63, 68, 227, 310, 375] 」、「物性物理学 [1, 99, 145] 」、「相対論的量子力学 (Dirac方程式やKlein-Gordon方程式) [367, 369, 370] 」、「量子開放系 [376, 377, 378, 379] 」、「場の量子論 [107, 166, 228, 229, 230, 368] 」などについて、多くの量子シミュレーションのテクニックが開発されてきた。古典計算で量子系をシミュレートするのに指数的な時間を要することが、或るタスクについて量子計算機が古典計算機を上回るであろうという最初の提案にファインマンを導いた [40] 。局所ハミルトニアンの基底エネルギーを求める問題はQMA完全であり、従って量子計算機を用いても最悪ケースでは効率的に解けないだろうとされているが、幾つかのクラスのハミルトニアンに関しては基底状態 [102, 231, 232, 233, 234, 235, 308, 321, 322, 380, 381] や熱的な状態 [132, 121, 281, 282, 307] を近似する量子アルゴリズムが開発されてきた。或るクラスのテンソルネットワークの状態を準備する問題についても、効率的な量子アルゴリズムが得られている [323, 324, 325, 326, 327, 328] 。
Algorithm: 結び目不変量
Speedup: 超多項式的
詳細
組紐のプラット閉包に対するジョーンズ多項式(Jones polynomial)を、不定元に$e^{i2\pi/5}$を代入したもとで、或る加法的エラーで近似するのはBQP完全問題だということがFreedmanらによって示された [42, 41] 。Aharonovらはこの結果を、任意の$k$に対して$e^{i2\pi/k}$の場合へと拡張した [4, 2] 。WocjanとYardはこれをさらに一般化し、ジョーンズ多項式を特別な場合として含んでいるホムフリー多項式(HOMFLY polynomial)を推定するための量子アルゴリズムを示した [93] 。その後、Aharonovらはさらに、量子計算機を用いれば、平面グラフに対するより一般的なタット多項式(Tutte polynomial)を或る加法的エラーのもとで多項式時間で推定できることを示した [3] 。参考文献 [3] で得た近似の問題がどのパラメータ領域でBQP困難になるかは完全には分かっていない。(分配関数に対するアルゴリズムの箇所も参照せよ。)有限群の量子ダブル(quantum double)によって構成される絡み目不変量を加法的エラーで近似するための多項式時間量子アルゴリズムも発見された [174] 。(この問題がBQP困難かどうかは分かっていない。)参考文献 [83] で示されている通り、組紐の トレース 閉包に対するジョーンズ多項式を、不定元に$e^{i2\pi/5}$を代入したもとで、或る加法的エラーで近似する問題はDQC1完全問題である。
Algorithm: 3次元多様体の不変量
Speedup: 超多項式的
詳細
トゥラエフ-ビロ不変量(Turaev-Viro invariant)は3次元多様体を入力とし実数を出力する関数で、位相同型な多様体に対しては同じ値を出力する。ヒーガード分解(Heegaard splitting)によって決まる3次元多様体に対して、量子計算機は多項式時間でトゥラエフ-ビロ不変量の近似値を或る加算的エラーで計算することが出来、これはBQP完全な問題である [129] 。このことが分かる以前には、参考文献 [114] において、手術表示(surgery presentation)によって記述される多様体のウィッテン-レシェティヒン-トゥラエフ不変量(Witten-Reshitikhin-Turaev invariant, WRT不変量)を加算的エラーで近似するための多項式時間量子アルゴリズムが与えられていた。WRT不変量は2乗するとトゥラエフ-ビロ不変量になるが、参考文献 [114] で考えられている近似の問題がBQP完全かどうかは分かっていない。量子計算と3次元多様体の不変量との有り得る関連についての示唆は参考文献 [115] でも与えられている。
Algorithm: 分配関数
Speedup: 超多項式的
詳細
有限個の状態を取り得る古典系を考え、その状態の集合を$S$とする。この古典系に対する分配関数は$Z=\sum_{s\in S}e^{-E(s)/{kT}}$で与えられる。ここで、$T$は温度、$k$はボルツマン定数、$E(s)$は状態$s$の時のエネルギーである。基本的に全ての熱力学的な量は、分配関数を適切に偏微分することによって計算することが出来る。ポッツ模型(Potts model)の分配関数はタット多項式(Tutte polynomial)の特別な場合である。タット多項式を近似するための量子アルゴリズムは参考文献 [3] で与えられている。これらのアプローチの関係性は参考文献 [67] で議論されている。分配関数を推定するその他の量子アルゴリズムは参考文献 [112, 113, 45, 47] で与えられている。"エネルギー"が複素数になることを許した場合のBQP完全性に関する結果は参考文献 [113] で与えられている。熱平衡化過程をシミュレートすることで分配関数を近似する方法は参考文献 [121] で与えられている。一般の分配関数の近似における$2$乗の加速に関する結果は参考文献 [122] で与えられている。参考文献 [265] では、量子ウォークをもとにして、分配関数の評価の多項式的加速を達成する方法が与えられている。
Algorithm: 断熱アルゴリズム
Speedup: 不明
詳細
断熱量子計算では、基底状態が容易に準備できる初期ハミルトニアンからスタートし、基底状態に或る計算問題の答えを埋め込んだハミルトニアンにゆっくりと変化させていく。断熱定理により、ハミルトニアンの変化が十分ゆっくりであれば、系はその時間ごとに基底状態を追従する。断熱アルゴリズムの計算時間は最悪のケースでは $1/\gamma^3$ でスケールする。ただし、 $\gamma$ は基底状態と第一励起状態の最小の固有値のギャップである [185] 。もしハミルトニアンが十分に連続的に変化するなら、この値は $\tilde{O}(1/\gamma^2)$ まで改善できる [247] 。断熱量子計算は一番最初に Farhiらによって、NP完全な組合せ最適化問題を解く方法として提案された [96, 186] 。組合せ最適化問題を解くための断熱量子アルゴリズムは、典型的には負符号問題が起こらない"stoquastic"なハミルトニアンを用いる(訳注：stoquasticはstochasticとquantumをあわせたこの分野の造語)。こうしたアルゴリズムはときには量子アニーリングとして言及される。non-stoquasticな断熱量子計算は量子回路モデルと同等の計算能力を持つことが知られている [97] 。stoquasticなハミルトニアンを用いた断熱アルゴリズムは恐らく計算能力が劣っていると思われる [183] 。しかし、それでもなお古典計算よりも強力かもしれない。漸近的な断熱最適化アルゴリズムの計算時間は解析が難しいことで有名である。しかし、この点についていくつかの進展はある [179, 180, 181, 182, 187, 188, 189, 190, 191, 226] 。（並んで関連深いのは、量子アニーリングについての初期の文献である。これは最初は量子プロセスをシミュレートすることで機能する古典最適化アルゴリズムを引き合いに出していた。この事は焼きなまし法が熱的なプロセスをシミュレートすることで古典最適化アルゴリズムとして機能するのと似ている。例えば参考文献 [199, 198] を見よ。）断熱量子計算はグローバー探索と幾分か類似したプロセスを $O(\sqrt{N})$ の時間で行うことができる [98] 。より一般的なクラスの問題について$2$乗の高速化を実現する断熱量子アルゴリズム [184] は参考文献 [85] のテクニックを用いて構築されている。いくつかの特定の問題についても断熱量子アルゴリズムが提案されてきた。例えばページランク [176] 、機械学習 [192, 195] 、グラフの問題 [193, 194] などがある。いくつかの量子シミュレーションアルゴリズムもまた断熱的な状態準備を用いている。
Algorithm: 最適化問題の近似アルゴリズム
Speedup: 超多項式的
詳細
多くの組合せ最適化問題において、厳密な最適解を得るのはNP完全である。十分小さいエラーで近似解を求めるのがNP完全であることを証明するような近似困難性に関する結果も存在する。或る問題に関しては、多項式時間古典近似アルゴリズムによって達成される最適なエラー許容量とNP困難性が示されているエラー許容量の間にギャップがある。この領域において、量子計算による指数的加速が得られる可能性がある。参考文献 [242] において、Quantum Approximate Optimization Algorithm (QAOA)と呼ばれる組合せ最適化問題の近似解を得るための新しいアルゴリズムが提案された。その後、参考文献 [243] において、QAOAがMax E3LIN2という組合せ最適化問題を、当時知られていたどの多項式時間古典アルゴリズムよりも良い近似比で解くことが示された。しかしその後、より良い近似比(近似困難性によって決まる限界値に達する近似比)を達成する多項式時間古典アルゴリズムが発見された [260] 。現在、古典計算と比べてQAOAにどれだけの能力があるのかは盛んに研究されているテーマの1つである [300, 301, 302, 314] 。
Algorithm: 半正定値計画問題
Speedup: 超多項式的
詳細
$m+1$個の$n\times n$エルミート行列$C,A_1,A_2,\ldots,A_m$と$m$個の数$b_1,\ldots,b_m$が与えられた時、半正定値計画問題は${\rm tr}(CX)$を最大化する$n\times n$半正定値行列$X$を、${\rm tr}(A_jX)\le b_j$が$j=1,2,\ldots,m$に対して成り立つという制約のもとで見つける問題である。半正定値計画問題はオペレーションズ・リサーチ、組合せ最適化、量子情報において多くの応用があり、線形計画問題を特別な場合として含んでいる。参考文献 [313] を改良することで、$\pm\epsilon$の精度で半正定値計画問題を近似的に$\tilde{O}(\sqrt{m}\log{m}\cdot{\rm poly}(\log{n},r,\epsilon^{-1}))$の時間で解く量子アルゴリズムが提案された [383] 。ここで、$r$は$A_j$の階数の最大値である。$r$が$n$に比べて小さい時、この量子アルゴリズムは最速の古典アルゴリズムに対して$2$乗の加速を実現する。この量子アルゴリズムは振幅増幅と量子ギブスサンプリングをもとにして構成されている [121, 307] 。
Algorithm: ゼータ関数
Speedup: 超多項式的
詳細
$f(x,y)$を有限体$\mathbb{F}_p$上の$d$次多項式とする。拡大体$\mathbb{F}_{p^r}$上での$f(x,y)=0$の解の個数を$N_r$とする。$f$に対する(合同)ゼータ関数は$Z_f(T)=\exp{\bigg(\sum_{r=1}^\infty\frac{N_r}{r}T^r\bigg)}$で定義される。注目すべき点として、$Z_f(T)=\frac{Q_f(T)}{(1-pT)(1-T)}$が常に成り立つ。ここで、$Q_f(T)$は$2g$次多項式で、$g=\frac{1}{2}(d-1)(d-2)$は$f$の種数である。$Z_f(T)$が与えられた下では、任意の拡大体$\mathbb{F}_{p^r}$上において$f$の零点の数を簡単に計算することが出来る。$f$が定義されている最初の体の位数が素数でない場合でも、同様にしてゼータ関数を定義することが出来る。Kedlayaによって、量子計算機は有限体$\mathbb{F}_{p^r}$上の種数が$g$の曲線に対するゼータ関数を${\rm poly}(\log{p},r,g)$の時間で決定出来ることが示された [64] 。既知の古典アルゴリズムは最速のものでも$\log{p}$か$g$のどちらかに対して指数的な時間を必要とする。同じではないがいくらか関連した状況において、van Damは量子計算機が有限体上の方程式の解の数を効率良く近似出来るかもしれないということをリーマン(Riemann)ゼータ関数の零点と或る量子演算子の固有値の関係から予想した [87] 。
Algorithm: 重み多項式
Speedup: 超多項式的
詳細
$C$を$n$ビットから成る符号、つまり$\mathbb{Z}_2^n$の部分集合だとする。$C$の重み多項式は$S_C(x,y)=\sum_{c\in C}x^{|c|}y^{n-|c|}$で与えられる。ここで、$|c|$は$c$のハミング重みである。重み多項式は古典符号の研究においてとても有用である。$C$が線形符号の場合、重み多項式は$\mathbb{Z}_2$上の行列$A$を用いて$C=\{c~:~Ac=0\}$と定義される。この時、$S_C(x,y)=\sum_{c:Ac=0}x^{|c|}y^{n-|c|}$となる。これを一般化したものがQuadratically signed weight enumerators (QWGTs)で、$S(A,B,x,y)=\sum_{c:Ac=0}(-1)^{c^TBc}x^{|c|}y^{n-|c|}$と定義される。ここで、以下のような特別な場合を考えてみる。$A$を、${\rm diag}(A)=I$を満たす$\mathbb{Z}_2$上の$n\times n$行列だとする。そして、$A$の対角成分より上の成分を全て$0$にすることで作られる下三角行列を${\rm lwtr}(A)$と書くことにする。さらに、$l,k$を正の整数だとする。$|S(A,{\rm lwtr}(A),k,l)|\ge\frac{1}{2}(k^2+l^2)^{n/2}$が約束されている時に$S(A,{\rm lwtr}(A),k,l)$の符号を当てる問題はBQP完全問題であることがKnillとLaflammeによって示された [65] 。QWGTsの評価はイジング模型とポッツ模型(Potts model)の分配関数の評価とも密接に関連している [67, 45, 46] 。
Algorithm: シミュレーテッドアニーリング(焼きなまし法)
Speedup: 多項式的
詳細
シミュレーテッドアニーリングでは、確率行列$M_1,M_2,\ldots,M_n$で記述される一連のマルコフ連鎖を扱う。確率行列は、これらの極限分布$\pi_1,\pi_2,\ldots,\pi_n$が或る小さな$\epsilon$に対して$|\pi_{t+1}-\pi_t|<\epsilon$を満たすくらいゆっくりと変化する。大抵、これらの分布は温度が低くなっていく過程における熱力学的な分布として捉えることが出来る。もし$\pi_1$が簡単に用意出来るならば、一連のマルコフ連鎖を適用することで$\pi_n$からサンプリングすることが出来る。典型的には、$\pi_n$は何らかの最適化問題の良い解の分布になっていることが望ましい。$M_i$の最大固有値と2番目に大きい固有値の差を$\delta_i$とする。さらに$\delta={\rm min}_i\delta_i$を定義する。この古典アルゴリズムにかかる時間は$1/\delta$に比例する。Szegedyの結果 [135, 85] を用いることで、Sommaらは、量子計算機を使えば$1/\sqrt{\delta}$に比例した時間で$\pi_n$からサンプリング出来ることを示した [84, 177] 。古典マルコフ連鎖モンテカルロ法を量子ウォークによって加速出来る別の方法については参考文献 [265] で述べられている。
Algorithm: 文字列書き換え
Speedup: 超多項式的
詳細
文字列書き換えはとても一般的な計算モデルである。文字列書き換え系(文法と呼ばれることもある)は、或る部分文字列が他の或る部分文字列と置き換えることを許す書き換え規則のリストによって定まる。例えば、文脈自由文法はプッシュダウンオートマトンと等価である。参考文献 [59] において、JanzingとWocjanは或る文字列書き換え問題がPromiseBQP完全問題であることを示した。従って、量子計算機は多項式時間でこの問題を解くことが出来るが、古典計算機では多項式時間で解くことはおそらく出来無い。この問題とは、3つの文字列$s,t,t'$と文字列書き換え規則の集合が与えられ、これらが或る約束を満たしているとして、$s$から$t$を得る方法の数と$s$から$t'$を得る方法の数の差の或る近似値として求める問題である。同様に、グラフにおいて頂点のペア間の経路の数の差を近似的に求める、あるいはランダムウォークにおいて状態のペア間の遷移確率の差を近似的に求めるいくつかの問題もBQP完全問題である [58] 。
Algorithm: 行列の累乗
Speedup: 超多項式的
詳細
指数的に大きい疎行列の累乗の行列要素の近似において、量子計算機は指数的な加速を達成する。各列に高々${\rm polylog}(N)$個しか非零要素がなく、与えられた行について非零要素の集合が多項式時間で計算出来るような、$N\times N$の対称行列$A$を考える。今考えている問題は、任意の$1 \leq i \leq N$と任意の$m={\rm polylog}(N)$に対して$A^m$の$i$番目の対角要素$(A^m)_{ii}$を近似する問題である。要請される近似精度は、$\pm b^m\epsilon$の加法的エラーである。ここで、$b$は既知の$|A|$の上限値で、$\epsilon=1/{\rm polylog}(N)$である。JanzingとWocjanは、この問題が非対角要素に対する同様の問題と同じくPromiseBQP完全問題であることを示した [60] 。従って、量子計算機はこの問題を多項式時間で解くことが出来るが、古典計算機では多項式時間で解くことはおそらく出来無い。
参考文献
1
Daniel S. Abrams and Seth Lloyd
Simulation of many-body Fermi systems on a universal quantum computer.
Physical Review Letters, 79(13):2586-2589, 1997.
arXiv:quant-ph/9703054
2
Dorit Aharonov and Itai Arad
The BQP-hardness of approximating the Jones polynomial.
New Journal of Physics 13:035019, 2011.
arXiv:quant-ph/0605181
3
Dorit Aharonov, Itai Arad, Elad Eban, and Zeph Landau
Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane.
arXiv:quant-ph/0702008, 2007.
4
Dorit Aharonov, Vaughan Jones, and Zeph Landau
A polynomial quantum algorithm for approximating the Jones polynomial.
In Proceedings of the 38th ACM Symposium on Theory of Computing, 2006.
arXiv:quant-ph/0511096
5
Dorit Aharonov and Amnon Ta-Shma
Adiabatic quantum state generation and statistical zero knowledge.
In Proceedings of the 35th ACM Symposium on Theory of Computing, 2003.
arXiv:quant-ph/0301023.
12
D.W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders
Efficient quantum algorithms for simulating sparse Hamiltonians.
Communications in Mathematical Physics, 270(2):359-371, 2007.
arXiv:quant-ph/0508139
25
Andrew M. Childs
Quantum information processing in continuous time.
PhD thesis, MIT, 2004.
40
Richard P. Feynman
Simulating physics with computers.
International Journal of Theoretical Physics, 21(6/7):467-488, 1982.
41
Michael Freedman, Alexei Kitaev, and Zhenghan Wang
Simulation of topological field theories by quantum computers.
Communications in Mathematical Physics, 227:587-603, 2002.
42
Michael Freedman, Michael Larsen, and Zhenghan Wang
A modular functor which is universal for quantum computation.
Comm. Math. Phys. 227(3):605-622, 2002.
arXiv:quant-ph/0001108.
45
Joseph Geraci
A new connection between quantum circuits, graphs and the Isingpartition function
Quantum Information Processing, 7(5):227-242, 2008.
arXiv:0801.4833.
46
Joseph Geraci and Frank Van Bussel
A theorem on the quantum evaluation of weight enumerators for acertain class of cyclic Codes with a note on cyclotomic cosets.
arXiv:cs/0703129, 2007.
47
Joseph Geraci and Daniel A. Lidar
On the exact evaluation of certain instances of the Potts partition function by quantum computers.
Comm. Math. Phys. Vol. 279, pg. 735, 2008.
arXiv:quant-ph/0703023.
58
Dominik Janzing and Pawel Wocjan
BQP-complete problems concerning mixing properties of classical random walks on sparse graphs.
arXiv:quant-ph/0610235, 2006.
59
Dominik Janzing and Pawel Wocjan
A promiseBQP-complete string rewriting problem.
Quantum Information and Computation, 10(3/4):234-257, 2010.
arXiv:0705.1180.
60
Dominik Janzing and Pawel Wocjan
A simple promiseBQP-complete matrix problem.
Theory of Computing, 3:61-79, 2007.
arXiv:quant-ph/0606229.
63
Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik
Quantum algorithms for the simulation of chemical dynamics.
Proc. Natl. Acad. Sci. Vol. 105, pg. 18681, 2008.
arXiv:0801.2986.
64
Kiran S. Kedlaya
Quantum computation of zeta functions of curves.
Computational Complexity, 15:1-19, 2006.
arXiv:math/0411623.
65
E. Knill and R. Laflamme
Quantum computation and quadratically signed weight enumerators.
Information Processing Letters, 79(4):173-179, 2001.
arXiv:quant-ph/9909094.
67
Daniel A. Lidar
On the quantum computational complexity of the Ising spin glass partition function and of knot invariants.
New Journal of Physics Vol. 6, pg. 167, 2004.
arXiv:quant-ph/0309064.
68
Daniel A. Lidar and Haobin Wang
Calculating the thermal rate constant with exponential speedup on a quantum computer.
Physical Review E, 59(2):2429-2438, 1999.
arXiv:quant-ph/9807009.
83
Peter W. Shor and Stephen P. Jordan
Estimating Jones polynomials is a complete problem for one clean qubit.
Quantum Information and Computation, 8(8/9):681-714, 2008.
arXiv:0707.2831.
84
R. D. Somma, S. Boixo, and H. Barnum
Quantum simulated annealing.
arXiv:0712.1008, 2007.
85
M. Szegedy
Quantum speed-up of Markov chain based algorithms.
In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pg. 32, 2004.
87
Wim van Dam
Quantum computing and zeros of zeta functions.
arXiv:quant-ph/0405081, 2004.
92
Stephen Wiesner
Simulations of many-body quantum systems by a quantum computer.
arXiv:quant-ph/9603028, 1996.
93
Pawel Wocjan and Jon Yard
The Jones polynomial: quantum algorithms and applications in quantum complexity theory.
Quantum Information and Computation 8(1/2):147-180, 2008.
arXiv:quant-ph/0603069.
95
Christof Zalka
Efficient simulation of quantum systems by quantum computers.
Proceedings of the Royal Society of London Series A, 454:313, 1996.
arXiv:quant-ph/9603026.
96
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser
Quantum computation by adiabatic evolution.
arXiv:quant-ph/0001106,2000.
97
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, andOded Regev
Adiabatic Quantum Computation is Equivalent to Standard QuantumComputation.
SIAM Journal on Computing, 37(1):166-194, 2007.
arXiv:quant-ph/0405098
98
Jérémie Roland and Nicolas J. Cerf
Quantum search by local adiabatic evolution.
Physical Review A, 65(4):042308, 2002.
arXiv:quant-ph/0107015
99
L.-A. Wu, M.S. Byrd, and D. A. Lidar
Polynomial-Time Simulation of Pairing Models on a Quantum Computer.
Physical Review Letters, 89(6):057904, 2002.
arXiv:quant-ph/0108110
102
Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon
Simulated quantum computation of molecular energies.
Science, 309(5741):1704-1707, 2005.
arXiv:quant-ph/0604193
107
Tim Byrnes and Yoshihisa Yamamoto
Simulating lattice gauge theories on a quantum computer.
Physical Review A, 73, 022328, 2006.
arXiv:quant-ph/0510027.
112
Itai Arad and Zeph Landau
Quantum computation and the evaluation of tensor networks.
SIAM Journal on Computing, 39(7):3089-3121, 2010.
arXiv:0805.0040.
113
M. Van den Nest, W. Dür, R. Raussendorf, and H. J. Briegel
Quantum algorithms for spin models and simulable gate sets for quantum computation.
Physical Review A, 80:052334, 2009.
arXiv:0805.1214.
114
Silvano Garnerone, Annalisa Marzuoli, and Mario Rasetti
Efficient quantum processing of 3-manifold topologicalinvariants.
Advances in Theoretical and Mathematical Physics,13(6):1601-1652, 2009.
arXiv:quant-ph/0703037.
115
Louis H. Kauffman and Samuel J. Lomonaco Jr.
q-deformed spin networks, knot polynomials and anyonic topological quantum computation.
Journal of Knot Theory, Vol. 16, No. 3, pg. 267-332, 2007.
arXiv:quant-ph/0606114.
121
David Poulin and Pawel Wocjan
Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer.
Physical Review Letters 103:220502, 2009.
arXiv:0905.2199
122
Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe, and Daniel Nagaj
Quantum speed-up for approximating partition functions.
Physical Review A 80:022340, 2009.
arXiv:0811.0596
129
Gorjan Alagic, Stephen Jordan, Robert Koenig, and Ben Reichardt
Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation.
Physical Review A 82, 040302(R), 2010.
arXiv:1003.0923
132
K. Temme, T.J. Osborne, K.G. Vollbrecht, D. Poulin, and F. Verstraete
Quantum Metropolis Sampling.
Nature, Vol. 471, pg. 87-90, 2011.
arXiv:0911.3635.
135
Mario Szegedy
Spectra of Quantized Walks and a $\sqrt{\delta \epsilon}$ rule.
arXiv:quant-ph/0401053,2004.
145
G. Ortiz, J.E. Gubernatis, E. Knill, and R. Laflamme
Quantum algorithms for Fermionic simulations.
Physical Review A 64: 022319, 2001.
arXiv:cond-mat/0012334
166
Stephen Jordan, Keith Lee, and John Preskill
Quantum algorithms for quantum field theories.
Science, Vol. 336, pg. 1130-1133, 2012.
arXiv:1111.3633
170
Andrew Childs and Nathan Wiebe
Hamiltonian simulation using linear combinations of unitaryoperations.
Quantum Information and Computation 12, 901-924, 2012.
arXiv:1202.5822
174
Hari Krovi and Alexander Russell
Quantum Fourier transforms and the complexity of link invariantsfor quantum doubles of finite groups.
Commun. Math. Phys. 334, 743-777, 2015
arXiv:1210.1550
176
Silvano Garnerone, Paolo Zanardi, and Daniel A. Lidar
Adiabatic quantum algorithm for search engine ranking.
Physical Review Letters 108:230506, 2012.
177
R. D. Somma, S. Boixo, H. Barnum, and E. Knill
Quantum simulations of classical annealing.
Physical Review Letters 101:130504, 2008.
arXiv:0804.1571
179
Boris Altshuler, Hari Krovi, and Jérémie Roland
Anderson localization casts clouds over adiabatic quantum optimization.
Proceedings of the National Academy of Sciences107(28):12446-12450, 2010.
arXiv:0912.0746
180
Ben Reichardt
The quantum adiabatic optimization algorithm and local minima.
In Proceedings of STOC 2004, pg. 502-510. [Erratum].
181
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
Quantum adiabatic evolution algorithms versus simulated annealing.
arXiv:quant-ph/0201031, 2002.
182
E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer, and P. Shor
Quantum adiabatic algorithms, small gaps, and different paths.
Quantum Information and Computation, 11(3/4):181-214, 2011.
arXiv:0909.4766.
183
Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal
The Complexity of Stoquastic Local Hamiltonian Problems.
Quantum Information and Computation, 8(5):361-385, 2008.
arXiv:quant-ph/0606140.
184
Rolando D. Somma and Sergio Boixo
Spectral gap amplification.
SIAM Journal on Computing, 42:593-610, 2013.
arXiv:1110.2494.
185
Sabine Jansen, Mary-Beth Ruskai, Ruedi Seiler
Bounds for the adiabatic approximation with applications to quantum computation.
Journal of Mathematical Physics, 48:102111, 2007.
arXiv:quant-ph/0603175.
186
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem.
Science, 292(5516):472-475, 2001.
arXiv:quant-ph/0104129.
187
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel Nagaj
How to make the quantum adiabatic algorithm fail.
International Journal of Quantum Information, 6(3):503-516, 2008.
arXiv:quant-ph/0512159.
188
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Daniel Nagaj
Unstructured randomness, small gaps, and localization.
Quantum Information and Computation, 11(9/10):840-854, 2011.
arXiv:1010.0009.
189
Edward Farhi, Jeffrey Goldstone, Sam Gutmann
Quantum adiabatic evolution algorithms with different paths.
arXiv:quant-ph/0208135,2002.
190
Wim van Dam, Michele Mosca, and Umesh Vazirani
How powerful is adiabatic quantum computation?
In Proceedings of FOCS 2001, pg. 279-287.
arXiv:quant-ph/0206003[See also this.]
191
E. Farhi, D. Gosset, I. Hen, A. W. Sandvik, P. Shor, A. P. Young, and F. Zamponi
The performance of the quantum adiabatic algorithm on randominstances of two optimization problems on regular hypergraphs.
Physical Review A, 86:052334, 2012.
arXiv:1208.3757.
192
Kristen L. Pudenz and Daniel A. Lidar
Quantum adiabatic machine learning.
Quantum Information Processing, 12:2027, 2013.
arXiv:1109.0325.
193
Frank Gaitan and Lane Clark
Ramsey numbers and adiabatic quantum computing.
Physical Review Letters, 108:010501, 2012.
arXiv:1103.1345.
194
Frank Gaitan and Lane Clark
Graph isomorphism and adiabatic quantum computing.
Physical Review A, 89(2):022342, 2014.
arXiv:1304.5773,2013.
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.
198
S. Morita, H. Nishimori
Mathematical foundation of quantum annealing.
Journal of Methematical Physics, 49(12):125210, 2008.
199
A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, J. D. Doll
Quantum annealing: a new method for minimizing multidimensionalfunctions.
Chemical Physics Letters, 219:343-348, 1994.
205
D. W. Berry, R. Cleve, and R. D. Somma
Exponential improvement in precision for Hamiltonian-evolution simulation.
arXiv:1308.5424,2013.
211
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Exponential improvement in precision for simulating sparse Hamiltonians
arXiv:1312.1414
226
Michael Jarret and Stephen P. Jordan
Adiabatic optimization without local minima
Quantum Information and Computation, 15(3/4):0181-0199, 2015.
arXiv:1405.7552
227
Matthew B. Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer
Improving quantum algorithms for quantum chemistry
Quantum Information and Computation, 15(1/2):0001-0021, 2015.
arXiv:1403.1539
228
Stephen P. Jordan, Keith S. M. Lee, and John Preskill
Quantum simulation of scattering in scalar quantum field theories
Quantum Information and Computation, 14(11/12):1014-1080, 2014.
arXiv:1112.4833
229
Stephen P. Jordan, Keith S. M. Lee, and John Preskill
Quantum algorithms for fermionic quantum field theories
arXiv:1404.7115
230
Gavin K. Brennen, Peter Rohde, Barry C. Sanders, and Sukhi Singh
Multi-scale quantum simulation of quantum field theory using wavelets
arXiv:1412.0750
231
Hefeng Wang, Sabre Kais, Alán Aspuru-Guzik, and Mark R. Hoffmann.
Quantum algorithm for obtaining the energy spectrum of molecularsystems
Physical Chemistry Chemical Physics, 10(35):5388-5393, 2008.
arXiv:0907.0854
232
Ivan Kassal and Alán Aspuru-Guzik
Quantum algorithm for molecular properties and geometry optimization
Journal of Chemical Physics, 131(22), 2009.
arXiv:0908.1921
233
James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik
Simulation of electronic structure Hamiltonians using quantum computers
Molecular Physics, 109(5):735-750, 2011.
arXiv:1001.3855
234
Borzu Toloui and Peter J. Love
Quantum algorithms for quantum chemistry based on the sparsityof the CI-matrix
arXiv:1312.2529
235
James D. Whitfield
Spin-free quantum computational simulations and symmetry adapted states
Journal of Chemical Physics, 139(2):021105, 2013.
arXiv:1306.1147
242
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
A quantum approximate optimization algorithm
arXiv:1411.4028, 2014.
243
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
A quantum approximate optimization algorithm applied to abounded occurrence constraint problem
arXiv:1412.6062, 2014.
244
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, andRolando D. Somma
Simulating Hamiltonian dynamics with a truncated Taylor series
arXiv:1412.4687, 2014.
245
Dominic W. Berry, Andrew M. Childs, and Robin Kothari
Hamiltonian simulation with nearly optimal dependence on all parameters
arXiv:1501.01715, 2015.
247
Alexander Elgart and George A. Hagedorn
A note on the switching adiabatic theorem
Journal of Mathematical Physics 53(10):102202, 2012.
arXiv:1204.2318
260
Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, OdedRegev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, DavidWitmer, and John Wright
Beating the random assignment on constraint satisfaction problems of bounded degree
arXiv:1505.03424, 2015.
265
Ashley Montanaro
Quantum speedup of Monte Carlo methods
arXiv:1504.06987, 2015.
278
Rolando D. Somma
Quantum simulations of one dimensional quantum systems
arXiv:1503.06319, 2015.
281
Arnau Riera, Christian Gogolin, and Jens Eisert
Thermalization in nature and on a quantum computer
Physical Review Letters, 108:080402 (2012)
arXiv:1102.2389.
282
Michael J. Kastoryano and Fernando G. S. L. Brandao
Quantum Gibbs Samplers: the commuting case
Communications in Mathematical Physics, 344(3):915-957 (2016)
arXiv:1409.3435.
293
Rolando D. Somma
A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation
arXiv:1512.03416, 2015.
294
Guang Hao Low and Isaac Chuang
Optimal Hamiltonian simulation by quantum signal processing
arXiv:1606.02685, 2016.
295
Dominic W. Berry and Leonardo Novo
Corrected quantum walk for optimal Hamiltonian simulation
arXiv:1606.03443, 2016.
300
Cedric Yen-Yu Lin and Yechao Zhu
Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree
arXiv:1601.01744, 2016.
301
Dave Wecker, Matthew B. Hastings, and Matthias Troyer
Training a quantum optimizer
arXiv:1605.05370, 2016.
302
Edward Farhi and Aram W. Harrow
Quantum supremacy through the quantum approximate optimization algorithm
arXiv:1602.07674, 2016.
307
Anirban Naryan Chowdhury and Rolando D. Somma
Quantum algorithms for Gibbs sampling and hitting-time estimation
arXiv:1603.02940, 2016.
308
Edward Farhi, Shelby Kimmel, and Kristan Temme
A quantum version of Schoning's algorithm applied to quantum 2-SAT
arXiv:1603.06985, 2016.
310
Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer
Elucidating reaction mechanisms on quantum computers
arXiv:1605.03590, 2016.
313
Fernando G.S.L. Brandao and Krysta Svore
Quantum speed-ups for semidefinite programming
arXiv:1609.05537, 2016.
314
Z-C Yang, A. Rahmani, A. Shabani, H. Neven, and C. Chamon
Optimizing variational quantum algorithms using Pontryagins's minimum principle
arXiv:1607.06473, 2016.
321
Or Sattath and Itai Arad
A constructive quantum Lovász local lemma for commuting projectors
Quantum Information and Computation, 15(11/12)987-996pg, 2015.
arXiv:1310.7766
322
Martin Schwarz, Toby S. Cubitt, and Frank Verstraete
An information-theoretic proof of the constructive commutative quantum Lovász local lemma
arXiv:1311.6474
323
C. Shoen, E. Solano, F. Verstraete, J. I. Cirac, and M. M. Wolf
Sequential generation of entangled multi-qubit states
Physical Review Letters, 95:110503, 2005.
arXiv:quant-ph/0501096
324
C. Shoen, K. Hammerer, M. M. Wolf, J. I. Cirac, and E. Solano
Sequential generation of matrix-product states in cavity QED
Physical Review A, 75:032311, 2007.
arXiv:quant-ph/0612101
325
Yimin Ge, András Molnár, and J. Ignacio Cirac
Rapid adiabatic preparation of injective PEPS and Gibbs states
Physical Review Letters, 116:080503, 2016.
arXiv:1508.00570
326
Martin Schwarz, Kristan Temme, and Frank Verstraete
Preparing projected entangled pair states on a quantum computer
Physical Review Letters, 108:110502, 2012.
arXiv:1104.1410
327
Martin Schwarz, Toby S. Cubitt, Kristan Temme, Frank Verstraete, and David Perez-Garcia
Preparing topological PEPS on a quantum computer
Physical Review A, 88:032321, 2013.
arXiv:1211.4050
328
M. Schwarz, O. Buerschaper, and J. Eisert
Approximating local observables on projected entangled pair states
arXiv:1606.06301, 2016.
367
Francois Fillion-Gourdeau, Steve MacLean, and Raymond Laflamme
Quantum algorithm for the dsolution of the Dirac equation
arXiv:1611.05484, 2016.
368
Ali Hamed Moosavian and Stephen Jordan
Faster quantum algorithm to simulate Fermionic quantum field theory
arXiv:1711.04006, 2017.
369
Pedro C.S. Costa, Stephen Jordan, and Aaron Ostrander
Quantum algorithm for simulating the wave equation
arXiv:1711.05394, 2017.
370
Jeffrey Yepez
Highly covariant quantum lattice gas model of the Dirac equation
arXiv:1106.0739, 2011.
372
Bruce M. Boghosian and Washington Taylor
Simulating quantum mechanics on a quantum computer
Physica D 120:30-42, 1998.
[arXiv:quant-ph/9701019]
375
Kanav Setia and James D. Whitfield
Bravyi-Kitaev superfast simulation of fermions on a quantum computer
arXiv:1712.00446, 2017.
376
Richard Cleve and Chunhao Wang
Efficient quantum algorithms for simulating Lindblad evolution
arXiv:1612.09512, 2016.
377
M. Kliesch, T. Barthel, C. Gogolin, M. Kastoryano, and J. Eisert
Dissipative quantum Church-Turing theorem
Physical Review Letters 107(12):120501, 2011.
[arXiv:1105.3986]
378
A. M. Childs and T. Li
Efficient simulation of sparse Markovian quantum dynamics
arXiv:1611.05543, 2016.
379
R. Di Candia, J. S. Pedernales, A. del Campo, E. Solano, and J. Casanova
Quantum simulation of dissipative processes without reservoir engineering
Scientific Reports 5:9981, 2015.
380
R. Babbush, D. Berry, M. Kieferová, G. H. Low, Y. Sanders, A. Sherer, and N. Wiebe
Improved techniques for preparing eigenstates of Fermionic Hamiltonians
arXiv:1711.10460, 2017.
381
D. Poulin, A. Kitaev, D. S. Steiger, M. B. Hasting, and M. Troyer
Fast quantum algorithm for spectral properties
arXiv:1711.11025, 2017.
382
Guang Hao Low and Isaac Chuang
Hamiltonian simulation bt qubitization
arXiv:1610.06546, 2016.
383
F.G.S.L. Brandão, A. Kalev, T. Li, C. Y.-Y. Lin, K. M. Svore, and X. Wu
Exponential quantum speed-ups for semidefinite programming with applications to quantum learning
arXiv:1710.02581, 2017.