JP4332167B2 - Quantum circuit for performing approximate quantum Fourier transform, approximate quantum Fourier transform calculation method and apparatus - Google Patents

Description

  The present invention relates to a quantum circuit that performs approximate quantum Fourier transform, a calculation method and a calculation apparatus for approximate quantum Fourier transform. More specifically, the present invention relates to a quantum circuit, an arithmetic method, and an arithmetic device that perform an approximate quantum Fourier transform composed of only one qubit operation and neighboring two qubit operations.

First, a quantum Fourier transform will be described, then a non-approximate quantum Fourier transform quantum circuit constructed by linear nearest neighbor quantum bit operation, and a single quantum A quantum circuit of an approximate quantum Fourier transform constituted only by a 1-qubit operation on a bit and a neighboring 2-qubit operation that is a qubit operation between adjacent qubits will be described.
In the present specification, the calculation amount is described according to the O notation.

<Quantum Fourier transform QFT>
For example, Non-Patent Document 1 details the quantum Fourier transform. Here, the quantum Fourier transform will be outlined.
Quantum bit (hereinafter referred to as q bit). ], The quantum Fourier transform on the orthonormal basis | 0>, | 1>,..., | N−1>, which is the ground state forming the orthonormal system of FIG. Defined. Here, the q-bit state is a vector in a complex vector space, which is a computational basis state. In Equation (1), i is an imaginary unit, and e is a Napier's constant (the base of natural logarithm). In the present specification, the p-th power of the Napier number e may be expressed as exp (p).

Here, N = 2 ⁿ , n is an integer [positive integer] of 1 or more, and the bases | 0>, | 1>,..., | 2 ⁿ -1> are calculated ground states for n q-bit quantum computers. To do. State | b> is expressed in binary notation as b = b _n-1 b _n-2 ... B ₁ b ₀ . In decimal representation, b = b _n-1 2 ^n-1 + b _n-2 2 ^n-2 +... + B ₁ 2 ¹ + b ₀ 2 ⁰ . Binary decimal representation is defined by equation (2). The tensor products of the states | v> and | w> are expressed as | v> | w>, | v, w>, | vw>, and the like.

At this time, the expressions (1) and (3) are equivalent. Equation (3) is a product representation of the quantum Fourier transform modulo ²ⁿ . Hereinafter, unless otherwise noted, the quantum Fourier transform is assumed to be a quantum Fourier transform modulo the power of 2 regardless of approximate quantum Fourier transform or non-approximate quantum Fourier transform.

A quantum circuit that performs efficient quantum Fourier transform represented by Expression (3) is shown in FIG. 1 by taking n = 8 as an example. In general, a quantum circuit uses a single qubit operation on a single q bit and CNOT (controlled-NOT) as basic operations, but in this specification, operations other than these operations are performed to avoid the complexity of the quantum circuit. The quantum circuit will be described using the above. It should be noted that all operations used in the quantum circuit can be decomposed into one qubit operation for a single q bit and CNOT [see Non-Patent Document 1]. CNOT is a two-qubit operation on two input q bits.
Note that Non-Patent Document 1 describes a quantum circuit that performs a quantum Fourier transform by performing an exchange operation on the last state of the quantum circuit shown in FIG. 1 and inverting the q-bit state. However, in this specification, the quantum circuit shown in FIG. 1 that does not perform the exchange operation is a quantum circuit of the quantum Fourier transform. This is only based on the difference in the expression (3) expressed by the tensor product.

The quantum Fourier transform QFT8 in the case of n = 8 has an output state (| 0> + exp (2πi0.b ₇ b ₆ ... b ₁ b ₀ ) | with respect to an input state | b ₇ b ₆ ... b ₁ b ₀ >. 1>) (| 0> + exp (2πi0.b ₆ ... B ₁ b ₀ ) | 1>)... (| 0> + exp (2πi0.b ₀ ) | 1>) / 2 ^{n / 2} . FIG. 1 shows a quantum circuit of QFT 8 in which an input state and an output state are disassembled into single q-bit wires. In FIG. 1, the output state | φ _k (b)> is | φ _k (b)> = (| 0> + exp (2πiΣ _{m = 0} ^k (b _k−m / 2 ^{m + 1} )) | 1>) / 2 ^{1 / 2} . However, k = 0, 1, 2, 3, 4, 5, 6, 7.

The quantum gate appearing in FIG. 1 will be outlined. In FIG. 1, the quantum gate represented by the symbol H is a Hadamard gate, and Hadamard transformation is performed. When the q-bit input state | x> is passed through a Hadamard gate, an output state (| 0> + (− 1) ^x | 1>) / 2 ^1/2 is obtained [see FIG. 2]. The output state can also be expressed as (| 0> + e ^2πi0.x | 1>) / 2 ^1/2 .

In FIG. 1, quantum gates represented by numerals t = 2, 3, 4, 5, 6, 7, and 8 are controlled phase shift gates and are represented by a matrix represented by Equation (4). Unitary conversion is performed. When two q-bit input states | x> and | y> are passed through the control phase shift gate, an output state exp (2πxy / 2 ^t ) | x> | y> is obtained (see FIG. 3). The control phase shift gate is a rotary gate having an angle of 2π / ^2t . Hereinafter, the operation of the control phase shift gate represented by the number t may be referred to as a control phase shift of an angle 2π / ^2t . FIG. 3 shows a quantum circuit in which the input state and the output state are broken down into single q-bit wirings. It should be noted that the control phase shift gate shown in FIG. 3 is equivalent to the control phase shift gate shown in FIG.

<Quantum circuit of non-approximate quantum Fourier transform LNN-QFT composed of two neighboring qubit operations>
In the QFT8 quantum circuit shown in FIG. 1, for example, in the first eight calculation steps, the input state | b ₇ b ₆ ... B ₁ b ₀ > ₇ > is subjected to the Hadamard transform, and the following calculation is performed on the intermediate state (| 0> + exp (2πi0.b ₇ ) | 1>) / 2 ^1/2 | b ₆ ... B ₁ b ₀ > obtained by this action. In step, the control phase shift based on the state | b ₆ > is applied, and the intermediate state (| 0> + exp (2πi0.b ₇ b ₆ ) | 1>) / 2 ^1/2 | b ₆ . The control phase shift based on the state | b ₅ > is applied to b ₁ b ₀ > in the next calculation step, and the intermediate state (| 0> + exp (2πi0.b ₇ b ₆ b ₅ ) | 1 obtained by this operation is applied. >) ^{/ 2 1/2} | control phase shifts based on a _{b 4>} | _b 6 _... state in the following calculation steps b 1 _{b 0>} To act, ... omission ..., obtained intermediate state in this action (| 0> + exp (2πi0.b 7 b 6 b 5 b 4 b 3 b 2 b 1) | 1>) / 2 1 / ² | b ₆ ... B ₁ b ₀ > is subjected to a control phase shift based on the state | b ₀ > in the next calculation step.

As is apparent here, when the control phase shift is applied to the immediately preceding intermediate state, for example, in the first eight calculation steps, the phase of the coefficient of the state | 1> based on the state | b ₇ > each time In addition, the target q bits of the control phase shift [or the control q bits are the same (see FIG. 4). An additional bit corresponding to] is added. More generally, in calculation theory, there is no particular problem with such an operation, but when the q-bit state is a physical state, the operation is based on q-bits that are separated from adjacent q-bits. This generally increases the risk of computation errors. In view of this, it has been proposed to construct a quantum circuit that performs quantum Fourier transform by a neighboring 2-qubit operation that is a qubit operation between adjacent qubits [see Non-Patent Document 2].

Here, the quantum circuit of the non-approximation quantum Fourier transform comprised by the neighborhood 2 qubit calculation is outlined.
The quantum circuit of the non-approximation quantum Fourier transform configured by the neighborhood 2 qubit operation appropriately performs the SWAP (swap operation) on the quantum circuit that performs the efficient quantum Fourier transform represented by the equation (3). Can be obtained. As an example of the case of n = 8, FIG. 5 shows an unapproximated quantum Fourier transform LNN-QFT8 quantum circuit composed of neighboring 2-qubit operations based on the QFT8 quantum circuit shown in FIG. FIG. 6 shows the SWAP quantum circuit used in FIG. The SWAP quantum circuit exchanges two input q-bit states. The SWAP quantum circuit shown in FIG. 6 uses three CNOTs. A CNOT quantum circuit is shown in FIG. A CNOT quantum circuit performs the most basic two-qubit operation, and in this sense is called a CNOT gate. The CNOT gate corresponds to a classical XOR gate and causes a change in the target q-bit state | y> in response to the control q-bit state | x>. Briefly, in a two-level system, if the state of the control q bit is | 0>, the target q bit state | y> is not changed, and if the state of the control q bit is | 1>. , Invert the target q-bit state | y>.

In the quantum circuit of LNN-QFT8 shown in FIG. 5, INV (inverse operation) is applied to each q-bit state. An INV quantum circuit is shown in FIG. In FIG. 8, the state is represented by the symbol | a _{s = 7, 6,..., 0} > so as not to be confused with the q-bit input state | b _{s = 7, 6,.} Hereinafter, the symbol | a _s > is used when it is desired to generally represent the state in distinction from the input state | b _s >.
An INV quantum circuit outputs an input q-bit state rearranged in the reverse order, and in this sense is called an INV gate. Note that if it is not configured with only SWAP between two neighboring qubits, an INV quantum circuit can be constructed so that the number of SWAPs is about O (n / 2). In FIG. 1 shows an INV quantum circuit composed only of SWAPs. In order to make the order of the output states the same as the output states of the quantum circuit shown in FIG. 1, the INN gate is used in the quantum circuit of LNN-QFT8 shown in FIG. The number of calculation steps and the number of basic operations in the LNN-QFT8 quantum circuit using the INV gate may be on the same order as those in the QFT8 quantum circuit not using the INV gate. In general, it should be noted that the use of INV gates does not make the LNN-QFT quantum circuit less efficient than the QFT quantum circuit.

A configuration method of the quantum circuit (3) of the non-approximation quantum Fourier transform LNN-QFT configured by the neighborhood 2 qubit operation will be described.
The state of the n q bits input to the quantum circuit _{(3) | b n-1} >, ..., | a _{b 0>,} the 1-q bits each q bits in sequence, ..., the n-q I'll call it a bit. That is, the q bit corresponding to the uppermost wiring is the 1-q bit, and the q bit corresponding to the lowest wiring is the n-q bit. For convenience of description, it is also described as the (·) -q bit.

<< 1 >> For g = 1,..., N, a quantum circuit that sequentially performs the following operations is used.
[When g = 1]
Apply Hadamard transform to 1-q bits.
[When g is an odd number of 3 or more]
Apply Hadamard transform to 1-q bits. A control phase shift of angle 2π / 2 ^j is applied to the (j−1) -qth bit and the j-qth bit, and SWAP is applied to these q bits. However, j is an odd number from 3 to g, and Hadamard transform and operations for all j are performed in parallel for each g.
[If g is an even number]
A control phase shift of angle 2π / 2 ^j is applied to the (j−1) -qth bit and the j-qth bit, and SWAP is applied to these q bits. However, j is an even number from 2 to g, and operations for all j are performed in parallel for each g.
<< 2 >> For g = n−1,..., 1, a quantum circuit that sequentially performs the following operations is used.
[When g = 1]
Apply Hadamard transform to 1-q bits.
[When g is an odd number of 3 or more]
Apply Hadamard transform to 1-q bits. A control phase shift of angle 2π / 2 ^j is applied to the (j−1) -qth bit and the j-qth bit, and SWAP is applied to these q bits. However, j is an odd number from 3 to g, and Hadamard transform and operations for all j are performed in parallel for each g.
[If g is an even number]
A control phase shift of angle 2π / 2 ^j is applied to the (j−1) -qth bit and the j-qth bit, and SWAP is applied to these q bits. However, j is an even number from 2 to g, and operations for all j are performed in parallel for each g.
<< 3 >> For g = 1,..., N−1, a quantum circuit that sequentially performs the following operations is used.
[When g is an odd number]
SWAP is applied to the j-qth bit and the (j + 1) -q-th bit. However, j is an odd number from 1 to g, and SWAP for all j is performed in parallel for each g.
[If g is an even number]
SWAP is applied to the j-qth bit and the (j + 1) -q-th bit. However, j is an even number from 2 to g, and SWAP for all j is performed in parallel for each g.
<< 4 >> For g = n−2,..., 1, a quantum circuit that sequentially performs the following operations is used.
[When g is an odd number]
SWAP is applied to the j-qth bit and the (j + 1) -q-th bit. However, j is an odd number from 1 to g, and SWAP for all j is performed in parallel for each g.
[If g is an even number]
SWAP is applied to the j-qth bit and the (j + 1) -q-th bit. However, j is an even number from 2 to g, and SWAP for all j is performed in parallel for each g.

<Quantum Circuit of Approximate Quantum Fourier Transform LNN-AQFT Comprising Only 1 Qubit Operation and Near 2 Qubit Operation>
A quantum circuit that performs an approximate quantum Fourier transform with an approximate threshold value m is a quantum circuit that performs a non-approximate quantum Fourier transform modulo 2 ⁿ and regards a control phase shift satisfying t> m as an identity transform. [Where t corresponds to the number of the control phase shift gate. ]. Note that m is a positive integer smaller than n.
The same applies to a non-approximate quantum Fourier transform quantum circuit composed of two adjacent qubit operations, and a control phase shift represented by a number t larger than the approximate threshold is regarded as an identity transform. The quantum circuit thus obtained is an approximate quantum Fourier transform quantum circuit composed of only one qubit operation and neighboring two qubit operations [see Non-Patent Document 3]. Taking the case of n = 8 as an example, the quantum circuit of the approximate quantum Fourier transform LNN-AQFT8 composed of only one qubit operation and neighboring two qubit operations based on the LNN-QFT8 quantum circuit shown in FIG. Is shown in FIG. The quantum circuit of LNN-AQFT8 shown in FIG. 9 shows a case where the approximate threshold value m is 5. The lower limit of the approximation threshold of the quantum Fourier transform is O (logn) [see Non-Patent Document 3]. In FIG. 9, the output state | φ _k (b)> is | φ _k (b)> = (| 0> + exp (2πiΣ _{m = 0} ⁴ (b _k−m / 2 ^{m + 1} )) | 1>) / 2 ^1/2 [where k = 5, 6, 7], | φ _k (b)> = (| 0> + exp (2πiΣ _{m = 0} ^k (b _k−m / 2 ^{m + 1} )) | 1>) / 2 ^1/2 [where k = 0, 1, 2, 3, 4].
The number of calculation steps and the number of basic operations in the quantum circuit that performs such approximate quantum Fourier transform are on the same order as those in the LNN-QFT quantum circuit and the QFT quantum circuit.

In the description here, the case of n = 8, that is, the case of 8q bits has been described, but it can be expanded to a general n-q bit. . ].
MA Nielsen and IL Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000. AG Fowler, SJ Devitt, and LCL Hollenberg, "Implementation of Shor's algorithm on a linear nearest neighbor qubit array", Quantum Information and Computation, Vol.4, No.4, pp.237-251, 2004. D. Coppersmith, "An approximate Fourier transform useful in quantum factoring", Technical Report RC19642, IBM, 1994.

The conventional quantum circuit of the approximate quantum Fourier transform described above has an approximate threshold value of O (logn), and uses only one qubit operation for a single qubit and two neighboring qubit operations, and O (n). Approximate quantum Fourier transform is realized using the number of calculation steps (depth) and O (n ² ) basic operations (size).

  By the way, the larger the number of basic operations, the greater the possibility that an operation error will occur. Therefore, the number of basic operations should be as small as possible. Also, for a short calculation time, it is better that the number of calculation steps is small.

  Therefore, the present invention provides an approximate quantum Fourier which is composed of only one qubit operation and two neighboring qubit operations, which is realized by the number of basic operations on the order of less than the conventional one, although the number of calculation steps is O (n). It is an object of the present invention to provide a quantum circuit that performs transformation, an approximate quantum Fourier transform computation method, and a computation device.

In order to solve the above problems, the quantum circuit of the present invention has the following configuration. That is, a quantum circuit that performs an approximate quantum Fourier transform using an approximate threshold as a positive integer m smaller than a positive integer ⁿ and modulo 2 ⁿ , wherein the first q bits, which are n q bits,. When n is an even number with respect to the n-q bits, << 1 >> modulo 2 ^{n / 2} composed of 2 qubit operations in the vicinity from the 1-q bit to the (n / 2) -q bit A quantum circuit that performs a quantum Fourier transform as follows: << 2 >> For g = 2,..., N / 2 + 1, in order, the (n / 2−g + 2j) −q bits and the (n / 2−g + 2j + 1) − A quantum circuit that performs an operation of applying a control phase shift of an angle 2π / 2 ^g to q bits and further applying SWAP to these q bits is configured [where j = 1,. In addition, a quantum circuit that performs operations for all j in parallel. , <3> For g = n / 2 + 2,..., N, the angle is 2π / 2 from the (g−n / 2 + 2j−2) −q bit and the (g−n / 2 + 2j−1) −q bit in order. ^A quantum circuit that performs an operation of applying a control phase shift of ^g and applying SWAP to these q bits is configured [where j = 1,..., n + 1−g, and operations for all j are performed for each g. Is a quantum circuit that performs in parallel. ], << 4 >> For g = n,..., N / 2 + 2, SWAP is applied to the (g−n / 2 + 2j−2) −q bit and the (g−n / 2 + 2j−1) −q bit in order. A SWAP quantum circuit that performs an operation is configured [where j = 1,..., N + 1−g, and a quantum circuit that performs operations for all j in parallel for each g. ], << 5 >> For g = n / 2 + 1,..., 2, SWAP that performs the operation of applying SWAP to the (n / 2−g + 2j) −q bits and the (n / 2−g + 2j + 1) −q bits in order. A quantum circuit is configured [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ], <6> Construct a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} composed of neighboring 2 qubit operations from the (n / 2 + 1) -q bit to the n-q bit, When n is an odd number, in either pattern 1 or pattern 2, (pattern 1) << 1 >> from 1st-qth bit to (n + 1) / 2) -qth bit is composed of neighboring 2 qubit operations The quantum circuit that performs the quantum Fourier transform modulo 2 ^{(n + 1) / 2} is constructed, and << 2 >> g = 2,..., (N + 1) / 2, in order ((n + 1) / 2−g + 2j) A quantum circuit is configured to apply a control phase shift of an angle 2π / 2 ^{g to} the -q bit and the ((n + 1) / 2-g + 2j + 1) -q bits, and further to apply an SWAP to these q bits. However, j = 1,..., G-1 and for every j for every g A quantum circuit for performing operations in parallel. , << 3 >> g = (n + 1) / 2 + 1,..., N in order of (g− (n + 1) / 2 + 2j−2) -q bits and (g− (n + 1) / 2 + 2j−1) bits Apply a control phase shift with an angle of 2π / 2 ^g , and further configure a quantum circuit that performs an operation to apply SWAP to these q bits [where j = 1,..., N + 1−g, Suppose a quantum circuit that performs operations on j in parallel. ], << 4 >> For g = n,..., (N + 1) / 2 + 1, in order, the (g− (n + 1) / 2 + 2j−2) −q bits and the (g− (n + 1) / 2 + 2j−1) −q A SWAP quantum circuit that performs an operation applying SWAP to bits is configured [where j = 1,..., N + 1−g, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 5 >> For g = (n + 1) / 2,..., 2, SWAP is sequentially applied to the ((n + 1) / 2−g + 2j) −q bits and the ((n + 1) / 2−g + 2j + 1) −q bits. A SWAP quantum circuit that performs an operation is configured [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ], << 6 >> For the ((n + 1) / 2 + 1) -q bits to the n-q bits, quantum Fourier transform modulo 2 ^{(n-1) / 2} configured by neighboring 2 qubit operations is performed. A quantum circuit is configured, and (pattern 2) << 1 >> 2 ^{(n-1) / 1} configured from the 1st -q bit to the ((n-1) / 2) -q bit by neighboring 2 qubit operations. ^A quantum circuit that performs a quantum Fourier transform modulo ² is constructed, and << 2 >> g = 2,..., (N + 1) / 2, in order, ((n + 1) / 2−g + 2j−1) −q bits A quantum circuit that performs an operation of applying a control phase shift of an angle 2π / 2 ^{g to} the ((n + 1) / 2−g + 2j) −q bits and applying SWAP to these q bits is configured [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ], << 3 >> For g = (n + 1) / 2 + 1,..., N, in order, the angle 2π between the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) bits. / 2 A quantum circuit that performs an operation of applying a control phase shift of ^g and applying SWAP to these q bits is configured [where j = 1,..., N + 1−g, and for all j for each g A quantum circuit that performs the above operations in parallel. , <4> g = n,..., (N + 1) / 2 + 1, in order, to (g− (n + 1) / 2 + 2j−1) −q bits and (g− (n + 1) / 2 + 2j) −q bits, respectively. A SWAP quantum circuit that performs an operation applying SWAP is configured [where j = 1,..., N + 1−g, and a quantum circuit that performs operations for all j in parallel for each g. ], << 5 >> g = (n + 1) / 2,..., 2 in order of ((n + 1) / 2−g + 2j−1) −q bits and ((n + 1) / 2−g + 2j) −q bits A SWAP quantum circuit that performs an operation applying SWAP is configured [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ], << 6 >> For the ((n-1) / 2 + 1) -q bits to the n-q bits, a quantum Fourier transform modulo 2 ^{(n + 1) / 2} composed of neighboring 2-qubit operations is performed. A quantum circuit is constructed, and when n = 1, a quantum circuit that applies Hadamard transform to the 1-q bits is constructed, and in the quantum circuit constructed by the above procedure, the number 2 smaller than 2 ^{n and} larger than 2 ^m 2 Regarding the quantum circuit of the quantum Fourier transform modulo ^B , this B is regarded as a new n, the quantum circuit is constructed according to the procedure according to the above case classification, and the number is 2 ^m or less. For the quantum circuit A that performs the quantum Fourier transform, for the first q bits that are N q bits input to the quantum circuit A,..., N1q bits, << 1 >> g = 1,. , N in order, when g = 1, Hadamard transform is applied to 1-q bits A quantum circuit that performs an operation that applies Hadamard transform to the 1-q bit when g is an odd number of 3 or more, and the (j−1) -q bit and the 1 A quantum circuit that performs an operation of applying a control phase shift of angle 2π / 2 ^j to j-q bits and further applying SWAP to these q bits is constructed (where j is an odd number from 3 to g, g For each quantum circuit, a Hadamard transform for the 1-q bits and an operation for all j are performed in parallel. When g is an even number, a control phase shift with an angle of 2π / 2 ^j is applied to the (j−1) -q-th bit and the j-q-th bit, and further, an operation for applying SWAP to these q-bits is performed. A quantum circuit is configured [where j is an even number from 2 to g, and a quantum circuit that performs operations for all j in parallel for each g. ], << 2 >> For g = N−1,..., 1 in order, when g = 1, a quantum circuit that performs an operation of applying Hadamard transform to the 1−q bits is constructed, and g is an odd number of 3 or more In this case, a quantum circuit that performs an operation applying Hadamard transform to the 1st-q bits is applied, and a control phase shift of angle 2π / 2 ^j is applied to the (j−1) -q bits and the j-q bits. In addition, a quantum circuit that performs an operation of applying SWAP to these q bits is configured (where j is an odd number from 3 to g, and the Hadamard transform for the 1st-q bits for each g and all j Let it be a quantum circuit that performs operations in parallel. When g is an even number, a control phase shift with an angle of 2π / 2 ^j is applied to the (j−1) -q-th bit and the j-q-th bit, and further, an operation for applying SWAP to these q-bits is performed. A quantum circuit is configured [where j is an even number from 2 to g, and a quantum circuit that performs operations for all j in parallel for each g. ], <3> For g = 1,..., N−1, in order, when g is an odd number, a quantum circuit that performs an operation applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured. [Where j is an odd number from 1 to g, and a quantum circuit that performs SWAP for all j in parallel for each g. When g is an even number, a quantum circuit that performs an operation of applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured [where j is an even number from 2 to g, and for each g A quantum circuit that performs SWAP for all j in parallel. ], <4> For g = N−2,..., 1, in order, when g is an odd number, configure a quantum circuit that performs an operation applying SWAP to the j-qth bit and the (j + 1) -q-th bit. [Where j is an odd number from 1 to g, and a quantum circuit that performs SWAP for all j in parallel for each g. When g is an even number, a quantum circuit that performs an operation of applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured [where j is an even number from 2 to g, and for each g A quantum circuit that performs SWAP for all j in parallel. ] In the quantum circuit configured by the procedure so far, the control phase shift of angle 2π / 2 ^t (t> m) is replaced with the identity transformation, and the control phase shift of angle 2π / 2 ^t (t = m) The quantum circuit C that performs each operation of the SWAP immediately after the control phase shift and the SWAP immediately after the control phase shift determined as the identity conversion, and the mirror circuit symmetrical mirror circuit portion of the quantum circuit C in the SWAP quantum circuit are configured to cancel each other. A quantum circuit that performs approximate quantum Fourier transform.

In order to solve the above problems, the approximate quantum Fourier transform calculation method of the present invention is the following method. That is, according to the quantum circuit that performs the approximate quantum Fourier transform described above, it approximates to the input 1-q-bit state | b _n-1 >, ..., n-q-bit state | b ₀ >. An approximate quantum Fourier transform calculation method for performing quantum Fourier transform is used.

In order to solve the above-described problems, the approximate quantum Fourier transform arithmetic unit of the present invention is configured as follows. That is, the approximation threshold is set to a positive integer m smaller than the positive integer n, and an approximate quantum Fourier transform arithmetic unit that performs an approximate quantum Fourier transform modulo 2 ⁿ is the first q − When n is an even number with respect to the q-bit,..., n-q bits, << 1 >> 2 from the first-q bits to the (n / 2) -q bits are composed of 2 neighboring qubit operations. a quantum operation unit that performs quantum Fourier transform modulo ^{n / 2} , and << 2 >> g = 2,..., n / 2 + 1, in order, (n / 2−g + 2j) −q bits and (n / 2−g + 2j + 1) −q bits are provided with a quantum operation unit that applies a control phase shift with an angle of 2π / 2 ^g and further applies SWAP to these q bits [where j = 1,..., G− It is assumed that the calculation for all j is performed in parallel for each g. , <3> For g = n / 2 + 2,..., N, the angle is 2π / 2 from the (g−n / 2 + 2j−2) −q bit and the (g−n / 2 + 2j−1) −q bit in order. a quantum operation unit that applies a control phase shift of ^g , and further performs an operation of applying SWAP to these q bits [provided that j = 1,..., n + 1−g, and operations for all j for each g Are performed in parallel. ], << 4 >> For g = n,..., N / 2 + 2, SWAP is applied to the (g−n / 2 + 2j−2) −q bit and the (g−n / 2 + 2j−1) −q bit in order. A SWAP calculation unit for performing calculations is provided [where j = 1,..., N + 1−g, and calculations for all j are performed in parallel for each g. ], << 5 >> For g = n / 2 + 1,..., 2, SWAP that performs the operation of applying SWAP to the (n / 2−g + 2j) −q bits and the (n / 2−g + 2j + 1) −q bits in order. An arithmetic unit is provided [where j = 1,..., G−1, and arithmetic operations for all j are performed in parallel for each g. ], <6> a quantum operation unit that performs a quantum Fourier transform modulo 2 ^{n / 2} configured by neighboring 2 qubit operations from the (n / 2 + 1) -q bit to the n-q bit, When n is an odd number, in either pattern 1 or pattern 2, (pattern 1) << 1 >> from 1st-qth bit to (n + 1) / 2) -qth bit is composed of neighboring 2 qubit operations 2 ^{(n + 1) / 2} modulo, and a quantum operation unit for performing a quantum Fourier transform modulo ² (n + 1) / 2, and << (2) g = 2, ..., (n + 1) / 2, in order ((n + 1) / 2-g + 2j) a quantum operation unit that applies a control phase shift of an angle of 2π / 2 ^{g to} the -q bits and the ((n + 1) / 2-g + 2j + 1) -q bits, and further performs an operation of applying SWAP to these q bits [ However, j = 1,..., G-1 and for every j for every g And performs operations in parallel. , << 3 >> g = (n + 1) / 2 + 1,..., N in order of (g− (n + 1) / 2 + 2j−2) -q bits and (g− (n + 1) / 2 + 2j−1) bits A quantum operation unit that applies a control phase shift with an angle of 2π / 2 ^g and further performs an operation of applying SWAP to these q bits is provided [where j = 1,..., N + 1−g, It is assumed that operations on j are performed in parallel. ], << 4 >> For g = n,..., (N + 1) / 2 + 1, in order, the (g− (n + 1) / 2 + 2j−2) −q bits and the (g− (n + 1) / 2 + 2j−1) −q A SWAP operation unit that performs an operation that applies SWAP to bits is provided [where j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g. ], << 5 >> For g = (n + 1) / 2,..., 2, SWAP is sequentially applied to the ((n + 1) / 2−g + 2j) −q bits and the ((n + 1) / 2−g + 2j + 1) −q bits. A SWAP operation unit that performs an operation to be applied is provided [where j = 1,..., G−1, and operations for all j are performed in parallel for each g. ], << 6 >> For the ((n + 1) / 2 + 1) -q bits to the n-q bits, quantum Fourier transform modulo 2 ^{(n-1) / 2} configured by neighboring 2 qubit operations is performed. comprising a quantum computation unit, (pattern 2) "1" first from the 1-q-bit ((n-1) / 2) for up to -q bit was composed of two neighboring qubit operations 2 ^{(n-1) /} Quantum operation unit that performs quantum Fourier transform modulo ² and << 2 >> g = 2,..., (N + 1) / 2, in order, ((n + 1) / 2−g + 2j−1) −q bits A quantum operation unit is provided that performs an operation of applying a control phase shift of an angle 2π / 2 ^{g to} the ((n + 1) / 2−g + 2j) −q bits and applying SWAP to these q bits [where j = 1,..., G−1, and operations for all j are performed in parallel for each g. ], << 3 >> For g = (n + 1) / 2 + 1,..., N, in order, the angle 2π between the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) bits. / 2 A quantum operation unit that applies a control phase shift of ^g and further performs an operation of applying SWAP to these q bits [provided that j = 1,..., N + 1−g, and for every j for each g Are performed in parallel. , <4> g = n,..., (N + 1) / 2 + 1, in order, to (g− (n + 1) / 2 + 2j−1) −q bits and (g− (n + 1) / 2 + 2j) −q bits, respectively. A SWAP calculation unit that performs a calculation that applies SWAP is provided. [Where j = 1,. ], << 5 >> g = (n + 1) / 2,..., 2 in order of ((n + 1) / 2−g + 2j−1) −q bits and ((n + 1) / 2−g + 2j) −q bits A SWAP operation unit that performs an operation applying SWAP is provided [where j = 1,..., G−1, and operations for all j are performed in parallel for each g. ], << 6 >> For the ((n-1) / 2 + 1) -q bits to the n-q bits, a quantum Fourier transform modulo 2 ^{(n + 1) / 2} composed of neighboring 2-qubit operations is performed. A quantum operation unit including a quantum operation unit that applies a Hadamard transform to the 1-q bits when n = 1, and is a number smaller than 2 ^{n and} greater than 2 ^m for quantum computing unit of the quantum Fourier transform of the 2 ^B modulo, deemed the B and new n, constitute quantum computing unit in the procedure in accordance with the divided case above, the number of less 2 ^m For the quantum operation unit D that performs the quantum Fourier transform as a modulo, << 1 >> with respect to the first q bits, which are N q bits input to the quantum operation unit D,. For g = 1,..., N, in order, if g = 1, adder to 1-q bit A quantum operation unit that performs an operation that applies transformation, and when g is an odd number greater than or equal to 3, a quantum operation unit that performs an operation that applies Hadamard transform to the 1-q bits, and (j−1) −q A quantum operation unit that applies a control phase shift of an angle 2π / 2 ^j to the bit and the j-qth bit and further applies SWAP to these q bits [where j is an odd number from 3 to g And the Hadamard transform for the 1-q bits and the computation for all j are performed in parallel for each g. When g is an even number, a control phase shift with an angle of 2π / 2 ^j is applied to the (j−1) -qth bit and the j-qth bit, and further, an operation is applied to apply SWAP to these q bits. A quantum operation unit is provided [where j is an even number from 2 to g, and operations for all j are performed in parallel for each g. ], << 2 >> For g = N−1,..., 1 in order, when g = 1, a quantum operation unit that performs an operation applying Hadamard transform to the 1-q bits is provided, and g is an odd number of 3 or more In this case, a quantum operation unit that performs an operation applying Hadamard transform to the 1-q bits is applied, and a control phase shift of angle 2π / 2 ^j is applied to the (j−1) -q bits and the j-q bits. And a quantum operation unit that performs an operation of applying SWAP to these q bits (where j is an odd number from 3 to g, the Hadamard transform for the 1st-q bits for each g and all j It is assumed that operations are performed in parallel. When g is an even number, a control phase shift with an angle of 2π / 2 ^j is applied to the (j−1) -q-th bit and the j-q-th bit, and further, an operation for applying SWAP to these q-bits is performed. A quantum operation unit is provided [where j is an even number from 2 to g, and operations for all j are performed in parallel for each g. ], << 3 >> For g = 1,..., N−1, in order, when g is an odd number, a SWAP operation unit is provided that performs an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit. [However, j is an odd number from 1 to g, and SWAP for all j is performed in parallel for each g. ], When g is an even number, a SWAP operation unit for performing an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit is provided [where j is an even number from 2 to g, and for each g It is assumed that SWAP for all j is performed in parallel. ], << 4 >> For g = N−2,..., 1, in order, when g is an odd number, a SWAP operation unit that performs an operation to apply SWAP to the j-qth bit and the (j + 1) -qth bit is provided [However, j is an odd number from 1 to g, and SWAP for all j is performed in parallel for each g. ], When g is an even number, a SWAP operation unit for performing an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit is provided [where j is an even number from 2 to g, and for each g It is assumed that SWAP for all j is performed in parallel. In the approximate quantum Fourier transform arithmetic apparatus configured as described above, the quantum arithmetic unit that performs the control phase shift of the angle 2π / 2 ^t (t> m) is replaced with the quantum arithmetic unit that performs the identity transformation, and the angle 2π / 2 ^t (t = m) SWAP immediately after the control phase shift and quantum operation unit E that performs each operation of SWAP immediately after the control phase shift determined to be an identity transformation, and in the SWAP operation unit, the quantum operation unit E Approximate quantum Fourier transform arithmetic unit configured without the mirror image symmetric quantum arithmetic unit.

  According to the present invention, an approximate threshold is set to O (logn), and an approximate quantum Fourier transform is performed with O (n) number of calculation steps and O (nlogn) number of basic operations by using a neighborhood 2 qubit operation. be able to. In addition, since the number of basic operations is reduced as compared to the prior art, the possibility of calculation errors can be reduced.

[Quantum circuit]
First, the quantum circuit (1) of the present invention that performs approximate quantum Fourier transform will be described.
The quantum circuit (1) that performs the approximate quantum Fourier transform uses a single qubit operation for a single qubit and CNOT as basic operations. The description will be made assuming that the quantum circuit is configured. It should be noted that all operations used in the quantum circuit of the present invention can be decomposed into one qubit operation for a single qubit and CNOT [see Non-Patent Document 1 above].

The quantum circuit (1) that performs the approximate quantum Fourier transform includes the non-approximate quantum Fourier transform quantum circuit (2) [see the following reference] that is not configured by the neighborhood 2-qubit operation and the above-described neighborhood 2-qubit operation. It is based on the quantum circuit (3) of the non-approximation quantum Fourier transform comprised by.
(Reference) R. Cleve and J. Watrous, "Fast parallel circuits for the quantum Fourier transform", Proc. Of the 4lst Annual Symposium on Foundations of Computer Science, pp.526-536, 2000.

First, a non-approximate quantum Fourier transform quantum circuit (2) that is not constituted by the neighborhood 2-qubit operation will be described. The quantum circuit (2) is configured to be self-similar. That is, a quantum circuit that performs non-approximation quantum Fourier transform modulo a certain X is decomposed into a quantum circuit that performs non-approximation quantum Fourier transform modulo a number smaller than X. The configuration is precisely as follows.
The quantum Fourier transform that is not approximated by the quantum circuit (2) is the quantum Fourier transform represented by the equation (3), but considering that the quantum circuit (2) is configured in a self-similar manner, A non-approximate quantum Fourier transform to be performed is denoted as QFT-SS.

[When n is an even number]
constituting from quantum circuits two performing quantum Fourier transform to n ^2/4 pieces of control phase shifting and 2 ^{n / 2} modulo.
More specifically, the two quantum circuits that perform the quantum Fourier transform modulo 2 ^{n / 2} correspond to the upper half [the upper half wiring in the quantum circuit that performs the linear quantum Fourier transform. ] Corresponding to the lower half wiring in a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} with respect to ^{n / 2} q bits, and a lower [quantum circuit that performs a linear quantum Fourier transform. ] Sequence by the quantum circuit that performs quantum Fourier transform to 2 ^{n / 2} modulo for n / 2 pieces of q bits, a quantum circuit including the n ^2/4 pieces of control phase shift, modulo 2 n ^{/ 2} The structure is sandwiched between two quantum circuits that perform quantum Fourier transform.

[When n is an odd number]
(n-1) (n + 1) / 4 control phase shift and quantum circuit for performing a quantum Fourier transform modulo 2 ^{(n + 1) / 2} and a quantum Fourier transform modulo 2 ^{(n-1) / 2} It consists of a quantum circuit to perform.
More specifically, two configurations are possible.
The first [Pattern 1] corresponds to a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n + 1) / 2} , and corresponds to an upper wiring in a quantum circuit that performs a linear quantum Fourier transform. And a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n-1) / 2} with respect to ^{(n + 1) / 2} q bits Corresponds to the lower wiring in the quantum circuit that performs linear quantum Fourier transform. ) Of (n-1) / 2 q bits, a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n-1) / 2} , and (n-1) (n + 1) / 4 control phase shifts The quantum circuit including the structure is sandwiched between a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n + 1) / 2} and a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n-1) / 2.} is there.
The second [pattern 2] corresponds to the lower wiring in the quantum circuit that performs the quantum Fourier transform modulo 2 ^{(n + 1) / 2} , and the lower [quantum circuit that performs the linear quantum Fourier transform. And a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n-1) / 2} with respect to ^{(n + 1) / 2} q bits Corresponds to the upper wiring in the quantum circuit that performs linear quantum Fourier transform. ) Of (n-1) / 2 q bits, a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n-1) / 2} , and (n-1) (n + 1) / 4 control phase shifts The quantum circuit including the structure is sandwiched between a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n + 1) / 2} and a quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n-1) / 2.} is there.

[When n = 1]
It consists only of Hadamard Gate. That is, it is configured as a quantum circuit that performs one qubit operation.

The quantum circuit of the quantum Fourier transform modulo the smaller number 2 ^B is considered to be a new n and decomposed in a self-similar manner according to the above case classification. For example, when n is an even number, a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} is considered as a new n and decomposed in a self-similar manner according to the above case classification. Configure.

Hereinafter, three specific examples of the quantum circuit (2) will be shown.
FIG. 10 shows a QFT8-SS quantum circuit (2) in the case of n = 8. The quantum circuit (2) of the QFT8-SS is a quantum circuit 2 that performs quantum Fourier transform QFT4-SS modulo 2 ^8/2 as shown in FIG. 10 according to the method described in [when n is an even number]. And 16 control phase shift gates. It should be noted that the quantum circuit (2) shown in FIG. 10 is substantially the same as the quantum circuit of the QFT 8 shown in FIG.
The quantum circuit that performs the quantum Fourier transform QFT4-SS modulo 2 ^8/2 has a quantum Fourier modulo 2 ^4/2 according to the method described in [when n is an even number], as shown in FIG. It consists of two quantum circuits that perform the transformation QFT2-SS and four control phase shift gates.
Quantum circuit for performing quantum Fourier transform QFT2-SS for the 2 ^4/2 and law, according to the method [n is an even number] described, as shown in FIG. ^12, the quantum Fourier for a ^{2 2/2} modulo It consists of two quantum circuits that perform transformation QFT1-SS and one control phase shift gate.
Quantum circuit for performing quantum Fourier transform QFT1-SS for the 2 ^2/2 and law, according to the method described in [the case of n = 1], as shown in FIG. 13, and one Hadamard gate.

FIG. 14 shows a QFT7-SS [pattern 1] quantum circuit (2) in the case of n = 7. Quantum circuit [Pattern 1] of QFT7-SS (2), according to the method described in [Pattern 1] of [if n is odd, as shown in FIG. 14, the quantum of the 2 ^8/2 modulo a quantum circuit that performs Fourier transform ^QFT4-SS, a quantum circuit that performs quantization Fourier transform QFT3-SS for the ^{2 6/2} modulo composed of twelve control phase shift gate.
The quantum circuit that performs the quantum Fourier transform QFT4-SS modulo 2 ^8/2 has a quantum Fourier modulo 2 ^4/2 according to the method described in [when n is an even number], as shown in FIG. It consists of two quantum circuits that perform the transformation QFT2-SS and four control phase shift gates.
The quantum circuit that performs the quantum Fourier transform QFT3-SS modulo 2 ^6/2 has 2 ^4/2 as shown in FIG. 15 according to the method described in [Pattern 1] of [when n is an odd number]. a quantum circuit that performs quantization Fourier transform QFT2-SS ^modulo, and a quantum circuit that performs quantization Fourier transform QFT1-SS for the ^{2 2/2} modulo composed of a two control phase shift gate.
Quantum circuit for performing quantum Fourier transform QFT2-SS for the 2 ^4/2 and law, according to the method [n is an even number] described, as shown in FIG. ^12, the quantum Fourier for a ^{2 2/2} modulo It consists of two quantum circuits that perform transformation QFT1-SS and one control phase shift gate.
Quantum circuit for performing quantum Fourier transform QFT1-SS for the 2 ^2/2 and law, according to the method described in [the case of n = 1], as shown in FIG. 13, and one Hadamard gate.

FIG. 16 shows a QFT7-SS [pattern 2] quantum circuit (2) in the case of n = 7. According to the method described in [Pattern 2] of [When n is an odd number], the quantum circuit (2) of [Pattern 2] of QFT7-SS has a quantum modulo of 2 ^6/2 as shown in FIG. a quantum circuit that performs Fourier transform ^QFT3-SS, a quantum circuit that performs quantization Fourier transform QFT4-SS for the ^{2 8/2} modulo composed of twelve control phase shift gate.
The quantum circuit that performs the quantum Fourier transform QFT4-SS modulo 2 ^8/2 has a quantum Fourier modulo 2 ^4/2 according to the method described in [when n is an even number], as shown in FIG. It consists of two quantum circuits that perform the transformation QFT2-SS and four control phase shift gates.
The quantum circuit that performs the quantum Fourier transform QFT3-SS modulo 2 ^6/2 has 2 ^2/2 as shown in FIG. 17 according to the method described in [Pattern 2] of [when n is an odd number]. a quantum circuit that performs quantization Fourier transform QFT1-SS ^modulo, and a quantum circuit that performs quantization Fourier transform QFT2-SS for the ^{2 4/2} modulo composed of a two control phase shift gate.
Quantum circuit for performing quantum Fourier transform QFT2-SS for the 2 ^4/2 and law, according to the method [n is an even number] described, as shown in FIG. ^12, the quantum Fourier for a ^{2 2/2} modulo It consists of two quantum circuits that perform transformation QFT1-SS and one control phase shift gate.
Quantum circuit for performing quantum Fourier transform QFT1-SS for the 2 ^2/2 and law, according to the method described in [the case of n = 1], as shown in FIG. 13, and one Hadamard gate.

  In the above example, in the case of [Pattern 1], it is assumed that the quantum circuit that performs the quantum Fourier transform modulo a smaller odd number is also made of [Pattern 1], and in the case of [Pattern 2] A quantum circuit that performs quantum Fourier transform modulo a smaller odd number has been described as being configured by [Pattern 2], but is not limited to such a configuration. Without being bound by the configuration pattern of a quantum circuit that performs a quantum Fourier transform modulo a larger odd number, a quantum circuit that performs a quantum Fourier transform modulo a smaller odd number can be configured with an arbitrary pattern.

  As is clear from the above examples, since the QFT-SS quantum circuit separates the operations that can be processed in one calculation step, the number of calculation steps is larger than that of the LNN-QFT quantum circuit (see FIG. 5). It has become.

As in the configuration of the quantum circuit (2), the quantum circuit (1p) that performs non-approximate quantum Fourier transform is configured. However, the configuration is different in the following points.
The first point is 2 ^m [m is an approximate threshold value. ] Self-similar decomposition is performed until a quantum circuit that performs quantum Fourier transform modulo the following number is used. For a quantum circuit that performs quantum Fourier transform modulo a number of 2 ^m or less, no further self-similar decomposition is performed. A quantum circuit that performs quantum Fourier transform modulo a number of 2 ^m or less is configured as a quantum circuit (3) of non-approximate quantum Fourier transform LNN-QFT configured by the above-described neighboring 2-qubit operation.
The second point is that the quantum circuit (2) is not a quantum circuit using the neighborhood 2 qubit operation, and is therefore a quantum circuit using the neighborhood 2 qubit operation.
The quantum Fourier transform that is not approximated by the quantum circuit (1p) is the quantum Fourier transform represented by the equation (3), but it is considered that it is configured in a self-similar manner and uses a neighboring 2-qubit operation. A quantum Fourier transform that is not approximated by the quantum circuit (1p) is denoted as LNN-QFT-SS.

The configuration of the quantum circuit (1p) will be described with reference to FIG. For convenience of explanation, FIG. 18 assumes a case where n is a power of 2. The quantum circuit (1p) that performs non-approximate quantum Fourier transform LNN-QFT-SS is decomposed in a self-similar manner. It is a schematic diagram explaining what to do. LNN controlled phase shift circuit shown in the center of FIG. 18, in the quantum circuit that performs the n q-bit quantization Fourier transform ^{LNN-QFTn-SS, n 2} /4 pieces of control appears in quantum circuit (2) This shows a quantum circuit configured such that the phase shift is a close 2-qubit operation, and details thereof will be described later. On both sides of the LNN controlled phase shift circuit shown in the center of FIG. 18, there is a quantum circuit that performs n / 2 q-bit quantum Fourier transform LNN-QFTn / 2-SS composed of neighboring 2-qubit operations. Composed.

A quantum circuit that performs LNN-QFTn / 2-SS is configured in a self-similar manner to a quantum circuit that performs LNN-QFTn-SS. The LNN controlled phase shift circuit shown in the center of the quantum circuit that performs LNN-QFTn / 2-SS is a quantum circuit that performs n / 2 q-bit quantum Fourier transform LNN-QFTn / 2-SS. represents a quantum circuit configured such that the two neighboring qubit calculates appeared was (n / 2) ^2/4 pieces of control phase shift (2). On the both sides of the LNN controlled phase shift circuit shown in the center of the quantum circuit that performs LNN-QFTn / 2-SS, (n / 2) / 2 q-bit quantum Fouriers composed of neighboring 2 qubit operations A quantum circuit that performs the conversion LNN-QFT (n / 2) / 2-SS is configured.

A quantum circuit that performs LNN-QFT (n / 2) / 2-SS is configured in a self-similar manner to a quantum circuit that performs LNN-QFTn / 2-SS. The LNN controlled phase shift circuit shown in the center of the quantum circuit performing LNN-QFT (n / 2) / 2-SS is (n / 2) / 2 q-bit quantum Fourier transform LNN-QFT (n / in quantum circuit for performing 2) / 2-SS, (it appeared in 2) ((n / 2) quantum circuit / 2) ^2/4 quanta control phase shift is constructed as a near two-qubit operations Represents a circuit. LNN-QFT (n / 2) / 2-SS is composed of two adjacent qubit operations on both sides of the LNN controlled phase shift circuit shown at the center of the quantum circuit ((n / 2) / 2) A quantum circuit is configured to perform / 2 q-bit quantum Fourier transform LNN-QFT ((n / 2) / 2) / 2-SS.

By repeating such a self-similar decomposition configuration, a quantum circuit (1p) that performs non-approximate quantum Fourier transform is configured, but quantum circuit LNN-QFTn / 2 ^d [d = 1, 2,. ] If the the m ≧ n / ^{2 d,} to stop be configured by decomposing a quantum circuit LNN-QFTn / ^{2 d} in a self-similar. That is, quantum circuits LNN-QFTn / ^{2 d} is configured as a quantum circuit (3).

  Here, for convenience of explanation, the case where n is a power of 2 has been described. However, in the case where n is generally an even number or an odd number, the above two different points are taken into consideration. The quantum circuit (1p) can be configured in the same manner as the configuration of (2).

Therefore, a method for constructing the quantum circuit (1p) by dividing it into a case where n is an even number and a case where it is an odd number will be described.
The state of the n q bits input to the quantum circuit _{(1p) | b n-1} >, ..., | a _{b 0>,} the 1-q bits each q bits in sequence, ..., the n-q I'll call it a bit. That is, the q bit corresponding to the uppermost wiring is the 1-q bit, and the q bit corresponding to the lowest wiring is the n-q bit. For convenience of description, it is also described as the (·) -q bit.

[When n is an even number]
<< 1 >> For the 1st to qth bits to the (n / 2) th to qth bits, a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} configured by a neighboring 2 qubit operation is applied.

<< 2 >> For g = 2,..., N / 2 + 1, a quantum circuit that sequentially performs the following operations is used. A control phase shift with an angle of 2π / 2 ^g is applied to the (n / 2−g + 2j) −q bits and the (n / 2−g + 2j + 1) −q bits, and SWAP is applied to these q bits. However, it is assumed that j = 1,..., G−1, and operations for all j are performed in parallel for each g. The increase in the number of calculation steps is suppressed by calculating in parallel [the same applies hereinafter].

<< 3 >> For g = n / 2 + 2,..., N, a quantum circuit that sequentially performs the following operations is used. Apply a control phase shift of angle 2π / 2 ^{g to} the (g−n / 2 + 2j−2) -q bits and (g−n / 2 + 2j−1) −q bits, and apply SWAP to these q bits To do. However, j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g.
Note that the last SWAP when g = n is offset with the first SWAP of << 4 >> below.

<< 4 >> For g = n,..., N / 2 + 2, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the (g−n / 2 + 2j−2) −q bit and the (g−n / 2 + 2j−1) −q bit. However, j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g.

<< 5 >> For g = n / 2 + 1,..., 2, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the (n / 2−g + 2j) −qth bit and the (n / 2−g + 2j + 1) −qth bit. However, j = 1,..., G−1, and calculations for all j are performed in parallel for each g.

<< 6 >> For the (n / 2 + 1) -q-th bit to the n-q-th bit, a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} constituted by neighboring 2-qubit operations is applied.

[When n is an odd number]
Specifically, two configurations are possible.

(Pattern 1)
<< 1 >> A quantum circuit that performs a quantum Fourier transform modulo 2 ^{(n + 1) / 2} composed of neighboring 2-qubit operations is applied from the 1st to qth bits to the ((n + 1) / 2) -q bits. To do.

<< 2 >> For g = 2,..., (N + 1) / 2, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the ((n + 1) / 2−g + 2j) −q bits and the ((n + 1) / 2−g + 2j + 1) −q bits, and SWAP is applied to these q bits. To do. However, j = 1,..., G−1, and calculations for all j are performed in parallel for each g.

<< 3 >> For g = (n + 1) / 2 + 1,..., N, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the (g− (n + 1) / 2 + 2j−2) −q bits and the (g− (n + 1) / 2 + 2j−1) bits, and SWAP is applied to these q bits. Apply. However, j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g.
Note that the last SWAP when g = n is offset with the first SWAP of << 4 >> below.

<< 4 >> For g = n,..., (N + 1) / 2 + 1, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the (g− (n + 1) / 2 + 2j−2) −q bits and the (g− (n + 1) / 2 + 2j−1) −q bits. However, j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g.

<< 5 >> For g = (n + 1) / 2,..., 2, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the ((n + 1) / 2−g + 2j) −q bits and the ((n + 1) / 2−g + 2j + 1) −q bits. However, j = 1,..., G−1, and calculations for all j are performed in parallel for each g.

<< 6 >> Quantum circuit that performs quantum Fourier transform modulo 2 ^{(n−1) / 2} , which is constituted by neighboring 2 qubit operations for the (n + 1) / 2 + 1) -q bits to the n-q bits Apply.

(Pattern 2)
<< 1 >> Quantum Fourier transform modulo 2 ^{(n-1) / 2} composed of neighboring 2-qubit operations is performed from the 1-q bit to the ((n-1) / 2) -q bit. Apply quantum circuits.

<< 2 >> For g = 2,..., (N + 1) / 2, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the ((n + 1) / 2−g + 2j−1) −q bits and the ((n + 1) / 2−g + 2j) −q bits, and SWAP is applied to these q bits. Apply. However, j = 1,..., G−1, and calculations for all j are performed in parallel for each g.

<< 3 >> For g = (n + 1) / 2 + 1,..., N, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) bits, and SWAP is applied to these q bits. To do. However, j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g.
Note that the last SWAP when g = n is offset with the first SWAP of << 4 >> below.

<< 4 >> For g = n,..., (N + 1) / 2 + 1, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) −q bits. However, j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g.

<< 5 >> For g = (n + 1) / 2,..., 2, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the ((n + 1) / 2−g + 2j−1) −q bits and the ((n + 1) / 2−g + 2j) −q bits. However, j = 1,..., G−1, and calculations for all j are performed in parallel for each g.

<< 6 >> Quantum circuit that performs quantum Fourier transform modulo 2 ^{(n + 1) / 2} composed of neighboring 2-qubit operations from the ((n-1) / 2 + 1) -q bit to the n-q bit Apply.

[When n = 1]
Apply Hadamard transform to 1-q bits.

The quantum Fourier transform quantum circuit modulo the number 2 ^B smaller than 2 ^{n and} larger than 2 ^m is considered to be a new n and decomposed in a self-similar manner according to the above case classification. To do. For example, when n is an even number, a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} is considered as a new n and decomposed in a self-similar manner according to the above case classification. Configure.

Note that no further self-similar decomposition is performed for quantum circuits that perform quantum Fourier transform modulo a number of 2 ^m or less. A quantum circuit that performs quantum Fourier transform modulo a number of 2 ^m or less is configured as a quantum circuit (3) of non-approximate quantum Fourier transform LNN-QFT configured by the above-described neighboring 2-qubit operation.

Hereinafter, three specific examples of the quantum circuit (1p) are shown.
FIG. 19 shows a quantum circuit (1p) of LNN-QFT8-SS where n = 8. The quantum circuit (1p) of the LNN-QFT8-SS is configured as follows according to the method described in [when n is an even number].
"1" for the first 1-q bit to the (8/2) -q bits, a quantum circuit that performs quantization Fourier transform LNN-QFT4-SS modulo ^{2 8/2} constructed near two-qubit operations [Quantum circuit indicated by symbol α1 in FIG. 19]. A quantum circuit that performs LNN-QFT4-SS is configured according to the method described in [when n is an even number].
<< 2 >> For g = 2,..., 8/2 + 1, a quantum circuit that performs the following operation is configured. A control phase shift of an angle 2π / 2 ^g is applied to the (8 / 2−g + 2j) −q bits and the (8 / 2−g + 2j + 1) −q bits, and SWAP is applied to these q bits [FIG. Quantum circuit indicated by α2 in FIG. However, j = 1,..., G−1, and the calculation for all j is performed in parallel for each g. That is, in FIG. 19, for example, a portion surrounded by a solid line can be calculated in parallel in one calculation step, and the others are the same.
<< 3 >> For g = 8/2 + 2,..., 8, a quantum circuit that performs the following operation is configured. The (g-8/2 + 2j -2) -q bit and the (g-8/2 + 2j -1) to -q bits by applying the control phase shift angle 2π / ^{2 g,} further applying SWAP to these q bits [Quantum circuit indicated by symbol α3 in FIG. 19]. However, it is set as j = 1, ..., 8 + 1-g, and the calculation about all j is performed in parallel for every g. The last SWAP in the case of g = 8 is canceled out with the first SWAP of the next << 4 >>, but in FIG. 19, it is intentionally left for convenience of explanation.
<< 4 >> For g = 8,..., 8/2 + 2, a quantum circuit that performs the following calculation is configured. SWAP is applied to the (g−8 / 2 + 2j−2) −q bits and the (g−8 / 2 + 2j−1) −q bits [quantum circuit indicated by symbol α4 in FIG. 19]. However, it is set as j = 1, ..., 8 + 1-g, and the calculation about all j is performed in parallel for every g.
<< 5 >> For g = 8/2 + 1,..., 2, a quantum circuit that performs the following operation is configured. SWAP is applied to the (8 / 2−g + 2j) −qth bit and the (8 / 2−g + 2j + 1) −qth bit [quantum circuit indicated by α5 in FIG. 19]. However, j = 1,..., G−1, and the calculation for all j is performed in parallel for each g.
<< 6 >> A quantum circuit that performs a quantum Fourier transform LNN-QFT4-SS modulo 2 ^8/2 composed of neighboring 2 qubit operations from the ( ^8/2 + 1) -q bit to the 8-q bit [Quantum circuit indicated by α6 in FIG. 19]. A quantum circuit that performs LNN-QFT4-SS is configured according to the method described in [when n is an even number].

FIG. 20 shows a quantum circuit (1p) of (pattern 1) of LNN-QFT7-SS in the case of n = 7. The quantum circuit (1p) of (pattern 1) of LNN-QFT7-SS is configured as follows according to the method described in (pattern 1) of [when n is an odd number].
<< 1 >> Quantum Fourier transform LNN-QFT4-SS modulo 2 ^{(7 + 1) / 2} is performed from the 1-qth bit to the ((7 + 1) / 2) -q-bit using neighborhood 2 qubit operations. A quantum circuit to be performed is configured [quantum circuit indicated by symbol β1 in FIG. 20]. A quantum circuit that performs LNN-QFT4-SS is configured according to the method described in [when n is an even number].
<< 2 >> For g = 2,..., (7 + 1) / 2, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the ((7 + 1) / 2−g + 2j) −q bits and the ((7 + 1) / 2−g + 2j + 1) −q bits, and SWAP is applied to these q bits. [Quantum circuit indicated by symbol β2 in FIG. 20]. However, j = 1,..., G−1, and the calculation for all j is performed in parallel for each g.
<< 3 >> For g = (7 + 1) / 2 + 1,..., 7, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the (g− (7 + 1) / 2 + 2j−2) −q bits and the (g− (7 + 1) / 2 + 2j−1) bits, and SWAP is applied to these q bits. [Quantum circuit indicated by symbol β3 in FIG. 20]. However, j = 1,..., N + 1−g, and the calculation for all j is performed in parallel for each g. The last SWAP in the case of g = 7 is offset with the first SWAP of the next << 4 >>. However, in FIG.
<< 4 >> For g = 7,..., (7 + 1) / 2 + 1, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the (g− (7 + 1) / 2 + 2j−2) −q bits and the (g− (7 + 1) / 2 + 2j−1) −q bits [quantum circuit indicated by symbol β4 in FIG. 20]. However, j = 1,..., N + 1−g, and the calculation for all j is performed in parallel for each g.
<< 5 >> For g = (7 + 1) / 2,..., 2, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the ((7 + 1) / 2−g + 2j) −q bit and the ((7 + 1) / 2−g + 2j + 1) −q bit (quantum circuit indicated by the symbol β5 in FIG. 20). However, j = 1,..., G−1, and the calculation is performed in parallel for all j for each g.
<< 6 >> Quantum circuit performing quantum Fourier transform modulo 2 ^{(7-1) / 2} using the neighboring 2-qubit operation from the ((7 + 1) / 2 + 1) -q bit to the 7-q bit LNN-QFT3-SS is configured [quantum circuit indicated by symbol β6 in FIG. 20]. A quantum circuit that performs LNN-QFT3-SS is configured according to the method described in [when n is an odd number].

FIG. 21 shows a (pattern 2) quantum circuit (1p) of LNN-QFT7-SS in the case of n = 7. The quantum circuit (1p) of (pattern 2) of LNN-QFT7-SS is configured as follows according to the method described in (pattern 2) of [when n is an odd number].
<< 1 >> Quantum Fourier transform LNN- modulo 2 ^{(7-1) / 2} using the neighboring 2-qubit operation from the 1-q bit to the ((7-1) / 2) -q bit A quantum circuit that performs QFT3-SS is configured [quantum circuit indicated by symbol γ1 in FIG. 21]. A quantum circuit that performs LNN-QFT3-SS is configured according to the method described in [when n is an odd number].
<< 2 >> For g = 2,..., (7 + 1) / 2, a quantum circuit that sequentially performs the following operations is used. A control phase shift of angle 2π / 2 ^g is applied to the ((7 + 1) / 2−g + 2j−1) −q bits and the ((7 + 1) / 2−g + 2j) −q bits, and SWAP is applied to these q bits. [Quantum circuit indicated by γ2 in FIG. 21]. However, j = 1,..., G−1, and the calculation for all j is performed in parallel for each g.
<< 3 >> For g = (7 + 1) / 2 + 1,..., 7, a quantum circuit that sequentially performs the following operations is used. Apply a control phase shift of angle 2π / 2 ^{g to} the (g− (7 + 1) / 2 + 2j−1) −q bits and the (g− (7 + 1) / 2 + 2j) bits, and apply SWAP to these q bits. [Quantum circuit indicated by symbol γ3 in FIG. 21]. However, j = 1,..., N + 1−g, and the calculation for all j is performed in parallel for each g. The last SWAP in the case of g = 7 is canceled out with the first SWAP of the next << 4 >>, but in FIG. 21 it is left for convenience of explanation.
<< 4 >> For g = 7,..., (7 + 1) / 2 + 1, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the (g− (7 + 1) / 2 + 2j−1) −q bits and the (g− (7 + 1) / 2 + 2j) −q bits [quantum circuit indicated by reference numeral γ4 in FIG. 21]. However, j = 1,..., N + 1−g, and the calculation for all j is performed in parallel for each g.
<< 5 >> For g = (7 + 1) / 2,..., 2, a quantum circuit that sequentially performs the following operations is used. SWAP is applied to the ((7 + 1) / 2−g + 2j−1) −q bits and the ((7 + 1) / 2−g + 2j) −q bits (quantum circuit indicated by reference numeral γ5 in FIG. 21). However, j = 1,..., G−1, and the calculation for all j is performed in parallel for each g.
<< 6 >> Quantum circuit that performs quantum Fourier transform modulo 2 ^{(7 + 1) / 2} using the neighboring 2-qubit operation from the ((7-1) / 2 + 1) -q bit to the 7-q bit LNN-QFT4-SS is configured [quantum circuit indicated by symbol γ6 in FIG. 21]. A quantum circuit that performs LNN-QFT4-SS is configured according to the method described in [when n is an even number].

  In the above example, when configured with (Pattern 1), the quantum circuit that performs the quantum Fourier transform modulo a smaller odd number is also configured with (Pattern 1), and when configured with (Pattern 2) Although the quantum circuit that performs the quantum Fourier transform modulo the smaller odd number has been described as being configured by (pattern 2), it is not limited to such a configuration. Without being bound by the configuration pattern of a quantum circuit that performs a quantum Fourier transform modulo a larger odd number, a quantum circuit that performs a quantum Fourier transform modulo a smaller odd number can be configured with an arbitrary pattern.

  A method of configuring the quantum circuit (1) that performs the approximate quantum Fourier transform LNN-AQFT-SS from the quantum circuit (1p) that performs the quantum Fourier transform LNN-QFT-SS that is not approximate will be described. Generally, the approximate threshold value m is about O (logn).

In the quantum circuit (1p) that performs LNN-QFT-SS, the control phase shift of the angle 2π / 2 ^t (t> m) is replaced with the identity transformation. Accordingly, the SWAP immediately after the control phase shift gate having an angle of 2π / 2 ^t (t = m) and the SWAP immediately after the control phase shift gate assumed to be an identity transformation are described in the configuration method of the quantum circuit (1p). In any case, the entire quantum circuit is simplified by canceling out a part of the SWAP of the quantum circuit portion composed only of the SWAP configured by << 4 >> and << 5 >>. That is, the quantum circuit C that performs each calculation of the SWAP immediately after the control phase shift of the angle 2π / 2 ^t (t = m) and the SWAP immediately after the control phase shift that is assumed to be an identity transformation, and the quantum circuit (1p) In any case described in the configuration method, in the quantum circuit including only SWAP configured by << 4 >> and << 5 >>, the mirror-symmetrical quantum circuit portion of the quantum circuit C is canceled.
The quantum circuit obtained by this processing is the quantum circuit (1) that performs LNN-AQFT-SS.
In this quantum circuit (1), the lower limit of the approximation threshold is O (logn), and the approximate quantum is calculated using the number of calculation steps of O (n) and the basic calculation of O (nlogn) using the neighboring 2-qubit operation. The Fourier transform is performed.

Hereinafter, three specific examples of the quantum circuit (1) that performs LNN-AQFT-SS will be described.
Here, from the viewpoint of facilitating comparison with FIG. 9, the approximate threshold value m is exemplified as 5.

FIG. 22 shows a quantum circuit (1) that performs LNN-AQFT8-SS corresponding to FIG.
Since the control phase shift corresponding to t = 6, 7, and 8 is regarded as an identity transformation, the last four SWAPs (rightmost) of the quantum circuit indicated by the symbol α2 and the six quantum circuits indicated by the symbol α3 The SWAP is canceled with the 10 SWAPs of the quantum circuit indicated by the symbol α4. As apparent from the comparison with FIG. 9, the SWAP is offset and reduced, resulting in a quantum circuit in which the number of basic operations is reduced as compared with the conventional circuit.
In FIG. 22, the quantum circuit that performs the quantum Fourier transform modulo a smaller number is specifically represented as LNN-AQFT4-SS, but since the approximate threshold value m is 5, The quantum circuit performs LNN-QFT4. The quantum circuit that performs this LNN-QFT4 is configured in the same manner as in the prior art, and is a quantum circuit (3) of non-approximate quantum Fourier transform that is configured by neighboring 2-qubit operations.
If m is 3, a quantum circuit that performs LNN-AQFT4-SS may be further configured to be self-similar, and at this time, a quantum circuit that performs LNN-AQFT2-SS appears, but 2 <3. Therefore, a quantum circuit that performs LNN-QFT2 may be used. That is, the quantum circuit (1) that performs LNN-AQFT8-SS includes four quantum circuits that perform LNN-QFT2 and three LNN controlled phase shift circuits.

FIG. 23 shows a quantum circuit (1) that performs LNN-AQFT7-SS corresponding to FIG. Since the control phase shift corresponding to t = 6, 7, and 8 is regarded as an identity transformation, the six SWAPs of the quantum circuit indicated by the symbol β3 are canceled with the six SWAPs of the quantum circuit indicated by the symbol β4. .
In FIG. 23, the quantum circuits that perform the quantum Fourier transform modulo a smaller number are specifically represented as LNN-AQFT4-SS and LNN-AQFT3-SS, but the approximate threshold value m is 5. Therefore, to be precise, a quantum circuit that performs LNN-QFT4 and a quantum circuit that performs LNN-QFT3, respectively. The quantum circuit for performing LNN-QFT4 and the quantum circuit for performing LNN-QFT3 are configured in the same manner as in the prior art, and are not approximate quantum quantum transform quantum circuits (3) configured by neighboring 2-qubit operations. It is.
If m is 3, a quantum circuit that performs LNN-AQFT4-SS may be further configured to be self-similar, and at this time, a quantum circuit that performs LNN-AQFT2-SS appears, but 2 <3. Therefore, a quantum circuit that performs LNN-QFT2 may be used. That is, the quantum circuit (1) that performs LNN-AQFT7-SS includes two quantum circuits that perform LNN-QFT2, a quantum circuit that performs LNN-QFT3, and two LNN controlled phase shift circuits.

FIG. 24 shows a quantum circuit (1) that performs LNN-AQFT7-SS corresponding to FIG. Since the control phase shift corresponding to t = 6, 7, and 8 is regarded as an identity transformation, the six SWAPs of the quantum circuit indicated by the symbol β3 are canceled with the six SWAPs of the quantum circuit indicated by the symbol β4. .
In FIG. 24, the quantum circuits that perform the quantum Fourier transform modulo a smaller number are specifically described as LNN-AQFT3-SS and LNN-AQFT4-SS, but the approximate threshold value m is set to 5. Therefore, to be precise, a quantum circuit that performs LNN-QFT3 and a quantum circuit that performs LNN-QFT4, respectively. The quantum circuit that performs the LNN-QFT3 and the quantum circuit that performs the LNN-QFT4 are configured in the same manner as in the past, and are non-approximate quantum Fourier transform quantum circuits (3) configured by neighboring 2-qubit operations. It is.
If m is 3, a quantum circuit that performs LNN-AQFT4-SS may be further configured to be self-similar, and at this time, a quantum circuit that performs LNN-AQFT2-SS appears, but 2 <3. Therefore, a quantum circuit that performs LNN-QFT2 may be used. That is, the quantum circuit (1) that performs LNN-AQFT7-SS includes two quantum circuits that perform LNN-QFT2, a quantum circuit that performs LNN-QFT3, and two LNN controlled phase shift circuits.

  Here, FIG. 25 shows a quantum circuit that performs LNN-QFT4, and FIG. 26 shows a quantum circuit that performs LNN-QFT3. The configuration of these quantum circuits (3) is as already described in the background art.

[Quantum calculation method]
Next, a quantum operation method in the quantum circuit (1) of the present invention will be described.
As is apparent from the configuration method of the quantum circuit (1), in general, a quantum circuit that performs a quantum Fourier transform on an odd number of q bits is generated in the process of decomposition. Therefore, the quantum circuit of the present invention for n q bits Cannot be determined uniquely.
Therefore, here, as an example, a quantum operation method in the quantum circuit (1) that performs the LNN-AQFT8-SS illustrated in FIG. 22 will be described. The input state is | b ₇ b ₆ ... B ₁ b ₀ >. | b ₇ > is the state of the 1st-q bit, | b ₆ > is the state of the 2nd-q bit, abbreviated, | b ₁ > is the state of the 7th-q bit, and | b ₀ > Is the state of the 8-q bit.
In general, operations according to a quantum circuit are performed in time series from the input side to the output side, and all operations that can be performed in parallel are calculated in one calculation step.

Step S1
Apply Hadamard transform to 1-q bits.

Step S2
A control phase shift with an angle of 2π / 2 ² is applied to the 1-q bit and the 2-q bit, and SWAP is applied to these q bits.

Step S3
Apply Hadamard transform to 1-q bits. A control phase shift with an angle of 2π / 2 ³ is applied to the 2nd-q bit and the 3rd-q bit, and SWAP is applied to these q bits. However, these operations are performed in parallel.

Step S4
A control phase shift with an angle of 2π / 2 ² is applied to the 1-q bit and the 2-q bit, and SWAP is applied to these q bits. A control phase shift with an angle of 2π / 2 ⁴ is applied to the 3rd-qth bit and the 4th-qth bit, and SWAP is further applied to these qbits. However, these operations are performed in parallel.

Step S5
Apply Hadamard transform to 1-q bits. A control phase shift with an angle of 2π / 2 ³ is applied to the 2nd-q bit and the 3rd-q bit, and SWAP is applied to these q bits. However, these operations are performed in parallel.

Step S6
A control phase shift with an angle of 2π / 2 ² is applied to the 1-q bit and the 2-q bit, and SWAP is applied to these q bits.

Step S7
Apply Hadamard transform to 1-q bits.

Step S8
SWAP is applied to the first-q bits and the second-q bits.

Step S9
SWAP is applied to the 2nd-qth bit and the 3rd-qth bit.

Step S10
SWAP is applied to the first-q bits and the second-q bits. SWAP is applied to the 3rd-qth bit and the 4th-qth bit. However, these operations are performed in parallel.

Step S11
SWAP is applied to the 2nd-qth bit and the 3rd-qth bit.

Step S12
SWAP is applied to the first-q bits and the second-q bits.

Step S13
A control phase shift of angle 2π / 2 ² is applied to the 4th-qth bit and the 5th-qth bit, and SWAP is further applied to these qbits.

Step S14
A control phase shift with an angle of 2π / 2 ³ is applied to the 3rd-qth bit and the 4th-qth bit, and SWAP is further applied to these qbits. A control phase shift with an angle of 2π / 2 ³ is applied to the 5th-q bit and the 6th-q bit, and SWAP is applied to these q bits. However, these operations are performed in parallel.

Step S15
A control phase shift of angle 2π / 2 ⁴ is applied to the 2nd-q bit and the 3rd-q bit, and SWAP is applied to these q bits. Apply the control phase shift of the angle 2 [pi / 2 ⁴ to a 4-q-bit and the 5-q bits, to further apply SWAP to these q bits. A control phase shift with an angle of 2π / 2 ⁴ is applied to the 6th-qth bit and the 7th-qth bit, and SWAP is applied to these q bits. However, these operations are performed in parallel.

Step S16
A control phase shift with an angle of 2π / ²⁵ is applied to the 1-q bit and the 2-q bit. A control phase shift of an angle 2π / ²⁵ is applied to the 3rd-qth bit and the 4th-qth bit. A control phase shift of an angle 2π / ²⁵ is applied to the 5th-qth bit and the 6th-qth bit. A control phase shift of an angle 2π / ²⁵ is applied to the 7th-qth bit and the 8th-qth bit. However, these operations are performed in parallel.

Step S17
SWAP is applied to the 2nd-qth bit and the 3rd-qth bit. SWAP is applied to the 4th-qth bit and the 5th-qth bit. SWAP is applied to the 6th-qth bit and the 7th-qth bit. However, these operations are performed in parallel.

Step S18
SWAP is applied to the 3rd-qth bit and the 4th-qth bit. SWAP is applied to the 5th-qth bit and the 6th-qth bit. However, these operations are performed in parallel.

Step S19
SWAP is applied to the 4th-qth bit and the 5th-qth bit.

Step S20
Apply Hadamard transform to the 5th-qth bit.

Step S21
A control phase shift with an angle of 2π / 2 ² is applied to the 5th to qth bits and the 6th to qth bits, and SWAP is applied to these q bits.

Step S22
Apply Hadamard transform to the 5th-qth bit. A control phase shift with an angle of 2π / 2 ³ is applied to the 6th-qth bit and the 7th-qth bit, and SWAP is applied to these qbits. However, these operations are performed in parallel.

Step S23
A control phase shift with an angle of 2π / 2 ² is applied to the 5th to qth bits and the 6th to qth bits, and SWAP is applied to these q bits. A control phase shift with an angle of 2π / 2 ⁴ is applied to the 7th-qth bit and the 8th-qth bit, and SWAP is applied to these q bits. However, these operations are performed in parallel.

Step S24
Apply Hadamard transform to the 5th-qth bit. A control phase shift with an angle of 2π / 2 ³ is applied to the 6th-qth bit and the 7th-qth bit, and SWAP is applied to these qbits. However, these operations are performed in parallel.

Step S25
A control phase shift with an angle of 2π / 2 ² is applied to the 5th to qth bits and the 6th to qth bits, and SWAP is applied to these q bits.

Step S26
Apply Hadamard transform to the 5th-qth bit.

Step S27
SWAP is applied to the 5th-qth bit and the 6th-qth bit.

Step S28
SWAP is applied to the 6th-qth bit and the 7th-qth bit.

Step S29
SWAP is applied to the 5th-qth bit and the 6th-qth bit. SWAP is applied to the 7th-qth bit and the 8th-qth bit. However, these operations are performed in parallel.

Step S30
SWAP is applied to the 6th-qth bit and the 7th-qth bit.

Step S31
SWAP is applied to the 5th-qth bit and the 6th-qth bit.

[Quantum arithmetic unit]
Next, a quantum arithmetic device that performs approximate quantum Fourier transform in accordance with the quantum circuit of the present invention will be described. As is apparent from the quantum circuit of the present invention, the quantum arithmetic device of the present invention includes a quantum arithmetic unit that performs a quantum Fourier transform modulo a number smaller than n, a quantum arithmetic unit that performs a SWAP operation, or a conventional quantum circuit. In (3), a quantum computation unit that performs quantum Fourier transform is used. Further, these quantum operation units include a quantum operation unit that performs a 1-qubit operation and a quantum operation unit that performs a neighboring 2-qubit operation. That is, the quantum gate shown in the quantum circuit of the present invention corresponds to the quantum operation unit of the quantum operation device.

  The quantum arithmetic unit can be realized by 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 ".

<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. ”) is used. 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, by performing operations such as Walsh Hadamard transform, CNOT, rotation, etc. realized by a beam splitter, a polarization rotation element, etc. on a single photon generated by parametric down conversion, etc., the above initial quantum state is generated. 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), http: //www.snf.unsw edu.au/, 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.

  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. The various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes.

By the way, the procedure itself for performing the quantum operation according to the quantum circuit of the present invention can be determined by a classical computer.
In other words, the procedure for performing the quantum operation in accordance with the quantum circuit of the present invention is each calculation step for sequentially performing the quantum circuit of the present invention from the input side toward the output side, so after configuring the quantum circuit of the present invention, Each calculation step performed in order from the input side to the output side of the quantum circuit can be determined as a procedure for performing the quantum operation.

Specifically, for example, taking the quantum circuit shown in FIG. 19 as an example, a procedure for performing a quantum operation in each quantum circuit of codes α1 to α6 is determined (this procedure is based on each quantum of codes α1 to α6 described above). However, the quantum circuits denoted by reference signs α1 and α6 are decomposed in a self-similar manner to be repeated in any case (as described above in any case). By replacing the control phase shift of 2π / 2 ^t (t> m) with the identity transformation, the procedure for performing the quantum operation determined by each quantum circuit is excluded, and the procedure for performing the quantum operation determined by each quantum circuit is excluded. By arranging the steps in order from the input side to the output side of the circuit (corresponding to FIG. 22 in this example), the procedure for performing the quantum operation in accordance with the quantum circuit of the present invention can be determined. However, if parallel calculation is possible in one calculation step, one procedure may be used to perform these calculations in parallel.
In other words, it can be said that this classical computer determines and outputs the procedure of steps S1 to S31 shown in FIGS.

Such a classical computer, that is, an approximate quantum Fourier transform calculation procedure determination device for determining a quantum calculation procedure in a quantum circuit that performs the approximate quantum Fourier transform of the present invention is realized by a so-called classic device configuration. For example, as exemplified by a personal computer, a storage device (eg, RAM, ROM, hard disk), an arithmetic processing device (eg, CPU), an input / output device (eg, keyboard, display), and data can be exchanged between these devices. It can be realized by a classic computer equipped with a bus connected to the.
In this case, for example, in the example of FIG. 19, each program for determining the procedure for performing the quantum operation in each of the quantum circuits denoted by reference numerals α1 to α6, the control phase shift of the angle 2π / 2 ^t (t> m) is converted to the identity. The input side of the quantum circuit (corresponding to FIG. 22 in this example) that has completed the procedure for performing the quantum operation determined by each quantum circuit and the program for excluding the calculation procedure of SWAP to be canceled Is stored in a program storage device for arranging the steps in order from the output side to the output side, and the arithmetic processing device reads the program and interprets and executes it as necessary, whereby the quantum operation in each quantum circuit of codes α1 to α6 Each function for determining the procedure to perform the function, a function to replace the control phase shift of the angle 2π / 2 ^t (t> m) with the identity transformation and exclude the calculation procedure of the canceled SWAP The function of arranging the procedures in order from the input side to the output side of the quantum circuit that has completed the procedure for performing the quantum operation determined in each quantum circuit is realized. Each program can also be recorded on a computer-readable recording medium (for example, CD-R, DVD-RAM, MO).

  As a field of application of the present invention, for example, it is used for phase estimation and quantum cryptography.

28. Quantum circuit that performs non-approximation quantum Fourier transform modulo ⁸ (conventional example). Quantum circuit of Hadamard transform. Control phase shift quantum circuit. Control phase shift quantum circuit. Using Near 2 qubit operations, quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ⁸ modulo (conventional example). SWAP quantum circuit. CNOT quantum circuit. INV quantum circuit. As 5 a threshold of approximation Using Near 2 qubit operations, quantum circuit for performing an approximate quantum Fourier transform of the 2 ⁸ modulo (conventional example). Was constructed self-similar manner decompose, quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ⁸ modulo. Was constructed by self-similar degraded, 2 ⁴ quantum circuit that performs quantization Fourier transform is not an approximation modulo. Was constructed by self-similar decomposed quantum circuit that performs quantization Fourier transform is not an approximation to 2 modulo ^2. Was constructed by self-similar decomposed quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ¹ modulo. Was constructed by self-similar decomposed quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ⁷ modulo [Pattern 1]. Was constructed by self-similar decomposed quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ³ mod [Pattern 1]. Was constructed by self-similar decomposed quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ⁷ modulo [Pattern 2]. Was constructed by self-similar decomposed quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ³ modulo [Pattern 2]. 1 is a conceptual diagram of a quantum circuit according to the present invention. Was constructed self-similar manner decompose, quantum circuit that performs quantization Fourier transform is not an approximation modulo 2 ⁸ Using Near 2 qubit operations. Was constructed self-similar manner decompose, quantum circuit that performs quantization Fourier transform is not an approximation modulo 2 ⁷ Using Near 2 qubit operation (Pattern 1). Was constructed self-similar manner decompose, quantum circuit that performs quantization Fourier transform is not an approximation modulo 2 ⁷ Using Near 2 qubit operation (Pattern 2). As 5 a threshold approximation was constructed decomposed in a self-similar, quantum circuit that performs quantization Fourier transform is not an approximation modulo 2 ⁸ Using Near 2 qubit operations. As 5 a threshold approximation was constructed decomposed in a self-similar, quantum circuit that performs quantization Fourier transform is not an approximation modulo 2 ⁷ Using Near 2 qubit operation (Pattern 1). As 5 a threshold approximation was constructed decomposed in a self-similar, quantum circuit that performs quantization Fourier transform is not an approximation modulo 2 ⁷ Using Near 2 qubit operation (Pattern 2). Using Near 2 qubit operations, 2 ⁴ quantum circuit that performs quantization Fourier transform is not an approximation modulo. Using Near 2 qubit operations, quantum circuit that performs quantization Fourier transform is not an approximation to the 2 ³ modulo. FIG. 23 is a flowchart (No. 1) of a quantum operation method in the quantum circuit shown in FIG. 22; FIG. 23 is a flow diagram of a quantum operation method in the quantum circuit shown in FIG. 22 (part 2); FIG. 23 is a flowchart of a quantum operation method in the quantum circuit shown in FIG. 22 (part 3); FIG. 23 is a flowchart (No. 4) of a quantum operation method in the quantum circuit shown in FIG. 22; FIG. 23 is a flowchart (No. 5) of a quantum operation method in the quantum circuit shown in FIG. 22; FIG. 23 is a flowchart (No. 6) of a quantum operation method in the quantum circuit shown in FIG. 22;

Explanation of symbols

1 Quantum circuit that performs approximate quantum Fourier transform

Claims (3)

A quantum circuit that performs an approximate quantum Fourier transform modulo 2 ⁿ with an approximate threshold value being a positive integer m smaller than a positive integer n,
For the 1st-q bits, which are n q bits,..., the n-q bits,
If n is an even number,
<< 1 >> Construct a quantum circuit that performs quantum Fourier transform modulo 2 ^{n / 2} composed of neighboring 2 qubit operations from 1-q bit to (n / 2) -q bit,
<< 2 >> For g = 2,..., N / 2 + 1, the control phase shift of angle 2π / 2 ^g is sequentially applied to the (n / 2−g + 2j) −q bit and the (n / 2−g + 2j + 1) −q bit. And a quantum circuit that performs an operation of applying SWAP to these q bits [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. And ],
<< 3 >> For g = n / 2 + 2,..., N, an angle of 2π / 2 ^g is formed in order from the (g−n / 2 + 2j−2) −q bit to the (g−n / 2 + 2j−1) −q bit. A quantum circuit that performs an operation of applying a control phase shift and applying SWAP to these q bits is configured [where j = 1,..., N + 1−g, and operations for all j are parallelized for each g. The quantum circuit is ],
<< 4 >> For g = n,..., N / 2 + 2, operations for applying SWAP to the (g−n / 2 + 2j−2) −q bits and the (g−n / 2 + 2j−1) −q bits in order are performed. A SWAP quantum circuit to be performed is configured [where j = 1,..., N + 1−g, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 5 >> For g = n / 2 + 1,..., 2, a SWAP quantum circuit that performs an operation to apply SWAP to the (n / 2−g + 2j) −q bits and the (n / 2−g + 2j + 1) −q bits in order. [Where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ],
<6> Construct a quantum circuit that performs a quantum Fourier transform modulo 2 ^{n / 2} composed of neighboring 2 qubit operations from the (n / 2 + 1) -q bit to the n-q bit,
If n is odd,
In either pattern 1 or pattern 2,
(Pattern 1)
<< 1 >> Constructs a quantum circuit that performs quantum Fourier transform modulo 2 ^{(n + 1) / 2} , which is composed of neighboring 2 qubit operations, from 1-q bit to ((n + 1) / 2) -q bit And
<< 2 >> For g = 2,..., (N + 1) / 2, the angle is 2π / 2 in order of the ((n + 1) / 2−g + 2j) −q bit and the ((n + 1) / 2−g + 2j + 1) −q bit. ^A quantum circuit that performs an operation of applying a control phase shift of ^g and applying SWAP to these q bits is configured [where j = 1,..., g−1, and operations for all j are performed for each g. Is a quantum circuit that performs in parallel. ],
<< 3 >> With respect to g = (n + 1) / 2 + 1,..., N, the angle 2π between the (g− (n + 1) / 2 + 2j−2) −q bits and the (g− (n + 1) / 2 + 2j−1) bits in order. / 2 A quantum circuit that performs an operation of applying a control phase shift of ^g and applying SWAP to these q bits is configured [where j = 1,..., N + 1−g, and for all j for each g A quantum circuit that performs the above operations in parallel. ],
<< 4 >> For g = n,..., (N + 1) / 2 + 1, in order, (g− (n + 1) / 2 + 2j−2) −q bits and (g− (n + 1) / 2 + 2j−1) −q bits A SWAP quantum circuit that performs an operation applying SWAP is configured [where j = 1,..., N + 1−g, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 5 >> For g = (n + 1) / 2,..., 2, SWAP is sequentially applied to the ((n + 1) / 2−g + 2j) −q bits and the ((n + 1) / 2−g + 2j + 1) −q bits. A SWAP quantum circuit that performs an operation is configured [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 6 >> Quantum circuit that performs quantum Fourier transform modulo 2 ^{(n−1) / 2} , which is constituted by neighboring 2 qubit operations, for the ((n + 1) / 2 + 1) -q bits to the n-q bits Configure
(Pattern 2)
<< 1 >> For the 1st to qth bits to the ((n-1) / 2) -qth bit, a quantum Fourier transform modulo 2 ^{(n-1) / 2} configured by neighboring 2 qubit operations is performed. Construct a quantum circuit,
<< 2 >> For g = 2,..., (N + 1) / 2, in order, the angle (2π) between the ((n + 1) / 2−g + 2j−1) −q bits and the ((n + 1) / 2−g + 2j) −q bits. / 2 A quantum circuit that applies a control phase shift of ^g , and further performs an operation of applying SWAP to these q bits [provided that j = 1,..., G−1, for all j for each g A quantum circuit that performs the above operations in parallel. ],
<< 3 >> For g = (n + 1) / 2 + 1,..., N, the angle is 2π / 2 in order from the (g− (n + 1) / 2 + 2j−1) −q bit and the (g− (n + 1) / 2 + 2j) bit. ^A quantum circuit that performs an operation of applying a control phase shift of ^g and applying SWAP to these q bits is configured [where j = 1,..., n + 1−g, and operations for all j are performed for each g. Is a quantum circuit that performs in parallel. ],
<< 4 >> For g = n,..., (N + 1) / 2 + 1, SWAP is sequentially applied to the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) −q bits. A SWAP quantum circuit that performs an operation to be applied is configured [where j = 1,..., N + 1−g, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 5 >> For g = (n + 1) / 2,..., 2, SWAP is sequentially applied to the ((n + 1) / 2−g + 2j−1) −q bits and the ((n + 1) / 2−g + 2j) −q bits. A SWAP quantum circuit that performs an operation to be applied is configured [where j = 1,..., G−1, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 6 >> Quantum circuit that performs quantum Fourier transform modulo 2 ^{(n + 1) / 2} , which is constituted by neighboring 2 qubit operations, for the ((n-1) / 2 + 1) -q bits to the n-q bits Configure
If n = 1,
Construct a quantum circuit that applies the Hadamard transform to the 1-q bits;
In the quantum circuit constituted by the above procedure, for the quantum circuit of the quantum Fourier transform modulo the number 2 ^B smaller than 2 ^{n and} larger than 2 ^m , this B is regarded as a new n, and the above case Configure the quantum circuit with the procedure according to the division,
For quantum circuit A that performs quantum Fourier transform modulo a number of 2 ^m or less,
For the first q bits, which are N q bits input to the quantum circuit A,.
<< 1 >> For g = 1,...
When g = 1
Construct a quantum circuit that performs an operation applying the Hadamard transform to the 1-q bits,
If g is an odd number greater than 3,
Construct a quantum circuit that performs an operation applying the Hadamard transform to the 1-q bits,
A quantum circuit that performs an operation of applying a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further applying SWAP to these q-bits is configured. j is an odd number from 3 to g, and for each g, a Hadamard transform for the first -q bits and a quantum circuit that performs operations for all j in parallel. ],
If g is an even number,
A quantum circuit that performs an operation of applying a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further applying SWAP to these q-bits is configured. j is an even number from 2 to g, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 2 >> For g = N−1,.
When g = 1
Construct a quantum circuit that performs an operation applying the Hadamard transform to the 1-q bits,
If g is an odd number greater than 3,
Construct a quantum circuit that performs an operation applying the Hadamard transform to the 1-q bits,
A quantum circuit that performs an operation of applying a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further applying SWAP to these q-bits is configured. j is an odd number from 3 to g, and for each g, a Hadamard transform for the first -q bits and a quantum circuit that performs operations for all j in parallel. ],
If g is an even number,
A quantum circuit that performs an operation of applying a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further applying SWAP to these q-bits is configured. j is an even number from 2 to g, and a quantum circuit that performs operations for all j in parallel for each g. ],
<< 3 >> For g = 1,..., N−1,
If g is odd,
A quantum circuit that performs an operation applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured [where j is an odd number from 1 to g, and SWAPs for all j are parallelized for each g. The quantum circuit is ],
If g is an even number,
A quantum circuit that performs an operation of applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured [where j is an even number from 2 to g, and SWAPs for all j are parallelized for each g. The quantum circuit is ],
<< 4 >> For g = N−2,.
If g is odd,
A quantum circuit that performs an operation applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured [where j is an odd number from 1 to g, and SWAPs for all j are parallelized for each g. The quantum circuit is ],
If g is an even number,
A quantum circuit that performs an operation of applying SWAP to the j-qth bit and the (j + 1) -q-th bit is configured [where j is an even number from 2 to g, and SWAPs for all j are parallelized for each g. The quantum circuit is ],
In the quantum circuit configured by the procedure so far, the control phase shift of the angle 2π / 2 ^t (t> m) is replaced with the identity transformation,
Quantum circuit C that performs each operation of SWAP immediately after the control phase shift of the angle 2π / 2 ^t (t = m) and SWAP immediately after the control phase shift determined to be the identity transformation, and in the SWAP quantum circuit, the quantum circuit C A quantum circuit for performing an approximate quantum Fourier transform, which is configured by canceling out a mirror image symmetrical quantum circuit portion of According to the quantum circuit that performs the approximate quantum Fourier transform according to claim 1,
Approximate quantum Fourier transform operation method, comprising performing approximate quantum Fourier transform on input 1-q-bit state | b _n-1 >,..., N-q-bit state | b ₀ >. . 1st-q bits which are n q bits to be operated by an approximate quantum Fourier transform arithmetic unit that performs an approximate quantum Fourier transform using an approximate threshold as a positive integer m smaller than a positive integer ⁿ and modulo 2 ⁿ ..., for the n-qth bits,
If n is an even number,
<< 1 >> A quantum operation unit that performs a quantum Fourier transform modulo 2 ^{n / 2} configured by neighborhood 2 qubit operations from the 1-q bit to the (n / 2) -q bits,
<< 2 >> For g = 2,..., N / 2 + 1, the control phase shift of angle 2π / 2 ^g is sequentially applied to the (n / 2−g + 2j) −q bit and the (n / 2−g + 2j + 1) −q bit. And a quantum operation unit that performs an operation of applying SWAP to these q bits [where j = 1,..., G−1, and operations for all j are performed in parallel for each g. To do. ],
<< 3 >> For g = n / 2 + 2,..., N, an angle of 2π / 2 ^g is formed in order from the (g−n / 2 + 2j−2) −q bit to the (g−n / 2 + 2j−1) −q bit. A quantum operation unit that applies a control phase shift and further performs an operation of applying SWAP to these q bits is provided [where j = 1,..., N + 1−g, and operations for all j are parallelized for each g. Shall be performed. ],
<< 4 >> For g = n,..., N / 2 + 2, operations for applying SWAP to the (g−n / 2 + 2j−2) −q bits and the (g−n / 2 + 2j−1) −q bits in order are performed. SWAP operation section to perform is provided [where j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g. ],
<< 5 >> For g = n / 2 + 1,..., 2, a SWAP operation unit that performs operations to apply SWAP to the (n / 2−g + 2j) −q bits and the (n / 2−g + 2j + 1) −q bits in order. [Where j = 1,..., G−1, and operations for all j are performed in parallel for each g. ],
<< 6 >> A quantum operation unit that performs a quantum Fourier transform modulo 2 ^{n / 2} configured by neighboring 2 qubit operations for the (n / 2 + 1) -q bits to the n-q bits,
If n is odd,
In either pattern 1 or pattern 2,
(Pattern 1)
<< 1 >> A quantum operation unit that performs a quantum Fourier transform modulo 2 ^{(n + 1) / 2} composed of neighboring 2-qubit operations from the 1-q bit to the ((n + 1) / 2) -q bits Prepared,
<< 2 >> For g = 2,..., (N + 1) / 2, the angle is 2π / 2 in order of the ((n + 1) / 2−g + 2j) −q bit and the ((n + 1) / 2−g + 2j + 1) −q bit. a quantum operation unit that applies a control phase shift of ^g , and further performs an operation of applying SWAP to these q bits [where j = 1,..., g−1, and operations for all j for each g Are performed in parallel. ],
<< 3 >> With respect to g = (n + 1) / 2 + 1,..., N, an angle 2π between the (g− (n + 1) / 2 + 2j−2) −q bits and the (g− (n + 1) / 2 + 2j−1) bits in order. / 2 A quantum operation unit that applies a control phase shift of ^g and further performs an operation of applying SWAP to these q bits [provided that j = 1,..., N + 1−g, and for every j for each g Are performed in parallel. ],
<< 4 >> For g = n,..., (N + 1) / 2 + 1, in order, (g− (n + 1) / 2 + 2j−2) −q bits and (g− (n + 1) / 2 + 2j−1) −q bits A SWAP operation unit that performs an operation applying SWAP is provided [where j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g. ],
<< 5 >> For g = (n + 1) / 2,..., 2, SWAP is sequentially applied to the ((n + 1) / 2−g + 2j) −q bits and the ((n + 1) / 2−g + 2j + 1) −q bits. A SWAP calculation unit for performing calculations is provided [where j = 1,..., G−1, and calculations for all j are performed in parallel for each g. ],
<< 6 >> Quantum operation for performing quantum Fourier transform modulo 2 ^{(n-1) / 2} composed of neighboring 2 qubit operations from the ((n + 1) / 2 + 1) -q bits to the n-q bits Part
(Pattern 2)
<< 1 >> For the 1st to qth bits to the ((n-1) / 2) -qth bit, a quantum Fourier transform modulo 2 ^{(n-1) / 2} configured by neighboring 2 qubit operations is performed. It has a quantum operation part,
<< 2 >> For g = 2,..., (N + 1) / 2, in order, the angle (2π) between the ((n + 1) / 2−g + 2j−1) −q bits and the ((n + 1) / 2−g + 2j) −q bits. / 2 A quantum operation unit that applies a control phase shift of ^g and further performs an operation of applying SWAP to these q bits [provided that j = 1,..., G−1, for all j for each g. Are performed in parallel. ],
<< 3 >> For g = (n + 1) / 2 + 1,..., N, the angle is 2π / 2 with the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) bits in order. a quantum operation unit that applies a control phase shift of ^g , and further performs an operation of applying SWAP to these q bits [provided that j = 1,..., n + 1−g, and operations for all j for each g Are performed in parallel. ],
<< 4 >> For g = n,..., (N + 1) / 2 + 1, SWAP is sequentially applied to the (g− (n + 1) / 2 + 2j−1) −q bits and the (g− (n + 1) / 2 + 2j) −q bits. A SWAP operation unit that performs an operation to be applied is provided [where j = 1,..., N + 1−g, and operations for all j are performed in parallel for each g. ],
<< 5 >> For g = (n + 1) / 2,..., 2, SWAP is sequentially applied to the ((n + 1) / 2−g + 2j−1) −q bits and the ((n + 1) / 2−g + 2j) −q bits. A SWAP operation unit that performs an operation to be applied is provided [where j = 1,..., G−1, and operations for all j are performed in parallel for each g. ],
<< 6 >> Quantum operation for performing quantum Fourier transform modulo 2 ^{(n + 1) / 2} composed of neighboring 2 qubit operations from the ((n-1) / 2 + 1) -q bits to the n-q bits Part
If n = 1,
A quantum operation unit that applies Hadamard transform to the 1-q bits;
In the quantum arithmetic device configured in the above procedure, regarding the quantum arithmetic unit of the quantum Fourier transform modulo the number 2 ^B smaller than 2 ^{n and} larger than 2 ^m , this B is regarded as a new n, Configure the quantum operation unit according to the procedure according to
For the quantum operation unit D that performs the quantum Fourier transform modulo 2 ^m or less,
For the 1st to qth bits, which are N q bits input to the quantum operation unit D,...
<< 1 >> For g = 1,...
When g = 1
A quantum operation unit that performs an operation applying Hadamard transform to the 1-q bits;
If g is an odd number greater than 3,
A quantum operation unit that performs an operation applying Hadamard transform to the 1-q bits;
A quantum operation unit that applies a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further performs an operation to apply SWAP to these q-bits, It is assumed that j is an odd number from 3 to g, and the Hadamard transform for the 1-q bits and the operation for all j are performed in parallel for each g. ],
If g is an even number,
A quantum operation unit that applies a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further performs an operation to apply SWAP to these q-bits, It is assumed that j is an even number from 2 to g, and operations for all j are performed in parallel for each g. ],
<< 2 >> For g = N−1,.
When g = 1
A quantum operation unit that performs an operation applying Hadamard transform to the 1-q bits;
If g is an odd number greater than 3,
A quantum operation unit that performs an operation applying Hadamard transform to the 1-q bits;
A quantum operation unit that applies a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further performs an operation to apply SWAP to these q-bits, It is assumed that j is an odd number from 3 to g, and the Hadamard transform for the 1-q bits and the operation for all j are performed in parallel for each g. ],
If g is an even number,
A quantum operation unit that applies a control phase shift of an angle 2π / 2 ^{j to} the (j−1) -q-th bit and the j-q-th bit, and further performs an operation to apply SWAP to these q-bits, It is assumed that j is an even number from 2 to g, and operations for all j are performed in parallel for each g. ],
<< 3 >> For g = 1,..., N−1,
If g is odd,
A SWAP operation unit that performs an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit [where j is an odd number from 1 to g, and SWAPs for all j are parallelized for each g Shall be performed. ],
If g is an even number,
A SWAP operation unit that performs an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit [where j is an even number from 2 to g, and SWAP for all j is parallelized for each g Shall be performed. ],
<< 4 >> For g = N−2,.
If g is odd,
A SWAP operation unit that performs an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit [where j is an odd number from 1 to g, and SWAPs for all j are parallelized for each g Shall be performed. ],
If g is an even number,
A SWAP operation unit that performs an operation to apply SWAP to the j-qth bit and the (j + 1) -q-th bit [where j is an even number from 2 to g, and SWAPs for all j are parallelized for each g Shall be performed. ],
In the approximate quantum Fourier transform operation device configured according to the above, a quantum operation unit that performs a control phase shift of an angle 2π / 2 ^t (t> m) is replaced with a quantum operation unit that performs identity conversion,
Quantum operation unit E for performing each operation of SWAP immediately after the control phase shift of angle 2π / 2 ^t (t = m) and SWAP immediately after the control phase shift assumed to be the identity transformation, and the quantum operation in the SWAP operation unit An approximate quantum Fourier transform arithmetic apparatus characterized in that it is configured without the mirror image symmetry quantum arithmetic part of the part E.

Images