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

はじめに

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].

Speedup: Unknown

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

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

注意事項

※ こちらのイベント情報は、外部サイトから取得した情報を掲載しています。
※ 掲載タイミングや更新頻度によっては、情報提供元ページの内容と差異が発生しますので予めご了承ください。
※ 最新情報の確認や参加申込手続き、イベントに関するお問い合わせ等は情報提供元ページにてお願いします。

18:00 〜20:00

connpass

4月 24 WED

19:30 〜21:30

Doorkeeper

4月 24 WED

09:00 〜17:00

ATND

5月 6 MON

13:30 〜19:00

connpass

5月 6 MON

量子情報勉強会 |66>

〒101-0032 東京都千代田区岩本町２丁目１０−９ （株）ねこねこエンジニアリング

13:00 〜17:00

connpass

5月 11 SAT