[go: up one dir, main page]

WO2018190064A1 - 量子アニーリング計算のための処理方法 - Google Patents

量子アニーリング計算のための処理方法 Download PDF

Info

Publication number
WO2018190064A1
WO2018190064A1 PCT/JP2018/009994 JP2018009994W WO2018190064A1 WO 2018190064 A1 WO2018190064 A1 WO 2018190064A1 JP 2018009994 W JP2018009994 W JP 2018009994W WO 2018190064 A1 WO2018190064 A1 WO 2018190064A1
Authority
WO
WIPO (PCT)
Prior art keywords
state
physical
physical system
quantum
systems
Prior art date
Application number
PCT/JP2018/009994
Other languages
English (en)
French (fr)
Inventor
健太郎 今福
Original Assignee
国立研究開発法人産業技術総合研究所
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 国立研究開発法人産業技術総合研究所 filed Critical 国立研究開発法人産業技術総合研究所
Priority to JP2019512393A priority Critical patent/JP7046379B2/ja
Publication of WO2018190064A1 publication Critical patent/WO2018190064A1/ja
Priority to US16/598,265 priority patent/US11403548B2/en

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N10/00—Quantum computing, i.e. information processing based on quantum-mechanical phenomena
    • G06N10/60—Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N10/00—Quantum computing, i.e. information processing based on quantum-mechanical phenomena
    • G06N10/40—Physical realisations or architectures of quantum processors or components for manipulating qubits, e.g. qubit coupling or qubit control
    • H—ELECTRICITY
    • H10—SEMICONDUCTOR DEVICES; ELECTRIC SOLID-STATE DEVICES NOT OTHERWISE PROVIDED FOR
    • H10N—ELECTRIC SOLID-STATE DEVICES NOT OTHERWISE PROVIDED FOR
    • H10N60/00—Superconducting devices
    • H10N60/10—Junction-based devices

Definitions

  • the present invention relates to quantum annealing calculation, and more specifically to a processing method for performing quantum annealing calculation to solve a discrete optimization problem.
  • Quantum annealing computers are known as quantum computers that solve discrete optimization problems using quantum effects.
  • the quantum annealing computer is a computer for solving problems that require frequent combinations of discrete variables that minimize evaluation functions (equivalent to optimization) (hereinafter referred to as "discrete optimization problems") that frequently appear in operation research. .
  • a physical system is constructed in which a discrete variable is in a physical state and the value of an evaluation function for that discrete variable is the energy of that state. That is, energy is a function of state.
  • Quantum annealing using quantum mechanical effects is known as a mechanism for bringing a physical system to the lowest energy state. Quantum annealing is known to solve problems more efficiently than those that do not use quantum mechanical effects.
  • Quantum annealing gradually changes the correspondence between energy and state by controlling the external field (potential) acting on the system.
  • the initial potential is chosen to have a trivial minimum energy state. It is designed so that the relation between energy and state corresponding to the evaluation function that changes the potential and finally wants to actually find the optimum solution is achieved.
  • quantum mechanics when the initial state of the system is set to the lowest energy state determined by the initial potential and the potential is changed sufficiently slowly, the state follows the lowest energy state determined by the potential at each moment. Are known. In this way, it is possible to obtain a state that minimizes the evaluation function to be finally examined.
  • Patent Document 1 discloses a method for adiabatic quantum computation using a quantum system including a plurality of superconducting qubits.
  • quantum mechanical states states that cannot be expressed by ordinary classical physics
  • this calculation method may solve the problem more efficiently than an ordinary computer that uses classical physics as the implementation principle.
  • the present invention proposes a method different from the method using the conventional adiabatic theorem as a mechanism for guiding the physical state to the lowest energy state, and aims to avoid the bottleneck problem described above.
  • the present invention provides a processing method for performing quantum annealing calculations to solve discrete optimization problems.
  • the outline of the processing method is as follows. (I) construct an energy function (problem Hamiltonian H) so that the solution of the problem is in the lowest energy state, (Ii) repeatedly applying a method of transitioning one to a low energy state and the other to a high energy state between two physical systems having the same quantum state between a plurality of systems; (Iii) determining the lowest energy state whose state is the solution to the problem.
  • the processing method of the present invention includes, as one embodiment thereof, (A) preparing an operation for changing one energy state to a low energy state and transitioning the other energy state to a high energy state between two physical systems (u, d) having the same quantum state; (B) The state values of the plurality of physical systems in each step are set under a predetermined rule while sequentially changing the steps from step 0 to among the plurality of physical systems, and the physical systems having the same state value are set.
  • the number of calculation steps can be suppressed to a polynomial (second order (n 2 )) increase at most with respect to n, and conventional quantum annealing calculation or
  • the number of calculation steps can be significantly reduced as compared with the case where the number of calculation steps increases exponentially (2 n / 2 ) with respect to n.
  • the number of calculation steps and the necessary number of qubits can solve the problem with a polynomial size (second order (n 2 )) at most for n. As a result, an increase in calculation time according to the size of the problem can be suppressed.
  • step S10 of FIG. 2 which changes the energy state of one embodiment of the processing method of this invention.
  • step S30 which calculates
  • step S30 which calculates
  • step S30 which calculates
  • FIG. 5 shows the time development of the expected value of energy at the time of implementing one embodiment of the processing method of this invention.
  • FIG. 5 is a diagram showing m dependency of step * obtained by subtracting 1 from step where ⁇ (step) is an empty set and the number of quantum operations C (m).
  • FIG. 1 is a diagram showing an overview of the processing method of the present invention.
  • an energy function problem Hamiltonian H
  • S1 an energy function
  • S2 a method of transitioning one to a low energy state and the other to a high energy state
  • S3 the lowest energy state whose state is the solution to the problem
  • FIG. 2 is a diagram showing a flow of one embodiment of the processing method of the present invention.
  • step S10 an operation is prepared for changing one energy state to a low energy state and transitioning the other energy state to a high energy state between two physical systems (u, d) having the same quantum state.
  • step S20 the state value of each of the plurality of physical systems in each step is set under a predetermined rule while sequentially transitioning from step 0 to the plurality of physical systems, and the physical system having the same state value Are collected until reaching the step where the same state value disappears.
  • step S30 the operation of changing the energy state in step S10 while applying the two physical systems (u, d) to the pairs of all physical systems in the set is applied, and a plurality of physical systems in the set are applied. Find the physical system with the minimum energy state of.
  • FIG. 3 is a conceptual diagram of an operation (step S10 in FIG. 2) for transitioning to an energy state according to an embodiment of the processing method of the present invention.
  • the same quantum state shown in the following (1) is prepared as an initial state in two physical systems (u, d).
  • u and d have the same expected value of energy as shown in (2) below.
  • energy dispersion in the quantum state of (1) is given by the following formula (3).
  • a ⁇ first operation> the quantum state of u is developed for a time ⁇ (> 0) using a Hamiltonian shown in the following (4).
  • the block denoted by reference numeral 1 in FIG. 3 indicates this first operation.
  • a ⁇ second operation> a quantum swapping operation is performed between u and d for a time ⁇ t (> 0).
  • the block denoted by reference numeral 2 in FIG. 3 indicates this second operation.
  • the time evolution is performed for time ⁇ (> 0) using the Hamiltonian shown in the following (5) in which the quantum state of u is inverted.
  • a block denoted by reference numeral 3 in FIG. 3 indicates the third operation.
  • the quantum states of u and d after the first to third series of operations are in the approximate range up to the first order of ⁇ and ⁇ t as a result of the quantum mechanical time evolution defined by the operations.
  • the quantum state of d can be represented by the following formula (7).
  • equation (8) considering the solution (9) of the following nonlinear equation (8): It can be seen that the following equations (10) and (11) are established within the approximate range up to the first order of ⁇ and ⁇ t.
  • the expected value of energy in (12) below in the state given in (9) above is monotonously decreasing with respect to t.
  • the expected value of energy in the states after the first to third operations is expressed by the following equation (13) for u, and is higher than the expected value in the initial state by ⁇ E ⁇ t.
  • d is expressed by the following formula (14), which is lower than the expected value in the initial state by ⁇ E ⁇ t.
  • FIG. 4 is a schematic diagram of the conceptual diagram of FIG.
  • black circles 4 and white circles 5 correspond to the operation blocks 1, 2, and 3 in FIG.
  • FIG. 5 is a diagram for explaining step S20 for obtaining a set of one embodiment of the processing method of the present invention and step S30 for obtaining a physical system having a minimum energy state among a plurality of physical systems.
  • the summary description (black circle 4 and white circle 5) of FIG. 4 is used.
  • FIG. 6 is a diagram showing the time evolution of the expected value of energy when one embodiment of the processing method of the present invention is implemented (FIG. 5).
  • step 0 is an initial state and step is sequentially increased by one.
  • An integer s j (step) determined by the following rule is introduced into the j-th physical system.
  • s j (0) is 0 for all physical systems j.
  • s j ′ is paired.
  • step * A step in which ⁇ (step) is an empty set minus 1 is defined as step *.
  • the following (18) is called a network structure.
  • This network structure (18) is characterized in that it can be determined independently of the Hamiltonian H whose minimum eigenstate is desired.
  • the quantum state is evolved over time as follows.
  • (1) Prepare the same quantum state as an initial state in 2m physical systems.
  • (3) For all pairs ⁇ j, j ′ ⁇ (note that j ⁇ j ′) included in ⁇ (step), the physical system j is changed to the physical system u in step S10 in FIG. 2 (FIG. 3). Then, the operation of making the physical system j ′ correspond to the physical system d and transitioning the energy state in step S10 is applied.
  • step step *, since the equations (19, 20 and 20) are monotonically decreasing with respect to t, the expected value of energy in the state in each physical system j is monotonously decreasing with respect to j.
  • the state of the lowest expected value of energy (21) below is the result of quantum mechanical time evolution defined by the above-described series of operations. Realize.
  • FIG. 7 is a diagram showing an implementation example (configuration example).
  • FIG. 7 shows an example of two qubits 1 and 2.
  • the superconducting loop 10 constituting the qubits 1 and 2 includes a mini-loop 11 including two Josephson junctions (x).
  • x two Josephson junctions
  • each coefficient of the following (23) in Formula (22) is a function of time which takes an integer value.
  • FIG. 8 is a diagram showing the control sequence of the embodiment of FIG. 7, that is, the time transition of the values ( ⁇ 1,0, + 1) of the coefficients (23) below.
  • each coefficient of the following (24) is a Pauli matrix of qubit i.
  • the Hamiltonian of the equation (4) is expressed as follows using the interaction between the qubits constituting the physical system u in the equation (25) as in the case of the quantum annealing calculation. This is realized as shown in equation (27). That is, the following operations (28) and (29) are set for the time ⁇ (for the time ⁇ in FIG. 8), thereby completing the first operation.
  • Equation (34) Operation of equation (34): In the equation (25), as the following equation (38), all remaining coefficients are set to 0 for the time ⁇ / 2 (during the third ⁇ / 2 in FIG. 8). Thereafter, the remaining coefficients are all set to 0 in Expression (36) and time ⁇ / 2 is elapsed (during the fourth ⁇ / 2 in FIG. 8), and then the remaining coefficients are all set to 0 in Expression (35). Is set for a time ⁇ t (during the third ⁇ t in FIG. 8). Further, as expression (37), after all the remaining coefficients are set to 0 and time ⁇ / 2 has elapsed (during the fifth ⁇ / 2 in FIG.
  • the interaction of equation (5) is set for the time interval ⁇ using the interaction between qubits constituting the physical system u in equation (25). Since this is an inversion of the equation (27), the following equation (40) may be set corresponding to the equation (28). Thereby, the third operation is completed.
  • the method (operation) of step S10 of FIG. 2 by the implemented CJJ-rf-SQUID repeatedly to 2m systems and use it for quantum computation refer to FIG. 4 to FIG. It can be used (implemented) by using the series of processes described above.
  • FIG. 9 is a diagram illustrating the n dependence of the temporal behavior of the correct answer probability P (t) of the search problem based on the nonlinear equation, obtained by plotting P (t) of the equation (43).
  • FIG. 10 is a plot of t * in equation (47), and graph A shows the n dependence of time t * when the correct answer probability P (t) ⁇ 0.9.
  • Equation (21) if m corresponding to t * in Equation (47) is m *, the following Equation (48) is obtained.
  • step * and m are the following formula (49), regardless of the details of Hamiltonian (H), and step * determined by m * is the following formula (50), and the second order ( n 2 ).
  • the following Equation (51) is obtained for the entire 2m * system.
  • FIG. 11 is a diagram illustrating the m dependency of the step * obtained by plotting the equation (50) and the number C (m) of quantum operations obtained by plotting the equation (53).
  • the number of calculation steps is 2 n / (although it is smaller than the calculation not using the quantum). 2 and is known to behave exponentially with respect to n.
  • the number of calculation steps (step *) according to the present invention is suppressed to a polynomial (for example, n 2 ) at most with respect to n.
  • the number of qubits required for calculation is proportional to n in the present invention, whereas the conventional calculation method is proportional to n 2.
  • the problem can be solved with a number (C (m)) that is at most a polynomial size (eg, n 3 ) for n.

Landscapes

  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Data Mining & Analysis (AREA)
  • Evolutionary Computation (AREA)
  • Condensed Matter Physics & Semiconductors (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computing Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Artificial Intelligence (AREA)
  • Superconductor Devices And Manufacturing Methods Thereof (AREA)

Abstract

問題の大きさに対して計算時間の期待値が指数関数的に大きくなってしまう問題を回避するために、本発明の離散最適化問題を解くために量子アニーリング計算を行うための処理方法では、（ａ）同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、（ｃ）集合中の全ての物理系のペアに対して２つの物理系(u,d)を対応させながら（ａ）の操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物を求めるステップを含む。

Description

量子アニーリング計算のための処理方法
　本発明は、量子アニーリング計算に関し、より具体的には、離散最適化問題を解くために量子アニーリング計算を行うための処理方法に関する。
　離散最適化問題を、量子効果を利用して解く量子計算機として、量子アニーリング計算機が知られている。量子アニーリング計算機は、オペレーションリサーチ等に頻出する、評価関数を最小化（最適化に相当）する離散変数の組み合わせを求める問題（以下、「離散最適化問題」よ呼ぶ）を解くための計算機である。
　離散変数を物理状態に、およびその離散変数に対する評価関数の値がその状態のエネルギーとなる物理系を構成する。すなわち、エネルギーは状態の関数である。これにより、何らかの方法でその物理系をエネルギーが最も低い状態にすることができれば、その状態を測定することにより最適解が得られる。物理系をエネルギーが最も低い状態にするメカニズムとして、量子力学的効果を用いた量子アニーリングが知られている。量子アニーリングは、量子力学的効果を使わないものと比較して効率よく問題を解く場合があることが知られている。
　量子アニーリングでは、系に作用する外場（ポテンシャル）を制御することにより、エネルギーと状態の対応を時間的に徐々に変化させる。初期のポテンシャルは、自明な最低エネルギー状態を持つものが選ばれる。ポテンシャルを変化させ、最終的に実際に最適解を調べたい評価関数に対応したエネルギーと状態の関係が達成されるよう設計されている。系の初期状態を初期ポテンシャルで決定される最低エネルギー状態に準備し、ポテンシャルを十分ゆっくり変化させると、状態は各瞬間各瞬間のポテンシャルで決定される最低エネルギー状態をたどることが量子力学の結果として知られている。こうして、最終的に調べたい評価関数を最小化する状態を得ることができる。
　ポテンシャルの時間変化がゆっくりであれば、状態は最低エネルギー状態をたどることは、量子力学における断熱定理として一般的に知られており、この計算手法は断熱量子計算という呼び名でも知られている。一例として、特許文献１は、複数の超伝導キュビットを具備する量子システムを使用した断熱量子計算のための方法を開示する。断熱量子計算では、計算の過程に現れる状態に量子力学的な状態（通常の古典物理学では表現できない状態）が出現する。このため、この計算方法は古典物理学を実装原理とする通常のコンピュータよりも効率よく問題を解ける場合がある。
特表２００９－５２４８５７号公報
　特許文献１等の従来の量子アニーリング計算では、断熱定理が成立するように、ポテンシャルの時間変化をゆっくりとしたものにしなければならない。このため、計算をその制限を超えて加速させることができない。特に、問題の規模が大きい場合、問題の大きさに対して計算時間の期待値が指数関数的に大きくなってしまうという問題（ボトルネック）がある。
　本発明は、物理状態を最低エネルギー状態に導くメカニズムとして、従来の断熱定理を用いた方法とは異なる方法を提案し、上述したボトルネック問題を回避できるようにすることを目的とする。
　本発明は離散最適化問題を解くために量子アニーリング計算を行うための処理方法を提供する。その処理方法の概要は、
（ｉ）問題の解が最低エネルギー状態になるようにエネルギー関数（問題ハミルトニアンH）を構成し、
（ｉｉ）同じ量子状態を持つ２つの物理システム間で、一方を低エネルギー状態へ、もう一方を高エネルギー状態へ遷移させる方法を繰り返して複数のシステム間に適用して、
（ｉｉｉ）状態が問題の解である最低エネルギー状態を求めることを含む。
　より具体的には、本発明の処理方法は、その一実施態様として、
（ａ）同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、
（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、
（ｃ）（ｂ）の集合中の全ての物理系のペアに対して（ａ）の２つの物理系(u,d)を対応させながら（ａ）の操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップと、を含む。
　本発明の方法を一例として探索空間2nの探索問題に適用した場合、計算ステップ数はnに対して高々多項式的（２次（n2））な増加に抑えられ、従来の量子アニーリング計算やゲート式の量子計算を適用した場合に計算ステップ数がnに対して指数関数的（2n/2）に増加するのに比べて、計算ステップ数を大幅に削減することができる。また、本発明の方法を用いた場合、計算ステップ数と必要な量子ビット数は、nに対して高々多項式的なサイズ（２次（n2））で問題を解くことができる。その結果、問題のサイズに従う計算時間の増加を抑制することができる。
本発明の処理方法の概要を示す図である。 本発明の処理方法の一実施態様のフローを示す図である。 本発明の処理方法の一実施態様のエネルギー状態を遷移させる操作（図２のステップＳ１０）の概念図である。 図３の概念図の略式図である。 本発明の処理方法の一実施態様の集合を得るステップＳ２０及び複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップＳ３０を説明するための図である。 本発明の処理方法の一実施態様を実施した場合（図５）のエネルギーの期待値の時間発展を示す図である。 本発明の処理方法をジョセフソン接合を用いた超伝導回路（CJJ-rf-SQUID）に適用する実装例（構成例）を示す図である。 図７の実施例の制御シーケンスを示す図である。 非線形方程式による探索問題の正解確率P(t)の時間的挙動のn依存性を示す図である。 正解確率P(t)がP(t)≧0.9となる時間t*のn依存性を示す図である。 Ω(step)が空集合になるstepから1を引いたstep*および量子操作の数C(m)のm依存性を示す図である。
　図面を参照しながら本発明の実施形態について説明する。図１は、本発明の処理方法の概要を示す図である。その処理方法の概要は、最初に、問題の解が最低エネルギー状態になるようにエネルギー関数（問題ハミルトニアンH）を構成する（Ｓ１）。次に、同じ量子状態を持つ２つの物理システム間で、一方を低エネルギー状態へ、もう一方を高エネルギー状態へ遷移させる方法を繰り返して複数のシステム間に適用する（Ｓ２）。その結果、状態が問題の解である最低エネルギー状態が求められる（Ｓ３）。
　図２は、本発明の処理方法の一実施態様のフローを示す図である。ステップＳ１０として、同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備する。ステップＳ２０として、複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得る。ステップＳ３０として、その集合中の全ての物理系のペアに対して、２つの物理系(u,d)を対応させながらステップＳ１０のエネルギー状態を遷移させる操作を適用して、複数の物理系中の最小のエネルギー状態を持つ物理系を求める。
　図３を参照しながら、図２のステップＳ１０のエネルギー状態を遷移させる操作について詳細に説明する。図３は、本発明の処理方法の一実施態様のエネルギー状態に遷移させる操作（図２のステップＳ１０）の概念図である。最初に、二つの物理系（u,d）に下記（１）で示す同じ量子状態を初期状態として準備する。
Figure JPOXMLDOC01-appb-M000001
 　この時点で、uとdは下記（２）で示す同じエネルギーの期待値を持っている。
Figure JPOXMLDOC01-appb-M000002
 　後のため、（１）の量子状態におけるエネルギーの分散を下記の式（３）で与えておく。
Figure JPOXMLDOC01-appb-M000003
　＜第１の操作＞として、uの量子状態を下記（４）で示すハミルトニアンを用いて時間τ（>0）の間時間発展させる。図３の符号１のブロックはこの第１の操作を示している。
Figure JPOXMLDOC01-appb-M000004
 　＜第２の操作＞として、uとdの間で量子スワッピング操作を時間Δt（>0）の間実行する。図３の符号２のブロックはこの第２の操作を示している。
　＜第３の操作＞として、uの量子状態を反転した下記（５）で示すハミルトニアンを用いて時間τ（>0）の間時間発展させる。図３の符号３のブロックはこの第３の操作を示している。
Figure JPOXMLDOC01-appb-M000005
　第１～第３の一連の操作後のuとdの量子状態は、操作によって規定される量子力学的時間発展の結果、τとΔtの一次までの近似の範囲で、uの量子状態は下記の式（６）で表すことができ、dの量子状態は下記の式（７）で表すことができる。
Figure JPOXMLDOC01-appb-M000006
Figure JPOXMLDOC01-appb-M000007
 　ここで、下記の非線形方程式（８）の解（９）を考えると、
Figure JPOXMLDOC01-appb-M000008
Figure JPOXMLDOC01-appb-M000009
 　τとΔtの一次までの近似の範囲で、下記の式（１０）、（１１）が成立していることがわかる。
Figure JPOXMLDOC01-appb-M000010
Figure JPOXMLDOC01-appb-M000011
　上記の（９）で与えられる状態における下記（１２）のエネルギーの期待値は、tについて単調減少である。
Figure JPOXMLDOC01-appb-M000012
 　第１～第３の操作後の状態におけるエネルギーの期待値は、uについては下記の式（１３）となり、初期状態における期待値よりもΔEτΔtだけ高くなる。
Figure JPOXMLDOC01-appb-M000013
 　一方dについては下記の式（１４）となり、初期状態における期待値よりもΔEτΔtだけ低いものとなる。
Figure JPOXMLDOC01-appb-M000014
 　以上から、第１から第３までの一連の操作により、uはエネルギーの高い状態に、dはエネルギーの低い状態に遷移していることがわかる。
　次に、図４～図６を参照しながら図２のステップＳ２０、Ｓ３０について詳細に説明する。言い換えれば、図２のステップＳ１０の方法を複数のシステム間に適用することにより離散最適化問題を解くための量子計算機を構成するための処理方法を説明する。図４は、図３の概念図の略式図である。図４において、黒丸４と白丸５が、図３の操作ブロック１、２、及び３に対応している。図５は、本発明の処理方法の一実施態様の集合を得るステップＳ２０及び複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップＳ３０を説明するための図である。図５では、図４の略式記述（黒丸４と白丸５）を用いて表示している。図６は、本発明の処理方法の一実施態様を実施した場合（図５）のエネルギーの期待値の時間発展を示す図である。
　mを整数として、2m個の物理系を考える。これらの物理系の間のネットワーク構造を以下の手順で導入する。図５ではm=4（システム1～システム8）の場合を示している。
　(1)0から始まる非負の整数stepを導入する。図５と図６では、step=0を初期状態とし、stepが順次１増える状態遷移を示している。
　(2)j番目の物理系に以下の規則で決まる整数sj(step)を導入する。
　(2-1) sj(0)はすべての物理系jについて0とする。
　(2-2) j<j’である物理系jと物理系j’について、sj(step)= sj’(step)であれば物理系jと物理系j’をペアにする。図５では、黒丸と白丸を縦方向で結ぶが１つの線が１つのペアを示している。例えば、step=2のシステム1と3ではs1(2)= s3(2)=-1となりシステム1と3はペアとなる。同様に、step=7のシステム4と7ではs4(7)= s7(7)=+2となりシステム4と7はペアとなる。一度ペアとなった物理系jと物理系j’をのぞいて、可能な限りこのようなペアを集める。
　(2-3) 上記で構成した物理系のペアを要素とする集合をΩ(step)とする。
　(2-4) Ω(step)の中に現れる物理系jと物理系j’について、sj(step+1)とsj’(step+1)を下記の式（１５）、（１６）のように定義をする。
Figure JPOXMLDOC01-appb-M000015
Figure JPOXMLDOC01-appb-M000016
 　図５では、例えば、step=5のシステム3と6のペアにおいて、s3(6)= s3(5)-1=-1、s6(6)= s6(5)+1=0とする。他のペアも同様である。
　(2-5) Ω(step)の中に現れないjについて下記の式（１７）の定義をする。
Figure JPOXMLDOC01-appb-M000017
 　図５では、例えば、システム1のstep=4からstep=7において、s1(7)= s1(6)=s1(5)= s1(4) s1(3)=-3とする。他も同様である。
　(2-6) step+1をstepとして上記の(2-2)に戻り、Ω(step)が空集合となるまでこれを繰り返す。
　(2-7) Ω(step)が空集合になるstepから1を引いたものをstep*と定義する。図５では、Ω(step)が空集合になるstep=12（終状態）から1を引いたstep=11がstep*となる。このとき下記（１８）をネットワーク構造と呼ぶ。このネットワーク構造（１８）は、最小固有状態を求めたいハミルトニアンHとは独立に決定できることが特徴である。
Figure JPOXMLDOC01-appb-M000018
 　また、このネットワークの構成法より各jにおけるsj(step*)の値は下記の式（１９）で求めることができる。
Figure JPOXMLDOC01-appb-M000019
 　図５では、例えば、システム4において、s4(step*)= s4(11)=j-m-1=4-4-1=-1となり、システム8において、s8(step*)= s8(11)=j-m=8-4=+4となる。
　上記のネットワーク構造と、図２のステップＳ１０のエネルギー状態を遷移させる操作（同じ量子状態を持つ２つの物理システム間でのエネルギー交換方法）を用いて、量子状態を次のように時間発展させる。
　(1)2m個の物理系に同じ量子状態を初期状態として準備する。
　(2)step=0とする。
　(3)Ω(step)に含まれる全てのペア{j,j’}（j<j’であることに注意）に対し、物理系jを図２のステップＳ１０（図３）における物理系u、物理系j’を物理系dにそれぞれ対応させ、ステップＳ１０のエネルギー状態を遷移させる操作を適用する。
　(4)step+1を新たにstepとして(3)に戻り、step=step*に到達するまで繰り返す。
　このとき、 上記の式（１０）と（１１）が繰り返し適用され、各物理系jにおける各stepの状態は、式（８）の解（９）を使って、τとΔtの一次までの近似の範囲で下記の（２０）で表される。
Figure JPOXMLDOC01-appb-M000020
 　このときのエネルギー期待値を厳密に計算した結果が、図６のエネルギーの期待値の時間発展を示す図である。図６において、破線７で囲まれる１つの領域がエネルギーの期待値を表し、白黒の濃淡がエネルギーの期待値の大小を表し、色が濃くなる程エネルギーの期待値が小さくなることを示している。図６は図５のm=4の物理系（システム）に対応しているので、システム８のstep=11においてエネルギーの期待値が最小となっていることがわかる。
　step=step*では、式（１９と式（２０）および式（１２）がtについて単調減少であることより、各物理系jにおける状態でのエネルギーの期待値はjについて単調減少となる。その中でも特に、j=2mの物理系（図５の例ではシステム8）では、下記（２１）の最もエネルギーの期待値の低い状態が上記した一連の操作によって規定される量子力学的時間発展の結果、実現する。
Figure JPOXMLDOC01-appb-M000021
　実施例１として、図２のステップＳ１０の方法（操作）をジョセフソン接合を用いた超伝導回路（「CJJ-rf-SQUID」、Physical Review B 80,052506,2009）に適用した場合の実装例を以下に示す。図７は、その実装例（構成例）を示す図である。図７では、二つの量子ビット1,2の例を示している。物理システムu、dにおいて、量子ビット1,2を構成する超伝導ループ１０は、２つのジョセフソン接合（×）を含むミニループ１１を含む。超伝導ループ１０の各々は、同様な超伝導ループ同士が相互インダクタンスを介して磁気的に接合する。なお、以下の説明では、より一般的に二つの量子ビットi,jを想定した場合について説明する。
　CJJ-rf-SQUID系では、二つの量子ビットi,jの間に下記の式（２２）の形の相互作用を形成することができる。
Figure JPOXMLDOC01-appb-M000022
 　ただし、式（２２）中の下記（２３）の各係数は整数の値を取る時間の関数である。図８は、図７の実施例の制御シーケンス、すなわち、下記（２３）の各係数の値（-1,0,+1）の時間遷移を示す図である。
Figure JPOXMLDOC01-appb-M000023
 　さらに、下記（２４）の各係数は、量子ビットiのパウリ行列とする。
Figure JPOXMLDOC01-appb-M000024
　上記の式（２２）の相互作用が実現された量子ビットの集合を考える。これらの量子ビットの集合を２つに分けて、１つを物理システムu、残りを物理システムdに対応させる。このとき、uに属する量子ビットiのラベルを(i,u)とし、同様にdに属する量子ビットiのラベルを(i,d)とする。すなわち、これらの量子ビット間の相互作用は下記の式（２５）のように表される。
Figure JPOXMLDOC01-appb-M000025
 　このとき、量子アニーリング計算の場合と同様に、t<0において数（２５）の相互作用において、下記の式（２６）を導入し、かつ、他の係数を0に設定して初期状態（図８のt<0の範囲）を用意する。
Figure JPOXMLDOC01-appb-M000026
　上記した第１の操作に対応して、式（２５）中の物理系uを構成する量子ビット間の相互作用を用いて、量子アニーリング計算の場合と同様に、式（４）のハミルトニアンを下記の式（２７）のように実現する。
Figure JPOXMLDOC01-appb-M000027
 　すなわち、下記の式（２８）及び（２９）を時間τの間設定する（図８の時間τの間）ことで、第１の操作が完了する。
Figure JPOXMLDOC01-appb-M000028
Figure JPOXMLDOC01-appb-M000029
　上記した第２の操作に対応して、スワッピングの操作を行う。スワッピングは式（２５）中の物理系uとdを構成する量子ビット間に、下記の式（３０）の相互作用を構成し、時間Δtの間設定することで第２の操作が完了する。
Figure JPOXMLDOC01-appb-M000030
 　しかし、式（３０）の相互作用は式（２５）の形をした相互作用では直接実現することができない。そこで、下記の式（３１）～（３４）
Figure JPOXMLDOC01-appb-M000031
Figure JPOXMLDOC01-appb-M000032
Figure JPOXMLDOC01-appb-M000033
Figure JPOXMLDOC01-appb-M000034
 　に着目すると、式（６）や式（７）を成立させるΔtの１次までの範囲では、下記の(1)～(3)の操作を順に行うことで、間接的に第２の操作を実装することができる。
　(1)式（３２）の操作:
　式（２５）において、下記の式（３５）として、残りの係数は全て0を時間Δtの間設定する（図８の最初のΔtの間）。これにより式（３１）の操作が完了する。
Figure JPOXMLDOC01-appb-M000035
 　(2)式（３３）の操作:
　式（２５）において、下記の式（３６）として、残りの係数は全て０を時間π/2の間設定する（図８の最初のπ/2の間）。その後、式（３５）として残りの係数は全て0を時間Δtの間設定する（図８の２番目のΔtの間）。
Figure JPOXMLDOC01-appb-M000036
 　さらに、下記の式（３７）として、残りの係数は全て0を時間π/2の間設定する（図８の２番目のπ/2の間）。これにより式（３３）の操作が完了する。
Figure JPOXMLDOC01-appb-M000037
　(3)式（３４）の操作:
　式（２５）において、下記の式（３８）として、残りの係数は全て０を時間π/2の間設定する（図８の３番目のπ/2の間）。
Figure JPOXMLDOC01-appb-M000038
 　その後、式（３６）として残りの係数を全て0に設定し時間π/2を経過させ（図８の４番目のπ/2の間）、続いて式（３５）として残りの係数は全て0を時間Δtの間設定する（図８の３番目のΔtの間）。さらに、式（３７）として、残りの係数を全て0として時間π/2を経過後（図８の５番目のπ/2の間）、さらに下記の式（３９）として、残りの係数の全て0を時間π/2の間設定する（図８の最後のπ/2の間）。
Figure JPOXMLDOC01-appb-M000039
 　これにより式（３４）の操作が完了する。以上の一連の(1), (2) 及び(3)の操作より、第２の操作が完了する。
　上記した第３の操作に対応して、式（２５）中の物理系uを構成する量子ビット間の相互作用を用いて、式（５）の相互作用を時間間隔τの間設定する。これは式（２７）を反転させたものであるから、式（２８）に対応して下記の式（４０）を設定すればよい。これにより、第３の操作が完了する。
Figure JPOXMLDOC01-appb-M000040
 　以上により、実装されるCJJ-rf-SQUIDによる図２のステップＳ１０の方法（操作）を2m個のシステムに繰り返して適用して量子計算に利用するには、図４～図６を参照しながら上述した一連の処理を用いることにより利用（実装）することができる。
　次に、実施例２として、計算ステップ数および必要な量子ビット数の評価を行うために、本発明を探索空間2nの探索問題に適用した場合について説明する。最初に、探索問題に対応する下記の式（４１）のハミルトニアンを式（８）の非線形方程式に適用する。
Figure JPOXMLDOC01-appb-M000041
 　時刻tにおける下記の式（４２）の正解確率を計算すると解析解が存在して下記の式（４３）が得られる。図９は、式（４３）のP(t)をプロットして得られた、非線形方程式による探索問題の正解確率P(t)の時間的挙動のn依存性を示す図である。
Figure JPOXMLDOC01-appb-M000042
Figure JPOXMLDOC01-appb-M000043
　ここで、解空間の大きさが下記の（４４）であって、初期の正解確率が下記の式（４５）となる場合を考える。
Figure JPOXMLDOC01-appb-M000044
Figure JPOXMLDOC01-appb-M000045
 　このとき、下記の式（４６）を満たす時刻tをt*と定義すると、t*は下記の式（４７）として得られる。図１０は、式（４７）のt*をプロットしたもので、グラフＡは正解確率P(t)≧0.9となる時間t*のn依存性を示す。
Figure JPOXMLDOC01-appb-M000046
Figure JPOXMLDOC01-appb-M000047
　ここで本発明によって得られる状態が式（２１）であることより、式（４７）のt*に対応するmをm*とすれば、下記の式（４８）が得られる。
Figure JPOXMLDOC01-appb-M000048
 　step*とmの関係はハミルトニアン(H)の詳細によらず、下記の式（４９）であることに注目すると、m*で決まるstep*は下記の式（５０）となり、nの２次（n2）であることがわかる。
Figure JPOXMLDOC01-appb-M000049
Figure JPOXMLDOC01-appb-M000050
 　また、式（４３）の問題を表現するのに必要な１システムあたりの量子ビット数はn個であるから、2m*システム全体では下記の式（５１）となる。
Figure JPOXMLDOC01-appb-M000051
　さらに、与えられたmに対し必要な量子操作の数C(m)は下記の式（５２）であることから、上記の探索問題に適用した場合には下記の式（５３）となる。図１１は、式（５０）をプロットして得られるstep*及び式（５３）をプロットして得られる量子操作の数C(m)のm依存性を示す図である。
Figure JPOXMLDOC01-appb-M000052
Figure JPOXMLDOC01-appb-M000053
　上記した探索空間2nの探索問題に従来の量子アニーリング計算、およびゲート式の量子計算探索問題に適用した場合、（量子を使わない計算に比べて小さくはなるものの）その計算ステップ数は2n/2となり、nに対して指数関数的に振る舞うことが知られている。一方、本発明による計算ステップ数（step*）は、上述したように、nに対して高々多項式的（例えばn2）に抑えられる。同様に、計算に必要な量子ビットの数は、従来の計算手法がnに比例する程度だったのに対し、本発明ではn2に比例することになるが、計算ステップ数と必要な量子操作数（C(m)）がnに対して高々多項式的なサイズ（例えばn3）で問題を解くことができる。
　本発明の実施形態について、図を参照しながら説明をした。しかし、本発明はこれらの実施形態に限られるものではない。さらに、本発明はその趣旨を逸脱しない範囲で当業者の知識に基づき種々なる改良、修正、変形を加えた態様で実施できるものである。
　１：第１の操作
　２：第２の操作
　３：第３の操作
　４、５：第１～第３の操作の略式記述
　７：エネルギーの期待値
　１０：超伝導ループ
　１１：２つのジョセフソン接合を含むミニループ

Claims (5)

  1. 　離散最適化問題を解くために量子アニーリング計算を行うための処理方法であって、
    　（ａ）同一の量子状態を持つ２つの物理系(u,d)間において、一方のエネルギー状態を低エネルギー状態にし、他方のエネルギー状態を高エネルギー状態に遷移させる操作を準備するステップと、
    　（ｂ）複数の物理系間において、ステップ0から順次ステップを遷移させながら各ステップでの複数の物理系の各々の状態値を所定の規則下で設定し、同一の状態値を持つ物理系のペアを同一の状態値が無くなるステップに至るまで集めて集合を得るステップと、
    　（ｃ）前記集合中の全ての前記物理系のペアに対して前記２つの物理系(u,d)を対応させながら前記操作を適用して、前記複数の物理系中の最小のエネルギー状態を持つ物理系を求めるステップと、を含む処理方法。
  2. 　前記操作を準備するステップ（ａ）は、
    　（ａ１）前記２つの物理系(u,d)に初期状態として同一の量子状態を与えるステップと、
    　（ａ２）物理系uの量子状態をハミルトニアン(H)を用いて時間τ(>0)の間時間発展させるステップと、
    　（ａ３）物理系uと物理系dの間で量子スワッピング操作を時間Δt(>0)の間行うステップと、
    　（ａ４）物理系uの量子状態を反転したハミルトニアン（-H）を用いて時間τ(>0)の間時間発展させるステップと、を含む請求項１に記載の処理方法。
  3. 　前記集合を得るステップ（ｂ）は、
    　（ｂ１）2m個の物理系において、j番目の物理系jの状態値をＳｊ（step）とし、全ての物理系ｊについてＳｊ（0）=0にするステップと、
    　（ｂ２）j＜j’である全てのjとj’について、Ｓｊ（step）=Ｓｊ’（step）となる物理系jと物理系j’をペアとして選択するステップと、
    　（ｂ３）物理系jと物理系j’のペアを集めて集合Ω(step)とするステップと、
    　（ｂ４）集合Ω(step)に含まれるjとj’について、Ｓｊ（step+1）=Ｓｊ（step）-1、Ｓｊ’（step+1）=Ｓｊ’（step）+1とするステップと、
    　（ｂ５）集合Ω(step)に含まれないjについて、Ｓｊ（step+1）=Ｓｊ（step）とし、step+1をstepとするステップと、
    　（ｂ６）ステップ（ｂ２）からステップ（ｂ５）までを集合Ω(step)が空集合になるまで繰り返すステップと、
    　（ｂ７）集合Ω(step)が空集合になるstepから1減算したstepをstep*とするステップと、を含む請求項２に記載の処理方法。
  4. 　前記最小のエネルギー状態を持つ物理系を求めるステップ（ｃ）は、
    　（ｃ１）2m個の物理系に初期状態として同じ量子状態を与えるステップと、
    　（ｃ２）step=0とするステップと、　
    　（ｃ３）前記集合Ω(step)中の全ての前記物理系のペアj、j’に対して、前記物理系jを前記物理系uに対応させ、前記物理系j’を前記物理系dに対応させながら前記ステップ（ａ１）～（ａ４）を含む操作を適用するステップと、を含む請求項３に記載の処理方法。
  5. 　各物理系jにおける状態値Ｓｊ（step*）は、
    　　Ｓｊ（step*）=j-m-1  (j=1,2,・・・,m)
    　　Ｓｊ（step*）=j-m    (j=m+1,m+2,・・・,2m)
    で与えられる、請求項３に記載の処理方法。

     
PCT/JP2018/009994 2017-04-13 2018-03-14 量子アニーリング計算のための処理方法 WO2018190064A1 (ja)

Priority Applications (2)

Application Number Priority Date Filing Date Title
JP2019512393A JP7046379B2 (ja) 2017-04-13 2018-03-14 量子アニーリング計算のための処理方法
US16/598,265 US11403548B2 (en) 2017-04-13 2019-10-10 Method for quantum annealing computation

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2017-079583 2017-04-13
JP2017079583 2017-04-13

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US16/598,265 Continuation-In-Part US11403548B2 (en) 2017-04-13 2019-10-10 Method for quantum annealing computation

Publications (1)

Publication Number Publication Date
WO2018190064A1 true WO2018190064A1 (ja) 2018-10-18

Family

ID=63792883

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2018/009994 WO2018190064A1 (ja) 2017-04-13 2018-03-14 量子アニーリング計算のための処理方法

Country Status (3)

Country Link
US (1) US11403548B2 (ja)
JP (1) JP7046379B2 (ja)
WO (1) WO2018190064A1 (ja)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130282636A1 (en) * 2012-04-19 2013-10-24 D-Wave Systems Inc. Systems and methods for solving combinatorial problems

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101375302B (zh) 2006-01-27 2012-03-28 D-波系统公司 绝热量子计算的方法

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130282636A1 (en) * 2012-04-19 2013-10-24 D-Wave Systems Inc. Systems and methods for solving combinatorial problems

Also Published As

Publication number Publication date
US11403548B2 (en) 2022-08-02
JP7046379B2 (ja) 2022-04-04
US20200042894A1 (en) 2020-02-06
JPWO2018190064A1 (ja) 2020-02-20

Similar Documents

Publication Publication Date Title
JP7186797B2 (ja) 量子計算のための方法及びシステム
EP3740910B1 (en) Classification using quantum neural networks
Cai et al. Approximating quantum many-body wave functions using artificial neural networks
US11605015B2 (en) Hybrid quantum-classical computer system for implementing and optimizing quantum Boltzmann machines
US20200104740A1 (en) Hybrid Quantum-Classical Computer for Solving Linear Systems
US11157827B2 (en) Hybrid quantum-classical computer system for parameter-efficient circuit training
EP3837647A1 (en) Hybrid quantum-classical computer system and method for performing function inversion
JP2022032703A (ja) 情報処理システム
US20230131510A1 (en) Quantum computing system and method for time evolution of bipartite hamiltonians on a lattice
WO2020003434A1 (ja) 機械学習方法、機械学習装置、及び機械学習プログラム
CN116167446A (zh) 量子计算处理方法、装置及电子设备
KR20240175003A (ko) 플렉시블 잡샵 스케줄링 방법 및 플렉시블 잡샵 스케줄링 장치
WO2020170410A1 (ja) 情報処理システム、情報処理方法およびプログラム
Leleu et al. Scaling advantage of nonrelaxational dynamics for high-performance combinatorial optimization
CN110288444B (zh) 实现用户相关推荐的方法和系统
JP7579579B2 (ja) 組合せ最適化問題処理装置、組合せ最適化問題処理方法及びプログラム
US20230394344A1 (en) Quantum enhanced learning agent
WO2018190064A1 (ja) 量子アニーリング計算のための処理方法
CN117859138A (zh) 用于量子计算生成联合概率分布的系统和方法
Wu et al. Finding quantum many-body ground states with artificial neural network
CN117313881B (zh) 量子电路的分类方法、装置及电子设备
JP2021047780A (ja) 組合せ最適化問題処理装置、組合せ最適化問題処理方法及びプログラム
CN117556909B (zh) 量子电路模拟方法、装置及电子设备
CN116187456B (zh) 量子模拟方法、装置、设备以及存储介质
JP7536710B2 (ja) 求解装置、求解方法およびプログラム

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 18785228

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2019512393

Country of ref document: JP

Kind code of ref document: A

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 18785228

Country of ref document: EP

Kind code of ref document: A1