機能改善 イベント資料の投稿において、SlideShareやSpeakerDeckと同様に、Docswellの資料を埋め込みスライド表示できるように対応いたしました。資料の投稿機能は、資料URLを指定するだけで、URLから取得した情報を、適した形でconnpass上で表示・共有できる機能です

このエントリーをはてなブックマークに追加

Aug

9

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る

いくつかありますので絞って見て見ます。

Registration info

参加枠1

Free

FCFS
25/50

Description

はじめに

量子ゲートのアルゴリズムの殿堂
https://math.nist.gov/quantum/zoo/
こちらの中で、特に近似アルゴリズムシミュレーションアルゴリズムのいくつかの概要を見ていきます。

たとえば

量子シミュレーション

Algorithm: Quantum Simulation
Speedup: Superpolynomial
Description: It is believed that for any physically realistic Hamiltonian H on n degrees of freedom, the corresponding time evolution operator e−iHt can be implemented using poly(n,t) gates. Unless BPP=BQP, this problem is not solvable in general on a classical computer in polynomial time. Many techniques for quantum simulation have been developed for general classes of Hamiltonians [25,95,92,5,12,170,205,211,244,245,278,293,294,295,372,382], chemical dynamics [63,68,227,310,375], condensed matter physics [1,99, 145], relativistic quantum mechanics (the Dirac and Klein-Gordon equations) [367,369,370,371], open quantum systems [376, 377,378,379], and quantum field theory [107,166,228,229,230,368]. The exponential complexity of classically simulating quantum systems led Feynman to first propose that quantum computers might outperform classical computers on certain tasks [40]. Although the problem of finding ground energies of local Hamiltonians is QMA-complete and therefore probably requires exponential time on a quantum computer in the worst case, quantum algorithms have been developed to approximate ground [102,231,232,233,234,235,308,321,322,380,381] and thermal [132,121,281,282,307] states for some classes of Hamiltonians. Efficient quantum algorithms have been also obtained for preparing certain classes of tensor network states [323,324,325,326,327,328].

分配関数

Algorithm: Partition Functions
Speedup: Superpolynomial
Description: For a classical system with a finite set of states S the partition function is Z=∑s∈Se−E(s)/kT, where T is the temperature and k is Boltzmann's constant. Essentially every thermodynamic quantity can be calculated by taking an appropriate partial derivative of the partition function. The partition function of the Potts model is a special case of the Tutte polynomial. A quantum algorithm for approximating the Tutte polynomial is given in [3]. Some connections between these approaches are discussed in [67]. Additional algorithms for estimating partition functions on quantum computers are given in [112,113,45,47]. A BQP-completeness result (where the "energies" are allowed to be complex) is also given in [113]. A method for approximating partition functions by simulating thermalization processes is given in [121]. A quadratic speedup for the approximation of general partition functions is given in [122]. A method based on quantum walks, achieving polynomial speedup for evaluating partition functions is given in [265].

断熱計算
Algorithm: Adiabatic Algorithms
Speedup: Unknown
Description: In adiabatic quantum computation one starts with an initial Hamiltonian whose ground state is easy to prepare, and slowly varies the Hamiltonian to one whose ground state encodes the solution to some computational problem. By the adiabatic theorem, the system will track the instantaneous ground state provided the variation of the Hamiltonian is sufficiently slow. The runtime of an adiabatic algorithm scales at worst as 1/γ3 where γ is the minimum eigenvalue gap between the ground state and the first excited state [185]. If the Hamiltonian is varied sufficiently smoothly, one can improve this to O˜(1/γ2) [247]. Adiabatic quantum computation was first proposed by Farhi et al. as a method for solving NP-complete combinatorial optimization problems [96, 186]. Adiabatic quantum algorithms for optimization problems typically use "stoquastic" Hamiltonians, which do not suffer from the sign problem. Such algorithms are sometimes referred to as quantum annealing. Adiabatic quantum computation with non-stoquastic Hamiltonians is as powerful as the quantum circuit model [97]. Adiabatic algorithms using stoquastic Hamiltonians are probably less powerful [183], but may be nevertheless more powerful than classical computation. The asymptotic runtime of adiabatic optimization algorithms is notoriously difficult to analyze, but some progress has been achieved [179,180,181,182,187,188,189,190,191,226]. (Also relevant is an earlier literature on quantum annealing, which originally referred to a classical optimization algorithm that works by simulating a quantum process, much as simulated annealing is a classical optimization algorithm that works by simulating a thermal process. See e.g. [199, 198].) Adiabatic quantum computers can perform a process somewhat analogous to Grover search in O(N‾‾√) time [98]. Adiabatic quantum algorithms achieving quadratic speedup for a more general class of problems are constructed in [184] by adapting techniques from [85]. Adiabatic quantum algorithms have been proposed for several specific problems, including PageRank [176], machine learning [192, 195], and graph problems [193, 194]. Some quantum simulation algorithms also use adiabatic state preparation.

シミュレーテッドアニーリング

Algorithm: Simulated Annealing
Speedup: Polynomial
Description: In simulated annealing, one has a series of Markov chains defined by stochastic matrices M1,M2,…,Mn. These are slowly varying in the sense that their limiting distributions pi1,π2,…,πn satisfy |πt+1−πt|<ϵ for some small ϵ. These distributions can often be thought of as thermal distributions at successively lower temperatures. If π1 can be easily prepared, then by applying this series of Markov chains one can sample from πn. Typically, one wishes for πn to be a distribution over good solutions to some optimization problem. Let δi be the gap between the largest and second largest eigenvalues of Mi. Let δ=miniδi. The run time of this classical algorithm is proportional to 1/δ. Building upon results of Szegedy [135,85], Somma et al. have shown [84, 177] that quantum computers can sample from πn with a runtime proportional to 1/δ√. Additional methods by which classical Markov chain Monte Carlo algorithms can be sped up using quantum walks are given in [265].

などです。

勉強会オンラインコミュニティ

随時情報の更新や勉強会の資料が手に入ります。わからないところを質問したり、ニュースの交換があります。
下記招待コードよりぜひご参加ください。

https://join.slack.com/t/mdr-qc/shared_invite/enQtMzgxNDI3MTAyNzA3LThmYmRhZjkwYzFiZjRjNWZkNzJhOWMwOWNiYzgxYjdkNWE4ODA5ZWExZGYwZjFjM2RmNjE2ODJlYjgyNzNkNjY

場所について

本郷三丁目を予定しています。

Media View all Media

If you add event media, up to 3 items will be shown here.

Feed

Yuichiro Minato

Yuichiro Minato published Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る.

07/07/2018 02:02

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る を公開しました!

Ended

2018/08/09(Thu)

18:30
20:00

You cannot RSVP if you are already participating in another event at the same date.

Registration Period
2018/07/07(Sat) 02:02 〜
2018/08/09(Thu) 20:00

Location

Blueqat Hub/ MDR株式会社

東京都文京区本郷2丁目40-14山崎ビル3F

Organizer

Attendees(25)

sonicmove

sonicmove

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る に参加を申し込みました!

takumi-kato

takumi-kato

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る に参加を申し込みました!

hiro10

hiro10

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見るに参加を申し込みました!

ryo

ryo

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見るに参加を申し込みました!

KanSAKAMOTO

KanSAKAMOTO

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見るに参加を申し込みました!

satoshi matsuzaki

satoshi matsuzaki

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見るに参加を申し込みました!

MakotoKubodera

MakotoKubodera

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見るに参加を申し込みました!

efuji001

efuji001

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る に参加を申し込みました!

yyanagihara1213

yyanagihara1213

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見るに参加を申し込みました!

walker

walker

Quantum Algorithm Zooの近似・シミュレーションアルゴリズムを見る に参加を申し込みました!

Attendees (25)

Canceled (4)