BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//https://techplay.jp//JP
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALDESC:Quantum Algorithm Zooの近似・シミュレーションア
 ルゴリズムを見る
X-WR-CALNAME:Quantum Algorithm Zooの近似・シミュレーションア
 ルゴリズムを見る
X-WR-TIMEZONE:Asia/Tokyo
BEGIN:VTIMEZONE
TZID:Asia/Tokyo
BEGIN:STANDARD
DTSTART:19700101T000000
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:JST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:683897@techplay.jp
SUMMARY:Quantum Algorithm Zooの近似・シミュレーションアルゴ
 リズムを見る
DTSTART;TZID=Asia/Tokyo:20180809T183000
DTEND;TZID=Asia/Tokyo:20180809T200000
DTSTAMP:20260427T033734Z
CREATED:20180706T210438Z
DESCRIPTION:イベント詳細はこちら\nhttps://techplay.jp/event/68389
 7?utm_medium=referral&utm_source=ics&utm_campaign=ics\n\nはじめに\n
 量子ゲートのアルゴリズムの殿堂\nhttps://math.nist.gov/quan
 tum/zoo/\nこちらの中で、特に近似アルゴリズムシミュレ
 ーションアルゴリズムのいくつかの概要を見ていきま
 す。\nたとえば\n量子シミュレーション  \nAlgorithm: Quantu
 m Simulation\nSpeedup: Superpolynomial\nDescription: 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 po
 ly(n\,t) gates. Unless BPP=BQP\, this problem is not solvable in general 
 on a classical computer in polynomial time. Many techniques for quantum s
 imulation have been developed for general classes of Hamiltonians [25\,95
 \,92\,5\,12\,170\,205\,211\,244\,245\,278\,293\,294\,295\,372\,382]\, che
 mical dynamics [63\,68\,227\,310\,375]\, condensed matter physics [1\,99\
 , 145]\, relativistic quantum mechanics (the Dirac and Klein-Gordon equat
 ions) [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 firs
 t propose that quantum computers might outperform classical computers on 
 certain tasks [40]. Although the problem of finding ground energies of lo
 cal Hamiltonians is QMA-complete and therefore probably requires exponent
 ial time on a quantum computer in the worst case\, quantum algorithms hav
 e 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 so
 me classes of Hamiltonians. Efficient quantum algorithms have been also o
 btained for preparing certain classes of tensor network states [323\,324\
 ,325\,326\,327\,328].   \n分配関数  \nAlgorithm: Partition Functions\
 nSpeedup: Superpolynomial\nDescription: For a classical system with a fin
 ite set of states S the partition function is Z=∑s∈Se−E(s)/kT\, whe
 re 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 Pott
 s model is a special case of the Tutte polynomial. A quantum algorithm fo
 r approximating the Tutte polynomial is given in [3]. Some connections be
 tween these approaches are discussed in [67]. Additional algorithms for e
 stimating 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 qu
 adratic speedup for the approximation of general partition functions is g
 iven in [122]. A method based on quantum walks\, achieving polynomial spe
 edup for evaluating partition functions is given in [265].   \n断熱計
 算\nAlgorithm: Adiabatic Algorithms\nSpeedup: Unknown\nDescription: In a
 diabatic quantum computation one starts with an initial Hamiltonian whose
  ground state is easy to prepare\, and slowly varies the Hamiltonian to o
 ne whose ground state encodes the solution to some computational problem.
  By the adiabatic theorem\, the system will track the instantaneous groun
 d state provided the variation of the Hamiltonian is sufficiently slow. T
 he runtime of an adiabatic algorithm scales at worst as 1/γ3 where γ is
  the minimum eigenvalue gap between the ground state and the first excite
 d state [185]. If the Hamiltonian is varied sufficiently smoothly\, one c
 an improve this to O˜(1/γ2) [247]. Adiabatic quantum computation was fi
 rst proposed by Farhi et al. as a method for solving NP-complete combinat
 orial 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-stoquasti
 c Hamiltonians is as powerful as the quantum circuit model [97]. Adiabati
 c algorithms using stoquastic Hamiltonians are probably less powerful [18
 3]\, but may be nevertheless more powerful than classical computation. Th
 e 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 litera
 ture on quantum annealing\, which originally referred to a classical opti
 mization algorithm that works by simulating a quantum process\, much as s
 imulated annealing is a classical optimization algorithm that works by si
 mulating a thermal process. See e.g. [199\, 198].) Adiabatic quantum comp
 uters can perform a process somewhat analogous to Grover search in O(N‾
 ‾√) time [98]. Adiabatic quantum algorithms achieving quadratic speed
 up for a more general class of problems are constructed in [184] by adapt
 ing techniques from [85]. Adiabatic quantum algorithms have been proposed
  for several specific problems\, including PageRank [176]\, machine learn
 ing [192\, 195]\, and graph problems [193\, 194]. Some quantum simulation
  algorithms also use adiabatic state preparation. \nシミュレーテッ
 ドアニーリング\nAlgorithm: Simulated Annealing \nSpeedup: Polynomi
 al\nDescription: In simulated annealing\, one has a series of Markov chai
 ns defined by stochastic matrices M1\,M2\,…\,Mn. These are slowly varyi
 ng in the sense that their limiting distributions pi1\,π2\,…\,πn sati
 sfy |πt+1−πt|<ϵ for some small ϵ. These distributions can often be 
 thought of as thermal distributions at successively lower temperatures. I
 f π1 can be easily prepared\, then by applying this series of Markov cha
 ins one can sample from πn. Typically\, one wishes for πn to be a distr
 ibution 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/δ. Bu
 ilding upon results of Szegedy [135\,85]\, Somma et al. have shown [84\, 
 177] that quantum computers can sample from πn with a runtime proportion
 al to 1/δ√. Additional methods by which classical Markov chain Monte C
 arlo algorithms can be sped up using quantum walks are given in [265]. \n
 などです。\n勉強会オンラインコミュニティ\n随時情報
 の更新や勉強会の資料が手に入ります。わからないと
 ころを質問したり、ニュースの交換があります。\n下
 記招待コードよりぜひご参加ください。\nhttps://join.slac
 k.com/t/mdr-qc/shared_invite/enQtMzgxNDI3MTAyNzA3LThmYmRhZjkwYzFiZjRjNWZk
 NzJhOWMwOWNiYzgxYjdkNWE4ODA5ZWExZGYwZjFjM2RmNjE2ODJlYjgyNzNkNjY\n場所
 について\n本郷三丁目を予定しています。
LOCATION:MDR株式会社 東京都文京区本郷2丁目40-14山崎ビル3F
URL:https://techplay.jp/event/683897?utm_medium=referral&utm_source=ics&utm
 _campaign=ics
END:VEVENT
END:VCALENDAR