Method and apparatus for configuring quantum mechanical state, and communication method and apparatus using the same

[0002] 1. Field of the Invention

[0003] The present invention relates to a method and apparatus for configuring a, quantum mechanical state required for quantum information processing, quantum communication, or quantum precision measurements, as well as a communication method and apparatus using such a method and apparatus.

[0004] 2. Related Background Art

[0005] The fields of quantum computations (see R. P. Feynman, “Feynman Lectures on Computation,” Addison-Wesley (1996)) and quantum information theories are advancing rapidly. In these fields, superposition, interference, and an entangled state, which are the basic nature of quantum mechanics, are ingeniously utilized.

[0006] In the field of quantum computations, since the publication of Shor's algorithm concerning factorization (see P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” LANL quantum physics archive quant-ph/9508027. Similar contents are found in SIAM J. Computing 26 (1997), 1484. In addition, the first document is P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (ed. S. Goldwasser) 124-134 (IEEE Computer Society, Los Alamitos, Calif., 1994). A detailed description is found in Artur Ekert and Richard Jozsa, “Quantum computation and Shor's factoring algorithm,” Rev. Mod. Phys. 68, 733 (1996)) and Grover's algorithm concerning the search problem (L. K. Grover, “A fast quantum mechanical algorithm for database search,” LANL quantum physics archive quant-ph/9605043. Almost similar contents are found in L. K. Grover, “Quantum Mechanics Helps in Searching for a Needle in a Haystack,” Phys. Rev. Lett. 79, 325 (1997)), many researchers have been proposing methods for implementing quantum computations and developing new quantum algorithms.

[0007] On the other hand, in the field of quantum information theories, the entangled state has been known to play an important role due to its unlikelihood to be affected by decoherence (see C. H. Bennett, C. A. Fuchs, and J. A. Smolin, “Entanglement-Enhanced Classical Communication on a Noisy Quantum Channel,” Quantum Communication, Computing, and Measurement, edited by Hirota et al., Plenum Press, New York, p. 79 (1997)).

[0008] Furthermore, as an application of these results, a method for overcoming the quantum shot noise limit using (n) two-level entangled states has been established through experiments on Ramsey spectroscopy (see D. J. Wineland, J. J. Bollinger, W. M. Itano, F. L. Moore, and D. J. Heizen, “Spin squeezing and reduced quantum noise in spectroscopy,” Phys. Rev. A 46}, R6797 (1992) or D. J. Wineland, J. J. Bollinger, W. M. Itano, and D. J. Heizen, “Squeezed atomic states and projection noise in spectroscopy,” Phys. Rev. A 50, 67 (1994)). Despite the lack of discussion of the two-level Ramsey spectroscopy, a similar concept is described in M. Kitagawa and M. Ueda, “Nonlinear-Interferometric Generation of Number-Phase-Correlated Fermion States,” Phys. Rev Lett. 67, 1852 (1991).

[0009] If decoherence in the system caused by the environment is negligible, the maximally entangled state serves to improve the accuracy in measuring the frequency of an energy spectrum.

[0010] In this case, the fluctuation of the frequency decreases by 1/{square root over (n)}. With decoherence in the system considered, however, the resolution achieved by the maximally entangled state is only equivalent to that achieved by an uncorrelated system.

[0011] In addition, the use of a partly entangled state having a high symmetry has been proposed in S. F. Huelga, C. Macchiavello, T. Pellizzari, A. K. Ekert, M. B. Plenio, J. I. Cirac, “Improvement of Frequency Standards with Quantum Entanglement,” Phys. Rev. Lett. 79, 3865 (1997).

[0012] If optimal parameters (coefficients of basic vectors) can be selected beforehand, this method can provide a higher resolution than the maximally entangled or uncorrelated state.

[0013] The partly entangled state having a high symmetry is given by the following equation: $\begin{array}{cc}|{\psi }_n⟩=\sum _{k=0}^{\lfloor n/2\rfloor }{a}_k{|k⟩}_s\mathrm{for}n\geqq 2& \left(1\right)\end{array}$

[0014] where (n) represents the number of qubits that are twolevel particles constituting a state, and ┐n/2┘ represents a maximum integer not more than n/2. {a_k} is a real number wherein, for example, an optimal combination of values are assumed to be provided beforehand so as to provide a high resolution in the Ramsey spectroscopy. In this case, {a_k} may be a constant.

[0015] |k>_sis a superposition of states in which (k) or (n−k) qubits are excited, wherein the superposition is established using an equal weight. For example, |ψ₄> is given by the following equation. $\begin{array}{c}|{\psi }_4⟩=a_0|0⟩+a_1|1⟩+a_2|2⟩\\ =a_0(|0000⟩+|1111⟩)+\\ a_1(|0001⟩+|0010⟩+|0100⟩+|1000⟩+|1110⟩+|1101⟩+\\ |1011⟩+|0111⟩)+\\ a_2(|0011⟩+|0101⟩+|0110⟩+|1001⟩+|1010⟩+|1100⟩)\end{array}$

[0016] These states have symmetry such as that described below.

[0017] Invariable despite the substitution of any two qubits

[0018] Invariable despite the simultaneous inversion of {|0>, |1>} for each qubit.

[0019] To conduct experiments on the Ramsey spectroscopy using a partly entangled state having a high symmetry, a target entangled state must be provided as soon as possible as an initial system state before decoherence may occur. Thus, all actual physical systems have a decoherence time, and quantum mechanical operations must be performed within this time. This is a problem in not only quantum precision measurements but also quantum communication and general quantum computations.

[0020] In addition, to configure the target entangled state from a specified state, an operation using basic quantum gates must be performed out many times. Minimizing this number of times leads to the reduction of the time required to provide the target entangled state.

[0021] In addition, to configure a quantum gate network for obtaining the target entangled state, a conventional computer must be used to determine in advance which qubits will be controlled by the basic quantum gates, the order in which the basic quantum gates will be used, and a rotation parameter for unitary rotations. The amount of these computations is desirably reduced down to an actually feasible level.

[0022] Thus, an object of the present invention is to provide a method used to configure a target entangled state within a decoherence time in an actual physical system, for configuring the desired state using as less steps as possible if the computation time is evaluated based on the total number of basic quantum gates.

[0023] Another object of the present invention is to provide an effective procedure used in configuring a network consisting of basic quantum gates, for using a conventional computer to determine in advance which qubits will be controlled by the basic quantum gates, the order in which the basic quantum gates will be used, and a unitary rotation parameter.

[0024] Yet another object of the present invention is to provide a method and apparatus for configuring not only a partly entangled state having a high symmetry but also a partly entangled state defined by a function with an even number of collisions, using as less steps as possible if the computation time is evaluated based on the total number of basic quantum gates.

[0025] According to one aspect, the present invention which achieves these objects relates to a method for configuring a quantum mechanical state consisting of a plurality of two-level systems wherein if a superposition of orthonormal bases in which each two-level system assumes a basic or an excited state is used for expression, a desired partly-entangled quantum mechanical state in which the coefficients of the bases are all real numbers is configured using an operation that is a combination of a selective rotation operation and an inversion about average operation.

[0026] According to one aspect, the present invention which achieves these objectives relates to a state configuration apparatus comprising a selective rotation operation means for a plurality of two-level systems and an inversion about average operation means for the plurality of two-level systems, wherein if a quantum mechanical state consisting of the plurality of two-level systems is expressed by a superposition of orthonormal bases in which each two-level system assumes a basic or an excited state, a desired partly-entangled quantum mechanical state in which the coefficients of the bases are all real numbers is configured using an operation that is a combination of an operation performed by the selective rotation operation means and an operation performed by the inversion about average operation means.

[0027] Other objectives and advantages besides those discussed above shall be apparent to those skilled in the art from the description of a preferred embodiment of the invention which follows. In the description, reference is made to accompanying drawings, which form a part thereof, and which illustrate an example of the invention. Such an example, however, is not exhaustive of the various embodiments of the invention, and therefore reference is made to the claims which follow the description for determining the scope of the invention.

[0028] FIG. 1 is a Feynman diagram of a quantum gate network showing a case in which the “first trial method” does not use a second register for n=2;

[0029] FIG. 2 is a Feynman diagram of the quantum gate network showing a case in which the “first trial method” does not use the second register for n=3;

[0030] FIG. 3 is a Feynman diagram of the quantum gate network showing a case in which the “first trial method” does not use the second register for n=4;

[0031] FIG. 4 is a Feynman diagram of the quantum gate network showing a case in which the “first trial method” does not use the second register for n=4;

[0032] FIG. 5 is a Feynman diagram of the quantum gate network showing a case in which the “first trial method” does not use the second register for n=4;

[0033] FIG. 6 shows the overall flow of the “first trial method” processing for a general (n);

[0034] FIG. 7 is a Feynman diagram of quantum gates that selectively rotate a particular state of a first register;

[0035] FIGS. 8A, 8B and 8C show the variation of the coefficients of basic vectors when a quantum mechanical state is subjected to an inversion about average operation D and an operation for selectively rotating the phase by π;

[0036] FIG. 9 shows a mapping caused by a function (f) having an even number of collisions;

[0037] FIG. 10 is a Feynman diagram of a quantum gate network for the function (f);

[0038] FIG. 11 describes an operation of an auxiliary qubit;

[0039] FIG. 12 is a Feynman diagram of a program QUBIT-ADDER2.

[0040] FIG. 13 is a Feynman diagram showing how QUBIT-ADDER2 is repeatedly operated to configure QUBIT-ADDER1;

[0041] FIG. 14 is a Feynman diagram showing a quantum gate network with a selective rotation in the second registers;

[0042] FIG. 15 is a Feynman diagram showing a network of quantum gates that executes a selective rotation in the second register for η=η−η=n/2;

[0043] FIG. 16 is a Feynman diagram showing a network for D;

[0044] FIG. 17 is a Feynman diagram showing a network for a subroutine (R(π)D).

[0045] FIG. 18 is a Feynman diagram showing a selective π phase rotation in the first: register;

[0046] FIG. 19 is a Feynman diagram of the quantum gates in a case in which |ψn> can be configured using merely a (R′{η}DR{η}) contraction method without a (R(π)D) repetition operation;

[0047] FIG. 20 is a Feynman diagram showing a method for dividing Λ_n(R_Z(α)) into simpler quantum gates;

[0048] FIG. 21 is a Feynman diagram showing a conventional processing for n=2;

[0049] FIG. 22 is a Feynman diagram showing a method operative on a 7-quibit network for dividing Λ₅(σ_x) into simpler quantum gates;

[0050] FIG. 23 is a Feynman diagram showing a method operative on a (n+1)-qubit: network for dividing Λ_n−1(σ_x) into simpler quantum gates for n≧7;

[0051] FIG. 24 is a Feynman diagram showing a method operative on the (n+1)-qubit network for dividing Λ_m(σ_x) into simpler quantum gates for n≧7;

[0052] FIG. 25 is a table showing into how many basic gates Λ_n−1(σ_x) can be divided on the (n+1)-qubit network;

[0053] FIG. 26 is a table showing into how many basic gates Λ_n(R_Z(α)) can be divided on the (n+1)-qubit network; and

[0054] FIG. 27 shows an example of a quantum communication apparatus using a method and apparatus for configuring an entangled state according to the present invention.

[0055] One preferred embodiment of the present invention will be described with reference to the accompanying drawings.

[0056] (Basic Ideas Common to Each Embodiment)

[0057] This embodiment is described in the following order.

[0058] 1. Simple method (“first trial method”)

[0059] 2. Specific example of the “first trial” method

[0060] 3. Method for configuring a gate network for the first trial method if second registers are not used.

[0061] 4. Conditions under which the (R′{η}DR{η}) contraction method is successful

[0062] 5. (R(π)D) repetition method

[0063] 6. Simple example of the R(π)D) repetition method

[0064] 7. Configuration of a partly entangled state using a function with an even number of collisions

[0065] 8. Example of configuration of a specific quantum gate network and the evaluation of computation time

[0066] (First embodiment) Quantum gate network for a function with an even number of collisions

[0067] (Second embodiment) Quantum gate network for selective phase rotations

[0068] (Third embodiment) Quantum gate network for inversion about average operations

[0069] (Fourth embodiment) Evaluation of the amount of computations during the overall process

[0070] (Fifth embodiment) Method for configuring a Λ_n(R_Z(α) gate

[0071] (Sixth embodiment) Method implemented using the cold trapped ion method

[0072] (Seventh embodiment) Method applied to quantum communication

[0073] These embodiments are sequentially described below.

[0074] [Simple Method (First Trial Method)]

[0075] First, the following method is considered as one for configuring a partly entangled state having a high symmetry. For convenience, this method is referred to as the “first trial method” herein. Although shown below, this method can configure |ψ_n> specified by a set of arbitrary real coefficients {a_k} for n=2, 3 but only in special cases for n≧4.

[0076] The “first trial method,” however, is a basic concept for all the embodiments, and the embodiments have been proposed as improved versions of the first trial method.

[0077] (First Trial Method)

[0078] 1. The following initial state is prepared in an n-qubit register. |s₁>=|0 . . . 0>.

[0079] 2. Hadamard transformation is applied to each qubit of the register. The Hadamard transformation is given by the following equation. $\begin{array}{cc}H=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\begin{array}{c}1\\ -1\end{array}\right]& \left(2\right)\end{array}$

[0080] In the expression in Equation (2), |0>=(1, 0), |1>=(0, 1). This operation provides a flat superposition in the register as shown by the following equation. $\begin{array}{cc}|s_2⟩=\frac{1}{\sqrt{2^n}}\sum _{k={\left\{0,1\right\}}^n}|k⟩& \left(3\right)\end{array}$

[0081] 3. s(k) is defined to be the total number of qubits excited at|k. When p=└n/2┘, a permutation {η₀, η₁, . . . η_p−1} is assumed to be obtained by selecting (p) elements from (0, 1, . . .p and placing them in an appropriate order (thus, η_iis an integer that meets 0≦η_i≦p for 0≦i≦p, and η_i≠η_jfor i≠j). The following three operations (a), (b), and (c) are sequentially performed for i=0, 1, . . . p−1.

[0082] (a) An appropriate 0≦φ_i<2π is selected. If s(k) is equal to η_i, a selective rotation is executed to rotate the phase of |k> by φ_i. If s(k) is equal to (n−η_i), the phase of |k> is rotated by (−φ_i).

[0083] (b) Grover's inversion about average operation D is performed on the register (see L. K. Grover, “A fast quantum mechanical algorithm for database search,” LANL quantum physics archive quant-ph/9605043 and L. K. Grover, “Quantum Mechanics Helps in Searching for a Needle in a Haystack,” Phys. Rev. Lett. 79, 325 (1997))

[0084] (c) If s(k) is equal to η_i, the phase of |k> is rotated by θ_i. If s(k) is equal to (n−η_i), a selective rotation is executed to rotate the phase of |k> by (−θ_i). A phase rotation parameter θ_iis selected so as to offset the phase of a basic vector to make the coefficient a real number.

[0085] In the above description, the permutation (η_o, η₁, . . . η_p−i} and phase rotation parameter {θ₀, θ₁, . . . θ_p−1, depend on the set of coefficients {a_k} in the Equation (1).

[0086] If (n) is an even number and η=n−η=n/2, the number of basic vectors with which s(k)=η is established is even. Thus, in the above step 3(a), the phase is rotated by θ for half of all the basic vectors with which s(k)=η is established, whereas the phase is rotated by (−θ) for the remaining half of the basic vectors. Similar operations are performed in step 3(c).

[0087] To execute the selective rotation efficiently, two registers are provided. A first register consists of (n) qubits and a second register consists of ┌log₂(n+1)┐ qubits. ┌log₂(n+1)┐ represents a minimum integer larger than or equal to log₂(n+1). The Hadamard transformation is applied to each qubit of the first register to obtain the flat superposition, and then the value of s(k) is written to the second register as shown in the following expression. $\begin{array}{cc}\frac{1}{\sqrt{2^n}}\sum _{k={\left\{0,1\right\}}^n}|k⟩\otimes |0⟩\to \frac{1}{\sqrt{2^n}}\sum _{k={\left\{0,1\right\}}^n}|k⟩\otimes |s\left(k\right)⟩.& \left(4\right)\end{array}$

[0088] When the selective rotation is executed, the number of quantum gates used can be saved by setting in the second register a control section for the quantum gates. For example, consider a case in which n=4 and s(k)=1. The rotation of the phase of the second register in the state of |1> is equal to the rotation of the phases of eight basic vectors in the first vector. The second register must be initialized to |0 . . . 0> before the inversion about average operation D is performed and before a final state is obtained.

[0089] To confirm the operation of the method described above, the status |s₃> after step 3(a) (i=0) is expressed as follows. $\begin{array}{cc}\begin{array}{c}|s_3⟩=R\left\{\eta \right\}|s_2⟩\\ =\frac{1}{\sqrt{2^n}}\underset{h}{\underbrace{[\exp \left(i\phi \right),\dots ,}}\underset{h}{\underbrace{\exp \left(-i\phi \right),\dots ,}}1,\dots ,1\underset{\underset{2^n-2h}{⏟}}{]}\end{array}& \left(5\right)\end{array}$

[0090] where (h) is the number of basic vectors for which s(k) is equal to η is h.

[0091] R{η}) represents the selective rotation used in step 3(a). In this case, i=0 that is a subscript has been omitted. In Equation (5), {|k>|kε{0,1}ⁿ} is used as an orthonormal basis. As in the expression in Equation (5), the embodiments often describe vertical vectors as horizontal vectors. In addition, the embodiments represent (h) as the number of basic vectors for which s(k) is Equal to η. Thus, (h) components exp(iφ) and (h) components exp(−iφ) exist in |s₃>.

[0092] In the expression in (5), the order of the basic vectors {|0 . . . 00>, |0 . . . 01> . . . , |1 . . . 11>} has been changed so that the components exp (iφ) and exp(−iφ) are collected at the left end of |s₃>. Such a change in the order of the basic vectors does not change the matrix expression of the inversion about average operation D. A 2ⁿ×2ⁿmatrix expression of D is given as shown below. $\begin{array}{cc}\{\begin{array}{cc}{D}_{\mathrm{ij}}=2^{-n+1}& \mathrm{if}i\ne j\\ D_{\mathrm{ii}}=-1+2^{-n+1}& \end{array}& \left(6\right)\end{array}$

[0093] Applying D to |s₃> results in the following state:

[0094] |s₄>=D|s₃>=[α, . . . , α′, . . . β, . . . ],  (7)

[0095] where α and β meet the following conditions. $\begin{array}{cc}\{\begin{array}{c}{2}^{\left(3n/2\right)-1}\alpha =2h\cos \phi +\left(2^n-2h\right)-2^{n-1}{e}^{i\phi },\\ 2^{\left(3n/2\right)-1}\beta =2h\cos \phi +\left(2^n-2h\right)-2^{n-1}\end{array}& \left(8\right)\end{array}$

[0096] To offset the phase, θ is defined as follows: $\begin{array}{cc}{e}^{i\theta }=\frac{\mathrm{\alpha •}}{\left|\alpha \right|}& \left(9\right)\end{array}$

[0097] Next, selective rotation R′ {η} acts upon |s₄>. $\begin{array}{cc}|s_5⟩=R^{\prime }\left\{\eta \right\}|s_4⟩=[e^{i\theta }\alpha ,\dots ,e^{-i\theta }{\alpha }^{\prime },\dots ,\beta ,\dots ]=[\underset{2h}{\underbrace{\left|\alpha \right|,\dots ,}}\beta ,\dots ].& \left(10\right)\end{array}$

[0098] where the number of components |α| is 2h. To make the coefficients of 2h basic vectors negative, the phases of the 2h basic vectors may be rotated selectively by π.

[0099] For example, for n=2, |ψ₂> is given as follows:

[0100] |ψ>₂=a₀(|00>+|11>)+a₁(|01>+|10>),  (11)

[0101] where the following relations are established. $\begin{array}{cc}\{\begin{array}{ccc}\left(i\right)& 1/2\leqq a_0\leqq 1/\sqrt{2},& 0\leqq \left|a_1\right|\leqq 1/2,\\ \left(\mathrm{ii}\right)& 0\leqq \left|a_0\right|\leqq 1/2,& 1/2\leqq a_1\leqq 1/\sqrt{2}.\end{array}& \left(12\right)\end{array}$

[0102] By executing the above method using the operation for rotating the phase by (±φ) for |00> and |11> in which 2-qubits are flatly superposed on one another, |ψ₂> is obtained as shown by the following equation. $\begin{array}{cc}{a}_0=\sqrt{\frac{1+{\sin }^2\phi }{2}},a_1=\frac{\cos \phi }{2}& \left(13\right)\end{array}$

[0103] This is included within the range of 12(i). φ must be determined from (13) using conventional computations before quantum operations are performed.

[0104] The “first trial method” enables the configuration of |ψ₂> and |ψ₃> that are provided by arbitrary real coefficients. For n≧4, however, |ψ_n> that cannot be configured by this method exists depending on the set of coefficients {a_k}. For example, the following state cannot be configured by this method. $|{\psi }_4⟩=\sqrt{\frac{3}{7}}{|0⟩}_s+\frac{1}{7\sqrt{2}}{|1⟩}_s+\frac{1}{7\sqrt{2}}{|2⟩}_s.$

[0105] The “first trial method” corresponds to continuous execution of the (R′{η}DR{η}) contraction method, which is described below. The (R′{η}DR{η}) contraction method is not always successful, but there are sufficient conditions for success, which will also be described below.

[0106] In addition, as described for Equation (13), the “first trial method” must use conventional computations to determine the phase rotation parameter φ_nbefore unitary gates are operated. The needs for conventional computations prior to the configuration of a quantum gate network are common to all embodiments.

[0107] According to the “first trial method,” (p+1) basic vectors are available for selective rotations for p=└n/2┘. Thus, there are (p+1)! permutations to which (R′{η}DR{η}) is applied. If, however, |ψ_r> can be configured, (R′{η}DR{η}) is applied to only some of these permutations. Furthermore, certain |ψ_n> cannot be configured by this method.

[0108] In addition, trials and errors must be carried out (p+1)! times using conventional computations before the phase rotation parameter can be determined. Thus, the burden of computations becomes heavier as (n) increases.

[0109] Thus, as a method for solving these problems, a method will be described below that uses sufficient conditions for the success of the (R′{η}DR{η}) contraction method and a (R(π)D) repetition method according to the embodiments.

[0110] [Specific Example of the “First Trial Method”]

[0111] Before explaining the sufficient conditions for the success of the (R′{η}DR{η}) contraction method and the (R(π)D) repetition method, descriptions are given of changes in qubit for n=2, 3, 4 according to the “first trial method” and of a quantum gate network configuration in a case where the second register is not used.

[0112] (n) and (a₀, a₁, . . . , a_p} are assumed to be given beforehand, where p=└n/2┘. A quantum gate network is considered that configures the partly entangled state with a high symmetry |ψ_n> specified by these constants and expressed by Equation (1).

[0113] To examine specific changes in qubit state, a case of n=2 is considered as a first simple example. In the meantime, the following relations are assumed in Equation (11).

[0114] ½≦a₀≦1/{square root over (2)}, −½≦a₁≦½

[0115] First, as an initial state, |00> is provided for a first and a second qubits, and H (Hadamard transformation) is individually applied to each qubit. This operation transforms the qubits to the following state.

[0116] |00>→½(|00>+|11>+|10>+|11>)

[0117] A selective rotation is executed in such a way that |00> and |11> are each multiplied by phase factor exp(iφ). The resulting state of the first and second qubits is denoted as |ψ>.

[0118] |ψ>=½(e^iφ|00>+|01>+|10>+e^−iφ|11>)

[0119] Next, an inversion about average operation is performed. Since n=2, D is given in the form of a matrix of 4×4, using Equation (6). $D=\frac{1}{2}\left|\begin{array}{cccc}-1& 1& 1& 1\\ 1& -1& 1& 1\\ 1& 1& -1& 1\\ 1& 1& 1& -1\end{array}\right|\begin{array}{c}|00⟩\\ |01⟩\\ |10⟩\\ |11⟩\end{array}$ $⟨00|⟨01|⟨10|⟨11|$

[0120] The application of D to |ψ> leads to the following transformation. $|\psi ⟩=\frac{1}{2}\left[\begin{array}{c}\exp \left(i\phi \right)\\ 1\\ 1\\ \exp \left(-i\phi \right)\end{array}\right]\to D|\psi ⟩=\frac{1}{2}\left[\begin{array}{c}1-i\sin \phi \\ \cos \phi \\ \cos \phi \\ 1+i\sin \phi \end{array}\right]$

[0121] Next, |00> and |11> are again multiplied by phase factors exp(iθ) and exp(−iθ), respectively. In this case, θ meets the following relation. $e^{i\theta }=\frac{1+i\sin \phi }{\left|1+i\sin \phi \right|}$

[0122] Such a selective rotation causes the two qubits to enter the following state. $\frac{\sqrt{1+{\sin }^2\phi }}{2}\left(|00⟩+|11⟩\right)+\frac{\cos \phi }{2}\left(|01⟩+|10⟩\right)$

[0123] Thus, by selecting beforehand φ to meet the following equation, $a_0=\frac{\sqrt{1+{\sin }^2\phi }}{2},\left(a_1=\frac{\cos \phi }{2}\right)$

[0124] the target partly entangled state |ψ₂> is obtained.

[0125] The following point is noted. Since the physical quantity of |ψ₂> does not vary despite a rotation of the phase of the entire |ψ₂>, the ranges of the values of a₀and a₁are as shown below.

[0126] ½≦a₀≦1/{square root over (2)}, 0≦|a₁|≦½  (i)

[0127] 0≦|a₀|≦½, ½≦a₁≦1/{square root over (2)}  (ii)

[0128] The above specific example provides a method for configuring |ψ₂> that meets the condition in (i). To configure |ψ₂> that meets the condition in (ii), the selective rotation may be applied to |01>and |10>instead of |00>and |11>. Thus, for n=2, an arbitrary |ψ₂> can be configured using the “first trial method.”

[0129] Next, a case of n=3 is considered.

[0130] |ψ₃>=a₀(|000>+|111>)+a₁(|001>+|010>+|100>+|110>+|101>+|011>)  (14)

[0131] In this equation, a₀²+3a₁²=½. In the meantime, the following relations are assumed.

[0132] ½{square root over (2)}≦a₀≦1/{square root over (2)}, 0≦a₁≦½{square root over (2)}

[0133] First, as an initial state, |000> is provided for a first, a second, and a third qubits, and H (Hadamard transformation) is applied to each qubit independently. $|000⟩\to \frac{1}{2\sqrt{2}}\left(|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+|111⟩\right)$

[0134] A selective rotation is executed in such a way that |000> and |111> are multiplied by phase factor exp(iφ) and exp(−iφ), respectively. Then, the following state |ψ> is obtained. $|\psi ⟩=\frac{1}{2\sqrt{2}}\left(e^{i\phi }|000⟩+|001⟩+|010⟩+|011⟩+|100⟩+|101⟩+|110⟩+e^{-i\phi }|111⟩\right)$

[0135] Next, the inversion about average operation D is performed. If n=3 in Equation (6), the following matrix expression is given. $\begin{array}{c}D=\frac{1}{4}\left|\begin{array}{cccccccc}-3& 1& 1& 1& 1& 1& 1& 1\\ 1& -3& 1& 1& 1& 1& 1& 1\\ 1& 1& -3& 1& 1& 1& 1& 1\\ 1& 1& 1& -3& 1& 1& 1& 1\\ 1& 1& 1& 1& -3& 1& 1& 1\\ 1& 1& 1& 1& 1& -3& 1& 1\\ 1& 1& 1& 1& 1& 1& -3& 1\\ 1& 1& 1& 1& 1& 1& 1& -3\end{array}\right|\begin{array}{c}|000⟩\\ |001⟩\\ |010⟩\\ |011⟩\\ |100⟩\\ |101⟩\\ |110⟩\\ |111⟩\end{array}\\ \begin{array}{cccccccc}⟨000|⟨001|⟨010|⟨011|⟨100|⟨101|⟨110|⟨111|& & & & & & & \end{array}\end{array}$

[0136] The application of D to |ψ> leads to the following transformation. $D|\psi ⟩=\frac{1}{8\sqrt{2}}\left[\begin{array}{c}6-3e^{i\phi }+e^{-i\phi }\\ 2\left(1+\cos \phi \right)\\ 2\left(1+\cos \phi \right)\\ 2\left(1+\cos \phi \right)\\ 2\left(1+\cos \phi \right)\\ 2\left(1+\cos \phi \right)\\ 2\left(1+\cos \phi \right)\\ 6-3e^{-i\phi }+e^{i\phi }\end{array}\right]$

[0137] Next, |000> and |111> are again multiplied by phase factors exp(iθ) and exp(−iθ). In this case, θ meets the following relation. $e^{i\phi }=\frac{6-3e^{-i\phi }+e^{i\phi }}{\left|6-3e^{i\phi }+e^{-i\phi }\right|}$

[0138] Such a selective rotation causes the two qubits to enter the following state. $\begin{array}{cc}\frac{\sqrt{23-12\cos \phi -3\cos 2\phi }}{8}\left(|00⟩+|11⟩\right)+\frac{1+\cos \phi }{4\sqrt{2}}\left(|01⟩+|10⟩\right)& \left(15\right)\end{array}$

[0139] Thus, by selecting beforehand φ to meet the following equation, $a_0=\frac{\sqrt{23-12\cos \phi -3\cos 2\phi }}{8},\left(a_1=\frac{1+\cos \phi }{4\sqrt{2}}\right)$

[0140] the target partly entangled state |ψ₃> is obtained.

[0141] The following point is noted. Based on Equation (15), a₀and a₁in Equation (14) each assume the following four values.

[0142] ½{square root over (2)}≦a₀≦1/{square root over (2)}, 0≦a₁≦½{square root over (2)}  (i)

[0143] ½{square root over (2)}≦a₀≦1/{square root over (2)}, −½{square root over (2)}≦a₁≦0  (ii)

[0144] 0≦a₀≦½{square root over (2)}, ½{square root over (2)}≦a₁≦1/{square root over (6)}  (iii)

[0145] ½{square root over (2)}≦a₀≦0, ½{square root over (2)}≦a₁≦1/{square root over (6)}  (iv)

[0146] The above specific example provides a method for configuring |ψ₃> that meets the condition in (i). To configure ψ₃> that meets the condition in (ii), |000> and |111> may be multiplied by −exp(iθ) and −exp(−θ) in the second selective rotation, respectively. In addition, by subjecting |001>, |010>, |100>, as well as |110>, |101>, and |011> to a selective rotation, $\frac{1}{2\sqrt{2}}[|000⟩+e^{i\phi }\{|001⟩+|010⟩+|100⟩\}+e^{-i\phi }\{|110⟩+|101⟩+|011⟩\}+|111⟩]$

[0147] then the inversion about average operation D, and $\frac{1}{8\sqrt{2}}[2\left(3\cos \phi -1\right)(|000⟩+|111⟩)+\left(2-e^{i\phi }+3e^{-i\phi }\right)(|001⟩+|010⟩+|100⟩)+\left(2-e^{-i\phi }+3e^{i\phi }\right)(|110⟩+|101⟩+|011⟩)]$

[0148] then a selective rotation again, the following relation is obtained. $\frac{3\cos \phi -1}{4\sqrt{2}}(|000⟩+|111⟩)+\frac{\sqrt{7+4\cos \phi -3\cos 2\phi }}{8}(|001⟩+|010⟩+|100⟩+|110⟩+|101⟩+|011⟩)$

[0149] This result indicates that the elementary computations have been used to configure |ψ₃> that meets the condition in (iii) within the range of 0≦φ≦ζ for cos ζ=⅓. |ψ₃> that meets the condition in (iv) can be similarly configured. Consequently, the “first trial method” can configure an arbitrary |ψ₃>.

[0150] Next, a case of n=4 is considered.

[0151] |ψ₄>=a₀(|0000>+|1111>)+a₁(|0001>+|0010>+|0100>+|1000>+|1110>+|1101>+|1011>+|0111>)+a₂(|0011>+|0101>+|0110>+|1001>+|1010>+|1100>)

[0152] In this equation, a₀²+4a₁²+3a₂²=½.

[0153] First, as an initial state, |0000> is provided for a first, a second, a third, and a fourth qubits, and H (Hadamard transformation) is applied to each qubit independently. $|0000⟩\to \frac{1}{4}\sum _{i=0}^{15}|\underset{\_}{i}⟩$

[0154] In the above expression, i is a binary expression of i. By selectively multiplying |0000> and |1111> by phase factor exp(iφ) and exp(−iφ), respectively, the following state |ψ> is obtained.

[0155] |ψ>=¼(e^iφ|0>+|1>+ . . . |14>+e^−iφ|15>)

[0156] Next, the inversion about average operation D is performed. If n=4, Equation (6) can be written as follows using a matrix expression. $D=\frac{1}{4}\left[\begin{array}{ccccc}-7& 1& 1& \cdots & 1\\ 1& -7& 1& \cdots & 1\\ & \cdots & \cdots & & \\ & \cdots & \cdots & & \\ 1& \cdots & \cdots & & -7\end{array}\right]$

[0157] The application of D causes the qubits to enter the following state. $D|\psi ⟩=\frac{1}{32}\left[\begin{array}{c}14-7e^{i\phi }+e^{-i\phi }\\ 2\left(3+\cos \phi \right)\\ 2\left(3+\cos \phi \right)\\ \cdots \\ 14-7e^{-i\phi }+e^{i\phi }\end{array}\right]$

[0158] Next, |0000> and |1111> are again multiplied by phase factors exp(iθ) and exp(−iθ). In this case, e meets the following equation. $e^{i\phi }=\frac{14-7e^{-i\phi }+e^{i\phi }}{\left|14-7e^{i\phi }+e^{-i\phi }\right|}$

[0159] Such a selective rotation causes the two qubits to enter the following state. $\frac{r_1\left(\phi \right)}{32}(|0000⟩+|1111⟩)+\frac{r_2\left(\phi \right)}{32}(|0001⟩+\dots +|1110⟩)$

[0160] In this case, the following equations are established.

[0161] r₁(φ)=|14−7e^iφ+e^−iφ|, r₂(φ)=2(3+cos φ)

[0162] Furthermore, |0011>, |0101>, and |0110 are multiplied by phase factor exp(iδ) and |1001>, |1010>, and |1100> are multiplied by phase factor exp(−iδ). Subsequently, another application of D causes the qubits to enter the following state. $\frac{1}{32}\left[\begin{array}{c}{r}_1\left(\phi \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\exp \left(i\delta \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\exp \left(i\delta \right)\\ r_2\left(\phi \right)\exp \left(i\delta \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\exp \left(-i\delta \right)\\ r_2\left(\phi \right)\exp \left(-i\delta \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\exp \left(-i\delta \right)\\ r_2\left(\phi \right)\\ r_2\left(\phi \right)\\ r_1\left(\phi \right)\end{array}\right]\to \frac{1}{256}\left[\begin{array}{c}-6r_1\left(\phi \right)+2r_2\left(\phi \right)\left(4+3\cos \delta \right)\\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(i\delta \right)+3\exp \left(-i\delta \right)\right)\\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(i\delta \right)+3\exp \left(-i\delta \right)\right)\\ 2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(i\delta \right)+3\exp \left(-i\delta \right)\right)\\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(-i\delta \right)+3\exp \left(i\delta \right)\right)\\ 2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(-i\delta \right)+3\exp \left(i\delta \right)\right)\\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(-i\delta \right)+3\exp \left(i\delta \right)\right)\\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ 2r_1\left(\phi \right)+6r_2\left(\phi \right)\cos \delta \\ -6r_1\left(\phi \right)+2r_2\left(\phi \right)\left(4+3\cos \delta \right)\end{array}\right]\begin{array}{c}|0000⟩\\ |0001⟩\\ |0010⟩\\ |0011⟩\\ |0100⟩\\ |0101⟩\\ |0110⟩\\ |0111⟩\\ |1000⟩\\ |1001⟩\\ |1010⟩\\ |1011⟩\\ |1100⟩\\ |1101⟩\\ |1110⟩\\ |1111⟩\end{array}$

[0163] |0011>, |0101>, and |0110> are multiplied by phase factor exp(iκ) and |1001>, |1010>, and |1100> are multiplied by phase factor exp(−iκ). In this case, κ meets the following relation. $e^{i\kappa }=\frac{2r_1\left(\phi \right)+r_2\left(\phi \right)\left(2-5\exp \left(-i\delta \right)+3\exp \left(i\delta \right)\right)}{\left|2r_1\left(\phi \right)+r_2\left(\phi \right)\left(8-5\exp \left(i\delta \right)+3\exp \left(-i\delta \right)\right)\right|}$

[0164] Such a selective rotation causes the qubits to enter the following state.

[0165] {fraction (1/256)}{s₁(φ,δ)(|0000>+|1111>)+s₂(φ,δ)(|0001>+ . . . |0111>)+s₃(φ,δ)(|0011>+ . . . +|1100>)}

[0166] In this case, the following equations are established.

[0167] S₁(φ,δ)=−6r₁(φ)+2r₂(φ) (4+3 cos δ)

[0168] S₂(φ,δ)=2r₁(φ)+6r₂(φ)cos δ)

[0169] S₃(φ,δ)=|2r₁(φ)+r₂(φ)(8−5 exp(iδ)+3 exp(−iδ))|

[0170] By selecting appropriate parameters as φ and δ, the particular partly entangled state |ψ₄> is obtained. Appropriate selection of a term for the selective rotation enables various combinations of possible values of coefficients {a₀, a₁, a₂} to be accommodated. As described above, however, the first trial method” cannot always configure an arbitrary |ψ_n> for n≧4.

[0171] [Method for Configuring a Gate Network Using the “First Trial Method” without the Second Register]

[0172] Next, FIGS. 1, 2, and 3 to 5 show a method for using of the “first trial method” to configure a network of quantum gates without the second register, for n=2, 3, and 4.

[0173] It is determined how the total number of basic quantum gates required for a network of quantum gates varies with an increase in (n) if the “first trial method” does not use the second register. For simplification, (n) is assumed to be an odd number, so it can be expressed as n=2p+1. In this case, Equation (1) is expressed as follows: $|{\psi }_{2p+1}⟩=\sum _{k=0}^p{a}_k{|k⟩}_s$

[0174] where |k> denotes a superposition of the states of 2_2p+1C_kterms in the (2p+1) qubits which contain k |1> or (2p+1−k)|1>, wherein the superposition is established using an equal weight. In addition the selective rotation is executed in the particular order of |k>(k=1, . . . , p).

[0175] FIG. 6 shows the flow of the overall process. X₁, . . . X_2p+1represent the (2p+1) qubits of the first register. A series of operations including a selective rotation, an inversion about average operation, and a selective rotation are continuously performed (q) times. During the selective rotation of φ_k, the _2p+1C_kterms containing k |1> is multiplied by phase factor exp(iφ_k), while the remaining _2p+1C_kterms containing (2p+1−k) |1> is multiplied by phase factor exp(−iφ_k).

[0176] FIG. 7 shows quantum gates that selectively rotate a single particular state. X₁, . . . , X_ndenote the n qubits of the first register. In addition, the shaded rectangles in the figure each contain a NOT-gate σ_xor an identity transformation I. Whether the rectangle contains the NOT-gate or the identity transformation depends on k. Thus, clearly, the selective rotation requires one Λ_n(R₂(2φ_k)) at minimum.

[0177] An(R₂(24))) is defined in the (second embodiment) of [Example of a configuration of a specific quantum gate network and evaluations of the computation time] described below. Although shown in the subsequent (fifth embodiment) of [Example of a configuration of a specific quantum gate network and evaluations of the computation time], 8(2n−7) basic gates have been confirmed to be required to configure Λ_n(R₂(2φ_k)). Accordingly, at least 8(2n−7) basic gates are required for the overall selective rotation. 2_2p+1C_kstates are selected for phase factors exp(iφ_k) and exp(−iφ_k). Similar operations performed on phase factors exp(iθ_k) and exp(−iθ_k). Since the selective rotation is carried out from k=1 to k=p, at least the following amount of computations is required in total. $\begin{array}{c}4\times 8\left(2n-7\right)\sum _{k=1}^p{}_{2p+1}C_k=32\left(2n-7\right)\left(2^{2p}-1\right)\\ =32\left(2n-7\right)\left(2^{n-1}-1\right)\end{array}$

[0178] As described above, if the “first trial method” does not use the second register, the amount of computations increases in the order of O(2ⁿ) with increasing n. In fact, a second register can be provided to limit the total number of basic gates to the order of O(2ⁿ/2), as described below.

[0179] [Conditions for the Success of the (R′{η}DR{η}) Contraction Method]

[0180] The phase rotation parameter may be determined as follows using conventional computations. The “first trial method” is a combination of the selective rotation and the inversion about average operation. These are unitary transformations and |ψ_n> can be assumed to be inverse to an operation for transformation to the flat superposition shown below. $\frac{1}{\sqrt{2^n}}\sum _{k={\left\{0,1\right\}}^n}|k⟩$

[0181] Fortunately, the inverse transformation of the selective rotation is also a selective rotation, while the inverse transformation of the inverse about average operation D is also an inverse about average operation D.

[0182] Thus, an operation for applying transformation (R′DR) to basic vectors having factors a_iand a_jto make new factors after transformation the same is called a “(R′DR) contraction operation.” The lemma described next provides a sufficient condition for the (R′DR) contraction operation. Then,

[0183] p=└n/2┘

[0184] is assumed and in the meantime, a_k≧0 is assumed for k=0, 1, . . . , p.

[0185] Lemma 0.1 [Sufficient Condition for a Contraction Operation]

[0186] |ψ> is assumed to be given as follows: $|\Psi ⟩=\left[\underset{\underset{2h}{⏟}}{a_0,\dots ,}\underset{\underset{2m}{⏟}}{a_1,\dots ,}{a}_{2\left(h+n\right)},\dots ,a_N\right],$

[0187] where N=2ⁿ⁻¹and 0≦a₀<a₁. The number of components a₀is assumed to be 2h while the number of components a, is assumed to be 2m. h≧1, m≧1, and h+m≦2ⁿ⁻¹are also assumed. The sum of all the coefficients of |ψ> is represented by S. $S=2{\mathrm{ha}}_0+2{\mathrm{ma}}_1+\sum _{k=2\left(h+m\right)}^{2^n-1}{a}_k$

[0188] If the following condition

[0189] S−ⁿ⁻²(a₀+a₁)≧0

[0190] is met, a (R′DR) contraction method including a selective rotation of 2m basic vectors can be used to constantly make the same the coefficients of 2(h+m) basic vectors, which have been a₀or a₁.

[0191] (Proof) When a selective rotation of a rotating angle θ(0≦θ<2π) is applied to 2m basic vectors having factor a₁, the following state is obtained. $R\left(\theta \right)|\Psi ⟩=\left[\underset{\underset{2h}{⏟}}{a_0,\dots ,}\underset{\underset{m}{⏟}}{e^{i\theta }{a}_1,\dots ,}\underset{\underset{m}{⏟}}{e^{-i\theta }{a}_1,\dots ,}{a}_{2\left(h+m\right)},\dots ,a_N\right],$

[0192] However, N=2ⁿ−1, thus R′(θ)DR(θ))|ψ> can be written as follows.

[0193] R′(θ)DR(θ)|ψ>=[A₀, . . . , A₁, . . . , A_2(h+m), . . . A₂₋₁],

[0194] In this case, the following equations are assumed. $\begin{array}{cc}\{\begin{array}{c}{2}^{n-1}{A}_0=\left(2h-2^{n-1}\right)a_0+2{\mathrm{ma}}_1\cos \theta +C\\ 2^{n-1}{A}_1=\left|2{\mathrm{ha}}_0+\left(m-2^{n-1}\right)a_1{e}^{i\theta }+{\mathrm{ma}}_1{e}^{-i\theta }+C\right|\\ 2^{n-1}{A}_j=2{\mathrm{ha}}_0+2{\mathrm{ma}}_1\cos \theta -2^{n-1}{a}_j+C\\ \mathrm{for}j=2\left(h+m\right),\dots ,2^n-1\end{array}& \left(16\right)\end{array}$

[0195] The following equation is also assumed. $C=\sum _{k=2\left(h+m\right)}^{2^n-1}{a}_k$

[0196] To make A₀²equal to A₁², the following function f(θ) is defined. $\begin{array}{cc}\begin{array}{c}f\left(\theta \right)=2^{n-2}\left(A_0^2-A_1^2\right)\\ =\left(2{\mathrm{ha}}_0+2{\mathrm{ma}}_1\cos \theta +C\right)\left(a_1\cos \theta -a_0\right)-2^{n-2}\left(a_1^2-a_0^2\right).\end{array}& \left(17\right)\end{array}$

[0197] If f(θ)=0 is met, A₀²is equal to A₁². Then, f(0) and f(π/2) are evaluated as shown below. $\begin{array}{cc}\{\begin{array}{c}f\left(0\right)=\left(a_1-a_0\right)\left[S-2^{n-2}\left(a_0+a_1\right)\right]\\ f\left(\pi /2\right)=-a_0\left(2{\mathrm{ha}}_0+C\right)-2^{n-2}\left(a_1^2-a_0^2\right)<0\end{array}& \left(18\right)\end{array}$

[0198] Thus, if S−2ⁿ⁻²(a₀+a₁)≧0 is met, 0≦θ<(π/2) exists that meets A₀²=A₁². If A₀and A₁have different signs, a selective π rotation may be carried out.

[0199] To determine the phase rotation parameter, the following procedure is used. A given state |ψ_n> is expressed using (1). In this case, a_k≧0 for 0≦k≦p.

[0200] a_minis the minimum coefficient of {a_k}, and a_min+1is the second smallest coefficient. Thus, 0≦a_min<a_min+1<a_j, but a_jis an arbitrary coefficient of |ψ_n< other than a_minand a_min+1.

[0201] The number of different coefficients in {a_k} is (P+1), so the time required to find a_minand a_min+1is only O(n) steps. S is the sum of all the coefficients of |ψ_n>.

[0202] 1. If S<2ⁿ⁻²(a_min+a_min+1) is established, S<2ⁿ⁻²(a_i+a_j) is established for all (i) and (j). In this case, the (R′DR) contraction method cannot be carried out. Thus, the (R(π)D) repetition method described below must be used.

[0203] 2. If S≧2ⁿ⁻²(a_min+a_min+1) is established, the (R′DR) contraction method can be executed to obtain relation A_min²=A_min+1². Since Equation (17) is a quadratic equation of cos θ, it can provide e efficiently.

[0204] In this case, there may be other pairs of coefficients that can be contracted, these coefficients are ignored. After the execution of the (R′DR) contraction method, by selectively rotating by π the phases of basic vectors having a negative coefficient, a state in which all coefficients are positive or zero can be obtained to determine again whether the condition in lemma 0.1 has been met.

[0205] If the (R′DR) contraction method can be executed (p) times for |ψ_n>, a flat superposition can be obtained. In contrast, since the quantum gate network is a reversible process, |ψ_n> can be configured from the flat superposition using this network. With Equation (16), {A_i} can be calculated within about O(n) steps using a conventional computer. This is because the number of different coefficients in {A_i} is (p+1).

[0206] [(R(π)D) Repetition Method]

[0207] Methods will be considered that can contract coefficients if the condition in lemma 0.1, that is, S≧2ⁿ⁻²(a_min+a_min+1) is not met. For example, the following state is assumed. $\begin{array}{cc}|\Psi ⟩=\left(\underset{\underset{\left(2^n-t\right)}{⏟}}{a_0,\dots ,}\underset{\underset{t}{⏟}}{a_1,\dots ,}\right)& \left(19\right)\end{array}$

[0208] In this equation, 0≦a₀<a₁is assumed, the number of components a, is assumed to be (2ⁿ−t), and the number of a₁is assumed to be (t). In this case, 2≦t≦2ⁿ−2 is assumed and (t) is assumed to be an even number. If the conditions 0<t<2ⁿ⁻²and [(3·2ⁿ⁻²−t)/(2ⁿ⁻²−t)] a₀<a₁are established, |ψ> meets S<2ⁿ⁻²(a₀+a₁).

[0209] In this case, the difference between coefficients A₀and A₁can be reduced performing the inversion about average operation D and then an operation for selectively rotating by π the phases of basic vectors having a negative coefficient. FIGS. 8A, 8B and 8C simply show this operation. FIGS. 8A, 8B and 8C show the coefficients of basic vectors of (8A)|ψ>, (8B)D|ψ>, and (8C)R(π)D|ψ>. These figures show that the difference between coefficients decreases after the application of (R(π)D) to |ψ>. Thus, [S−2ⁿ⁻²(a_min+a_min+1)] is expected to be increased by continuously applying (R(π)D). This will be clarified using the next lemma.

[0210] (Lemma 0.2)

[0211] A state given as shown below is considered. $|\Psi ⟩=\left(\underset{\underset{2h}{⏟}}{a_0,\dots ,}\underset{\underset{2m}{⏟}}{a_1,\dots ,}{a}_{2\left(h+m\right)},\dots ,a_N\right).$

[0212] In this case, N=2ⁿ−1 and 0≦a₀<a_i<a₁for j=2(h+m), . . . , N. The number of components a₀is assumed to be 2h, the number of components a₁is assumed to be 2m, and h≧1, m≧1, and h+m≦2ⁿ⁻¹are assumed. S, which is the sum of all the coefficients of |ψ>, is assumed to meet the following condition.

[0213] S−ⁿ⁻²(a₀+a₁)<0.  (20)

[0214] The following state is assumed to have been obtained by performing the inversion about average operation on lip>and selectively rotating by n the phases of basic vectors having a negative coefficient.

[0215] R(π)D|ψ>=[B₀, . . . , B₁, . . . , B₂(h+m), . . . , B_N],

[0216] S′ is defined as the sum of all the coefficients of R(π)D|ψ>.

[0217] 1. The following relations are established. For

[0218] j=2(h+m), . . . , N(=2ⁿ−1),0<B₀<B₁<B_jand [S′−2ⁿ⁻²(B₀+B₁)]−[S−2ⁿ⁻²(a₀+a₁)]>(2h−2ⁿ⁻¹)a₀+(2ⁿ−2h)a₁>0.  (21)

[0219] 2. When the following quantity is defined, $\begin{array}{cc}\{\begin{array}{c}{ϵ}^{\left(0\right)}=\left(2h-2^{n-1}\right)a_0+\left(2^n-2h\right)a_1\\ {ϵ}^{\left(1\right)}=\left(2h-2^{n-1}\right)B_0+\left(2^n-2h\right)B_1\end{array}& \left(22\right)\end{array}$

[0220] the following relation is established.

[0221] ε⁽¹⁾>ε⁽⁰⁾>0.

[0222] (Proof)

[0223] D|ψ> is determined as follows.

[0224] D|ψ>=[a′₀, . . . ,a′₁, . . . ,a′_2(h+m), . . . , a′_N]

[0225] In this case, N=2ⁿ−1 $\begin{array}{cc}\{\begin{array}{cc}{2}^{n-1}{a}_0^{\prime }=S-2^{n-1}{a}_0& \\ 2^{n-1}{a}_1^{\prime }=S-2^{n-1}{a}_1& \\ 2^{n-1}{a}_j^{\prime }=S-2^{n-1}{a}_j& \mathrm{for}2\left(h+m\right)\leqq j\leqq 2^n-1\end{array}& \left(23\right)\end{array}$

[0226] Obviously, S−2ⁿ⁻¹a₀>0. Using condition S−2ⁿ⁻²(a₀+a₁)<0 provides relation S−²⁻¹a_k<0 for ^∀k≠0. Thus, R(π)D|ψ> is obtained as shown below. $\begin{array}{cc}\{\begin{array}{cc}{2}^{n-1}{B}_0=S-2^{n-1}{a}_0& \\ 2^{n-1}{B}_1=-S+2^{n-1}{a}_1& \\ 2^{n-1}{B}_j=-S+2^{n-1}{a}_j& \mathrm{for}2\left(h+m\right)\leqq j\leqq 2^n-1\end{array}& \left(24\right)\end{array}$

[0227] The difference between B₁and B₀is determined as follows.

[0228] 2ⁿ⁻¹(B₁−B₀)=−2[S−2ⁿ⁻²(a₀+a₁)]>0.  (25)

[0229] In this case, the assumption in Equation 20 has been used. In addition, B₁<B_jis obvious for j=2(h+m), . . . 2ⁿ−1. Thus, 0<B₀<B₁<B_jis obtained for j=2(h+m), . . . , 2−1.

[0230] Based on the following relations, $S^{\prime }=\frac{4h}{2^{n-1}}\left(S-2^{n-1}{a}_0\right)-S,B_0+B_1=a_1-a_0.$

[0231] Δ, which denotes a change in [S−2ⁿ⁻²(a₀+a₁)] caused by the (R(π)D) operation, can be rewritten as shown below. $\begin{array}{cc}\begin{array}{c}\Delta =\left[S^{\prime }-2^{n-2}\left(B_0+B_1\right)\right]-\left[S-2^{n-2}\left(a_0+a_1\right)\right]\\ =2\left(\frac{2h}{2^{n-1}}-1\right)S-\left(4h-2^{n-1}\right)a_0.\end{array}& \left(26\right)\end{array}$

[0232] To precisely evaluate Δ, several convenient inequalities are provided. Defining S provides the following relation. $\begin{array}{cc}S=2{\mathrm{ha}}_0+2{\mathrm{ma}}_1+\sum _{k=2\left(h+m\right)}^{2^n-1}{a}_k\geqq 2{\mathrm{ha}}_0+\left(2^n-2h\right)a_1.& \left(27\right)\end{array}$

[0233] Assumptions (20) and (27) allow the following relation to be derived. $\begin{array}{cc}\begin{array}{c}0>S-2^{n-2}\left(a_0+a_1\right)\\ \geqq 2{\mathrm{ha}}_0+\left(2^n-2h\right)a_1-2^{n-2}\left(a_0+a_1\right)\\ =\left(2h-2^{n-2}\right)a_0+\left(3·2^{n-2}-2h\right)a_1.\end{array}& \left(28\right)\end{array}$

[0234] Then, rougher inequalities can be obtained by modifying (28).

[0235] 0>2ha₀−2ⁿ⁻²a₁+(3·2ⁿ⁻²−2h)a₁=2ha₀+(2ⁿ⁻¹−2h)a₁.   (29)

[0236] Since 0≦a₀<a₁, the following inequality is obtained.

[0237] 2h−2ⁿ⁻¹>0.  (30)

[0238] Reviewing relations (30) and (28) allows the following inequality to be obtained.

[0239] 2h>3·2ⁿ⁻².  (31)

[0240] Then, the system is ready for strictly evaluating Δ. Relation (31) enables (27) to be assigned to Equation (26). $\begin{array}{cc}\begin{array}{c}\Delta \geqq 2\left(\frac{2h}{2^{n-1}}-1\right)\left[2{\mathrm{ha}}_0+\left(2^n-2h\right)a_1\right]-\left(4h-2^{n-1}\right)a_0\\ =(1/2^{n-1}\})\left[8h^2-8h·2^{n-1}+2^{2\left(n-1\right)}\right]a_0+\left(1/2^{n-1}\right)\\ \left[-8h^2+6h·2^n-2^{2n}\right]a_1\\ =\left(1/2^{n-1}\right)[(4h-3·2^{n-1}\})\left(2h-2^{n-2}\right)-2^{2n-3}]a_0+\\ \left(1/2^{n-1}\right)[\left(-4h+3·2^{n-1}\right)(2h-3·2^{n-2}\})+2^{2n-3}]a_1\\ =\left(1/2^{n-1}\right)\left(4h-3·2^{n-1}\right)\left[\left(2h-2^{n-2}\right)a_0+\left(3·2^{n-2}-2h\right)a_1\right]+\\ 2^{n-2}\left(a_1-a_2\right).\end{array}& \left(32\right)\end{array}$