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

断熱計算
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

場所について

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