JP4366348B2 - Quantum calculation method and quantum calculation device - Google Patents

Description

  The present invention relates to the field of quantum computers, and more particularly to a technique for obtaining a number useful for order discovery using a quantum computer.

Using a j-digit binary number N and a binary number A smaller than N as input, 2j + 3 qubits are used to calculate the number of basic operations proportional to the fourth power of j with the number of calculation steps proportional to the third power of j. Configuration of a quantum circuit that outputs a 2j-digit binary number C useful for finding the order of A with respect to mod N (ie, the smallest binary number R satisfying A ^R = 1 mod N) with high probability. The method is known (for example, refer nonpatent literature 1). Here, “a 2j-digit binary number C useful for order discovery” means c in Equation (5.13) of Non-Patent Document 2. By inputting this C into a classical circuit using polynomial basic operations related to j, the order R (r in Non-Patent Document 2) related to mod N of A can be obtained with high probability.

  The conventional quantum circuit described in Non-Patent Document 1 will be outlined below. In addition, although a quantum circuit uses the operation for a qubit and a CNOT operation as a basic operation, in order to avoid that a figure becomes complicated, below, a quantum circuit is comprised also using operations other than these operations. That is, all the operations used in this quantum circuit can be decomposed into an operation for one qubit and a CNOT operation (for example, see Non-Patent Document 3). Each figure shows the case of j = 5, but it is easy to extend these quantum circuits to the general case of j. Each variable appearing in the input represents 0 or 1. Further, the output of the quantum circuit for the superposition state is expressed by a linear combination of the respective quantum states, and all numbers larger than N are interpreted as mod N. Further, | ·> means a quantum state indicating •.

FIG. 31 is a diagram showing a conventional configuration of a quantum circuit for finding a value useful for this order finding. In the configuration of FIG. 31, quantum operations are performed on two qubits whose quantum states are | 0> and | 1> and 2j + 1 qubits of quantum state | 0>, respectively. position binary number of useful 2j digits of the number found _{c 2j-1} ... _{c 0} is obtained. H, X, and R are operators defined as shown in FIGS. 32 (a), 32 (b) and 33, respectively.
FIG. 34 is a quantum circuit showing details of the calculation of CU (A) = CU (A · 2 ⁰ ) in FIG. As shown in FIG. 34, CU (A) has d = 1 for a quantum state input indicating dε {0, 1}, U = u ₀ ... U ₄ and j + 2 0s, respectively. Then, each digit of d and A · U mod N (d and A · U mod N) ₀ ... (d and A · U mod N) ₄ and a quantum state indicating j + 2 0s respectively If d = 0, the input quantum state is output as it is. Here, CSWAP in FIG. 34 is an operator as shown in FIG. Moreover, the structure of each operator used for FIG. 35 is shown to FIG. 36 (a) (b) and FIG. Incidentally, ^CU of FIG. 31 (A · 2 1) ··· CU (A · 2 9) consists of A in FIG. 34 to that replaced by ^{A · 2 1 ··· A · 2} 9.

FIG. 38 is a quantum circuit showing details of the operation of CMULT (A) MOD (N) in FIG. As shown in FIG. 38, CMULT (A) MOD (N) is a quantum indicating d, U, a value obtained by adding 0 to the most significant bit of B = b _j−1 ... B ₀ , and 0, respectively. If the state is an input and d = 1, a quantum state indicating each digit of d, U, and A · U + M mod N and 0 and 0 is generated. If d = 0, the quantum state of the input is determined. Output as is. Note that CMULT (A ⁻¹ ) MOD (N) is obtained by replacing A in FIG. 38 with A ⁻¹ .
FIG. 39 is a quantum circuit showing details of the operation of QFT (quantum Fourier transform) in FIG. Note that Kε {2,..., 6} in FIG. 39 is an operator as shown in FIG. Also, QFT ⁻¹ in FIG. 38 indicates the inverse operation of QFT.

Figure 41 is a quantum circuit showing details of the operation of FaiADD in FIG 38 (A) MOD (N) = φADD (2 0 · A) MOD (N). φADD (A) MOD (N) is obtained by substituting d ₁ , d ₂ , a value obtained by applying QFT to B with 0 added to the most significant bit, φ _j (B),..., φ ₀ (B), and 0 If each quantum state is an input and d ₁ = d ₂ = 1, then d ₁ , d ₂ and a value obtained by applying QFT to A + B mod N φ _j (A + B mod N),..., Φ ₀ (A + B mod N) and quantum states respectively indicating 0 are generated, and if d ₁ = d ₂ = 1, the input quantum state is output as it is. Note that φADD (A) in FIG. 41 is an operator as shown in FIG. 42, and a value φ _j (B),..., Φ ₀ (B) obtained by applying QFT to B with 0 added to the most significant bit. the inputs the quantum state shown, a + value was applied QFT to _{B φ j (a + B)} , ..., and generates a quantum state shown phi ₀ to (a + B). Note that σ _k (kε {1,..., 5}) in FIG. 42 is an operator as shown in FIG. ΦADD (A) ⁻¹ is an inverse operation of φADD (A). ΦADD (N) and φADD (N) ⁻¹ are operators obtained by replacing A in φADD (A) and φADD (A) ⁻¹ with N. For other φADD (A · 2 ¹ ) MOD (N)... ΦADD (A · 2 ⁴ ) MOD (N), A in FIG. 41 is replaced with A · 2 ¹ ... A · 2 ⁴ It will be.
S. BEAUREGARD, CIRCUIT FOR SHOR'S ALGORITHM USING 2N + 3 QUBITS, QUANTUM INFORMATION AND COMPUTATION, Vol. 3 No. 2, pp. 175-185, 2003. PETER W. SHOR, POLYNOMIAL-TIME ALGORITHMS FOR PRIME FACTORIZATION AND DISCRETE LOGARITHMS ON A QUANTUM COMPUTER, SIAM J. COMPUT, Vol. 26, No. 5, pp. 1448-1509, October 1997. MA Nielsen and IL Chuang, Quantum Computation and Quantum Information, Cambridge, 2000.

As described above, in the quantum circuit of Non-Patent Document 1, a 2j-digit number useful for finding the order of mod N of A from a j-digit binary number N and a j-digit binary number A smaller than N. In order to output the binary number C with high probability, the number of basic operations proportional to the fourth power of j, the number of calculation steps proportional to the third power of j, and 2j + 3 qubits are required. However, since it is physically difficult to realize a large number of qubits and operate them cooperatively, the number of qubits should be as small as possible.
The present invention has been made in view of such a point, and a technique that makes it possible to obtain a 2j-digit binary number C useful for order discovery with a high probability using fewer qubits than in the past. The purpose is to provide.

In order to solve the above object may be stored and binary j digits _{N = n j-1 ... n} 0 and _{A = a j-1 ... a} 0 in the memory _{(n h-1} 2 The _H-th value of N in decimal notation, a _h-1 is the _h-th value of A in binary), and the subtraction unit calculates N−A from N and A read from the memory. . Further, COMPARISON calculation unit, using the N-A calculated by the subtraction unit, qubit quantum states respectively each digit of _{B = b} binary j digits smaller than _{N j-1 ... b 0 QB} j ₋₁ ,..., QB ₀ and qubits QU _j−1 ,..., QU ₁ , QZ in any quantum state are subjected to a first quantum operation, and only when N−A> B, Invert the quantum state. Then, the qubit QZ processed by the COMPARISON operation unit is used as it is or inverted and used as a control bit for other quantum operations.

Here, the processing content of this COMPARISON calculation unit is included in the processing of φADD (A), φADD (N) ⁻¹ and QFT ⁻¹ in FIG. However, in the conventional configuration of FIG. 41, one of the qubits (the second qubit from the bottom in FIG. 41) subjected to the processing of φADD (A), φADD (N) ⁻¹ and QFT ⁻¹ The quantum state must be transferred to another qubit (bottom qubit in FIG. 41) by the CNOT operation, and this other qubit must be used as a control bit for another quanta operation [φADD (N)]. On the other hand, in the present invention, the qubit QZ itself processed by the COMPARISON operation unit can be used as a control bit for other quantum operations. Therefore, it is possible to reduce one qubit that has been conventionally required to shift the quantum state. Further, in the present invention, the COMPARISON operation unit performs quantum bits QU _j−1 ,..., QU ₁ (where φADD (A), φADD (N) ⁻¹ and QFT ⁻¹ in FIG. 41 have not been operated at all). value u _4, ..., the operation of the quantum bit) indicating a quantum state of u ₁ also performed, thereby achieving effective use of qubits. This is also the reason why the configuration of the present invention can reduce the number of qubits compared to the prior art.

In the present invention, it is preferable that the COMPARISON operation unit performs the first quantum operation using the quantum bits QD ₁ and QD ₂ in arbitrary quantum states as control bits, and the QFT operation unit performs the quantum bit QB _j−1. ,..., QB ₀ is subjected to a quantum Fourier transform operation. Then, the qubits QD ₁ , QD ₂ , and QZ are used as control bits, and the φADD arithmetic unit only applies to the qubit QB _k (k∈ {j−1,..., 0}) in the quantum state indicating 1

（ただし、量子ビットＱＢ_ｋの量子状態を｜ＱＢ_ｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施し、第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施す。さらに、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとし、φＡＤＤ^−１演算部が、１を示す量子状態の量子ビットＱＢ_ｋのみに対し、

(However, the quantum state of the qubit QB _k is | QB _k >, e is a Napier number, and i is an imaginary number unit), and the first NOT operation unit performs a NOT operation on the qubit QZ. Further, the qubits QD ₁ , QD ₂ , and QZ are used as control bits, and the φADD ⁻¹ arithmetic unit only applies to the qubit QB _{k in the} quantum state indicating 1.

（ただし、Ｎ−Ａ＝（ｎ−ａ）_ｊ−１…（ｎ−ａ）_０とする）の演算を施し、第１ＮＯＴ演算部が、量子ビットＱＺにＮＯＴ演算を施す。そして、ＱＦＴ^−１演算部が、量子ビットＱＢ_ｊ−１，…，ＱＢ_０に対して量子フーリエ変換の逆演算操作を施し、ＣＯＭＰＡＲＩＳＯＮ演算部が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＢ_ｊ−１，…，ＱＢ_０，ＱＵ_ｊ−１，…，ＱＵ_１，ＱＺに対し、Ａ＞Ｂの場合にのみ量子ビットＱＺの量子状態を反転させる量子操作を行い、第１Ｔｏｆｆｏｌｉ演算部が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を施す。

(However, NA = (na) _j-1 ... (Na) ₀ ), and the first NOT operation unit performs NOT operation on the qubit QZ. Then, ^{QFT -1} calculation unit, qubits _{QB j-1,} ..., performs inverse calculation operation of the quantum Fourier transform to QB _0, COMPARISON calculation unit, as the control bit qubit _QD 1, QD _2, Quantum bits QB _j−1 ,..., QB ₀ , QU _j−1 ,..., QU ₁ , QZ are subjected to a quantum operation that inverts the quantum state of the qubit QZ only when A> B, and the first Toffoli operation is performed. The unit performs Toffoli calculation using the qubits QD ₁ and QD ₂ as control bits and the qubit QZ as a target bit.

Here, the qubit QZ subjected to the first quantum operation of the COMPARISON operation unit is used as a control bit for the quantum operation of the φADD operation unit and the φADD- ¹ operation unit. As a result, the number of qubits can be reduced by one compared to the conventional configuration.
According to another embodiment of the present invention, the first quantum operations COMPARISON calculating unit performs the, HIGHBIT calculation unit, qubits _{QB j-1,} ..., and QB _0, qubits _{QU j-1,} ..., and QU _1, The second quantum operation is performed on the qubit QZ, and the qubit QZ is changed to a quantum state indicating z (+) β (β is the most significant digit of A−N + B, (+) is an exclusive OR), etc. qubit _{QB j-1 of, ..., QB 0, QU j} -1, ..., the quantum state of QU ₁ quantum state before the second quantum, the 2NOT calculation unit, a NOT operation on the qubit QZ Then, the classical control NOT operation unit reads the quantum bit QB _h corresponding to h for which the digit (an) n (an) _h (hε {j−1,..., 0}) read from the memory is 1. Only the NOT operation is performed, and the third NOT operation unit Bit _{QB j-1,} ..., subjected to NOT operation on QB _0, the 2Toffoli calculation unit, each qubit _{QB j-1,} ..., a QB ₀ as a control bit, the Toffoli operation in which the qubits QZ target bit The third NOT operation unit performs a NOT operation on each of the qubits QB _j−1 ,..., QB ₀ , and the classical control NOT operation unit reads the A−N digits (an) _h read from the memory. This is an operation of performing a NOT operation only on the qubit QB _h corresponding to h which becomes 1.

In this way, the HIGHBIT operation unit is configured to perform the quantum operation on the qubits QU _j−1 ,..., QU _{1 as} well, thereby effectively using the qubits and reducing the number of necessary qubits. I am trying.

  As described above, in the present invention, it is possible to obtain a 2j-digit binary number C useful for order discovery with a high probability by using fewer qubits than in the past.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
[First embodiment]
<Functional configuration>
FIG. 1 is a block diagram illustrating the configuration of the quantum computing device 1 in this embodiment.
As illustrated in FIG. 1, the quantum computation device 1 according to the present embodiment includes a qubit 10, an input unit 20, a classical memory 30, a subtraction unit 40, a multiplication unit 50, a quantum computation control unit 60, a quantum computation unit 70, and an observation unit. 80. The quantum computation unit 70 includes an initial quantum state generation unit 71, a CV unit 72, an H (Hadamard) computation unit, an _Rk computation unit 74, and an ^XCK computation unit 75.

FIG. 2A is a diagram illustrating a detailed configuration of the CV calculation unit 72. As shown in this figure, the CV calculation unit 72 includes an M MOD calculation unit 101 and a CSWAP calculation unit 102. FIG. 2B is a diagram illustrating a detailed configuration of the M MOD calculation unit 101. As shown in this figure, the M MOD calculation unit 101 includes an ADD MOD calculation unit 111 and a SWAP calculation unit 112. FIG. 2C is a diagram illustrating a detailed configuration of the ADD MOD calculation unit 111. As shown in this figure, the ADD MOD calculation unit 111 includes a COMPARISON calculation unit 121, a QFT calculation unit 122, a QFT- ¹ calculation unit 123, a φADD calculation unit 124, a φADD- ¹ calculation unit 125, a NOT calculation unit 126, and a Toffoli calculation unit. 127. FIG. 3A is a diagram illustrating a detailed configuration of the COMPARISON calculation unit 121. As shown in this figure, the COMPARISON computing unit 121 includes a HIGHBIT computing unit 131, a NOT computing unit 132, a classical control NOT computing unit 133, and a Toffoli computing unit 134. FIG. 3B is a diagram illustrating a detailed configuration of the HIGHBIT calculation unit 131. As shown in this figure, the HIGHBIT calculation unit 131 includes a control NOT calculation unit 141, an E calculation unit 142, an F calculation unit 143, a Toffoli calculation unit 144, a NOT calculation unit 145, and an F- ¹ calculation unit 143. Unless otherwise specified, the quantum computing device 1 executes each process under the control of the quantum computation control unit 60. Details of the functional configuration of each element and details of the hardware configuration will be described later.

<Processing>
[Overall processing]
The quantum computing device 1 inputs an input j-digit binary number N = n _j−1 ... N ₀ (n _j−1 ,..., N ₀ ∈ {0, 1}) and a j-digit binary number smaller than N. For A = a _j−1 ... A ₀ (a _j−1 ,..., A ₀ ∈ {0, 1}), j of the number of calculation steps proportional to the cube of j using 2j + 2 qubits A number of basic operations proportional to the fourth power are performed, and a 2j-digit binary number C = c _2j−1 ... C ₀ (c _j−1 ,..., C ₀ ∈ {0, 1}) useful for order discovery is obtained. Output with high probability. Details of this processing will be described below.

  FIG. 4 is a flowchart for explaining the entire processing of the quantum computing device 1 of the present embodiment. FIG. 11 is a quantum circuit illustrating the entire process. Note that the quantum circuit uses a calculation for one qubit and CNOT as the basic calculation, but in order to avoid the complexity of the figure, in FIG. 11, the calculation is also expressed using calculations other than these calculations. In addition, all operations used in this quantum circuit can be decomposed into operations for one qubit and CNOT (see Non-Patent Document 3 above). FIG. 11 shows an example when j = 5. All numbers greater than N are interpreted as mod N.

As illustrated in FIG. 11, the quantum circuit according to the present embodiment receives, as input, qubits indicating 0, 1 and 2j 0s, and is a 2j-digit binary number C = c _2j−1 useful for order finding. ... c ₀ is output. This configuration corresponds to a configuration in which the qubit holding the 2j + 3rd quantum state from the top is deleted and CU (a) is replaced with CV (a) in FIG. 31 showing the conventional configuration. In the following, the entire process constituting the quantum circuit will be described.
First, a binary number j digits _{N = n j-1 ... n} 0, and binary j digits _{A = a j-1 ... a} 0 less than N is inputted from the input unit 20, a classical memory 30 (FIG. 1) (step S1). Note that j is a value preset in the apparatus, for example. Then, based on the initial quantum state generator 71 of the control quantum computation control section 60, qubit _{QD 1, QD 2, QU 1} ~QU j-1, QB 0 ~QB j-1, QZ initial quantum state of Is generated (step S2). In this example, it is assumed that the quantum state of the qubit QD ₂ indicates 1 and the quantum state of the other qubits indicates 0. Next, the H operation unit 73 applies an H (Hadamard) operation (FIG. 32A) to the qubit QD ₁ (step S3). Note that applying a quantum operation means performing a quantum operation corresponding to the operation on the qubit. Next, the quantum calculation control unit 60 assigns 0 to the variable ga and stores it in the classical memory 30. Further, the multiplication unit 50 uses A and ga read from the classical memory 30 to calculate A · 2 ^2j−ga−1 . This is calculated and sent to the quantum calculation control unit 60 (step S4). Next, the quantum calculation control unit 60 controls the CV calculation unit 72 using the sent A · 2 ^2j-ga−1 , and the CV calculation unit 72 uses the qubit QD ₁ as a control bit and the qubit QD ₂ , CU (A · 2 ^2j−ga−1 ) calculation is applied to QU _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ (step S5). Details of this calculation will be described later. Next, the H operation unit 73 applies the H operation (FIG. 32A) to the qubit QD ₁ (step S6). Next, quantum computation control unit 60 reads out the variable ga from classical memory 30, by observing the quantum state of qubit QD ₁ to the observation unit 80, and stores in the classical memory 30 the observation result c _ga (step S7). By this observation, the quantum state of the qubit QD ₁ is reduced to c _ga (and so on).

Next, quantum computation control unit 60 reads out the _{c ga} from classical memory ^30, the ^{X ck} calculation unit 75, FIG. 32 and k = ga quantum operation (b) is applied to qubits QD _1, Furthermore, the H operation unit 73 is caused to apply the H operation (FIG. 32A) on the qubit QD ₁ (step S8). Next, the quantum computation control unit 60 reads the variable ga stored in the classical memory 30, updates ga + 1 as a new ga, and stores it in the classical memory 30 (step S9). Next, the multiplication unit 50 calculates A · 2 ^2j−ga−1 using A and ga read from the classical memory 30, and sends them to the quantum calculation control unit 60. The quantum calculation control unit 60 controls the CV calculation unit 72 using the sent A · 2 ^2j-ga-1 , and the CV calculation unit 72 uses the qubit QD ₁ as a control bit and the qubits QD ₂ , QU A CV (A · 2 ^2j−ga−1 ) operation is applied to _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ (step S10). Details of this calculation will be described later. Next, the R _k computation unit 74 applies the R _k computation (FIG. 33) with k = ga to the qubit QD ₁ (step S11), and the observation unit 80 observes the quantum state of the qubit QD ₁ Then, the observation result is stored as _cga in the classical memory 30 (step S12).

Next, the quantum calculation control unit 60 determines whether or not ga stored in the classical memory 30 is 2j−1. Here, if not ga = 2j-1, the quantum calculation control unit 60 returns the process to step S8. On the other hand, if ga = 2j−1, the quantum computation control unit 60 outputs C = c _2j−1 ... C ₀ stored in the classical memory 30.
[Details of CV (A) calculation]
Next, the details of the CV calculation mentioned in steps S5 and S11 will be described. In the following, a CV (A) operation using A as a parameter will be described as an example. However, if this A is replaced with A · 2 ^2j−ga−1 , a CV (A · 2 ^2j−ga−1 ) operation will be performed. Can be generalized.

FIG. 5 is a flowchart for explaining the details of the CV (A) calculation. FIG. 12 is a quantum circuit illustrating CV (A) calculation when j = 5.
As illustrated in FIG. 12, the quantum circuit indicating the CV (A) operation includes d + 1 and U = u _j−1 ... U ₀ (u _j−1 ,..., U ₀ ε {0, 1}) and j + 1 pieces. Quantum bits QD ₁ , QD ₂ , QU _{1 to} QU _{j−1 [QUh ′ (h′∈ {0,..., J−1})} correspond _to u _{h ′ ]} , QB _{0 to} QB _j−1 and QZ are input, and if d = 1, qubits QD ₁ , QD ₂ , QU _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , QZ are set to d and A · Each digit of U mod N (A · U mod N) ₀ (A · U mod N) is a quantum state indicating _j−1 and j + 1 0 respectively, and if d = 0, the input quantum state is To maintain. This configuration corresponds to the conventional configuration of FIG. 34, in which the qubit holding the 2j + 3rd quantum state from the top is deleted and CMULT (A) MOD (N) is replaced with M (A) MOD (N). To do. The details of the CV (A) calculation will be described below.

First, under the control of quantum computation control unit 60 to read the A from classical memory 30, M MOD calculation unit 101 (FIG. 2 (a)) is, as the control bit qubit QD _1, qubit _QD 2, QU _The M (A) MOD (N) operation is applied to _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ (step S21). Details of the M (A) MOD (N) calculation will be described later. Next, the CSWAP calculation unit 102 applies the CSWAP calculation (FIG. 35) to the qubits QD ₁ , QD ₂ , QU _{1 to} QU _j−1 , QB _{0 to} Q _Bj−1 (step S 22). Next, the multiplication unit 50 (FIG. 1) calculates A ⁻¹ using A stored in the classical memory 30 (step S <b> 23) and sends it to the quantum calculation control unit 60. The quantum calculation control unit 60 controls the M MOD calculation unit 101 using this A ⁻¹ , and the M MOD calculation unit 101 uses the qubit QD ₁ as a control bit and the qubits QD ₂ , QU _{1 to} QU _{j−. The} M (A ⁻¹ ) MOD (N) operation is applied to ₁ , QB _{0 to} QB _j−1 , QZ (step S24).

[Details of M (A) MOD (N) operation]
Next, details of the M (A) MOD (N) calculation and the M (A ⁻¹ ) MOD (N) calculation mentioned in steps S21 and S24 will be described. In the following description, an M (A) MOD (N) operation using A as a parameter will be described as an example. If A is replaced with A- ¹ , an M (A- ¹ ) MOD (N) operation is obtained.
FIG. 6 is a flowchart for explaining details of the M (A) MOD (N) calculation. FIG. 13 is a quantum circuit illustrating the M (A) MOD (N) operation when j = 5.

As illustrated in FIG. 13, the quantum circuit indicating the M (A) MOD (N) operation includes d, U, and B = b _j−1 ... B ₀ (b _j−1 ,..., B ₀ ε {0, 1}) and qubits QD ₁ , QD ₂ , QU _{1 to} QU _j−1 , QB _{0 to} QB _{j−1 [QBh (h∈ {0,..., J−1}) in} quantum states respectively indicating _{0 There} corresponds to _bh] as input QZ, d = 1, then the qubit _QD 1 quantum state shown d and U and a · X + B mod N and 0 and _{respectively,} QD _2, QU 1 _{~QU j- 1} , QB _{0 to} QB _j−1 are output, and if d = 0, the input quantum state is maintained. However, A * X + B mod N = (A * X + B mod N) _j-1 ... (A * X + B mod N) ₀ and _{QBh (hε {0, ..., j-1}) is} (A * X + B mod). N) _{corresponds to h. Hereinafter,} details of _the M (A) MOD (N) operations.

First, under the control of the quantum calculation control unit 60 that reads A from the classical memory 30, the ADD MOD calculation unit 111 (FIG. 2B) uses the qubits QD ₁ and QD ₂ as control bits and the qubit QU to _{1 ~QU j-1, QB 0} ~QB j-1, QZ, ADD (2 0 · a) MOD (N) to apply an operation (step S31). ^{Incidentally, ADD (2 0 · A)} MOD (N) will be described in detail later operation. Next, the quantum calculation control unit 60 assigns 1 to the variable gb, and stores this variable gb in the classical memory 30 (step S32). Then, under the control of quantum computation control unit 60 for reading the variable gb from classical memory 30, the SWAP operation unit 112, with respect to qubits QD ₂ and qubit _{QU gb,} applying the SWAP operation (step S33) . The SWAP calculation means a calculation combining three control NOT calculations as shown in FIG. Here, x, yε {0, 1}. By this SWAP operation, the quantum states of the two input qubits are switched.

Next, the multiplication unit 50 reads A and the variable gb from the classical memory 30, calculates 2 ^gb · A, and sends it to the quantum calculation control unit 60 (step S34). The quantum calculation control unit 60 controls the ADD MOD calculation unit 111 using 2 ^gb · A, and the ADD MOD calculation unit 111 uses the qubits QD ₁ and QD ₂ as control bits and qubits QU _{1 to} QU _j−. ADD (2 ^gb · A) MOD (N) operation is applied to ₁ , QB _{0 to} QB _j−1 , QZ (step S35). Then, under the control of quantum computation control unit 60 for reading the variable gb from classical memory 30, the SWAP operation unit 112, with respect to qubits QD ₂ and qubit _{QU gb,} applying the SWAP operation (step S36) . Thereafter, the quantum computation control unit 60 determines whether or not the variable gb stored in the classical memory 30 is j−1 (step S37). Here, if not gb = j−1, the quantum calculation control unit 60 stores gb + 1 as a new variable gb in the classical memory 30, returns the process to step S33, and if gb = j−1, (A) The MOD (N) operation is terminated.

[Details of ADD (A) MOD (N) calculation]
Next, details of the ADD (A) MOD (N) calculation and ADD (2 ^gb · A) MOD (N) calculation mentioned in steps S31 and S35 will be described. In the following description, the the ADD (A) MOD (N) calculates the A parameter as an example, if substituted the A to ^{2 gb · A ADD (2 gb} · A) MOD (N) and calculating Become.
FIG. 7 is a flowchart for explaining the details of the ADD (A) MOD (N) calculation. FIG. 15 is a quantum circuit illustrating an ADD (A) MOD (N) operation when j = 5.

As illustrated in FIG. 15, the quantum circuit indicating the ADD (A) MOD (N) operation includes d ₁ , d ₂ ε {0, 1} and u ₁ ,..., U _j−1 ε {0, 1}. Quantum bits QD ₁ , QD ₂ , QU _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ in the quantum state respectively indicating B, 0, and 0, and d ₁ = d ₂ = 1 , _d 1, _{d 2} and _{u 1, ..., u j-} 1 and a + B mod N and qubit _QD 1 quantum state shown 0 and _{respectively, QD 2, QU 1 ~QU j} -1, QB 0 ~QB j ₋₁ and QZ are output, and unless d ₁ = d ₂ = 1, the input quantum state is maintained. However, A + B mod N = (A + B mod N) _j−1 (A + B mod N) ₀ , and _{QBh (hε {0,..., J−1}) corresponds to} (A + B mod N) _{h. Hereinafter,} details of _the ADD (A) MOD (N) operations.

First, the subtraction unit 40 calculates N−A from A and N read from the classical memory 30, and sends this to the quantum calculation control unit 60 (step S41). Under the control of the quantum calculation control unit 60 using the NA, the COMPARISON calculation unit 121 (FIG. 2C) uses the qubits QD ₁ and QD ₂ as control bits and the qubits QD ₁ and QD ₂ The COMPARISON (NA) operation is applied to the qubits QU _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ only when the quantum states indicated by are respectively 1 (step S42). . Although details will be described later, this COMPARISON (NA) operation inverts the quantum state of the qubit QZ only when N-A> B (1 when 0 and 0 when 1). This is an operation to be performed. Next, the QFT calculation unit 122 applies a QFT (quantum Fourier transform) calculation (FIG. 39) to the quantum bits QB _{0 to} QB _j−1 (step S43).

Next, under the control of the quantum calculation control unit 60 that reads A from the classical memory 30, the φADD calculation unit 124 uses the qubits QD ₁ , QD ₂ , and QZ as control bits, and the qubits QD ₁ , QD ₂ , Only when the quantum states indicated by QZ are all 1, the φADD (A) operation is applied to the qubits QB _{0 to} QB _j−1 (step S44). Note that the φADD (A) calculation is as shown in FIGS. That is, in step S44, only when the quantum bits QD ₁ , QD ₂ , and QZ are control bits and the quantum states indicated by the quantum bits QD ₁ , QD ₂ , and QZ are all 1, the φADD operation unit 124 sets the 1 Only for quantum bits QB _k (k∈ {j−1,..., 0}) in the quantum state indicating

（ただし、量子ビットＱＢ_ｋの量子状態を｜ＱＢ_ｋ〉とし、ｅをネピア数とし、ｉを虚数単位とする）の演算を施す。
次に、ＮＯＴ演算部１２６が、量子ビットＱＺに対してＮＯＴ演算を適用し（ステップＳ４５）、φＡＤＤ^−１演算部１２５が、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとして、量子ビットＱＤ_１，ＱＤ_２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、φＡＤＤ（Ｎ−Ａ）^−１演算を適用する（ステップＳ４６）。なお、φＡＤＤ（Ｎ−Ａ）^−１演算とはφＡＤＤ（Ｎ−Ａ）演算の逆演算を意味する。すなわち、ステップＳ４６では、量子ビットＱＤ_１，ＱＤ_２，ＱＺを制御ビットとし、量子ビットＱＤ_１，ＱＤ_２，ＱＺがそれぞれ示す量子状態が全て１である場合にのみ、φＡＤＤ^−１演算部１２５が、１を示す量子状態の量子ビットＱＢ_ｋのみに対し、

(However, the quantum state of the qubit QB _k is set to | QB _k >, e is a Napier number, and i is an imaginary unit).
Next, the NOT operation unit 126 applies a NOT operation to the qubit QZ (step S45), and the φADD ⁻¹ operation unit 125 uses the qubits QD ₁ , QD ₂ , and QZ as control bits, and the qubit QD Only when the quantum states indicated by ₁ , QD ₂ , and QZ are all 1, φADD (NA) ⁻¹ operation is applied to the qubits QB _{0 to} QB _j−1 (step S 46). Note that the φADD (NA) ^-1 operation means the inverse operation of the φADD (NA) operation. That is, in step S46, only when the quantum bits QD ₁ , QD ₂ , and QZ are control bits and the quantum states indicated by the quantum bits QD ₁ , QD ₂ , and QZ are all 1, the φADD ⁻¹ calculation unit 125 is Only for qubits QB _{k in the} quantum state indicating 1,

（ただし、Ｎ−Ａ＝（ｎ−ａ）_ｊ−１…（ｎ−ａ）_０とする）の演算を施す。
次に、ＮＯＴ演算部１２６が、量子ビットＱＺに対してＮＯＴ演算を適用し（ステップＳ４７）、ＱＦＴ^−１演算部１２３が、量子ビットＱＢ_０〜ＱＢ_ｊ−１に対し、ＱＦＴ演算の逆演算であるＱＦＴ^−１演算を適用する（ステップＳ４８）。次に、古典メモリ３０からＡを読み込んだ量子計算制御部６０の制御のもと、ＣＯＭＰＡＲＩＳＯＮ演算部１２１が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとして、量子ビットＱＤ_１，ＱＤ_２がそれぞれ示す量子状態がともに１である場合にのみ、量子ビットＱＵ_１〜ＱＵ_ｊ−１，ＱＢ_０〜ＱＢ_ｊ−１，ＱＺに対し、ＣＯＭＰＡＲＩＳＯＮ（Ａ）演算を適用する（ステップＳ４９）。なお、ＣＯＭＰＡＲＩＳＯＮ（Ａ）の詳細については後述する。そして、Ｔｏｆｆｏｌｉ演算部１２７が、量子ビットＱＤ_１，ＱＤ_２を制御ビットとし、量子ビットＱＺを目標ビットとしたＴｏｆｆｏｌｉ演算を適用する（ステップＳ５０）。

(However, N−A = (na) _j−1 (n−a) ₀ ) is performed.
Next, NOT operation unit 126 applies a NOT operation on qubits QZ (step S47), ^{QFT -1} calculation section 123, to qubit _QB 0 _{~QB j-1,} the inverse operation of QFT operation QFT ⁻¹ calculation is applied (step S48). Next, under the control of the quantum calculation control unit 60 that reads A from the classical memory 30, the COMPARISON calculation unit 121 uses the qubits QD ₁ and QD ₂ as control bits, and the qubits QD ₁ and QD ₂ respectively indicate Only when the quantum states are both 1, the COMPARISON (A) operation is applied to the qubits QU _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ (step S49). Details of COMPARISON (A) will be described later. Then, the Toffoli calculation unit 127 applies the Toffoli calculation using the qubits QD ₁ and QD ₂ as control bits and the qubit QZ as a target bit (step S50).

[Details of COMPARISON (A) calculation]
Next, details of the COMPARISON (NA) calculation and the COMPARISON (A) calculation mentioned in steps S42 and S49 will be described. In the following description, the COMPARISON (A) operation using A as a parameter will be described as an example. However, if this A is replaced with NA, the COMPARISON (NA) operation is performed.
FIG. 8 is a flowchart for explaining details of the COMPARISON (A) calculation. FIG. 16 is a quantum circuit illustrating the COMPARISON (A) operation when j = 5.

As illustrated in FIG. 16, the quantum circuit indicating the COMPARISON (A) operation includes B = b _j−1 ... B ₀ and u ₁ ,..., U _j−1 and z indicating quantum bits QB _{0 to} QB, respectively. _j-1, QU ₁ to _{~QU j-1, QZ, B} = b j-1 ... b 0 and _{u 1, ..., u j-} 1 and the quantum bit _QB 0 of quantum states respectively _{～QB j- 1,} and _{QU 1 ~QU j-1,} and outputs a qubit QZ quantum state indicating the z (+) α. Note that (+) indicates exclusive OR (value obtained by sum mod 2). Α is a value that α = 1 when A> B and α = 0 when A ≦ B. That is, the COMPARISON (A) operation is an operation that inverts the quantum state of the qubit QZ only when A> B. Details of the COMPARISON (A) calculation will be described below.

First, under the control of the quantum calculation control unit 60 that has read A from the classical memory 30, the HIBIT operation unit 131 (FIG. 3A) performs quantum bits QU _{1 to} QU _j-1 and QB _{0 to} QB _{j−. 1} , HIGHBIT (A) calculation is applied to QZ (step S51). Details of the HIGHBIT (A) calculation will be described later. Next, the NOT operation unit 132 applies a NOT operation to the qubit QZ (step S52). Next, under the control of the quantum computation control unit 60 that has read A from the classical memory 30, the classical control NOT computation unit 133 determines that the digit a _h (h∈ {j−1,..., 0}) of A is 1. The NOT operation is applied only to the qubit QB _h corresponding to _h (step S53). In each figure, an operator such as a NOT operation is enclosed in a square, and a symbol is added to the upper part thereof, and an operator that executes an operation enclosed in the square only when the value of this code is 1. Means.

Thereafter, the NOT operation unit 132 applies a NOT operation to the qubits QB _{0 to} QB _j−1 (step S54), and the Toffoli operation unit 134 uses the qubits QB _{0 to} QB _j−1 as control bits. A Toffoli operation using the qubit QZ as a target bit is applied (step S55). FIG. 17 shows Toffoli calculation when j = 5. Thereafter, the NOT operation unit 132 applies a NOT operation to the qubits QB _{0 to} QB _j−1 (step S56). Then, the classical control NOT operation unit 133 applies the NOT operation only to the qubit QB _h corresponding to h in which the digit a _h (hε {j−1,..., 0}) of A becomes 1. (Step S57) ).

[Details of HIGHBIT (A) calculation]
Next, details of the HIGHBIT (A) calculation mentioned in step S51 will be described.
9 and 10 are flowcharts for explaining the details of the HIGHBIT (A) calculation. FIG. 18 is a quantum circuit illustrating the HIGHBIT (A) operation when j = 5.
As illustrated in FIG. 18, the quantum circuit indicating the HIGHBIT (A) operation includes quantum bits QB _{0 to} QB indicating B = b _j−1 ... B ₀ and u ₁ ,..., U _j−1 and z, respectively. _j-1, QU ₁ to _{~QU j-1, QZ, B} = b j-1 ... b 0 and _{u 1, ..., u j-} 1 and the quantum bit _QB 0 of quantum states respectively _{～QB j- 1,} and _{QU 1 ~QU j-1,} and outputs a qubit QZ quantum state indicating the z (+) β. Β means the value of the most significant bit of A + B. Details of the HIGHBIT (A) calculation will be described below.

First, the control NOT operation unit 141 (FIG. 3B) applies CNOT operation using the qubit QU _j−1 as a control bit and the qubit QZ as a target bit (step S61). Next, the quantum computation control unit 60 substitutes j−1 for the variable gc and stores it in the classical memory 30 (step S62).
Next, under the control of the quantum computation control unit 60 that reads A and the variable gc from the classical memory 30, the E operation unit 142 applies E (a to the quantum bits QU _gc , QU _gc−1 , and QB _{gc. gc} ) An operation is applied (step S63).

FIG. 19 is a quantum circuit showing this E (a _gc ) operation. As shown in FIG. 19, the E (a _gc ) operation receives three quantum bits QU _gc−1 , QB _gc , and QU _gc in quantum states respectively indicating p, r, and s∈ {0, 1}. . Then, the E operation unit 142 first applies a NOT operation to the qubit QB _gc only when a _gc = 1. Next, the E operation unit 142 applies Toffoli operation using the qubits QU _gc-1 and QB _gc as control bits and the qubit QU _gc as a target bit, and further, only when a _gc = 1 Apply NOT operation to QB _gc . By these operations, the quantum states of the three qubits QU _gc−1 , QB _gc , and QU _gc indicate p, r, s (+) (a _gc (+) r) · p, respectively. The above is the E (a _gc ) calculation.

Next, the quantum computation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is 2 (step S64). If gc = 2 is not satisfied, the quantum computation control unit 60 stores gc-1 as a new gc in the classical memory 30 (step S65), and then returns the process to step S63. On the other hand, if gc = 2, the quantum calculation control unit 60 reads the element a ₁ of A from the classical memory, and only when a ₁ = 1, the control bit calculation unit 141 sets the quantum bit QB ₁ to the control bit. And a control NOT operation using the qubit QU ₁ as a target bit is applied, and a NOT operation on the qubit QB ₁ is applied to the NOT operation unit 145 (step S66). Next, the quantum calculation control unit 60 reads the element a ₀ of A from the classical memory, and only when a ₀ = 1, the Toffoli calculation unit 144 uses the quantum bits QB ₀ and QB ₁ as control bits, and the quantum bits A Toffoli calculation using QU ₁ as a target bit is applied (step S67).

Next, under the control of the quantum calculation control unit 60 that has read the variable gc and the element a _{gc of the} A from the classical memory 30, the F operation unit 143 applies the qubits QU _gc , QU _gc-1 , QB _gc , F (a _gc ) calculation is applied (step S68).
FIG. 20 is a quantum circuit showing this F (a _gc ) operation. As shown in FIG. 20, the F (a _gc ) operation receives three quantum bits QU _gc−1 , QB _gc , and QU _gc in the quantum state respectively indicating p, r, and sε {0, 1}. . The F operation unit 143 first applies a control NOT operation using the qubit QB _gc as a control bit and the qubit QU _gc as a target bit only when a _gc = 1, and further applies NOT to the qubit QU _gc . Apply the operation. Next, the F operation unit 143 applies Toffoli operation using the qubits QU _gc-1 and QB _gc as control bits and the qubit QU _gc as a target bit. By these operations, the quantum states of the three qubits QU _gc−1 , QB _gc , and QU _gc are changed to p, a _gc (+) r, s (+) p · a _gc (+) a _gc · r ( +) R · p. The above is the F (a _gc ) calculation.

Next, the quantum computation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is j−1 (step S69). If not gc = j−1, the quantum computation control unit 60 stores gc + 1 as a new gc in the classical memory 30 (step S70), and then returns the process to step S68. On the other hand, if gc = j−1, the control NOT operation unit 141 applies the CNOT operation using the qubit QU _j−1 as the control bit and the qubit QZ as the target bit (step S71). Next, under the control of the quantum calculation control unit 60 that has read the variable gc and the element a _{gc of the} A from the classical memory 30, the F operation unit 143 applies the qubits QU _gc , QU _gc-1 , QB _gc , F (a _gc ) ⁻¹ operation that is the inverse operation of F (a _gc ) operation is applied (step S72).

Next, the quantum calculation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is 2 (step S73). If gc = 2 is not satisfied, the quantum computation control unit 60 stores gc-1 as a new gc in the classical memory 30 (step S74), and then returns the process to step S72. On the other hand, if gc = 2, the quantum calculation control unit 60 reads the element a ₀ of A from the classical memory, and sets the quantum bits QB ₀ and QB ₁ to the Toffoli calculation unit 144 only when a ₀ = 1. A Toffoli operation is applied using the control bit and the qubit QU ₁ as the target bit (step S75).

Next, the quantum calculation control unit 60 reads the element a ₁ of A from the classical memory, and applies the NOT operation to the qubit QB ₁ to the NOT operation unit 145 only when a ₁ = 1, and performs control NOT. The control unit 141 is caused to apply a control NOT operation using the qubit QB ₁ as a control bit and the qubit QU ₁ as a target bit (step S76).
Next, under the control of the quantum computation control unit 60 that reads A and the variable gc from the classical memory 30, the E operation unit 142 applies E (a to the quantum bits QU _gc , QU _gc−1 , and QB _{gc. gc} ) An operation is applied (step S77). Next, the quantum computation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is j−1 (step S78). If not gc = j−1, the quantum computation control unit 60 stores gc + 1 as a new gc in the classical memory 30 (step S79), and then returns the process to step S77. On the other hand, if gc = j−1, the HIGHBIT (A) operation is terminated.

[Second Embodiment]
This embodiment is a modification of the first embodiment. In the first embodiment, although not address _{A = a j-1 ... a} 0 as a classical information, in the second embodiment deals with _{A = a j-1 ... a} 0 as quantum information. In the following description, differences from the first embodiment will be mainly described, and description of matters common to the first embodiment will be omitted.
<Configuration>
FIG. 21 is a block diagram illustrating a functional configuration of the quantum computing device 200 in this embodiment.

The difference in configuration between the quantum computing device 1 of the first embodiment and the quantum computing device 200 of the second embodiment is that A = a _j− that has been _treated as classical information in the first embodiment. ₁ ... _a each digit _a 0 _{0, ...,} the point of using the qubit 210 added qubit _QA 0, a ... _{QA j-1} to qubit 10, the quantum state indicating the value of _{a j-1,} quantum computing The initial quantum state generation unit 271 and the CV calculation unit 272 of the unit 270 perform each process using the quantum information of the qubits QA ₀ ,... QA _j−1 .
FIG. 22A is a diagram illustrating a detailed configuration of the COMPARISON calculation unit 321 included in the CV calculation unit 272 of the present embodiment. As shown in this figure, the COMPARISON computing unit 321 includes a HIGHBIT computing unit 331, a NOT computing unit 332, a control NOT computing unit 333, and a Toffoli computing unit 334. FIG. 22B is a diagram illustrating a detailed configuration of the HIGHBIT calculation unit 331. As shown in this figure, the HIGHBIT computing unit 331 includes a control NOT computing unit 341, an E computing unit 342, an F computing unit 343, a Toffoli computing unit 344, a NOT computing unit 345, and an F- ¹ computing unit 343. The other detailed configuration is the same as that of the first embodiment, and a description thereof will be omitted.

<Processing>
Below, it demonstrates centering on difference with 1st Embodiment.
[Initial quantum state generation]
In the first embodiment, the initial quantum state generation unit 71 generates the initial quantum states of the qubits QD ₁ , QD ₂ , QU _{1 to} QU _j−1 , QB _{0 to} QB _j−1 , and QZ. (Step S2), the initial quantum state generation unit 271 (FIG. 21) of this embodiment also generates initial quantum states of QA _{0 to} QA _j−1 . Specifically, under the control of quantum computation control unit 60 to read the _{A = a j-1 ... a} 0 from classical memory 30, the initial quantum state generator 271, qubit _QA 0, ... _{QA j-1} of quantum states, respectively _{a = a j-1} ... _a each digit _a 0 _{0, ...,} a quantum state indicating the value of _{a j-1.}

[CV calculation]
In the first embodiment, CV operation is performed using A = a _j−1 ... A ₀ as classical information. However, in this embodiment, quantum bits QA ₀ ,... QA _j−1 are used, and A = a _{j −1} ... CV calculation is performed using a ₀ as quantum information. Only the COMPARISON operation and the HIGHBIT operation will be described below. Other operations are the same as those in the first embodiment except that the results of the COMPARISON operation and the HIGHBIT operation using the qubits QA ₀ ,... QA _j−1 are used.

[Details of COMPARISON calculation]
FIG. 23 is a flowchart for explaining details of the COMPARISON calculation of the present embodiment. FIG. 26 is a quantum circuit illustrating the COMPARISON operation of this embodiment when j = 5.
As illustrated in FIG. 26, a quantum circuit showing a COMPARISON operation of this _{embodiment, A = a j-1 ...} a 0 and _{B = b j-1 ... b} 0 and _{u 1, ..., u j-} 1 and z For qubits QA _{0 to} QA _j−1 , QB _{0 to} QB _j−1 , QU _{1 to} QU _j−1 , QZ respectively indicating A = a _j−1 ... A ₀ and B = b _j−1 ... B ₀ and u ₁ ,..., U _j−1 representing quantum states QA _{0 to} QA _j−1 , QB _{0 to} QB _j−1 , QU _{1 to} QU _j−1 , and z (+ ) A quantum state quantum bit QZ indicating α is output. Α is a value that α = 1 when A> B and α = 0 when A ≦ B. That is, the COMPARISON operation is an operation that inverts the quantum state of the qubit QZ only when A> B. Details of this COMPARISON calculation will be described below.

First, the NOT operation unit 332 (FIG. 22A) applies a NOT operation to the qubits QA _{0 to} QA _j−1 (step S101). Next, under the control of the quantum calculation control unit 60 that reads A from the classical memory 30, the HIBIT operation unit 331 performs quantum bits QU _{1 to} QU _j−1 , QA _{0 to} QA _j−1 , QB _{0 to} QB. _A HIGHBIT operation is applied to _j−1 and QZ (step S102). Details of the HIGHBIT calculation will be described later. Next, the NOT operation unit 332 applies a NOT operation to the qubits QA _{0 to} QA _j−1 , QZ (step S103). Next, under the control of the quantum calculation control unit 60, the control NOT operation unit 333 performs control using the qubits QA _{0 to} QA _j-1 as control bits and the qubits QB _{0 to} QB _j-1 as target bits. A NOT operation is applied (step S104). Thereafter, the NOT operation unit 332 applies NOT operation to the qubits QB _{0 to} QB _j−1 (step S105), the Toffoli operation unit 334 uses the qubits QB _{0 to} QB _j−1 as control bits, A Toffoli operation using the qubit QZ as a target bit is applied (step S106). Thereafter, the NOT operation unit 332 applies a NOT operation to the qubits QB _{0 to} QB _j−1 (step S107). Then, under the control of the quantum calculation control unit 60, the control NOT operation unit 333 uses the control bits with the qubits QA _{0 to} QA _j-1 as control bits and the qubits QB _{0 to} QB _j-1 as target bits. The calculation is applied (step S108).

[Details of HIGHBIT calculation]
Next, details of the HIGHBIT calculation mentioned in step S102 will be described.
24 and 25 are flowcharts for explaining the details of the HIGHBIT calculation. FIG. 27 is a quantum circuit illustrating this HIGHBIT operation when j = 5.
As illustrated in FIG. 27, a quantum circuit showing a HIGHBIT _{operation, A = a j-1 ...} a 0 and _{B = b j-1 ... b} 0 and _u 1, _..., a _{u j-1} and z respectively to qubit _{QB 0 ~QB j-1, QU} 1 ~QU j-1, QZ _{shown, B = b j-1 ...} b 0 and _u 1, _..., quantum quantum state shown _{u j-1} and the respective Bits QA _{0 to} QA _j−1 , QB _{0 to} QB _j−1 , QU _{1 to} QU _j−1 and a quantum bit QZ in a quantum state indicating z (+) β are output. Β means the value of the most significant bit of A + B. Details of the HIGHBIT calculation will be described below.

First, the control NOT operation unit 341 (FIG. 22B) applies a CNOT operation using the qubit QU _j−1 as a control bit and the qubit QZ as a target bit (step S111). Next, the quantum computation control unit 60 substitutes j−1 for the variable gc and stores it in the classical memory 30 (step S112).
Next, under the control of the quantum calculation control unit 60 that has read the variable gc from the classical memory 30, the E calculation unit 142 performs E calculation on the qubits QU _gc , QU _gc−1 , QA _gc , and QB _gc. Apply (step S113).

FIG. 28 is a quantum circuit showing this E operation. As shown in FIG. 28, E (calculation is input with four quantum bits QU _gc−1 , QA _gc , QB _gc , and QU _gc in the quantum state respectively indicating p, q, r, and s∈ {0, 1}. Then, the E operation unit 142 first applies a control NOT operation using the qubit QA _gc as the control bit and the qubit QB _gc as the target bit. Apply Toffoli operation with _gc-1 and QB _gc as control bits and qubit QU _gc as target bit, and further perform control NOT operation with qubit QA _gc as control bit and qubit QB _gc as target bit apply. these operations, four qubits _{QU gc-1, QA gc,} QB gc, quantum state of _{QU gc} is, p respectively, q, r, s (+ ) (q +) R) · p is as shown a. Above is the E operation.

Next, the quantum calculation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is 2 (step S114). If gc = 2 is not satisfied, the quantum computation control unit 60 stores gc-1 as a new gc in the classical memory 30 (step S115), and then returns the process to step S113. On the other hand, if gc = 2, under the control of the quantum calculation control unit 60, the Toffoli calculation unit 344 performs Toffoli calculation with the qubits QA ₁ and QB ₁ as control bits and the qubit QU ₁ as a target bit. Apply (step S116). Next, the control NOT calculation unit 341
A control NOT operation using the qubit QA ₁ as a control bit and the qubit QB ₁ as a target bit is applied (step S117). Further, the Toffoli calculation unit 344 applies the Toffoli calculation using the qubits QA ₀ , QB ₀ , and QB ₁ as control bits and the qubit QU ₁ as a target bit (step S118). FIG. 30 is a quantum circuit showing such a Toffoli operation. FIG. 30 shows an example in which qubits QA ₀ , QB ₀ , QB ₁ , and QU ₁ whose respective quantum states are p, q, r, and s are input.

Next, the F operation unit 343 applies the F operation to the qubits QU _gc , QU _gc−1 , QA _gc , and QB _gc (step S119).
FIG. 29 is a quantum circuit showing this F operation. As shown in FIG. 29, the F operation inputs four quantum bits QU _gc−1 , QA _gc , QB _gc , and QU _gc in the quantum state respectively indicating p, q, r, and s∈ {0, 1}. To do. Then, the F operation unit 343 first applies Toffoli operation using the qubits QA _gc and QB _gc as control bits, the qubit QU _gc as a target bit, further using QA _gc as a control bit, and using the qubit QB _gc as a control bit. A control NOT operation using the target bit is applied. Next, the E operation unit 142 applies Toffoli operation using the qubits QU _gc-1 and QB _gc as control bits and the qubit QU _gc as a target bit. By these operations, the quantum states of the four qubits QU _gc−1 , QA _gc , QB _gc , and QU _gc become p, q, q (+) r, s (+) p · q (+) q · r (+) r · p is indicated. The above is the F operation.

Next, the quantum calculation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is j−1 (step S120). If gc = j−1 is not satisfied, the quantum computation control unit 60 stores gc + 1 as a new gc in the classical memory 30 (step S121), and then returns the process to step S119. On the other hand, if gc = j−1, the control NOT operation unit 141 applies the CNOT operation using the qubit QU _j−1 as the control bit and the qubit QZ as the target bit (step S122).
Next, under the control of the quantum calculation control unit 60 that reads the variable gc and the element a _{gc of} A from the classical memory 30, the F ⁻¹ calculation unit 346 performs the quantum bits QU _gc , QU _gc−1 , QA _gc. , QB _gc , an F ⁻¹ operation that is an inverse operation of the F operation is applied (step S123).

Next, the quantum computation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is 2 (step S124). Here, if not gc = 2, the quantum computation control unit 60 stores gc-1 as a new gc in the classical memory 30 (step S125), and then returns the process to step S123. On the other hand, if gc = 2, the Toffoli calculation unit 344 applies the Toffoli calculation using the qubits QA ₀ , QB ₀ , and QB ₁ as control bits and the qubit QU ₁ as a target bit (step S126). Next, the control NOT calculation unit 341
A control NOT operation using the qubit QA ₁ as a control bit and the qubit QB ₁ as a target bit is applied (step S127). further,
The Toffoli calculation unit 344 applies the Toffoli calculation using the qubits QA ₁ and QB ₁ as control bits and the qubit QU ₁ as a target bit (step S128).

Next, under the control of the quantum calculation control unit 60 that has read the variable gc from the classical memory 30, the E calculation unit 142 performs E calculation on the qubits QU _gc , QU _gc−1 , QA _gc , and QB _gc. Apply (step S129). Next, the quantum computation control unit 60 determines whether or not the variable gc stored in the classical memory 30 is j−1 (step S130). If not gc = j−1, the quantum computation control unit 60 stores gc + 1 as a new gc in the classical memory 30 (step S131), and then returns the process to step S129. On the other hand, if gc = j−1, the HIGHBIT operation is terminated.

[Hardware configuration]
Next, the hardware configuration of the quantum computing devices 1,200 according to each embodiment is illustrated.
The quantum arithmetic device 1 of this embodiment can be realized by a combination of a quantum computer and a classical computer, or a single quantum computer. As physical systems realized by quantum computers, for example, methods using ion traps (JI Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74; 4091, 1995), photon polarization and optical path as qubits, etc. (Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988), a method using each spin in a liquid (Gershenfield, Chuang , Bulk spin resonance quantum computation, Science, 275; 350, 1997), a method using nuclear spins in silicon crystals (BE Kane, A silicon-based nuclear spin quantum computer, Nature 393, 133, 1998), in quantum dots Method using electron spin (D. Loss and DP DiVincenzo, Quantum computation with quantum dots, Physical Review A 57, 120-126, 1998), method using superconducting element (Y. Nakamura, Yu. A. Pashkin and JS Tsai , Coherent control of macroscopic quantum states in a single-cooper pair box, Nature 393, 786-788, 1999). For details on how to implement quantum computers for each physical system, see `` http://www.ipa.go.jp/security/fy11/report/contents/crypto/crypto/report/QuantumComputers/contents/doc/qc_survey. pdf "and" MA Nielsen and IL Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Chapter 7 Physical Realization ".

Hereinafter, a specific hardware configuration for realizing the quantum arithmetic device 1 will be exemplified.
<Quantum bit>
In an ion trap quantum computer, for example, a quantum bit is realized by utilizing the ground state and excited state of ions. When nuclear spins are used as qubits, for example, “TD Ladd, et al.,“ All-Silicon quantum computer, ”Phys. Rev. Lett., Vol. 89, no. 1, 017901-1‐ [017901-4, July 1, 2002.], each qubit is generated on a Si (111) substrate or the like. The initial quantum state of the qubit may be, for example, one obtained by an operation by a quantum circuit for other operations, or the substrate on which each qubit is generated is cooled to the order of mK (millikelvin) or less. Then, after aligning the spin direction, a predetermined electromagnetic wave pulse may be applied and generated. When the polarization of a photon is used as a qubit, for example, parametric down conversion (PDC) (for example, “PG Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, AV Sergienko, and Y Shih, “New high-intensity source of polarization-entangled photon pairs,” Phys. Rev. Lett., 75: 4337-4341, 1995. “PG Kwiat, E. Waks, AG White, I. Appelbaum, and PH Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A, 60: R773-R776, 1999.) etc.). In this case, as the initial quantum state of each qubit, for example, the one obtained by an operation by a quantum circuit of another operation is used. In addition, the above-mentioned initial quantum state is generated by performing operations such as Walsh Hadamard transform, CNOT, and rotation realized by a beam splitter, a polarization rotation element, etc. on a single photon generated by parametric down conversion and the like. Also good.

In addition, it is good also as preparing a quantum bit by the method described in said literature.
In addition, when it is necessary to preserve the quantum state of the qubit before and after the operation, for example, the amount of electrons in the quantum dot, the nuclear spin, or the charge (Cooper pair) in the superconductor is quantized. Quantum memories that store data using bits may be used (A. Barenco, D. Deutsch, and A. Ekert, Phys. Rev. Lett. 74, 4083 (1995), Hideaki Matsueda, Journal of the Institute of Electronics, Information and Communication Engineers) A Vol.J81-A No.12 (1998) 1978, THOosterkamp et.al., Nature 395,873 (1998), D. Loss and DP DiVincenzo, Phys. Rev. A57 (1998) 120. T. Oshima, quant-ph / 0002004, http://arxiv.org/abs/quant-ph/0002004, BEKane, A silicon-based nuclear spin quantum computer, Nature, 393, 133 (1998),
1127708374343_6
Y. Nakamura, Yu. A. Pashkin and JSTsai, Nature 398 (1999) 768).

<CNOT operation>
In the ion trap quantum computer, for example, ions are arranged on a straight line, and CNOT calculation is realized by laser beam irradiation aiming at each ion. In addition, when using photon polarization as a qubit, for example, a polarization beam splitter or the like is used, and TB Pittman, MJ Fitch, BC Jacobs, JD Franson: “Experimental Controlled-NOT Logic Gate for Single Photons in the Coincidence Basis , “Quant-ph / 0303095, http://arxiv.org/abs/quant-ph/0303095”, the CNOT operation is realized by the Pittman et al. Method. When nuclear spin is used as a qubit, for example, a CNOT operation can be realized by applying a predetermined electromagnetic wave pulse to the qubit.

In addition, you may implement | achieve CNOT calculation by the method described in said literature.
<Single qubit operation>
In the ion trap quantum computer, for example, ions are arranged on a straight line, and the operation of a single qubit is realized by laser beam irradiation aimed at each ion. When nuclear spins are used as qubits, each processing is realized by electromagnetic pulse or laser beam irradiation. Moreover, when using the polarization of a photon as a qubit, it implement | achieves by a polarization rotation element etc., for example.

<Quantum calculation control unit 60 / classical memory 30>
The quantum calculation control unit 60 may be realized, for example, by causing a known computer to execute a predetermined program, or may be realized by the above-described quantum computer. The classical memory 30 is a readable / writable semiconductor memory such as DRAM, SRAM, flash memory, or NV (Nonvolatile) RAM. Further, the above-described quantum memory may be used instead of the classical memory 30.
Needless to say, the present invention is not limited to the above-described embodiment, and can be appropriately changed without departing from the spirit of the present invention. In addition, the various processes described above are not only executed in time series according to the description, but may be executed in parallel or individually according to the processing capability of the apparatus that executes the processes or as necessary.

  As a field of use of the present invention, for example, an encryption-type safety evaluation apparatus and the like that bases safety on the difficulty of factorization such as RSA can be exemplified.

FIG. 1 is a block diagram illustrating the configuration of the quantum computing device according to the first embodiment. FIG. 2A is a diagram illustrating a detailed configuration of the CV calculation unit according to the first embodiment. FIG. 2B is a diagram illustrating a detailed configuration of the M MOD calculation unit. FIG. 2C is a diagram illustrating a detailed configuration of the ADD MOD calculation unit. FIG. 3A is a diagram illustrating a detailed configuration of the COMPARISON calculation unit according to the first embodiment. FIG. 3B is a diagram illustrating a detailed configuration of the HIGHBIT calculation unit. FIG. 4 is a flowchart for explaining the entire processing of the quantum computing device according to the first embodiment. FIG. 5 is a flowchart for explaining details of the CV (A) calculation. FIG. 6 is a flowchart for explaining details of the M (A) MOD (N) calculation. FIG. 7 is a flowchart for explaining the details of the ADD (A) MOD (N) calculation. FIG. 8 is a flowchart for explaining the details of the COMPARISON (A) operation. FIG. 9 is a flowchart for explaining the details of the HIGHBIT (A) calculation. FIG. 10 is a flowchart for explaining the details of the HIGHBIT (A) calculation. FIG. 11 is a quantum circuit illustrating the entire processing of the quantum computing device according to the first embodiment. FIG. 12 is a quantum circuit illustrating CV (A) calculation when j = 5. FIG. 13 is a quantum circuit illustrating the M (A) MOD (N) operation when j = 5. FIG. 14 is a quantum circuit showing the SWAP operation. FIG. 15 is a quantum circuit illustrating an ADD (A) MOD (N) operation when j = 5. FIG. 16 is a quantum circuit illustrating the COMPARISON (A) operation when j = 5. FIG. 17 is a quantum circuit showing the Toffoli calculation when j = 5. FIG. 18 is a quantum circuit illustrating the HIGHBIT (A) operation when j = 5. FIG. 19 is a quantum circuit showing the E (a _gc ) operation. FIG. 20 is a quantum circuit illustrating the F (a _gc ) operation. FIG. 21 is a block diagram illustrating a functional configuration of the quantum computing device according to the second embodiment. FIG. 22A is a diagram illustrating a detailed configuration of a COMPARISON calculation unit included in the CV calculation unit according to the second embodiment. FIG. 22B is a diagram illustrating a detailed configuration of the HIGHBIT calculation unit. FIG. 23 is a flowchart for explaining details of the COMPARISON calculation according to the second embodiment. FIG. 24 is a flowchart for explaining the details of the HIGHBIT calculation. FIG. 25 is a flowchart for explaining the details of the HIGHBIT calculation. FIG. 26 is a quantum circuit illustrating the COMPARISON operation of the second embodiment when j = 5. FIG. 27 is a quantum circuit illustrating the HIGHBIT operation of the second embodiment when j = 5. FIG. 28 is a quantum circuit showing the E operation. FIG. 29 is a quantum circuit showing the F operation. FIG. 30 is a quantum circuit showing Toffoli calculation. FIG. 31 is a diagram showing a conventional configuration of a quantum circuit that finds a value useful for order discovery. 32A is a quantum circuit showing the operator H in FIG. 31, and FIG. 32B is a quantum circuit showing the operator X in FIG. FIG. 33 is a quantum circuit showing the operator R of FIG. FIG. 34 is a quantum circuit showing details of the calculation of CU (A) = CU (A · 2 ⁰ ) in FIG. FIG. 35 is a quantum circuit showing the CSWAP operation of FIG. FIG. 36A is a quantum circuit showing a NOT operation, and FIG. 36B is a quantum circuit showing a control NOT operation. FIG. 37 is a quantum circuit showing Toffoli calculation. FIG. 38 is a quantum circuit showing details of the operation of CMULT (A) MOD (N) in FIG. FIG. 39 is a quantum circuit showing details of the QFT operation in FIG. FIG. 40 is a quantum circuit showing the operators K∈ {2,..., 6} in FIG. Figure 41 is a quantum circuit showing details of the operation of FaiADD in FIG 38 (A) MOD (N) = φADD (2 0 · A) MOD (N). FIG. 42 is a quantum circuit illustrating details of the φADD (A) operation in FIG. FIG. 43 is a quantum circuit showing the operator σ _k (k∈ {1,..., 5}) in FIG.

Explanation of symbols

  1,200 quantum computing device

Claims (5)

From binary j digits N = n _j−1 ... N ₀ , binary j digits F = f _j−1 ... F ₀ and binary j digits B = b _j−1 ... B ₀ , F + B A quantum calculation method for calculating mod N ,
(A) storing the N and F in a memory;
(B) subtracting unit, calculating a N-F from the read N and the F from the memory,
(C) a 1 COMPARISON calculation unit, using the N-F of the subtraction unit is calculated, the B _{= b j-1} ... _b qubit _{QB j-1} of the quantum states respectively each digit of _0, ... , and QB _0, qubits _QU j-1 of any quantum state, and ... _QU 1, QZ, against two, performs a first quantum operation for comparing the N-F and B, N-F> B Inverting the quantum state of the qubit QZ only in the case of
(D) a QFT operation unit applying a QFT (quantum Fourier transform) operation to the qubits QB _j−1 ,..., QB ₀ as a result of the operation of the first COMPARISON operation unit ;
(E) The quantum bit QB _j−1 ,..., The result of the calculation by the QFT calculation unit only when the φADD calculation unit is in a quantum state in which the quantum bit QZ as a result of calculation by the first COMPARISON calculation unit is ₁ . For quantum bits QB _k (0 ≦ k ≦ j−1) in the quantum state indicating 1 out of QB ₀ ,

( _Wherein the quantum state of the qubit QB _k is | QB _k >, e is a Napier number, and i is an imaginary unit);
(F) a first NOT operation unit performing a NOT operation on the qubit QZ resulting from the operation of the first COMPARISON operation unit;
(G) The quantum bit QB _j−1 , the result of calculation by the φADD calculation unit only when the φADD ⁻¹ calculation unit is in a quantum state in which the qubit QZ as a result of calculation by the first NOT calculation unit is ₁ . , QB ₀ for quantum bits QB _k (0 ≦ k ≦ j−1) in the quantum state indicating 1

(Where N−F = (n−f) _j−1 ... (N−f) ₀ ),
(H) a second NOT operation unit performing a NOT operation on the qubit QZ as a result of the operation of the first NOT operation unit;
(I) a step in which a QFT ⁻¹ operation unit applies a reverse operation of the QFT operation to the qubits QB _j−1 ,..., QB ₀ resulting from the operation of the φADD ⁻¹ operation unit ;
(J) The second COMPARISON calculation unit uses the F and B, and the quantum bits QB _j−1 ,..., QB ₀ calculated by the QFT- ¹ calculation unit and the result calculated by the first COMPARISON calculation unit When the quantum bit QU _j−1 ,..., QU ₁ and the qubit QZ calculated by the second NOT operation unit are subjected to the first quantum operation for comparing F and B, and F> B Performing a quantum operation that inverts the quantum state of the qubit QZ as a result of the calculation by the second NOT operation unit only,
A quantum calculation method characterized in that qubits QB ₀ ... QB _j−1 as a result of calculation by the second COMPARISON calculation unit are output as qubits representing quantum states corresponding to the respective digits of F + B mod N. The quantum calculation method for calculating F + B mod N according to claim 1, wherein the binary j digits N = n _j−1 ... N ₀ and the binary j digits smaller than N A = a _{j -1} ... from _{a 0} ^Prefecture, a quantum computation method for calculating the minimum value _{C = c 2j-1 ··· c} 0 useful for the calculation of R that satisfies a R = 1 mod N,
Initial quantum state generator is 0 the qubit _QD 1 showing 1 and 2j zeros and _{respectively, QD 2, QU 1, ···} QU j-1, QB 0, ···, QB j-1, Generating QZ; and
(A) a step of applying an Hadamard operation to the qubit QD ₁ by the H operation unit ;
(B) a first multiplying unit calculating A · 2 ^2j−ga−1 from the A and the variable ga ;
(C) The qubits QU ₁ ,..., QU _j−1 , QB ₀ ,..., QB _j only when the first M MOD calculation unit is in a quantum state where the qubits QD ₁ and QD ₂ indicate ₁ . The step according to claim ¹ , wherein 2 ⁰ · A · 2 ^2j-ga-1 calculated from A · 2 ^2j-ga-1 calculated by the first multiplication unit is set as F for ₋₁ and QZ. a) to (j) are executed, and the toffoli operation is applied using the resulting qubits QD ₁ and QD ₂ as control bits and QZ as the target bit, and further, the variable gb = 1 to j−1 SWAP operation is applied to QD ₂ and U _gb , and 2 ^gb · A · 2 ^2j-ga-1 calculated from the variable gb and A · 2 ^2j-ga-1 calculated by the first multiplication unit is changed to F Applying steps (a) to (j) according to claim 1 as And repeating an operation of applying a SWAP operation on qubits QD ₂ and _{QU gb} results,
(D) For the qubits QD ₁ , QD ₂ , QU ₁ ,..., QU _j−1 , QB ₀ ,..., QB _j−1 , QD _{2 is set} to QU ₀ and k = For 0 to j−1, a control NOT operation with QB _k as the control bit and QU _k as the target bit is applied, a Toffoli operation with QD ₁ and QU _k as the control bits and QB _k as the target bit is applied, and QB applying a control NOT operation with _k as the control bit and QU _k as the target bit;
(E) a step in which the second multiplier unit calculates the ^{(A · 2 2j-ga-} 1) -1 from ^{A · 2 2j-ga-1} calculated by the first multiplication section,
(F) The qubits QU ₁ ,..., QU _j−1 , QB ₀ ,..., QB _j only when the _second M MOD calculation unit is in a quantum state where the qubits QD ₁ and QD ₂ indicate ₁ . ₋₁ , QZ, and 2 ⁰ · (A · 2 ^2j−ga−1 ) ⁻¹ calculated from (A · 2 ^2j−ga−1 ) ⁻¹ calculated by the second multiplication unit as F applying the (a) ~ (j) according to claim 1, the QZ a result qubits QD ₁ and QD ₂ and the control bits applied to Toffoli operation that targets bit further, qubits result For the variable gb = 0 to j−1 , the SWAP operation is applied to the qubits QD ₂ and U _gb , and the variable gb and the second multiplication unit calculate (A · 2 ^2j−ga−1 ). was calculated from the Metropolitan ^{-1 2 gb · (a · 2} 2j-ga-1) -1 And repeating an operation of applying the serial steps of claim 1 as F (a) ~ (j) , applying a SWAP operation on the result of the qubit QD ₂ and _{QU gb,}
(G) an observing unit observing the quantum state of the qubit QD ₁ and storing the result in the memory as the _cga ;
_{(H) X ck} calculation unit, the result of observation by the observation unit _{c ga} only when the 1, comprising the steps of reversing the quantum state of qubit QD _1,
(I) _{R k} calculation unit, only when the quantum state quantum bits QD ₁ indicates 1, the QD ₁

(However, the quantum state of qubit QD ₁ is set to | QD ₁ >);
The quantum computation control unit assigns 0 to the variable ga, causes the above steps (A) to (F) to be executed in order, executes the above step (A) for the resulting quantum bits, G) is executed, and the above steps (H), (A) to (F), (I) are performed while increasing ga one by one from the variable ga = 1 to ga = 2j−1 for the resulting qubit. ), (G) are sequentially executed, and c _ga (ga = 0,..., 2j−1) observed by the observation unit is a value useful for calculating the minimum R satisfying A ^R = 1 mod N A quantum calculation method characterized by outputting each digit of C. The quantum calculation method according to claim 1 or 2,
The first quantum operation performed by the first COMPARISON calculation unit is:
HIGHBIT calculation unit, qubits _{QB j-1,} ..., and QB _0, qubits _{QU j-1,} ..., and QU _1, performs a second Quantum for the qubit QZ, a qubit QZ, z (+) Β [β is the most significant digit of N −F + B, (+) is exclusive OR], and other quantum bits QB _j−1 ,..., QB ₀ , QU _j−1 , ..., setting the quantum state of QU _{1 to} the quantum state before the second quantum operation;
A third NOT operation unit performing a NOT operation on the qubit QZ;
The 4 NOT operation unit which is controlled by classical information, digit N -F classical information read from the memory _{(n -f) h (h∈ {} j-1, ..., 0}) is the value of Performing a NOT operation only on the qubit QB _h corresponding to h which becomes 1,
A fifth NOT operation unit performing a NOT operation on each qubit QB _j−1 ,..., QB ₀ ;
A second Toffoli operation unit performs a Toffoli operation with each qubit QB _j−1 ,..., QB ₀ as a control bit and a qubit QZ as a target bit;
A sixth NOT operation unit performs a NOT operation on each qubit QB _j−1 ,..., QB ₀ ;
The 7 NOT operation unit which is controlled by classical information, only the qubits QB _h to the value of the digit (n _{-f) h} of N -F classical information read from the memory corresponds to h which becomes 1 Performing a NOT operation;
A quantum computation method characterized by comprising: From binary j digits N = n _j−1 ... N ₀ , binary j digits F = f _j−1 ... F _0, and binary j digits B = b _j−1 ... B ₀ , F + B a quantum computing device for calculating mod N ,
A memory for storing N and F ;
A subtracting section for calculating a N-F from the read N and the F from the memory,
Using N-F of the subtraction unit is calculated, the B _{= b j-1} ... _b qubit _QB j-1 of the quantum states respectively each digit of _0, ..., and QB _0, any quantum state qubit _QU j-1, ... and _QU 1, QZ, against two, performs a first quantum operation for comparing the N-F and B, N-F> quantum state of qubit QZ only if B A first COMPARISON calculation unit for inverting
A QFT operation unit that applies a QFT (quantum Fourier transform) operation to the qubits QB _j−1 ,..., QB ₀ as a result of the operation of the first COMPARISON operation unit ;
The qubit _{QB j-1} of the results qubit QZ results claim 1COMPARISON calculation unit is calculated only when the quantum state indicating 1, the QFT calculation unit is calculated, ..., quantum showing one of the QB ₀ For state qubits QB _k (0 ≦ k ≦ j−1),

A φADD operation unit that performs an operation of ( _where the quantum state of the qubit QB _k is | QB _k >, e is a Napier number, and i is an imaginary unit);
A first NOT operation unit that performs a NOT operation on the qubit QZ obtained as a result of the operation of the first COMPARISON operation unit;
Quantum state indicating 1 out of quantum bits QB _j−1 ,..., QB ₀ calculated by the φADD calculation unit only when the quantum bit QZ calculated by the first NOT calculation unit is 1 For qubits QB _k (0 ≦ k ≦ j−1) of

A φADD ⁻¹ operation unit that performs an operation of (where N−F = (n−f) _j−1 ... (N−f) ₀ ) ;
A second NOT operation unit that performs a NOT operation on the qubit QZ resulting from the operation of the first NOT operation unit;
A QFT ⁻¹ operation unit that applies a reverse operation of the QFT operation to the qubits QB _j−1 ,..., QB ₀ obtained by the φADD ⁻¹ operation unit ;
The use as F and B, the ^{QFT -1} result calculating unit is calculated qubit _{QB j-1, ..., QB} 0 and, as a result of the first 1COMPARISON calculation unit has calculated qubit _{QU j-1,} ..., A first quantum operation for comparing F and B is performed on QU ₁ and a qubit QZ obtained as a result of calculation by the second NOT calculation unit, and the second NOT calculation unit calculates only when F> B. A second COMPARISON operation unit that performs a quantum operation to invert the quantum state of the resulting qubit QZ,
A quantum computation device that outputs qubits QB ₀ ... QB _j−1 as a result of computation by the second COMPARISON computation unit as qubits representing a quantum state corresponding to each digit of F + B mod N. The quantum calculation method for calculating F + B mod N according to claim 1, wherein the binary j digits N = n _j−1 ... N ₀ and the binary j digits smaller than N A = a _{j -1} ... from _{a 0} ^Prefecture, a quantum computing device for calculating the minimum value _{C = c 2j-1 ··· c} 0 useful for the calculation of R that satisfies a R = 1 mod N,
Initial quantum states for generating qubits QD ₁ , QD ₂ , QU ₁ ,..., QU _j−1 , QB ₀ ,..., QB _j−1 , QZ respectively indicating 0, 1 and 2j 0 A generator,
An H operation unit that applies a Hadamard operation to the qubit QD ₁ ;
A first multiplier for calculating A · 2 ^2j−ga−1 from A and the variable ga ;
Only when the qubit QD ₁ and QD ₂ is a quantum state indicating 1, qubit _{QU 1, ··· QU j-1} , QB 0, ···, to the _{QB j-1,} QZ, wherein the 1 perform step (a) ~ (j) according to ^{2 0 · a · 2 2j-} ga-1 calculated from the multiplying unit ^{a · 2 2j-ga-1} was calculated to claim 1 as the F, Apply the Toffoli operation with the resulting qubits QD ₁ and QD ₂ as control bits and QZ as the target bit, and apply the SWAP operation to qubits QD ₂ and U _gb from variable gb = 1 to j−1 The step (a) according to claim ¹ , wherein 2 ^gb · A · 2 ^2j-ga-1 calculated from the variable gb and A · 2 ^2j-ga-1 calculated by the first multiplication unit is ^defined as F. ) was applied - the (j), the qubit QD ₂ resulting A first 1M MOD calculator repeats operation to apply the SWAP operation on U _gb,
For the qubits QD ₁ , QD ₂ , QU ₁ ,..., QU _j−1 , QB ₀ ,..., QB _j−1 , QD ₂ is QU ₀ and k = 0 to j−1 the QU _k and the control bits _k by applying a control NOT operation with the goal bits, by applying the Toffoli operation with the goal bits QB _k as a control bit QD ₁ and QU _k, the QU _k as a control bit QB _k A CSWAP calculation unit that applies a control NOT calculation as a target bit;
A second multiplying unit for calculating a ^{(A · 2 2j-ga-} 1) -1 from ^{A · 2 2j-ga-1} calculated by the first multiplication section,
Only when the qubit QD ₁ and QD ₂ is a quantum state indicating 1, qubit _{QU 1, ··· QU j-1} , QB 0, ···, to the _{QB j-1,} QZ, wherein the 2. (a) to (a) to (1) according to claim ¹ , wherein 2 ⁰ · (A · 2 ^2j−ga−1 ) ⁻¹ calculated from (A · 2 ^2j−ga−1 ) ⁻¹ calculated by the 2 multiplication unit is ^defined as F. (J) is applied, and the Toffoli operation with the resulting qubits QD ₁ and QD ₂ as control bits and QZ as the target bit is applied, and the variable gb = 0 to j Up to −1 , the SWAP operation is applied to the qubits QD ₂ and U _gb , and 2 ^gb · ( 2 ) calculated from the variable gb and (A · 2 ^2j−ga−1 ) ⁻¹ calculated by the second multiplication unit. scan of claim 1 ^{a · 2 2j-ga-1} ) -1 as the F A second M MOD operation unit that applies the steps (a) to (j) and repeats the operation of applying the SWAP operation to the resulting qubits QD ₂ and QU _gb ;
An observation unit that observes the quantum state of the qubit QD ₁ and stores the result in the memory as the _cga ;
An X _ck operation unit that inverts the quantum state of the qubit QD ₁ only when the result _cga observed by the observation unit is 1 ,
Only when qubit QD ₁ is a quantum state indicating 1, the QD ₁

An R _k operation unit that performs an operation of ( where the quantum state of the qubit QD ₁ is | QD ₁ >) ;
Substituting 0 into the variable ga, the processing of the H calculation unit (A), the processing of the first multiplication unit (B), the processing of the first M MOD calculation unit (C), the processing of the CSWAP calculation unit (D) , The processing of the second multiplication unit (E) and the processing of the second M MOD calculation unit (F) are sequentially executed, the processing (A) is performed on the resultant qubit, and the observation Process (G), and the X _ck calculation process (H) described above while incrementing ga by 1 sequentially from variable ga = 1 to ga = 2j−1 for the resulting qubit C _ga (ga = 0,..., 2j−1 ) observed by the observation unit by sequentially executing the processes (A) to (F), the process (I) of the R _k calculation unit, and the process (G). ) As each digit of the value C useful for calculating the minimum R satisfying A ^R = 1 mod N A quantum computation control unit,
A quantum computing device comprising:

Images