Method for quantum annealing computation

Abstract

A method for performing quantum annealing computation for solving a discrete optimization problem includes the steps of: (a) identifying an operation for transferring an energy state of one of two physical systems (u, d) having the same quantum state to a low energy state and transferring an energy state of the other of the two physical systems to a high energy state; (b) constructing a network structure among a plurality of physical systems that indicates an order of application of the operation of the step (a) on two physical systems among the plurality of physical systems; and (c) obtaining a physical system having a minimum energy state in the plurality of physical systems by applying the operation of the step (a) to the plurality of physical systems according to the order indicated in the network structure of step (b).

Claims

1. A method for performing quantum annealing computation to solve a discrete optimization problem using a quantum annealing computer comprising the step of; (a) identifying an operation for transferring energy state of one of two physical systems (u, d) having a same quantum state to a low energy state and transferring energy state of the other of the two physical systems to a high energy state; (b) constructing a network structure among a plurality of physical systems that indicates an order of application of the operation of the step (a) on two physical systems among the plurality of physical systems; (c) obtaining a physical system having a minimum energy state in the plurality of physical systems by applying the operation of the step (a) to the plurality of physical systems according to the order indicated in the network structure of step (b).

2. A method for performing quantum annealing computation according to the claim 1, wherein the step (a) comprises the step of (a1) giving the same quantum state as an initial state to the two physical systems (u, d); (a2) performing time evolving of the quantum state of the physical system u for a time τ (>0) using a Hamiltonian (H); (a3) performing a quantum swapping operation between physical system u and physical system d for time Δt (>0); and (a4) performing time evolving of the quantum state of the physical system u for time τ (>0) using an inverted Hamiltonian (−H).

3. A method for performing quantum annealing computation according to the claim 2, wherein the step (c) comprises the step of (c1) giving a same quantum state as an initial state to 2m physical systems (m is a positive integer); (c2) setting step=0, and (c3) applying an operation including the steps (a1) to (a4) to all the physical system pairs (j, j′) in the set Ω (step), under the condition that the physical system j corresponds to the physical system u and the physical system j′ corresponds to the physical system d.

4. A method for performing quantum annealing computation according to the claim 1, wherein the step (b) comprises the step of (b1) defining a state value of j-th physical system j (j is a positive integer equal to or less than 2m−1 and m is a positive integer) as j (step) in 2m physical systems and setting s j (0)=0 for all physical systems j; (b2) selecting a plurality of pairs of the physical system j and the physical system j′ which have a state value sj (step)=s j′ (step), from all the physical systems j and j′ where j<j′ (j, j′ is a positive integer of 2 m or less); (b3) collecting the plurality of pairs of the physical system j and the physical system j′ as a set Ω (step); (b4) setting the physical system j and physical system j′ included in the set Ω (step) to s j (step+1)=s j (step)−1,s j′ (step+1)=s j′ (step)+1; (b5) setting the physical system j not included in the set Ω (step) to s j (step+1)=s j (step) and step+1 to step; (b6) repeating the steps (b2) to (b5) until the set Ω (step) becomes an empty set; and (b7) setting a step obtained by subtracting 1 from the step in which the set Ω (step) is an empty set, to a step *.

5. A method for performing quantum annealing computation according to the claim 4, wherein the state value s j (step *) in each of the physical system j is given as s j (step *)=j−m−1 (j=1, 2, . . . , m) or s j (step *)=j−m (j=m+1, m+2, . . . , 2m).

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a diagram illustrating an outline of an example of a computation method including a main part of an algorithm of a method of the present invention;

(2) FIG. 2 is a diagram illustrating a flow of one embodiment of the method of the present invention;

(3) FIG. 3 is a conceptual diagram of an operation (step S10 in FIG. 2) for transferring an energy state of one embodiment of the method of the present invention;

(4) FIG. 4 is a schematic diagram of the conceptual diagram in FIG. 3;

(5) FIG. 5 is a diagram illustrating step S20 of obtaining a set of one embodiment of the method of the present invention and step S30 of obtaining a physical system having a minimum energy state among a plurality of physical systems;

(6) FIG. 6 is a diagram illustrating the time evolution of an expectation value of energy when one embodiment of the method of the present invention is performed (FIG. 5);

(7) FIG. 7 is a diagram illustrating an implementation example (configuration example) in which the method of the present invention is applied to a superconducting circuit (CJJ-rf-SQUID) using Josephson junction;

(8) FIG. 8 is a diagram illustrating a control sequence of the embodiment of FIG. 7;

(9) FIG. 9 is a diagram illustrating n dependency of a temporal behavior of a correct solution probability P(t) of a search problem by a nonlinear equation;

(10) FIG. 10 is a diagram illustrating n dependency of time t* when the correct solution probability P(t) becomes P(t)≥0.9; and

(11) FIG. 11 is a diagram illustrating m dependency of step* obtained by subtracting 1 from step where Ω(step) becomes an empty set and the number of quantum operations C(m).

DESCRIPTION OF THE PREFERRED EMBODIMENTS

(12) An embodiment of the present invention (a method for performing quantum annealing computation to solve a discrete optimization problem using a quantum annealing computer) will be described with reference to the accompanying drawings. FIG. 1 is a diagram illustrating an outline of an example of a computation method including a main part of an algorithm of the method. In an outline of the computation method in FIG. 1, first, an energy function (problem Hamiltonian H) is defined so that a solution of a problem becomes a lowest energy state (S1). Next, a method for transferring an energy state of one of two physical systems having the same quantum state to a low energy state and transferring an energy state of the other of the two physical systems to a high energy state is repeatedly applied the two physical systems among the plurality of physical systems (S2). As a result, the lowest energy state whose state is the solution of the problem can be obtained (S3).

(13) FIG. 2 is a diagram illustrating a flow of one embodiment of the method for performing the quantum annealing computation of the present invention. As step S10, an operation for transferring an energy state of one of two physical systems (u, d) having the same quantum state to a low energy state and transferring an energy state of the other of the two physical systems (u, d) to a high energy state is identified. As step S20, among the plurality of physical systems, each state value of the plurality of physical systems in each step is set under a predetermined rule while sequentially transferring steps from step 0 which will be described later, and a set is obtained by collecting a pair of physical systems having the same state value until reaching a step in which a pair of physical systems having the same state value is eliminated. In other words, in step S20, a network structure (refer to FIG. 5 which will be described later) among the plurality of physical systems that indicates an order of application of the operation of step S10 on two physical systems among the plurality of physical systems is constructed. In step S30, a physical system having a minimum energy state in the plurality of physical systems is obtained by applying step 10 to the plurality of physical systems according to the order indicated in the network structure of step 20.

(14) An operation for transferring the energy state of step S10 in FIG. 2 will be described in detail with reference to FIG. 3. FIG. 3 is a conceptual diagram of an operation (step S10 in FIG. 2) for transferring an energy state of one embodiment of the method of the present invention. First, the same quantum state indicated in the following (1) is prepared as an initial state in the two physical systems (u, d).
|φ.sub.0φ.sub.0|  (1)

(15) At this point of time, the physical system u and the physical system d have the same expectation value of energy indicated in the following (2).
φ.sub.0|Ĥ|φ.sub.0  (2)

(16) Next, dispersion of energy in a quantum state of (1) is given by the following equation (3).
ΔE=φ.sub.0|Ĥ.sup.2|φ.sub.0−φ.sub.0|Ĥ|φ.sub.0.sup.2  (3)

(17) As a “first operation 1”, time evolution of the quantum state of the physical system u is performed for time τ (>0) using a Hamiltonian indicated in the following (4). A block denoted by a reference sign 1 in FIG. 3 indicates the first operation 1.
Ĥ  (4)
As a “second operation 2”, a quantum swapping operation is performed between the physical system u and the physical system d for time Δt (>0). A block denoted by a reference sign 2 in FIG. 3 indicates the second operation 2.

(18) As a “third operation 3”, time evolution of the quantum state of the physical system u is performed for time τ (>0) using an inverted Hamiltonian indicated in the following (5). A block denoted by a reference sign 3 in FIG. 3 indicates the third operation 3.
−Ĥ  (5)

(19) As a result of quantum mechanical time evolution defined by the operations, in the quantum states of the physical system u and the physical system d after the first to third operations in a series are performed, the quantum state of the physical system u can be represented by the following equation (6), and the quantum state of the physical system d can be represented by the following equation (7) in the approximate range up to the first order of τ and Δt.
ρ.sub.u=|φ.sub.0φ.sub.0|+τ[[Ĥ,|φ.sub.0φ.sub.0|],|φ.sub.0φ.sub.0|]Δt  (6)
ρ.sub.d=|φ.sub.0φ.sub.0|−τ[[Ĥ,|φ.sub.0φ.sub.0|],|φ.sub.0φ.sub.0|]Δt  (7)

(20) Here, in consideration of solution (9) of the following nonlinear equation (8),

(21) $\begin{array}{cc}\frac{d}{\mathrm{dt}}\left(.Math.{\phi }_t.Math..Math.{\phi }_t.Math.\right)=-7\left[\left[\hat{H},.Math.{\phi }_t.Math..Math.{\phi }_t.Math.\right],.Math.{\phi }_t.Math..Math.{\phi }_t.Math.\right]& \left(8\right)\\ .Math.{\phi }_t.Math..Math.{\phi }_t.Math.& \left(9\right)\end{array}$

(22) It can be seen that the following equations (10) and (11) are established in the approximate range up to the first order of τ and Δt.
ρ.sub.u=|φ.sub.t=−Δtφ.sub.t=−Δt|  (10)
ρ.sub.d=|φ.sub.t−|Δtφ.sub.t−|Δt|  (11)

(23) An expectation value of energy of the following (12) in a state given in the above-described (9) is monotonously decreasing with respect to t.
tr(Ĥ|φ.sub.tφ.sub.t|)  (12)

(24) An expectation value of energy in the state after the first to third operations is represented by the following equation (13) with respect to the physical system u, and is higher than an expectation value in the initial state by ΔEτΔt.
tr(Ĥρ.sub.u)=φ.sub.0|Ĥ|φ+τΔEΔt  (13)

(25) On the other hand, the expectation value of energy is represented by the following equation (14) with respect to the physical system d, and is lower than the expectation value in the initial state by ΔEτΔt.
tr(Ĥρ.sub.d)=φ.sub.0|Ĥ|φ.sub.0−τΔEΔt  (14)

(26) As described above, it can be seen that the physical system u is transferred to the high energy state and the physical system d is transferred to the low energy state by the first to third series of operations.

(27) Next, steps S20 and S30 in FIG. 2 will be described in detail with reference to FIGS. 4 to 6. In other words, a method used by the quantum computer for solving the discrete optimization problem by applying the method of step S10 in FIG. 2 among the plurality of physical systems will be described. FIG. 4 is a schematic diagram of the conceptual diagram of FIG. 3. In FIG. 4, a black circle 4 and a white circle 5 are simplified descriptions corresponding to the first operation 1 to the third operation 3 in FIG. 3. FIG. 5 is a diagram illustrating step S20 of constructing the network structure among the plurality of physical systems in one embodiment of the method of the present invention and step S30 of obtaining the physical system having the minimum energy state among the plurality of physical systems. In FIG. 5, the states of the plurality of physical systems are displayed by using the simplified descriptions (black circle 4 and white circle 5) in FIG. 4. FIG. 6 is a diagram illustrating the time evolution of the expectation value of energy of a case (FIG. 5) in which the operation of step S10 is applied to all the physical system pairs in the network structure illustrated in FIG. 5 by causing the two physical systems (u, d) to correspond thereto, and the physical system having the minimum energy state in the plurality of physical systems is obtained.

(28) m is set as a positive integer and 2m physical systems are considered. A network structure among the plurality of physical systems is constructed by the following procedure. FIG. 5 illustrates a case of m=4 (physical system 1 to physical system 8).

(29) (1) A non-negative integer step starting from 0 is introduced. FIGS. 5 and 6 illustrate a state transfer in which step=0 is set as an initial state and step=1 to step=11 are sequentially increased by one.

(30) (2) An integer s.sub.j (step) determined by the following rules is introduced into a physical system of j-th (j is a positive integer equal to or less than 2m−1).

(31) (2-1) s.sub.j(0) is set as 0 for all the physical systems j.

(32) (2-2) A pair of a physical system j and a physical system j′ which have a state value s.sub.j (step)=s.sub.j′ (step) is selected from all the physical systems j and j′ where j<j′ (j′ is a positive integer equal to or less than 2m). In FIG. 5, one line that connects a black circle and a white circle in a vertical direction (direction in which the physical systems 1 to 8 are arranged) represents one pair. For example, in the physical systems 1 and 3 of step=2, s.sub.1(2)=s.sub.3(2)=−1, and the physical system 1 and the physical system 3 are paired. In the same manner, in the physical system 4 and the physical system 7 of step=7, s.sub.4(7)=s.sub.7(7)=+2, and the physical system 4 and the physical system 7 are paired. Except for the physical system j and the physical system j′ once paired, such pairs are collected as much as possible.

(33) (2-3) A set having a plurality of pair of the physical systems configured as described above as an element is defined as Ω(step).

(34) (2-4) With respect to the physical system j and physical system j′ appearing in Ω(step), s.sub.j(step+1) and s.sub.j′ (step+1) are defined as in the following equations (15) and (16).
s.sub.j(step+1=s.sub.j(step)−1  (15)
s.sub.j′(step+1)=s.sub.j′(step)+1  (16)

(35) In FIG. 5, for example, in a pair of the physical system 3 and the physical system 6 of step=5, s.sub.3(6)=s.sub.3(5)−1=−1, s.sub.6(6)=s.sub.6(5)+1=0. The same applies to the other pairs.

(36) (2-5) With respect to j which does not appear in Ω(step), the following equation (17) is defined.
s.sub.j(step+1)=s.sub.j(step)  (17)

(37) In FIG. 5, for example, from step=4 to step=7 of the physical system 1, s.sub.1(7)=s.sub.1(6)=s.sub.1(5)=s.sub.1(4)s.sub.1(3)=−3. The same applies to others.

(38) (2-6) Returning to the above-described (2-2) with step+1 as step, and (2-2) to (2-6) are repeated until the set Ω(step) becomes an empty set.

(39) (2-7) A step obtained by subtracting 1 from a step where the set Ω (step) becomes the empty set is defined as step*. In FIG. 5, step=11 obtained by subtracting 1 from step=12 (final state) where the set Ω(step) becomes the empty set becomes step*. At this time, the following (18) is referred to as a network structure among the plurality of physical systems. This network structure (18) can be determined independently of the Hamiltonian H which desires to obtain a minimum eigenstate.

(40) $\begin{array}{cc}\underset{\mathrm{step}0}{\stackrel{\mathrm{step}*}{.Math.}}\Omega \left(\mathrm{step}\right)& \left(18\right)\end{array}$

(41) Further, the value of s.sub.j(step*) in each physical system j can be obtained by the following equation (19) by a construction method for the network structure among the plurality of physical systems.

(42) $\begin{array}{cc}{s}_j\left(\mathrm{step}\right)=\{\begin{array}{ccc}j-m-1& \mathrm{for}& j\in \left\{1,\mathrm{.Math.},m\right\}\\ j-m& \mathrm{for}& j\in \left\{m+1,\mathrm{.Math.},2m\right\}\end{array}& \left(19\right)\end{array}$

(43) In FIG. 5, for example, in the physical system 4, s.sub.4(step*)=s.sub.4(11)=j−m−1=4−4−1=−1, and in the physical system 8, s.sub.8(step*)=s.sub.8(11)=j−m=8−4=+4.

(44) The time evolution of the quantum state is performed by using the network structure among the plurality of physical systems constructed as described above and the operation of transferring the energy state of step S10 in FIG. 2 (an energy exchange method between the two physical systems having the same quantum state) as follows.

(45) (1) The same quantum state is prepared as an initial state in 2m physical systems.

(46) (2) Step=0 is set.

(47) (3) The operation of transferring the energy state of step S10 is applied to all the physical system pairs {j, j′} (note that j<j′) included in the set Ω(step) under the condition that the physical system j corresponds to the physical system u of step S10 (FIG. 3) in FIG. 2, and the physical system j′ corresponds to the physical system d.

(48) (4) Step+1 is returned to (3) as a new step, and repeated until step=step* is reached.

(49) In this case, the above-described equations (10) and (11) are repeatedly applied, and the state of each step in each physical system j is represented by the following (20) in the approximate range up to the first order of τ and Δt by using solution (9) of equation (8).
|φ.sub.t−s.sub.j.sub.(step)Δtφ.sub.t−s.sub.j.sub.(step)Δt|  (20)

(50) The result of strictly computing the expectation value of energy at this time is shown in a diagram illustrating the time evolution of the expectation value of energy in FIG. 6. In FIG. 6, it is shown that one area surrounded by a broken line 7 represents the expectation value of energy; black and white shading represents the magnitude of the expectation value of energy; and as the color becomes darker, the expectation value of energy becomes smaller. Since FIG. 6 corresponds to the physical system of m=4 in FIG. 5, it can be seen that the expectation value of energy becomes minimum in step=11 of the physical system 8.

(51) In step=step*, equation (19), equation (20), and equation (12) are monotonically decreasing with respect to t, whereby the expectation value of energy in the state of each physical system j is monotonously decreasing with respect to j. Among them, particularly, in the physical system of j=2m (physical system 8 in the example of FIG. 5), the lowest state of the expectation value of energy of the following (21) is realized as a result of the quantum mechanical time evolution defined by the series of operations described above.
|φ.sub.t−+mΔtρ.sub.t−+mΔt|  (21)

First Embodiment

(52) As a first embodiment, an implementation example when the operation of step S10 in FIG. 2 is applied to a superconducting circuit using Josephson junction (“CJJ-rf-SQUID”, Physical Review B 80,052506,2009) will be hereinafter described. FIG. 7 is a diagram illustrating the implementation example (configuration example). FIG. 7 illustrates an example of two quantum bits 1 and 2. In the physical system u and d, a superconducting loop 10 forming the quantum bits 1 and 2 includes a mini loop 11 including two Josephson junctions (x). In each of the superconducting loops 10, the similar superconducting loops are magnetically joined to each other through mutual inductance. Further, in the following description, a case in which two quantum bits i and j are more generally assumed will be described.

(53) In the CJJ-rf-SQUID system, an interaction in the form of the following equation (22) can be formed between the two quantum bits i and j.
Ĥ.sub.(i,j)=½[h.sub.i(t){circumflex over (σ)}.sub.z.sup.(i)+h.sub.j(t){circumflex over (σ)}.sub.z.sup.(j)+Δ.sub.i(t){circumflex over (σ)}.sub.x.sup.(i)+Δ.sub.j(t){circumflex over (σ)}.sub.x.sup.(j)]+J.sub.ij(t){circumflex over (σ)}.sub.z.sup.(i){circumflex over (σ)}.sub.z.sup.(j)  (22)

(54) Here, each coefficient of the following (23) in equation (22) is a function of time which takes an integer value. FIG. 8 is a diagram illustrating the control sequence of the embodiment in FIG. 7, that is, the time transfer of values (−1, 0, +1) of each coefficient of the following (23).
h.sub.i(t),h.sub.j(t),Δ.sub.i(t),Δ.sub.j(t),J.sub.ij(t)  (23)

(55) Further, each coefficient of the following (24) is a Pauli matrix of the quantum bit i.
{circumflex over (σ)}.sub.x.sup.(i){circumflex over (σ)}.sub.y.sup.(i),{circumflex over (σ)}.sub.z.sup.(i)  (24)

(56) A set of quantum bits in which the interaction of the above-described equation (22) is realized is considered. The set of these quantum bits is divided into two, and one is caused to correspond to the physical system u and the other is caused to correspond to the physical system d. At this time, a label of the quantum bit i belonging to the physical system u is defined as (i, u), and a label of the quantum bit i belonging to the physical system d is defined as (i, d). That is, the interaction between these quantum bits is represented as the following equation (25).

(57) $\begin{array}{cc}\underset{q\in \left\{u,d\right\}}{.Math.}\underset{i}{.Math.}\frac{1}{2}\left(h_{i,q}\left(i\right){\hat{\sigma }}_z^{\left(i,q\right)}+{\Delta }_{i,q}\left(t\right){\hat{\sigma }}_x^{\left(i,q\right)}\right)+\underset{q\in \left\{u,d\right\}}{.Math.}\underset{q^{\prime }\in \left\{u,d\right\}}{.Math.}\underset{i,j}{.Math.}{J}_{i,q,j,q^{\prime }}{\hat{\sigma }}_z^{\left(i,q\right)}{\hat{\sigma }}_z^{\left(j,q^{\prime }\right)}& \left(25\right)\end{array}$

(58) At this time, in the same manner as the case of the quantum annealing computation, in the interaction of equation (25) at t<0, the following equation (26) is introduced and other coefficients are set to 0, thereby preparing an initial state (range of t<0 in FIG. 8).
Δ.sub.i,u(t)=Δ.sub.i,d(t)=−1  (26)

(59) In the same manner as the case of the quantum annealing computation, corresponding to the above-described first operation, the Hamiltonian of equation (4) is realized as shown in the following equation (27) by using the interaction between the quantum bits forming the physical system u in equation (25).

(60) $\begin{array}{cc}\hat{H}=\underset{i}{.Math.}\frac{1}{2}{h}_{i,u}{\hat{\sigma }}_z^{\left(i,u\right)}+\underset{i,j}{.Math.}{J}_{i,u,j,u}{\sigma }_z^{\left(i,u\right)}{\sigma }_z^{\left(j,u\right)}& \left(27\right)\end{array}$

(61) That is, the following equations (28) and (29) are set for time τ (for time τ in FIG. 8), thereby completing the first operation.
h.sub.i,u(t)=h.sub.i,u,J.sub.i,u,j,u(t)=J.sub.i,u,j,u  (28)
h.sub.i,d(t)=Δ.sub.i,u(t)=Δ.sub.i,d(t)=J.sub.i,u,j,u′(t)=J.sub.i,u′,j,u′(t)=0  (29)

(62) Corresponding to the above-described second operation, a swapping operation is performed. The swapping operation forms the interaction of the following equation (30) between the quantum bits forming the physical system u and the physical system d in equation (25), and is set for the time Δt, thereby completing the second operation.

(63) $\begin{array}{cc}{\hat{S}}_{\mathrm{ud}}=\frac{1}{2}\left(I+\underset{i}{.Math.}\left({\hat{\sigma }}_x^{\left(i,u\right)}{\hat{\sigma }}_x^{\left(i,d\right)}+{\hat{\sigma }}_y^{\left(i,u\right)}{\hat{\sigma }}_y^{\left(i,d\right)}+{\hat{\sigma }}_z^{\left(i,u\right)}{\hat{\sigma }}_z^{\left(i,d\right)}\right)\right)& \left(30\right)\end{array}$

(64) However, the interaction of equation (30) cannot be directly realized by the interaction in the form of equation (25). Therefore, when the following equations (31) to (34) are paid attention to, in the range up to the first order of Δt that establishes equation (6) and equation (7), the second operation can be implemented indirectly by performing the following operations (1) to (3) in order.

(65) $\begin{array}{cc}{e}^{-i{\hat{S}}_{\mathrm{ud}}\Delta t}=e^{-i\frac{\Delta t}{2}}{U}_x{U}_y{U}_z+O\left(\Delta t^2\right)& \left(31\right)\\ U_z=\exp \left(-i\frac{\Delta t}{2}\underset{i}{.Math.}{\hat{\sigma }}_z^{\left(i,u\right)}{\hat{\sigma }}_z^{\left(i,d\right)}\right)& \left(32\right)\\ U_y=e^{-i\frac{\pi }{2}{.Math.}_i\left({\sigma }_x^{\left(i,u\right)}+{\sigma }_x^{\left(i,d\right)}\right)}{U}_z{e}^{+i\frac{\pi }{2}{.Math.}_i\left({\sigma }_x^{\left(i,u\right)}+{\sigma }_x^{\left(i,d\right)}\right)}& \left(33\right)\\ U_x=e^{-i\frac{\pi }{2}{.Math.}_i\left({\sigma }_z^{\left(i,u\right)}+{\sigma }_z^{\left(i,d\right)}\right)}{U}_y{e}^{+i\frac{\pi }{2}{.Math.}_i\left({\sigma }_z^{\left(i,u\right)}+{\sigma }_z^{\left(i,d\right)}\right)}& \left(34\right)\end{array}$

(66) (1) Operation of Equation (32):

(67) In equation (25), as the following equation (35), all the remaining coefficients are set to 0 for time Δt (for the first Δt in FIG. 8). Accordingly, the operation of equation (31) is completed.
J.sub.i,u,i,d(t)=1  (35)

(68) (2) Operation of Equation (33):

(69) In equation (25), as the following equation (36), all the remaining coefficients are set to 0 for time π/2 (for the first π/2 in FIG. 8). After that, as equation (35), all the remaining coefficients are set to 0 for time Δt (for the second Δt in FIG. 8).
Δ.sub.i,u(t)=Δ.sub.i,d(t)=1  (36)

(70) Further, as the following equation (37), all the remaining coefficients are set to 0 for time π/2 (for the second π/2 in FIG. 8). Accordingly, the operation of equation (33) is completed.
Δ.sub.i,u(t)=Δ.sub.i,d(t)=−1  (37)

(71) (3) Operation of Equation (34):

(72) In equation (25), as the following equation (38), all the remaining coefficients are set to 0 for time π/2 (for the third π/2 in FIG. 8).
h.sub.i,u(t)=h.sub.i,d(t)=1  (38)

(73) Thereafter, as equation (36), all the remaining coefficients are set to 0 and time π/2 is allowed to elapse (for the fourth π/2 in FIG. 8), and then as equation (35), all the remaining coefficients are set to 0 for time Δt (for the third Δt in FIG. 8). Further, as equation (37), all the remaining coefficients are set to 0 and time π/2 is allowed to elapse (for the fifth π/2 in FIG. 8), and further, as the following equation (39), all the remaining coefficients are set to 0 for time π/2 (for the last π/2 in FIG. 8).
h.sub.i,u(t)=h.sub.i,d(t)=−1  (39)

(74) Accordingly, the operation of equation (34) is completed. The second operation is completed by the above-described series of operations (1), (2), and (3).

(75) Corresponding to the above-described second operation, the interaction of equation (5) is set for time interval τ by using the interaction between the quantum bits forming the physical system u in equation (25). Since this is formed by the inversion of equation (27), the following equation (40) may be set corresponding to equation (28). Accordingly, the third operation is completed.
h.sub.i,d(t)=−h.sub.i,u,J.sub.i,u,j,u(t)=−J.sub.i,u,j,u  (40)

(76) As described above, in order to use the method (operation) of step S10 in FIG. 2 by the implemented CJJ-rf-SQUID for the quantum computation by being repeatedly applied to 2m physical systems, the method can be used (implemented) by using the above-described series of processes with reference to FIGS. 4 to 6.

Second Embodiment

(77) Next, as a second embodiment, in order to evaluate the number of computation steps and the required number of quantum bits, a case in which the present invention is applied to a search problem of a search space 2.sup.n will be described. First, the Hamiltonian of the following equation (41) corresponding to the search problem is applied to the nonlinear equation of equation (8).
Ĥ=−ω.sub.0|ω.sub.0ω.sub.0|,ω.sub.0>0  (41)

(78) When the correct solution probability of the following equation (42) at time t is computed, an analytical solution exists and thus the following equation (43) is obtained. FIG. 9 is a diagram illustrating n dependency of a temporal behavior of a correct solution probability P(t) of the search problem based upon the nonlinear equation, obtained by plotting P(t) of equation (43).

(79) $\begin{array}{cc}P\left(t\right):={.Math..Math.{\omega }_0.Math.{\phi }_i.Math..Math.}^2& \left(42\right)\\ P\left(t\right)=\frac{1}{1+\left({P\left(0\right)}^{-1}-1\right)\exp \left(-2{\omega }_0\tau t\right)}& \left(43\right)\end{array}$

(80) Here, considered is a case where a size of a solution space is the following (44) and an initial correct solution probability is represented by the following equation (45).
2.sup.n  (44)
P(0)=2.sup.−n  (45)

(81) At this time, when time t satisfying the following equation (46) is defined as t*, t* is obtained as the following equation (47). FIG. 10 illustrates a plot of t* in equation (47), and a graph A shows n dependency of time t* when the correct solution probability P(t)≥0.9.

(82) $\begin{array}{cc}P\left(t\right)\ge ϵ& \left(46\right)\\ t^{*}=\frac{1}{2{\omega }_0\tau }\left(\ln \frac{1-ϵ}{ϵ}+\ln \left(2^n-1\right)\right)=O\left(\frac{n}{{\omega }_0\tau }\right)& \left(47\right)\end{array}$

(83) Here, according to a fact that the state obtained by this example is equation (21), when m corresponding to t* of equation (47) is set to m*, the following equation (48) can be obtained.

(84) 0$\begin{array}{cc}{m}^{*}=\frac{1}{2{\omega }_0\tau \Delta t}\left(\ln \frac{1-ϵ}{ϵ}+\ln \left(2^n-1\right)\right)=O\left(\frac{n}{{\omega }_0\tau \Delta t}\right)& \left(48\right)\end{array}$

(85) When noting that a relationship between step* and m is the following equation (49) regardless of the details of the Hamiltonian (H), it can be seen that the step* determined by m* is represented by the following equation (50), which indicates the second order (n.sup.2) of n.

(86) $\begin{array}{cc}{\mathrm{step}}^{*}=O\left(m^2\right)& \left(49\right)\\ {\mathrm{step}}^{*}=O\left(\frac{n^2}{{\omega }_0^2{\tau }^2\Delta t^2}\right)& \left(50\right)\end{array}$

(87) Further, since the number of quantum bits per system required for representing the problem of equation (43) is n pieces, the following equation (51) is obtained for the whole 2m* system.

(88) $\begin{array}{cc}2m^{*}n=O\left(\frac{n^2}{{\omega }_0\tau \Delta t}\right)& \left(51\right)\end{array}$

(89) Further, since the number C(m) of quantum operations required for the given m is the following equation (52), the following equation (53) is obtained when applied to the search problem. FIG. 11 is a diagram illustrating m dependency of the step* obtained by plotting equation (50) and the number C(m) of quantum operations obtained by plotting equation (53).

(90) $\begin{array}{cc}C\left(m\right)=\underset{\mathrm{step}=1}{\overset{{\mathrm{step}}^{*}}{.Math.}}.Math.\Omega \left(\mathrm{step}\right).Math.=O\left(m^3\right)& \left(52\right)\\ C\left(m^{*}\right)=O\left(\frac{n^3}{{\omega }_0\tau \Delta t}\right)& \left(53\right)\end{array}$

(91) When the conventional quantum annealing computation is applied to the search problem of the search space 2.sup.n and the gate type quantum computation search problem, it is known that the number of computation steps is 2.sup.n/2 (even though the number is smaller than that of computation that does not use quantum) and behaves exponentially with respect to n. On the other hand, as described above, the number of computation steps (step*) according to the present invention is suppressed in a highly polynomial manner (for example, n.sup.2) with respect to n. In the same manner, the number of quantum bits required for the computation is proportional to n.sup.2 in the present invention, whereas the conventional computation method is approximately proportional to n. Further, the problem can be solved by the number of computation steps and the required number of quantum operations (C(m)) in a highly polynomial size (for example, n.sup.3) with respect to n.

(92) Embodiments of the present invention have been described with reference to the accompanying drawings. However, the present invention is not limited to the embodiments. Further, the present invention can be implemented in a manner to which various improvements, corrections, and modification are added based upon the knowledge of those skilled in the art without departing from the spirit of the present invention.