text:
# Appearance and Stability of Anomalously Fluctuating States in Shor’s Factoring Algorithm

## I Introduction

Quantum computers are considered to be more efficient than classical computers in solving certain problems Deutsch\_1 ; Shor\_1 ; Ekert\_Jozsa ; Nielsen\_Chaung . Since the efficiency of computation becomes relevant only when the size $`N`$ of the input is huge, the efficiency is defined in terms of the asymptotic behavior of the number $`Q`$ of the computational steps as the size $`N`$ of the input is increased. To study the asymptotic behavior, one must take the data size large but finite. Since larger $`N`$ generally requires a larger number $`L`$ of qubits as $`L\mathrm{log}N`$, $`L`$ of a relevant quantum computer becomes large but finite. Therefore, a relevant quantum computer is a many-body quantum system with large but finite degrees of freedom, $`1L<+\mathrm{}`$.

In the conventional many-body physics, one is usually interested in states that approach as $`L\mathrm{}`$ a “vacuum” state and finite excitations on it. This means that one is usually uninterested in other states of finite systems. In a quantum computer, on the other hand, various states are generated according to the algorithm and the input. It is therefore expected that some of them would be very different from states that are treated in the conventional many-body physics. It is very interesting to reveal physical properties of such “anomalous” states as well as their roles in quantum computations.

For quantum states of general systems with large but finite degrees of freedom, Shimizu and Miyadera (SM) recently studied the stabilities against weak noises, against weak perturbations from environments, and against local measurements SM02 . By fully utilizing the locality of the theory, they obtained the general and universal results: the stabilities of quantum states are determined by long-distance correlations between local operators. As measures of the long-range correlations of quantum states, SM employed the “cluster property,” which plays a fundamental role in field theory haag , and the “fluctuations of additive operators,” which will be explained in the following section. If a pure state has anomalously large fluctuation of an additive operator(s), then the state has a long-distance correlation(s). Such a state does not have the cluster property, and is quite anomalous in many-body physics. Such anomalies are directly related to the stabilities of the quantum states.

Since the stability of quantum states against noises has been considered as a key to realizing quantum computers unruh ; Palma ; Miquel\_Paz\_Perazzo , it is interesting to apply the general theory by SM to quantum computers. In this paper, we analyze quantum computers performing Shor’s factoring algorithm Shor\_1 ; Ekert\_Jozsa ; Nielsen\_Chaung  using the general theory by SM and numerical simulations. We show that anomalous states, which have anomalously large fluctuations of additive operators, appear during the computation. For large $`L`$, they decohere at anomalously great rates in the presence of long-wavelength noises, while for small $`L`$ the decoherence rates are of the same order of magnitude as those of normal states. The decoherence of some of the anomalous states, not all of them, results in the reduction of the success probability of the computation. Therefore, the decoherence of such anomalous states is crucial to Shor’s factoring algorithm with huge inputs.

## II Summary of the general theory of the decoherence rates of quantum states in systems of large but finite degrees of freedom

SM SM02  studied stabilities of quantum states of general systems of large but finite degrees of freedom. Among three kinds of stabilities discussed by them, we focus on the stability against weak classical noises; namely, we focus on the decoherence due to weak classical noises.

As compared with general many-body systems, quantum computers are often assumed to have the following special properties (although they are not necessary): (a) The system Hamiltonian is assumed to be negligible, so that quantum states of a quantum computer do not evolve unless the computer is subjected to external operations and/or noises. (b) Qubits are assumed to be located on a one-dimensional lattice. In this section, we summarize the result of SM for the decoherence rate $`\mathrm{\Gamma }`$, assuming these special properties.

### II.1 Normalized additive operator

We consider a quantum computer that is composed of $`L`$ ($`1`$) qubits which are located on sites of a one-dimensional lattice with a unit lattice constant. Let $`\widehat{a}(\mathrm{})`$ be a local operator at site $`\mathrm{}`$ ($`=1,2,\mathrm{},L`$), which for qubit systems is a polynomial of the Pauli operators $`\widehat{\sigma }_x(\mathrm{}),\widehat{\sigma }_y(\mathrm{}),\widehat{\sigma }_z(\mathrm{})`$, acting on the qubit at $`\mathrm{}`$. Such a polynomial becomes a linear combination of the identity operator $`\widehat{1}(\mathrm{})`$ and $`\widehat{\sigma }_x(\mathrm{}),\widehat{\sigma }_y(\mathrm{}),\widehat{\sigma }_z(\mathrm{})`$ because of the SU(2) algebra. We define a normalized additive operator $`\widehat{A}`$ by

$$\widehat{A}=\frac{1}{L}\underset{\mathrm{}=1}{\overset{L}{}}\widehat{a}(\mathrm{}),$$
(1)
which is the normalized one of the “additive operator” defined in Ref. SM02 . For example, if we take

$$\widehat{a}(\mathrm{})=(1)^{\mathrm{}}\widehat{\sigma }_z(\mathrm{}),$$
(2)
then $`\widehat{A}`$ is the $`z`$ component of the “staggered magnetization,” which has a finite expectation value when the system has an antiferromagnetic order.

Note that normalized additive operators are macroscopic operators. Thermodynamics assumes that fluctuations of any macroscopic observables are $`o(V^2)`$ for pure phases SM02 , where $`V`$ is the volume of the system. However, this is not necessarily satisfied by pure quantum states of finite macroscopic systems SM02 ; HL ; KT ; pre01 , as will be described in the following.

### II.2 $`L`$ dependence of quantum states

In order to discuss $`L`$ dependences of properties of quantum states, some rule is necessary that defines $`L`$ dependence of quantum states. The simplest one of such a rule is that the quantum states are homogeneously extended with increasing $`L`$. For example, consider a superposition of two Néel states,

$$\frac{1}{\sqrt{2}}|1010\mathrm{}10+\frac{1}{\sqrt{2}}|0101\mathrm{}01,$$
(3)
where $`|1`$ and $`|0`$ denote the spin-up and -down states, respectively. To increase $`L`$ of this state, one can simply add two spins as $`\frac{1}{\sqrt{2}}|1010\mathrm{}1010+\frac{1}{\sqrt{2}}|0101\mathrm{}0101.`$ Unfortunately, states in quantum computers do not have such simple homogeneity. However, they are homogeneous in a broad sense because states with a larger $`L`$ (which is necessary for a larger input $`N`$) and states with a smaller $`L`$ are both generated according to the same algorithm. As a result, both of them have similar structures, as will be demonstrated explicitly in Sec. V.4. This allows us to analyze the asymptotic behaviors of properties of states in quantum computers as $`N\mathrm{}`$.

### II.3 Normally and anomalously fluctuating states

As a measure of correlations between distant qubits for a system of many qubits, SM SM02  proposed the use of fluctuations of additive operators. We here summarize their proposal in terms of normalized additive operators.

Consider a pure state $`|\psi `$, and put

$$\mathrm{\Delta }\widehat{A}\widehat{A}\psi |\widehat{A}|\psi .$$
(4)
We focus on the $`L`$ dependence of the fluctuation $`\psi |(\mathrm{\Delta }\widehat{A})^2|\psi `$ for $`L1`$, and define an index $`p`$ by

$$\psi |(\mathrm{\Delta }\widehat{A})^2|\psi =O(L^{p2}).$$
(5)
The value of $`p`$ depends on both $`\widehat{A}`$ and $`|\psi `$. For example, if the correlation between $`\widehat{a}(\mathrm{})`$ and $`\widehat{a}(\mathrm{}^{})`$ for large $`|\mathrm{}\mathrm{}^{}|`$ is negligibly small for $`|\psi `$, then $`p=1`$ for the normalized additive operator $`\widehat{A}`$ which is composed of $`\widehat{a}(\mathrm{})`$ as Eq. (1).

For a given $`|\psi `$, if the maximum value of $`p`$ (among those of all normalized additive operators) is unity, $`|\psi `$ is called a normally fluctuating state (NFS). It is easy to show that any separable state is a NFS. Note however that the inverse is not necessarily true. For example, $`|100\mathrm{}0,|010\mathrm{}0,\mathrm{},|000\mathrm{}1`$ are all separable states, hence are NFSs. Their superposition

$$\frac{1}{\sqrt{L}}\left[|100\mathrm{}0+|010\mathrm{}0+|001\mathrm{}0+\mathrm{}+|000\mathrm{}1\right]|\mathrm{W}$$
(6)
is also a NFS because $`p=1+o(L)/L`$, but non separable.

On the other hand, if there is a normalized additive operator(s) $`\widehat{A}`$ for which $`p=2`$, then the pure state $`|\psi `$ is called an anomalously fluctuating state (AFS) because the fluctuation of $`\widehat{A}`$ is anomalously large. In this case, $`\widehat{a}(\mathrm{})`$ and $`\widehat{a}(\mathrm{}^{})`$, which compose $`\widehat{A}`$, are strongly correlated even when $`|\mathrm{}\mathrm{}^{}|L`$. Since AFSs are pure states, this indicates that AFSs are entangled macroscopically SM02 . This entanglement is macroscopic because one cannot turn a NFS into an AFS by adding a small ($`L^0`$) number of Bell pairs. Note, in particular, that the state $`|\mathrm{W}`$ of Eq. (6) is entangled, but not macroscopically entangled, hence is not an AFS but a NFS. In this way, the value of $`p`$ can be taken as a quantitative measure of macroscopic entanglement.

A simple example of an AFS is the state of Eq. (3), for which $`\psi |(\mathrm{\Delta }\widehat{A})^2|\psi =1`$ for the staggered magnetization defined by Eqs. (1) and (2). Another simple example of an AFS is

$$\frac{1}{\sqrt{2}}|000\mathrm{}0+\frac{1}{\sqrt{2}}|111\mathrm{}1|\mathrm{C},$$
(7)
for which the fluctuation of the “magnetization” $`\widehat{M}_z\frac{1}{L}_{\mathrm{}}\widehat{\sigma }_z(\mathrm{})`$ is anomalously large; $`\mathrm{C}|(\mathrm{\Delta }\widehat{M}_z)^2|\mathrm{C}=1.`$

From the viewpoints of many-body physics and experiments, the index $`p`$ seems a natural measure of macroscopic entanglement. In ferromagnets, for example, $`|\mathrm{C}`$ is quite anomalous because it is a superposition of two states that have different values of the macroscopic variable $`\widehat{M}_z`$. Such a state is usually discarded in many-body physics for many reasons. One reason is that it is very hard to generate such a state experimentally. Another reason is that such a state is not allowed as a pure state in the limit of infinite degrees of freedom, $`L\mathrm{}`$ SM02 . On the other hand, $`|\mathrm{W}`$ is a normal state which can easily be generated experimentally, although it is sometimes classified as a strongly entangled state in quantum information theory. In insulating solids, for example, the state vector of a many-body state in which a Frenkel exciton is excited on the ground state takes the form of $`|\mathrm{W}`$; namely, in many-body physics $`|\mathrm{W}`$ is just an ordinary state in which a single quasiparticle is excited on the ground state. Since many-body physics is directly related to (and has been tested by) experiments, a normal (abnormal) state in many-body physics is also a normal (abnormal) state in experiments. Therefore, our measure of macroscopic entanglement seems natural from the viewpoints of many-body physics and experiments. Considering that quantum computers should be fabricated from real materials, this indicates also that our measure would be suitable for discussing realization of quantum computers. Furthermore, an efficient method of computing $`p`$ for general states has been developed in Ref. SS03 , whereas some of the other measures are hard to compute for general states. This is also an advantage of the present measure disadv .

Although states with $`1<p<2`$ are possible NGmodes , we focus on two classes of states, NFSs ($`p=1`$) and AFSs ($`p=2`$), in this paper.

### II.4 Decoherence rate

We consider the decoherence rate $`\mathrm{\Gamma }`$ of states of quantum computers. For the origin of the decoherence, we assume a weak classical noise $`f(\mathrm{},t)`$, acting on every site $`\mathrm{}`$, with vanishing average $`\overline{f(\mathrm{},t)}=0`$. The case of a weak perturbation from the environment can be treated in a similar manner. We assume that $`\overline{f(\mathrm{},t)f(\mathrm{}^{},t^{})}`$ \[$`=\overline{f(\mathrm{}^{},t^{})f(\mathrm{},t)}`$\] depends only on $`|\mathrm{}\mathrm{}^{}|`$ and $`|tt^{}|`$. We denote the spectral intensity of $`f(\mathrm{},t)`$ by $`g(k,\omega )`$, which is non-negative by definition. Here, $`k`$ takes discrete values from $`\pi `$ to $`\pi `$ with separation $`2\pi /L`$ k , whereas $`\omega `$ takes continuous values. The autocorrelation function can be expressed as

$$\overline{f(\mathrm{},t)f(\mathrm{}^{},t^{})}=\underset{k}{}\frac{d\omega }{2\pi }g(k,\omega )e^{ik(\mathrm{}\mathrm{}^{})i\omega (tt^{})}.$$
(8)
Since physical interactions must be local, the interaction between the qubit system and the noise should be the sum of local interactions:

$$\widehat{H}_{\mathrm{int}}(t)=\lambda \underset{\mathrm{}=1}{\overset{L}{}}f(\mathrm{},t)\widehat{a}(\mathrm{}),$$
(9)
where $`\lambda `$ is a positive constant and $`\widehat{a}(\mathrm{})`$ is a local operator at site $`\mathrm{}`$. Since increasing $`\lambda `$ is equivalent to increasing the amplitude of the noise, $`\lambda `$ may be interpreted as the noise amplitude times the coupling constant. We shall therefore take $`f`$ to have a normalized amplitude, as Eq. (39), and vary the noise amplitude by varying $`\lambda `$.

Assuming this local interaction and a short correlation time for the noise, SM showed that for $`L1`$ the decoherence rate $`\mathrm{\Gamma }`$ of a pure state $`|\psi `$ is directly related to fluctuations of additive operators. In terms of normalized additive operators, their formula reads

$$\mathrm{\Gamma }\lambda ^2L^2\underset{k}{}g(k)\psi |\mathrm{\Delta }\widehat{A}_k^{}\mathrm{\Delta }\widehat{A}_k|\psi .$$
(10)
Here, $`g(k)`$ is an average value of $`g(k,\omega )`$ SM02  and $`\mathrm{\Delta }\widehat{A}_k\widehat{A}_k\psi |\widehat{A}_k|\psi `$, where

$$\widehat{A}_k\frac{1}{L}\underset{\mathrm{}=1}{\overset{L}{}}\widehat{a}(\mathrm{})e^{ik\mathrm{}}.$$
(11)
For quantum computers, $`g(k)g(k,0)`$ because the system Hamiltonian is negligible. Note that $`\widehat{A}_k`$ is a normalized additive operators, where $`\widehat{a}(\mathrm{})e^{ik\mathrm{}}`$ of Eq. (11) corresponds to $`\widehat{a}(\mathrm{})`$ of Eq. (1). Hence, formula (10) shows that $`\mathrm{\Gamma }`$ of a pure state $`|\psi `$ of a quantum computer is determined by the fluctuation of a normalized additive operator that is composed of the local operators in $`\widehat{H}_{\mathrm{int}}`$. Note that the formula of a pioneering work by Palma et alPalma  is a special case of the above general formula.

### II.5 Fragility

We say that a quantum state is “fragile” if its decoherence rate $`\mathrm{\Gamma }`$ is anomalously great in such a way that

$$\mathrm{\Gamma }KL^{1+\delta },$$
(12)
where $`K`$ is a function of microscopic parameters, such as $`\lambda `$, and $`\delta `$ is a positive constant. This is an anomalous situation in which the decoherence rate per qubit, $`\mathrm{\Gamma }/LKL^\delta `$, grows with increasing $`L`$. For a nonfragile state (for which $`\delta =0`$), in contrast, $`\mathrm{\Gamma }/LK`$ is independent of $`L`$, in consistency with the naive expectation. This is a normal situation in which the total decoherence rate $`\mathrm{\Gamma }`$ is simply the sum of local decoherence rates.

For large $`L`$, fragile quantum states decohere much faster than nonfragile states because $`\mathrm{\Gamma }`$ becomes anomalously great, even when the coupling constant between the system and the noise is small.

### II.6 Non fragility of all NFSs and fragility of some AFSs

When $`|\psi `$ is a NFS, $`\psi |\mathrm{\Delta }\widehat{A}_k^{}\mathrm{\Delta }\widehat{A}_k|\psi O(1/L)`$ for any $`\widehat{A}_k`$, hence

$$\mathrm{\Gamma }\lambda ^2O(L)\underset{k}{}g(k).$$
(13)
Since $`_kg(k)=\overline{f(x,t)f(x,0)}dt`$ does not depend on $`L`$, we find that NFSs never become fragile under weak perturbations from any random noises SM02 .

When $`|\psi `$ is an AFS, on the other hand, $`\psi |\mathrm{\Delta }\widehat{A}_k^{}\mathrm{\Delta }\widehat{A}_k|\psi =O(L^0)`$ for some $`\widehat{A}_k`$, i.e., for some local operator $`\widehat{a}(x)`$ and some wave number $`k=k_0`$. Hence, if $`\widehat{H}_{\mathrm{int}}`$ has a term that is composed of such $`\widehat{a}(x)`$’s, then

$$\mathrm{\Gamma }\lambda ^2O(L^2)g(k_0)+\lambda ^2O(L)\underset{k(k_0)}{}g(k).$$
(14)
In this case, the AFS becomes fragile if $`g(k_0)=O(L^{1+\delta })`$, where $`\delta >0`$; namely, for an AFS, there can exist weak classical noises or weak perturbations from environments that make the AFS fragile. Whether such a noise or environment really exists in a quantum computer system depends on physical situations.

Although SM also considered a more fundamental instability of AFSs (i.e., instability against local measurements), the fragility is sufficient for the purpose of the present paper.

## III Conjectures on quantum computers

From the general results summarized in the preceding section, we are led to the following conjectures on quantum computersS\_talk .

### III.1 Quantum computers should utilize AFSs

Entanglement has been considered to be essential to efficient quantum computations Deutsch\_1 ; Shor\_1 ; Ekert\_Jozsa ; Nielsen\_Chaung ; miyake ; Jozsa\_Linden . To discuss the efficiency of computation, one must study the asymptotic behavior of the computational time as $`N\mathrm{}`$. It is natural to consider that more entanglement is required for larger $`N`$. Since AFSs are entangled macroscopically, we are led to the following conjecture, which we call conjecture (i): In performing an algorithm that is much more efficient than any classical algorithms, a quantum computer should utilize AFSs in some stages of the computation.

Although the use of entanglement in quantum computations was somehow confirmed in the previous works miyake ; Jozsa\_Linden , the magnitude of entanglement for large $`L`$ can be defined in various ways. As a quantitative measure of entanglement, we propose here to use the asymptotic behavior, Eq. (5), of fluctuations of normalized additive operators. This enables us not only to identify macroscopically entangled states for large $`L`$, but also to estimate their decoherence rates using formulas (10), (13), and (14).

### III.2 Some of AFSs appearing during quantum computation would be fragile

If conjecture (i) is the case, the results of Sec. II.6 lead us to the second conjecture, which we call conjecture (ii): Some of the AFSs appearing during quantum computation would be fragile under realistic weak classical noises or weak perturbations from environments.

For example, suppose that electromagnetic noises at 4 K is the dominant noise. If the physical dimension of a quantum computer is less than 1 cm, then $`g(k)`$ of the electromagnetic noises behaves as follows k :

$$g(k)\{\begin{array}{cc}O(L^0)\hfill & (k=0)\hfill \\ O(1/L)\hfill & (k2\pi /L).\hfill \end{array}$$
(15)
Therefore, according to Eq. (14), AFSs with $`k_0=0`$ becomes fragile (with $`\delta =1`$), whereas AFSs with $`k_02\pi /L`$ are nonfragile; namely, if AFSs with $`k_0=0`$ appear during the computation, they are fragile in electromagnetic noises at 4 K.

### III.3 Fragility of some AFSs should be fatal to quantum computation

If a fragile AFS is used in the quantum computation, it decoheres at an anomalously great rate as given by Eq. (12) with $`\delta >0`$. Since quantum coherence is considered to be important in quantum computations, we are further led to the third conjecture, which we call conjecture (iii): The anomalously fast decoherence of such a fragile AFS(s) should be fatal to a quantum computation, and the quantum computation would become impossible for large $`L`$ even if the coupling constant between the system and the noise or environment is small, unless error correcting codes (ECC) ec1 ; ec2 ; ec3 ; ec4  and/or a decoherence-free subspace (DFS) dfs1 ; dfs2 ; dfs3  were successfully used. Since such efficient ECC and/or a DFS against all existing noises would not be easy to realize (see Sec. VIII.5), improvements of the algorithm seem necessary; namely, if possible, one should implement the algorithm in such a way that only AFSs that are not fragile in existing noises are used.

In this paper, we study these conjectures by analyzing quantum computers performing Shor’s factoring algorithm.

## IV Quick summary of Shor’s factoring algorithm

To study the conjectures raised in the preceding section, we perform numerical simulations on Shor’s factoring algorithm Shor\_1 ; Ekert\_Jozsa , which is believed to be much (exponentially) faster than any classical algorithms. In order to establish notations, we summarize in this section the main part, which we will simulate, of the algorithm.

In order to factor an integer $`N`$, we use two quantum registers $`R_1`$ and $`R_2`$, which are called the first and second registers, respectively. They are composed of $`L_1`$ and $`L_2`$ qubits, respectively, where

$`2\mathrm{log}NL_1<2\mathrm{log}N+1,`$ (16)
$`\mathrm{log}NL_2<\mathrm{log}N+1.`$ (17)
Here, $`\mathrm{log}`$ denotes $`\mathrm{log}_2`$. The total number of qubits is $`L_1+L_2L.`$ The state of each qubit is described by a vector of a Hilbert space spanned by two basis states, $`|0`$ and $`|1`$. As a computational basis of register $`R_k`$, we take the set of the tensor products of the basis states of $`L_k`$ qubits;

$$|a_1,a_2,\mathrm{},a_{L_k}^{(k)}|a^{(k)}.$$
(18)
Here $`a_{\mathrm{}}=0`$ or $`1`$ ($`\mathrm{}=1,2,\mathrm{},L_k`$) and $`a_{\mathrm{}=1}^{L_k}a_{\mathrm{}}2^\mathrm{}1,`$ for example, $`|0^{(1)}=|00\mathrm{}0^{(1)}`$, $`|1^{(1)}=|10\mathrm{}0^{(1)}`$, and $`|2^{L_1}1^{(1)}=|11\mathrm{}1^{(1)}`$. The initial state is taken as the following separable state;

$$|0^{(1)}|1^{(2)}|\psi _{\mathrm{init}}.$$
(19)
First, the Hadamard transformation is performed by successive unitary transformations on individual qubits of $`R_1`$, yielding

$$\frac{1}{\sqrt{2^{L_1}}}\underset{a=0}{\overset{2^{L_1}1}{}}|a^{(1)}|1^{(2)}|\psi _{\mathrm{HT}}.$$
(20)
Then, we take randomly an integer $`𝗑`$ ($`𝗑<N`$) that is coprime to $`N`$ x , and perform the modular exponentiation by successive pairwise unitary transformations, yielding

$$\frac{1}{\sqrt{2^{L_1}}}\underset{a=0}{\overset{2^{L_1}1}{}}|a^{(1)}|𝗑^a\text{ mod }N^{(2)}|\psi _{\mathrm{ME}}.$$
(21)
Finally, the discrete Fourier transformation (DFT) is performed by successive pairwise unitary transformations, yielding

$$\frac{1}{2^{L_1}}\underset{a=0}{\overset{2^{L_1}1}{}}\underset{c=0}{\overset{2^{L_1}1}{}}\mathrm{exp}\left(\frac{2\pi i}{2^{L_1}}ca\right)|\overline{c}^{(1)}|𝗑^a\text{ mod }N^{(2)}|\psi _{\mathrm{final}}.$$
(22)
Here, $`\overline{c}`$ is the number that is obtained by reading the bits of $`c`$ in the reversed order Ekert\_Jozsa . This completes the main part of Shor’s factoring algorithm, and no more quantum computation is necessary. Since one can read $`\overline{c}`$ reversely, the final state $`|\psi _{\mathrm{final}}`$ is practically equivalent to $`\frac{1}{2^{L_1}}_{a=0}^{2^{L_1}1}_{c=0}^{2^{L_1}1}\mathrm{exp}\left[\frac{2\pi i}{2^{L_1}}ca\right]|c^{(1)}|𝗑^a\text{ mod }N^{(2)}.`$

The amplitude of $`|\psi _{\mathrm{final}}`$ has dominant peaks at basis states $`|c^{(1)}`$ satisfying

$$\frac{r}{2}\overline{c}r\mathrm{mod}2^{L_1}\frac{r}{2},$$
(23)
where $`r`$ ($`<N`$) is the “order” of $`𝗑\text{ mod }N`$ Shor\_1 ; Ekert\_Jozsa . By performing a measurement that diagonalizes the computational basis $`\{|c^{(1)}\}`$ of $`R_1`$, one can obtain a value of $`c`$ satisfying inequality (23) with the probability greater than $`4/\pi ^2`$. When such an integer $`c`$ is obtained, one can find uniquely for each $`c`$, using the continued fraction expansion of $`\overline{c}/2^{L_1}`$, a fraction $`c^{}/r`$ that satisfies

$$\left|\frac{\overline{c}}{2^{L_1}}\frac{c^{}}{r}\right|\frac{1}{2^{L_1+1}},$$
(24)
where $`c^{}`$ is an integer. If $`c^{}`$ happens to be coprime to $`r`$, one can know the value of $`r`$. In other cases, where $`c^{}`$ is not coprime to $`r`$ or $`c`$ does not satisfy inequality (23), one would obtain wrong results for $`r`$ or could not obtain $`c^{}`$ satisfying inequality (24). Whether the obtained value of $`r`$ is correct or not can be checked easily by calculating $`𝗑^r`$ mod $`N`$ using a classical computer. When the correct value of $`r`$ is not obtained, one can perform the algorithm again. It is known that one can successfully obtain the correct value by repeating the algorithm $`O(\mathrm{log}N)`$ times. When $`r`$ is thus obtained, one can know a factor of $`N`$ with the probability greater than $`1/2`$. Therefore, one can factor $`N`$ efficiently by repeating the algorithm.

## V Numerical simulation without noise

In order to study conjecture (i), we perform numerical simulations without noise in this section.

### V.1 Simplification and the number of computational steps

The process of the modular exponentiation $`|\psi _{\mathrm{HT}}|\psi _{\mathrm{ME}}`$ costs $`O(L_1^3)`$ steps Shor\_1 ; Ekert\_Jozsa . Since it will turn out that $`R_1`$ takes a major role, we simplify operations on $`R_2`$ in our numerical simulations; namely, we represent the process $`|\psi _{\mathrm{HT}}|\psi _{\mathrm{ME}}`$ as the product of $`L_1`$ controlled unitary transformations $`U^{a_{\mathrm{}}2^\mathrm{}1}`$ ($`\mathrm{}=1,2,\mathrm{},L_1`$), which is described in Box 5.2 of Ref. Nielsen\_Chaung . Since $`U^{a_{\mathrm{}}2^\mathrm{}1}`$ can be decomposed into $`O(L_1^2)`$ pairwise unitary transformations, the states appearing during the modular exponentiation in our simulations correspond to $`L_1`$ representative states out of $`O(L_1^3)`$ states. As a result of this simplification, the total number $`Q`$ of computational steps, from $`|\psi _{\mathrm{init}}`$ to $`|\psi _{\mathrm{final}}`$, in our simulation becomes

$$Q=2L_1+\frac{L_1(L_1+1)}{2}.$$
(25)
Here, $`L_1`$ comes from the Hadamard transformation and another $`L_1`$ from the modular exponentiation, whereas $`L_1(L_1+1)/2`$ comes from the discrete Fourier transformation. This $`Q`$ is smaller than $`O(L_1^3)`$ steps of a real computation because of the above simplification.

We denote the time interval between subsequent computational steps by $`\tau `$. Although $`\tau `$ depends on the hardware of the quantum computer, this dependence does not matter in the following discussions because we are only interested in the $`N`$ dependence, which is the only crucial factor in discussing the exponential speedup. The total computational time, starting from $`|\psi _{\mathrm{init}}`$ and ending with the measurement of $`|\psi _{\mathrm{final}}`$, is given by

$$\tau _{\mathrm{total}}=(Q+1)\tau .$$
(26)
### V.2 Choice of normalized additive operators

To judge that a quantum state is not an AFS, fluctuations of all normalized additive operators have to be investigated. On the other hand, to judge that a state is an AFS, it is sufficient to find out one normalized additive operator $`\widehat{A}`$ for which $`\mathrm{\Delta }\widehat{A}^2=O(L^0)`$. In order to confirm conjecture (i), it is therefore sufficient to find out one $`\widehat{A}`$ for which a quantum state(s) appearing in the computational process has an anomalously large fluctuation, $`\mathrm{\Delta }\widehat{A}^2=O(L^0)`$.

As normalized additive operators, we here consider the “magnetization” in three directions $`\alpha =x,y,z`$, for the total and the individual registers, which are defined by

$$\widehat{M}_\alpha =\frac{1}{L}\underset{\mathrm{}R_1,R_2}{}\widehat{\sigma }_\alpha (\mathrm{})$$
(27)
and

$$\widehat{M}_{}^{(k)}{}_{\alpha }{}^{}=\frac{1}{L_k}\underset{\mathrm{}R_k}{}\widehat{\sigma }_\alpha (\mathrm{}),$$
(28)
respectively. The maximum value of $`(\mathrm{\Delta }\widehat{M}_\alpha )^2`$ is unity, which is taken, e.g., by the following AFS:

$$\frac{1}{\sqrt{2}}|0^{(1)}|0^{(2)}+\frac{1}{\sqrt{2}}|2^{L_1}1^{(1)}|2^{L_2}1^{(2)}.$$
(29)
For separable states, on the other hand, $`(\mathrm{\Delta }\widehat{M}_\alpha )^2`$ becomes as small as $`(\mathrm{\Delta }\widehat{M}_\alpha )^21/L.`$ This is consistent with the fact that any separable state is a NFS. For example, $`|\psi _{\mathrm{init}}`$ is a separable state, for which $`(\mathrm{\Delta }\widehat{M}_\alpha )^21/L`$ for all three directions $`\alpha =x,y,z`$.

### V.3 Anomalously fluctuating states are used in Shor’s algorithm

We evaluate fluctuations of $`\widehat{M}_\alpha `$ and $`\widehat{M}_{}^{(1)}{}_{\alpha }{}^{}`$ for all states appearing in Shor’s factoring algorithm, for various values of $`N`$ and $`𝗑`$. We assume in this section that noises are absent, because our purpose in this section is to find out AFSs.

Figure 1 shows the change of $`(\mathrm{\Delta }\widehat{M}_\alpha )^2`$ along the steps of the algorithm when $`N=21,L_1=10,L_2=5,𝗑=2`$, for which $`r=6`$. It is seen that $`(\mathrm{\Delta }\widehat{M}_\alpha )^2`$’s remain smaller than $`1/L=1/150.067`$ until the Hadamard transformation is finished. This is consistent with the fact that any separable state is a NFS (although the inverse is not necessarily true), because all states during the Hadamard transformation are separable states \[see, e.g., Eq. (61)\]. In the modular exponentiation processes, on the other hand, $`(\mathrm{\Delta }\widehat{M}_x)^2`$ grows quickly, until it becomes $`0.227`$, which is significantly greater than $`1/L`$, when the modular exponentiation is finished. During the DFT, $`(\mathrm{\Delta }\widehat{M}_x)^2`$ decreases gradually, whereas $`(\mathrm{\Delta }\widehat{M}_z)^2`$ grows in turn until it becomes $`0.109`$, which is significantly greater than $`1/L`$, at the final stage of the DFT.

To examine which register is responsible for the large fluctuations, we investigate $`W_\alpha `$ ($`\alpha =x,y,z`$) that is defined by

$$W_\alpha \frac{(\mathrm{\Delta }\widehat{M}_\alpha ^{(1)})^2}{(\mathrm{\Delta }\widehat{M}_\alpha )^2}=\frac{(\mathrm{\Delta }\widehat{M}_\alpha ^{(1)})^2}{\left(\frac{L_1}{L}\mathrm{\Delta }\widehat{M}_{\alpha }^{}{}_{}{}^{(1)}+\frac{L_2}{L}\mathrm{\Delta }\widehat{M}_{\alpha }^{}{}_{}{}^{(2)}\right)^2}.$$
(30)
If the first register gives dominant contribution to the fluctuation, we expect that

$$W_\alpha \left(\frac{L}{L_1}\right)^2=2.25.$$
(31)
In Fig. 2, we plot the change of $`(\mathrm{\Delta }\widehat{M}_\alpha ^{(1)})^2`$ along the steps of the algorithm. Comparing Fig. 1 with Fig. 2, we find that $`W_x=2.03`$ for $`|\psi _{\mathrm{ME}}`$ and $`W_z=2.05`$ for $`|\psi _{\mathrm{final}}`$. Since these values of $`W_\alpha `$ are close to $`(L/L_1)^2`$, we conclude that $`R_1`$ gives the dominant contribution.

In order to judge whether the states are AFSs or not, we also investigate the $`L`$ dependence of the fluctuations. Since $`R_1`$ gives dominant contributions, we calculate $`(\mathrm{\Delta }\widehat{M}_\alpha ^{(1)})^2`$ for a larger system with $`N=513,L_1=20,L_2=10,𝗑=26`$, for which $`r=6`$. Figure 3 plots $`(\mathrm{\Delta }\widehat{M}_\alpha ^{(1)})^2`$ in this case. By comparing this figure with Fig. 2, we find that $`(\mathrm{\Delta }\widehat{M}_x^{(1)})^2`$ for $`|\psi _{\mathrm{ME}}`$ is almost independent of $`L_1`$. In fact, $`\psi _{\mathrm{ME}}|(\mathrm{\Delta }\widehat{M}_x^{(1)})^2|\psi _{\mathrm{ME}}`$ is 0.460 and 0.477 in Figs. 2 and 3, respectively. We also find that $`(\mathrm{\Delta }\widehat{M}_z^{(1)})^2`$ is almost independent of $`L_1`$ for $`|\psi _{\mathrm{final}}`$. In fact, $`\psi _{\mathrm{final}}|(\mathrm{\Delta }\widehat{M}_z^{(1)})^2|\psi _{\mathrm{final}}`$ is 0.223 and 0.219 in Figs. 2 and 3, respectively. On the other hand, other fluctuations have different dependences on $`L_1`$, for example, $`(\mathrm{\Delta }\widehat{M}_x^{(1)})^2`$ for $`|\psi _{\mathrm{final}}`$ in Fig. 3 is nearly half of that in Fig. 2. Moreover, $`(\mathrm{\Delta }\widehat{M}_y^{(1)})^2`$’s of all states in Fig. 3 are nearly half of those in Fig. 2.

From these observations, we conclude that $`|\psi _{\mathrm{ME}}`$ and $`|\psi _{\mathrm{final}}`$ are AFSs, which have anomalously large fluctuations of $`\widehat{M}_x`$ and $`\widehat{M}_z`$, respectively. Although this does not exclude the possibility that some other states could also be AFSs, identification of the above AFSs are sufficient for the purpose of the present paper; namely, we have confirmed conjecture (i) when $`(N,𝗑)=(21,2)`$ and $`(513,26)`$, both for which $`r=6`$.

We also performed numerical simulations for other values of $`(N,𝗑)`$, for which $`r`$ takes various values from $`2`$ to $`20`$. We found that AFSs appear for all cases except when $`r`$ becomes an integral power of $`2`$, i.e., except when $`r=2,4,8,16`$; namely, we have confirmed conjecture (i) apart from the exceptional cases. Since such exceptional cases seem to be unimportant in quantum computation, we consider a typical case $`(N,𝗑)=(21,2)`$ in the following sections.

### V.4 Similarity of states with different values of $`L`$

From Figs. 2 and 3, it is seen that states of different values of $`L`$ have similar properties; namely, states in quantum computers are homogeneous in a broad sense, because states with a larger $`L`$ (which is necessary for larger inputs) and states with a smaller $`L`$ are both generated according to the same algorithm. This allows us to analyze the $`L`$ dependence of the properties of quantum states in the quantum computers.

## VI Modeling and theoretical basis of quantum computers subject to noises

In order to examine conjectures (ii) and (iii), we investigate in the following sections effects of weak perturbations from classical noises on quantum computers. In this section, we describe the modeling and theoretical basis.

### VI.1 Model of noises

We consider classical noises $`f_x,f_y,f_z`$, which act on the qubits through the following interaction Hamiltonian;

$$\widehat{H}_{\mathrm{int}}=\underset{\alpha =x,y,z}{}\lambda _\alpha \underset{\mathrm{}=1}{\overset{L}{}}f_\alpha (\mathrm{},t)\widehat{\sigma }_\alpha (\mathrm{}).$$
(32)
Since the computational basis is taken as Eq. (18), $`f_x`$ and $`f_y`$ are called “bit-flip noises” because they induce transitions between different basis states, whereas $`f_z`$ is called a “phase-shift noise” because it induces phase shifts of the basis states.

In this paper, we consider long-wavelength noises, whose spectral intensities behave as Eq. (15); namely, we take $`f_\alpha (\mathrm{},t)`$ to be independent of $`\mathrm{}`$:

$$f_\alpha (\mathrm{},t)=f_\alpha (t).$$
(33)
For simplicity, we assume that

$`\lambda _x=\lambda _y=\lambda _z\lambda ,`$ (34)
$`\overline{f_\alpha (t)}=0,`$ (35)
$`\overline{f_\alpha (t)f_\beta (t^{})}=\delta _{\alpha ,\beta }\overline{f_\alpha (t)f_\alpha (t^{})},`$ (36)
which seem natural in many physical situations. Here, the overline denotes the average over the ensemble of the noises:

$$\overline{\mathrm{}}=\underset{n_\nu \mathrm{}}{lim}\frac{1}{n_\nu }\underset{\nu =1}{\overset{n_\nu }{}}\mathrm{},$$
(37)
where $`\nu `$ labels realizations ($`1,2,\mathrm{},n_\nu `$) of the noises. From Eqs. (33) and (34), the interaction reduces to the simple form

$$\widehat{H}_{\mathrm{int}}(t)=\lambda L\underset{\alpha =x,y,z}{}f_\alpha (t)\widehat{M}_\alpha .$$
(38)
To simulate some real systems 1fa ; 1fb ; nakamura , $`f_\alpha (t)`$ is assumed to have the $`1/f`$ spectrum 1/f ;

$$f_\alpha (t)=\underset{\omega }{}\frac{1}{\sqrt{\omega \tau }}\mathrm{cos}\left[\omega t+\theta _\alpha (\omega )\right],$$
(39)
where $`\theta _\alpha (\omega )`$ is a random phase, which distributes uniformly in $`(\pi ,\pi ]`$ for each $`\omega `$, and the summation is taken over discrete values of $`\omega `$ in the interval $`\omega _{\mathrm{low}}\omega \omega _{\mathrm{high}}`$ with separations $`\mathrm{\Delta }\omega =2\pi /\tau _{\mathrm{total}}`$. Here, $`\omega _{\mathrm{low}}`$ and $`\omega _{\mathrm{high}}`$ are low- and high-frequency cutoffs, respectively.

In real systems, noises act continuously over the whole computational time $`\tau _{\mathrm{total}}`$. However, we wish to study effects of noises on each state in the computation. Therefore, we assume that the computation is perfectly performed until the $`m`$th step, and that the noises act between the $`m`$th and $`(m+1)`$th steps. By calculating changes of the quantum states and of the computational results in this case, we can analyze effects of the noises on each state.

For this purpose, we take $`\omega _{\mathrm{low}}=\mathrm{\Delta }\omega `$ because the variation at such a low frequency is negligible during the time interval $`\tau `$ of one step. Regarding $`\omega _{\mathrm{high}}`$, we take $`\omega _{\mathrm{high}}4.1\times 2\pi /\tau `$, where the fractional factor $`4.1`$ is taken in order to avoid possible troubles which may occur by setting $`\omega _{\mathrm{high}}`$ as an integral multiple of $`2\pi /\tau `$. We have confirmed that effects of higher-frequency components are negligible.

### VI.2 Fidelity and decoherence

Before presenting results of numerical simulations in the following section, we present in this section a theoretical basis for analyzing the numerical results.

As explained in Sec. II.4, $`\lambda `$ can be interpreted as the noise amplitude times the coupling constant. We are interested in the case of small $`\lambda `$, because otherwise it is obvious that the quantum computation would fail. We therefore assume that $`\lambda `$ is small enough so that its lowest-order contribution is dominant \[see, e.g., Eq. (41) below\]. Note, however, that the numerical results presented in the following section include all orders in $`\lambda `$. Since numerical simulations are possible only for relatively small $`L`$, we will draw general conclusions by using complementally both the numerical results and the analytic results of this section.

Suppose that the computation is perfectly performed until the $`m`$th step; namely, the state $`|\psi _m`$ that is obtained just after the $`m`$th step is exactly the state prescribed by the algorithm. When the noises act between the $`m`$th and $`(m+1)`$th steps, the state evolves into

$`|\psi _m^{}`$ $`=`$ $`|\psi _m+{\displaystyle \frac{1}{i\mathrm{}}}{\displaystyle _0^\tau }𝑑t\widehat{H}_{\mathrm{int}}(t)|\psi _m+{\displaystyle \frac{1}{(i\mathrm{})^2}}{\displaystyle _0^\tau }𝑑t{\displaystyle _0^t}𝑑t^{}\widehat{H}_{\mathrm{int}}(t)\widehat{H}_{\mathrm{int}}(t^{})|\psi _m+\mathrm{}.`$ (40)
We are interested in the density operator $`\widehat{\rho }_m^{}`$ that is the average of $`|\psi _m^{}\psi _m^{}|`$ over the ensemble of the noises. From Eqs. (35), (36), (38), and (40), we obtain

$`\widehat{\rho }_m^{}`$ $``$ $`\overline{|\psi _m^{}\psi _m^{}|}`$ (41)
$`=`$ $`\widehat{\rho }_m{\displaystyle \frac{\lambda ^2L^2}{2\mathrm{}^2}}{\displaystyle \underset{\alpha }{}}C_\alpha (\tau )\left(\widehat{M}_\alpha ^2\widehat{\rho }_m+\widehat{\rho }_m\widehat{M}_\alpha ^22\widehat{M}_\alpha \widehat{\rho }_m\widehat{\rho }_m\widehat{M}_\alpha \right)+O(\lambda ^3).`$
Here, $`\widehat{\rho }_m|\psi _m\psi _m|`$, and $`C_\alpha (\tau )`$ is an integral of the autocorrelation function of the noise,

$$C_\alpha (\tau )2_0^\tau 𝑑t_0^t𝑑t^{}\overline{f_\alpha (t)f_\alpha (t^{})}=_0^\tau 𝑑t_0^\tau 𝑑t^{}\overline{f_\alpha (t)f_\alpha (t^{})}=\overline{\left(_0^\tau f_\alpha (t)𝑑t\right)^2}.$$
(42)
As a measure of deviation of $`\widehat{\rho }_m^{}`$ from the ideal one $`\widehat{\rho }_m`$, we consider the fidelity that is defined by

$$F_m\text{Tr}\left[\rho _m\rho _m^{}\right].$$
(43)
This is not necessarily a good measure of decoherence, because it can be reduced even when $`\widehat{\rho }_m^{}`$ happens to be a pure state. As a measure of decoherence, we consider the $`\alpha `$ entropy of $`\alpha =2`$,

$$S_m\mathrm{ln}(\text{Tr}[(\rho _m^{})^2]).$$
(44)
To see the relation between $`F_m`$ and $`S_m`$, let us represent Eq. (41) as $`\widehat{\rho }_m^{}=\widehat{\rho }_m+\lambda ^2\widehat{\eta }_m+O(\lambda ^3).`$ Then we obtain

$`S_m`$ $`=`$ $`2\lambda ^2\text{Tr}[\widehat{\rho }_m\widehat{\eta }_m]+O(\lambda ^3),`$ (45)
$`F_m`$ $`=`$ $`1+\lambda ^2\text{Tr}[\widehat{\rho }_m\widehat{\eta }_m]+O(\lambda ^3).`$ (46)
We thus find

$$S_m=2(1F_m)+O(\lambda ^3).$$
(47)
Therefore, to $`O(\lambda ^2)`$, the reduction of the fidelity is directly related to the increase of the entropy, i.e., to the decoherence. Since we are interested in the case of small $`\lambda `$, this perturbative relation should hold. We thus simply call the reduction of the fidelity “decoherence” in the following discussions.

Inserting Eq. (41) into Eq. (43), we obtain a simple formula, which is correct up to $`O(\lambda ^2)`$,

$`F_m`$ $`=`$ $`1{\displaystyle \frac{\lambda ^2L^2}{\mathrm{}^2}}{\displaystyle \underset{\alpha }{}}C_\alpha (\tau )\psi _m|(\mathrm{\Delta }\widehat{M}_\alpha )^2|\psi _m,`$ (48)
where $`\mathrm{\Delta }\widehat{M}_\alpha \widehat{M}_\alpha \psi _m|\widehat{M}_\alpha |\psi _m.`$ It is seen that, to $`O(\lambda ^2)`$, $`F_m`$ decreases in proportion to $`L^2`$ and to the fluctuations of magnetizations, in accordance with the general result, Eq. (10). It is also seen that the noises in three directions $`f_x,f_y,f_z`$ contribute additively to $`F_m`$. We can therefore calculate effects of $`f_x,f_y,f_z`$ independently.

The decoherence rate (per step) $`\mathrm{\Gamma }_m`$ of $`|\psi _m`$ is given by

$$\mathrm{\Gamma }_m\frac{S_m}{2\tau },$$
(49)
where the factor of 2 has been inserted for convenience. From Eqs. (47) and (48), we obtain a formula for $`\mathrm{\Gamma }_m`$;

$$\mathrm{\Gamma }_m=\frac{\lambda ^2L^2}{\mathrm{}^2}\underset{\alpha }{}\frac{C_\alpha (\tau )}{\tau }\psi _m|(\mathrm{\Delta }\widehat{M}_\alpha )^2|\psi _m,$$
(50)
which is correct up to $`O(\lambda ^2)`$. This formula is a special case of the general result of SM, Eq. (10), except for the extra factor $`C_\alpha (\tau )/\tau `$. The case of $`\alpha =z`$ of the above formula agrees also with the result of Ref. Palma , except for the extra factor. The extra factor appears because the $`1/f`$ noise, Eq. (39), does not satisfy the assumption of short-time correlation. Since the extra factor is independent of the state of the qubit system, it can be considered as a constant when comparing decoherence rates of different states.

### VI.3 Fragility of anomalously fluctuating states

When $`|\psi _m`$ is a NFS, $`\psi _m|(\mathrm{\Delta }\widehat{M}_\alpha )^2|\psi _mO(1/L)`$ by definition. Formula (50) then yields

$$\mathrm{\Gamma }_m\lambda ^2O(L).$$
(51)
Therefore, NFSs never become fragile. When $`|\psi _m`$ is an AFS that has been found in Sec V.3, on the other hand, $`\psi _m|(\mathrm{\Delta }\widehat{M}_\alpha )^2|\psi _m=O(L^0)`$ for $`\alpha =x`$ or $`z`$. If the noise component $`f_\alpha `$ for such $`\alpha `$ is present, formula (50) yields

$$\mathrm{\Gamma }_m=\lambda ^2O(L^2),$$
(52)
hence the AFS becomes fragile (with $`\delta =1`$).

These results are consistent with conjecture (ii) and with the more general results that are summarized in Sec. II.6. It is important to note the following fact, which is obtained from Eqs. (51) and (52):

$$\frac{\text{(decoherence rate of fragile AFSs)}}{\text{(decoherence rate of NFSs)}}O(L).$$
(53)
This ratio becomes $`1`$ when $`L1`$, i.e., when the input $`N`$ is huge. Therefore, the decoherence rate of the quantum computer is almost determined by the decoherence rates of the fragile AFSs. These points will be studied more in detail using numerical simulations in the following section.

Note also that decoherence does not necessarily reduce the success probability of the computation. We will also study this point in the following sections.

## VII Results of numerical simulations with noises

In this section, we present results of numerical simulations of Shor’s factoring algorithm when noises act on a quantum computer. As explained in subsection V.3, we take $`N=21,L_1=10,L_2=5,𝗑=2`$, for which $`r=6`$ and $`Q=75`$.

### VII.1 Decoherence

In Fig. 4, we show a two-dimensional plot of the fidelity versus the fluctuation of $`\widehat{M}_z`$ for all steps, i.e., ($`\psi _m|(\mathrm{\Delta }\widehat{M}_z)^2|\psi _m`$, $`F_m`$) for all $`m`$, when only a phase-shift noise is present, i.e., when $`f_z`$ is given by Eq. (39) whereas $`f_x=f_y=0`$. Each point in the figure corresponds to a state appearing in the algorithm. The parameter $`\lambda `$ is taken as $`0.0015\mathrm{}/\tau `$.

Regarding a bit-flip noise, we show in Fig. 5 a two-dimensional plot of the fidelity versus the fluctuation of $`\widehat{M}_x`$ when $`f_x`$ is given by Eq. (39) whereas $`f_y=f_z=0`$ for $`\lambda =0.0015\mathrm{}/\tau `$. A similar plot (not shown) has been obtained if we plot ($`\psi _m|(\mathrm{\Delta }\widehat{M}_y)^2|\psi _m`$, $`F_m`$) when $`f_y`$ is given by Eq. (39) whereas $`f_x=f_z=0`$. This is reasonable because both $`f_x`$ and $`f_y`$ are bit-flip noises.

Figures 4 and 5 show that $`F`$ decreases, on an average, in proportion to the fluctuation of the normalized additive operator to which the noise couples via $`\widehat{H}_{\mathrm{int}}(t)`$ of Eq. (38). Distributions around the average curve are due to the fact that the number $`n_\nu `$ of noise samples is not very large; $`n_\nu =40`$. Therefore, formula (48) has been confirmed. Hence, formulas (50)-(52) have also been confirmed.

In these figures, states with larger fluctuations are more likely to be AFSs. In particular, the states with the largest fluctuations in Figs. 4 and 5 are $`|\psi _{\mathrm{final}}`$ and $`|\psi _{\mathrm{ME}}`$, respectively, which have been identified as AFSs in Sec. V.3. Although $`L`$ is rather small ($`L=15`$) in this simulation, we can extrapolate the results to the case of larger $`L`$ using formulas (50)-(52). (See discussions in subsection VII.4.) It is then clear that conjecture (ii) is correct.

### VII.2 Success probability

Generally speaking, decoherence of a particular state does not necessarily lead to false results of the quantum computation. For example, as will be discussed in Sec. VII.5, decoherence of $`|\psi _{\mathrm{final}}`$ by the phase-shift noise $`f_z`$ does not reduce the probability of getting the correct value of $`r`$ at all. Therefore, in this section we investigate effects of the noises on the computational result for each state.

For this purpose, we calculate the success probability $`T`$ that is defined as the probability of finding in the final state a basis state which gives the correct value of $`r`$. In Shor’s factoring algorithm, one performs measurement, which diagonalize the computational basis, on the final state $`|\psi _{\mathrm{final}}`$. When noises are absent, for example, we plot in Fig. 6 the probability of finding each basis state in $`|\psi _{\mathrm{final}}`$. Each dominant peak is accompanied by side peaks, as shown in Fig. 7, which is a magnification of Fig. 6. If the basis state with $`c=\overline{171}`$ or $`\overline{853}`$ happens to be obtained, one can successfully obtain the correct value of $`r=6`$, where the overline denotes the bit reversal. The other basis states do not give the correct value. For example, if one obtains $`c=\overline{512}`$, which corresponds to the central peak in Fig. 6, then $`c^{}`$ satisfying inequality (24) is $`c^{}=3`$. Since $`c^{}`$ is not coprime to $`r=6`$, it gives a wrong result as $`r=2`$. Whether the result is correct or not can be checked efficiently using a classical computer. Furthermore, if one obtains $`c=\overline{170}`$, which corresponds to the highest side peak associated with the dominant peak at $`c=\overline{171}`$ in Fig. 7, then there is no $`c^{}`$ satisfying inequality (24). Therefore, $`T`$ is given in the case of $`N=21,𝗑=2`$ by

$$T=P(\overline{171})+P(\overline{853}),$$
(54)
where $`P(c)`$ denotes the probability of finding in the final state a basis state $`|c^{(1)}`$.

It is essential to exclude $`P(c)`$’s of the basis states corresponding to the other peaks. In fact, we found that some of such excluded $`P(c)`$’s sometimes increase with increasing the strength of noises. Hence, we would have obtained unphysical results if we included them in the success probability.

It is evident from Eq. (54) that $`T<1`$ even in the absence of the noises. If we denote $`T`$ in the absence of noises by $`T_{\mathrm{clean}}`$, it is evaluated for the case of Fig. 6 as $`T_{\mathrm{clean}}=0.22797`$. When noises act on the quantum computer, $`T`$ would become smaller than $`T_{\mathrm{clean}}`$,

$$T=ϵT_{\mathrm{clean}},$$
(55)
where $`ϵ1`$. For a successful quantum computation, the factor $`ϵ`$ should be kept larger than some threshold value $`ϵ_{\mathrm{th}}`$ (see Sec. VIII.1):

$$ϵϵ_{\mathrm{th}}.$$
(56)
Consider now the case where noises act only between the $`m`$th and $`(m+1)`$th steps. We denote the success probability in this case by $`T_m`$. By investigating $`T_m`$ and $`F_m`$ for each $`m`$, we can study effects of the noises on the computational results for each state $`|\psi _m`$. In real situations, noises act continuously throughout all steps. Hence, the success probability in real situations is less than any $`T_m`$:

$$T\underset{m}{\mathrm{min}}T_m.$$
(57)
Therefore, the following condition is necessary for a successful quantum computation:

$$\underset{m}{\mathrm{min}}\frac{T_m}{T_{\mathrm{clean}}}ϵ_{\mathrm{th}}.$$
(58)
### VII.3 Relation between the success probability and decoherence

In Figs. 8 and 9, we plot the relation between the fidelity $`F_m`$ and the success probability $`T_m`$ when $`\lambda =0.0015\mathrm{}/\tau `$ for a bit-flip noise \[$`f_x0`$, given by Eq. (39\], whereas $`f_y=f_z=0`$) and a phase-shift noise \[$`f_x=f_y=0`$, whereas $`f_z0`$, given by Eq. (39)\], respectively; namely, $`(F_m,T_m)`$ are plotted for all $`m`$.

It is seen that for most states their decoherence results in the reduction of the success probability, as might be expected. If we define the rate of the reduction of the success probability per decoherence by

$$r_m\frac{T_{\mathrm{clean}}T_m}{1F_m},$$
(59)
then it is found that $`r_m`$ varies from state to state.

We notice that there are exceptional states located at the top of Fig. 9, for which the phase-shift noise does not reduce the success probability. These are states which appear in the latter part of the DFT. This means that quantum coherence among basis states of these states is unnecessary for quantum computation. This may be understood by considering effects of the phase-shift noise on the final state $`|\psi _{\mathrm{final}}`$. In order to estimate $`r`$, one will perform measurement on this state, which diagonalizes the computational basis. This means that one will not measure the relative phases among basis states. Therefore, decoherence of the relative phases in $`|\psi _{\mathrm{final}}`$ does not change the computational result at all. This point will be discussed later again in Sec. VII.5.

### VII.4 An AFS is crucial

We now investigate differences between effects of noises on NFSs and those on AFSs. For this purpose, we investigate effects of noises on $`|\psi _{\mathrm{HT}}`$, which is a typical NFS, and those on $`|\psi _{\mathrm{ME}}`$, which is a typical AFS.

Figures 10 and 11 plot $`(F_m,T_m)`$ for $`|\psi _m=|\psi _{\mathrm{HT}}`$ and for $`|\psi _m=|\psi _{\mathrm{ME}}`$, respectively, for various values of $`\lambda `$ ranging from $`0.00075\mathrm{}/\tau `$ to $`0.006\mathrm{}/\tau `$. The crosses represent the case of a bit-flip noise with $`f_x0`$, given by Eq. (39), whereas $`f_y=f_z=0`$. The triangles represent the case of another bit-flip noise with $`f_y0`$, given by Eq. (39), whereas $`f_x=f_z=0`$. On the other hand, the squares in the figures represent the case of a phase-shift noise with $`f_z0`$, given by Eq. (39), whereas $`f_x=f_y=0`$.

It is found that both $`F_m`$ and $`T_m`$ decrease with increasing $`\lambda `$. As a result, $`(F_m,T_m)`$ of either state composes a monotonic curve, although the data scatter slightly around the average curve because the average over noise realizations has been taken over a finite number ($`n_\nu =200`$) of samples. The average curves are almost straight for such small $`\lambda `$ as assumed in the numerical simulations; namely, for small $`\lambda `$,

$$r_m\text{ const, independent of }\lambda \text{, for each noise and }m,$$
(60)
where $`r_m`$ is defined by Eq. (59).

For $`|\psi _{\mathrm{HT}}`$, the rate $`r_m`$ takes similar values for the three noises. Regarding each of $`F_m`$ and $`T_m`$, on the other hand, the magnitudes of their reductions by $`f_x`$ are smaller than those by $`f_y`$ or $`f_z`$. This may be understood by noting that $`|\psi _{\mathrm{HT}}`$ can be rewritten simply as

$$|\psi _{\mathrm{HT}}=|+x,+x,\mathrm{},+x^{(1)}|1^{(2)},$$
(61)
where $`|+x,+x,\mathrm{},+x^{(1)}`$ denotes the simultaneous eigenstate of $`\widehat{\sigma }_x(1),\widehat{\sigma }_x(2),\mathrm{},\widehat{\sigma }_x(L_1)`$ with the eigenvalues $`+1,+1,\mathrm{},+1`$. It is then clear that the state of $`R_1`$ is not changed by $`f_x`$ which couples to $`\widehat{\sigma }_x(\mathrm{})`$ through the interaction (32), because $`f_x`$ induces only a random phase factor $`e^{i\theta }`$ as $`|+x,+x,\mathrm{},+x^{(1)}e^{i\theta }|+x,+x,\mathrm{},+x^{(1)},`$ which means no change in the quantum state. Hence, the reductions of $`F_m`$ and $`T_m`$ of $`|\psi _{\mathrm{HT}}`$ occur only through the decoherence of the state of $`R_2`$, and thus the reductions become small.

For $`|\psi _{\mathrm{ME}}`$, the reduction of $`F_m`$ by $`f_x`$ is larger than that by $`f_y`$ or $`f_z`$. This can be understood from Eq. (48): Through the interaction (38), $`f_x`$ couples to $`\widehat{M}_x`$, which has an anomalously large fluctuation for this state, whereas $`f_y`$ and $`f_z`$ couple to $`\widehat{M}_y`$ and $`\widehat{M}_z`$, respectively, which have normal fluctuations. Therefore, it is confirmed again that the reduction of $`F_m`$ is simply determined by the fluctuation of $`\widehat{M}_\alpha `$ to which the noise couples. Regarding $`T_m`$, on the other hand, there is no significant difference between the magnitudes of the reductions by $`f_x`$ and $`f_z`$, whereas the reduction by $`f_y`$ is smaller. As a result, $`r_m`$ takes different values for the three noises.

It seems reasonable to assume that in real systems noises in all directions coexist with similar magnitudes, because noises are uncontrollable, random objects. Then, it may be tempting from Figs. 10 and 11 to say that the effects on the computational result of the noises acting on $`|\psi _{\mathrm{HT}}`$ and those acting on $`|\psi _{\mathrm{ME}}`$ would be of the same order of magnitudes. However, to study the performance of computations, we must consider how the effects of noises scale as $`L`$ is increased. Although $`L`$ is not so large ($`L=15`$) in Figs. 10 and 11, it will be much larger in practical applications. In order to satisfy condition (58) for larger $`L`$, $`\lambda `$ should be made smaller. Suppose that one somehow reduces $`\lambda `$ with increasing $`L`$ in such a way that $`1F_m`$ for $`|\psi _{\mathrm{HT}}`$ is kept constant. According to Eq. (51), this means the following scaling rule:

$$\lambda ^21/L.$$
(62)
However, according to Eq. (52), $`1F_m`$ for $`|\psi _{\mathrm{ME}}`$ scales in this case as $`1F_mL`$. Then, since $`T_m`$ is a monotonically decreasing function with decreasing $`F_m`$, as seen from Fig. 11 and Eq. (60) nonlinear , it is expected that $`T_m`$ is greatly reduced, approaching zero, with increasing $`L`$. Therefore, condition (58) would be violated in practical applications, for which $`L`$ is large, if $`\lambda `$ is scaled as Eq. (62).

This argument is applicable also to other AFSs and NFSs that appear during quantum computations. Therefore, $`\underset{m}{\mathrm{min}}T_m`$ on the left-hand side of condition (58) is $`T_m`$ of an AFS, and it is necessary that

$$\lambda ^2O(1/L^2),$$
(63)
which is much severer than the naive one (62). This supports conjecture (iii); namely, we conclude that the bottleneck of the quantum computations is the anomalously fast decoherence of AFSs, which appear during quantum computations.

Note that inequality (63) is not a sufficient condition, but a necessary condition. We will discuss a sufficient condition in Sec. VIII.

### VII.5 Some AFSs may be noncrucial

We have shown that the decoherence of one of AFSs appearing in Shor’s factoring algorithm is crucial, in consistency with conjecture (iii). Note however that this does not mean that decoherence of all AFSs appearing in the algorithm were crucial.

For example, consider the final state $`|\psi _{\mathrm{final}}`$, which has an anomalously large fluctuation of $`\widehat{M}_z`$, whereas the fluctuations of $`\widehat{M}_x`$ and $`\widehat{M}_y`$ take normal values. When a phase-shift noise with $`f_z0,f_x=f_y=0`$ acts on this state, it evolves into

$$|\psi _{\mathrm{final}}^{}=\frac{1}{2^{L_1}}\underset{a=0}{\overset{2^{L_1}1}{}}\underset{c=0}{\overset{2^{L_1}1}{}}\mathrm{exp}\left(\frac{2\pi i}{2^{L_1}}ca+i\theta (c,a)\right)|\overline{c}^{(1)}|𝗑^a\text{ mod }N^{(2)},$$
(64)
where $`\theta (c,a)`$ is a phase, which depends on $`c,a,`$ and the noise. Since the probability $`P(c)`$ of finding a base $`|c^{(1)}`$ does not depend on this random phase, $`T_m`$ for this state is not reduced at all by the phase-shift noise, whereas the fidelity $`F_m`$ is reduced in proportion to $`L^2`$. Therefore, unlike $`|\psi _{\mathrm{ME}}`$, the anomalously fast decoherence of $`|\psi _{\mathrm{final}}`$ is not crucial. $`T_m`$ of this state is reduced only by $`f_x`$ or $`f_y`$, in proportion to $`L`$.

## VIII discussions

### VIII.1 A sufficient condition on $`\lambda `$

Inequality (63) is not a sufficient condition, but a necessary condition. In this section, we discuss a sufficient condition.

In real situations, noises act continuously throughout the computation, as discussed in Sec. VII.2. Hence, the success probability $`T`$ in real situations may be given by

$`T`$ $``$ $`T_{\mathrm{clean}}{\displaystyle \underset{m}{}}{\displaystyle \frac{T_m}{T_{\mathrm{clean}}}}`$ (65)
For a sufficiently small $`\lambda `$, since $`T_{\mathrm{clean}}T_m\lambda ^2`$, this may be approximated by

$`T`$ $``$ $`T_{\mathrm{clean}}\mathrm{exp}\left({\displaystyle \underset{m}{}}{\displaystyle \frac{T_{\mathrm{clean}}T_m}{T_{\mathrm{clean}}}}\right)`$ (66)
$`=`$ $`T_{\mathrm{clean}}\mathrm{exp}\left[\lambda ^2\left({\displaystyle \underset{m\text{ crucial AFSs}}{}}O(L^2)+{\displaystyle \underset{m\text{ noncrucial AFSs and NFSs}}{}}O(L)\right)\right].`$
We have already identified that $`|\psi _{\mathrm{ME}}`$ is a crucial AFS. It seems reasonable to assume that AFSs appearing before and after this state, having anomalously large fluctuations of $`\widehat{M}_x`$, should also be crucial AFSs. Figures 1 \- 3 suggest that the number of such AFSs is roughly proportional to the total number of computational steps, $`Q`$. As described in subsection V.1, $`Q=O(L_1^n)=O(L^n)`$, where $`n=2`$ in our simulation, whereas $`n=3`$ in an actual computation. Hence, for large $`L`$, we can estimate roughly as

$$TT_{\mathrm{clean}}\mathrm{exp}\left[\lambda ^2O(L^{n+2})\right].$$
(67)
Hence, $`ϵ`$ defined by Eq. (55) is roughly given by

$$ϵ\mathrm{exp}\left[\lambda ^2O(L^{n+2})\right].$$
(68)
To get a successful result within a time of $`\mathrm{poly}(\mathrm{log}N)=\mathrm{poly}(L)`$, where poly denotes a polynomial, the lowest allowable value $`ϵ_{\mathrm{th}}`$ of $`ϵ`$ should be

$$ϵ_{\mathrm{th}}=1/\mathrm{poly}(L).$$
(69)
Therefore, a sufficient condition would be

$$\lambda ^2=O\left(\frac{\mathrm{log}(L)}{L^{n+2}}\right).$$
(70)
For any value of $`n`$, we stress that the required condition for $`\lambda `$ becomes $`L`$ ($`1`$) times severer due to the appearance of AFSs than the case where only NFSs appear during the computation, and conjecture (iii) has been confirmed.

### VIII.2 Possible meaning of the appearance of a noncrucial AFS

It seems that macroscopic entanglement is necessary for the exponential speedup over classical computers in performing computation with huge inputs, because otherwise the quantum computation would be able to be simulated efficiently by classical computers. Since AFSs have macroscopic entanglement, they seem necessary for the exponential speedup.

We have shown that both $`|\psi _{\mathrm{ME}}`$ and $`|\psi _{\mathrm{final}}`$ in Shor’s factoring algorithm are AFSs. In agreement with the general theory of SM SM02 , the decoherence rates of these states become anomalously great as the number $`L`$ of qubits is increased. However, we have also shown that the anomalously fast decoherence of $`|\psi _{\mathrm{final}}`$ is not crucial, i.e., does not reduce the success probability, whereas that of $`|\psi _{\mathrm{ME}}`$ is crucial. This may indicate that the use of an AFS in the final stage would be dispensable, whereas the use of an AFS in the modular exponentiation stage would be indispensable, to Shor’s factoring algorithm; namely, it might be possible to modify the algorithm in such a way that it does not use an AFS in the final stage, while keeping the number $`Q`$ of computational steps as $`Q=\mathrm{poly}(\mathrm{log}N)=\mathrm{poly}(L)`$. On the other hand, it would be impossible to modify the algorithm in such a way that it does not use an AFS in the modular exponentiation stage, while keeping $`Q=\mathrm{poly}(\mathrm{log}N)`$. This interesting point will be a subject of future studies.

### VIII.3 A possible method of fighting against anomalously fast decoherence of crucial AFSs

If the use of an AFS in the modular exponentiation stage is indeed indispensable to Shor’s algorithm, we must find a way of fighting against the anomalously fast decoherence of such crucial AFSs. A possible solution may be the use of ECC ec1 ; ec2 ; ec3 ; ec4  and/or a DFS dfs1 ; dfs2 ; dfs3 , which will be mentioned in Sec. VIII.5. We here point out another possible solution.

We note that, according to formula (14), an AFS becomes fragile only when the spectrum density of the noise behaves as $`g(k_0)=O(L^{1+\delta })`$ with $`\delta >0`$. That is, when $`|\psi `$ is an AFS for which $`\psi |\mathrm{\Delta }\widehat{A}_{k_0}^{}\mathrm{\Delta }\widehat{A}_{k_0}|\psi =O(L^0)`$, and when the spectrum density of the noise at $`k=k_0`$ behaves as $`g(k_0)=O(L^{1+\delta })`$, then $`|\psi `$ becomes fragile if $`\delta >0`$ or non fragile if $`\delta 0`$. For example, if the physical dimension of the quantum computer is $`1`$ cm, and if the wavelengths of all noises are longer than $`1`$ cm, the spectral densities of the noises behave like Eq. (15). In such long-wavelength noises, AFSs with $`k_0=0`$ become fragile, whereas AFSs with $`k_01\mathrm{c}\mathrm{m}^1`$ are nonfragile. Therefore, we would be able to avoid anomalously-fast decoherence in such long-wavelength noises if we can improve the algorithm in such a way that crucial AFSs are replaced with other AFSs with $`k_01\mathrm{c}\mathrm{m}^1`$.

For example, we have shown that $`|\psi _{\mathrm{ME}}`$ is a crucial AFS that is fragile in a long-wavelength, bit-flip noise. In order to realize quantum computers with large $`L`$, one should improve the algorithm in such a way that $`|\psi _{\mathrm{ME}}`$ is replaced with another AFSs with $`k_01\mathrm{c}\mathrm{m}^1`$. Since the construction of such an improved algorithm is beyond the scope of the present paper, we will study it elsewhere.

### VIII.4 Possibilities of other AFSs and other noises

As normalized additive operators, we have only examined the “magnetizations” $`\widehat{M}_\alpha `$ and $`\widehat{M}_\alpha ^{(1)}`$ with $`\alpha =x,y,z`$. This is sufficient for the purpose of the present paper, as explained in Sec. V.2. However, it would be interesting to find out all AFSs used in the algorithm. To do this, we must study fluctuations of all normalized additive operators. A convenient method of doing this has recently been proposed by Sugita and Shimizu, and has been applied to quantum chaotic systems SS03 . It would be very interesting to apply their method to quantum computers, and thereby make a complete list of anomalous states used in the quantum computation.

To examine the anomalously fast decoherence of AFSs with anomalously large fluctuations of $`\widehat{M}_\alpha `$, we have considered long-wavelength noises. In real systems, it seems reasonable to assume that many different noises and/or components (wavelengths, frequencies, and directions) coexist. It would be necessary to examine effects of all existing noises to realize a quantum computer with a huge number $`L`$ of qubits, because, as we have shown in this paper, for huge $`L`$ some noises can be crucial even if its strength is much weaker than other noises.

These points will be subjects of future studies.

### VIII.5 Uses of error correcting codes and/or a decoherence-free subspace

We have studied Shor’s factoring algorithm without ECC ec1 ; ec2 ; ec3 ; ec4  or error avoiding using a DFS dfs1 ; dfs2 ; dfs3 ; namely, we have studied “bare” characteristics of quantum computers performing Shor’s algorithm.

Regarding the use of a DFS, it will be effective for fighting against the long-wavelength noises $`f_\alpha `$ that are considered in this paper. However, as mentioned in the preceding section, many different noises and/or components would coexist in real systems. It is not clear whether a DFS can be constructed efficiently in such a realistic case, because the number of extra qubits that are necessary to construct a DFS is increased as the number of different noises and/or components is increased dfs1 ; dfs2 . Also, at present, we do not have definite conclusions on the efficiency of ECC in such a realistic case. We can, however, say that the improvement of the bare characteristics is crucial in practical applications, because if the bare characteristics are bad, then ECC would become much complicated and large scale. Such a computer system would be impractical.

Therefore, we think that all of ECC, a DFS, and the improvement of the bare characteristics should be necessary to realize a quantum computer that accept huge inputs.

### VIII.6 Various definitions of decoherence

The decoherence and decoherence rate can be defined in many different ways. The definition of $`\mathrm{\Gamma }_m`$ of the present paper, Eq. (49), is one of many possible definitions. Fortunately, however, we are interested in the case of small $`\lambda `$ in this paper. In such a case, we can obtain similar conclusions for many different definitions of the decoherence rate. Indeed, we have shown in Sec. VI.2 that the loss of fidelity and the increase of the $`\alpha `$ entropy agree with each other for small $`\lambda `$.

Note, however, that the situation could be different if one employed some definitions used in condensed-matter physics. In condensed-matter physics, decoherence is often discussed with respect to a particular quantity, such as the line shape AW  and a nonequilibrium noise SU . In quantum information theory, on the other hand, the decoherence is usually defined with respect to all possible observable. The decoherence in the latter sense can take place without any change of the (expectation) value of a particular quantity. This point should be considered when using rich results of condensed-matter physics.

## IX summary and conclusions

With the help of the general theory of stabilities of many-body quantum states by SM SM02 , we have studied properties of quantum states in quantum computers that perform Shor’s factoring algorithm Shor\_1 . Since the efficiency of computation becomes relevant only when the size $`N`$ of the input is huge, we focus on asymptotic behaviors as the number $`L`$ \[$`=O(\mathrm{log}N)`$\] of qubits is increased.

Following the general theory by SM, we have paid attention to fluctuations of normalized additive operators, which are the sums of local operators, as defined by Eq. (1). If fluctuation $`\psi |(\mathrm{\Delta }\widehat{A})^2|\psi `$ of every normalized additive operator $`\widehat{A}`$ is $`O(1/L)`$ or less for a pure state $`|\psi `$, we call it a normally fluctuating state (NFS). Any separable state is a NFS, whereas the inverse is not necessarily true. On the other hand, if there is a normalized additive operator whose fluctuation is $`O(L^0)`$ for a pure state $`|\psi `$, we call $`|\psi `$ an anomalously fluctuating state (AFS). Since AFSs have such anomalously large fluctuations, they are entangled macroscopically. We have pointed out in Sec. II.3 that the use of fluctuations of normalized additive operators as a measure of macroscopic entanglement seems natural from the viewpoints of many-body physics and experiments.

By performing numerical simulations of Shor’s factoring algorithm, we have found that AFSs appear during the computation, although the initial state is a NFS. For example, the state $`|\psi _{\mathrm{ME}}`$ just after the modular exponentiation process is an AFS, which has anomalously large fluctuation of $`\widehat{M}_x`$. Here, $`\widehat{M}_x`$ is the $`\alpha =x`$ component of $`\widehat{M}_\alpha `$ that is defined by Eq. (27), which corresponds to the magnetization of a spin system. The final state $`|\psi _{\mathrm{final}}`$, which is obtained by a discrete Fourier transform, is also an AFS, which has anomalously large fluctuation of $`\widehat{M}_z`$ (the $`\alpha =z`$ component of $`\widehat{M}_\alpha `$).

According to the general theory by SM, the asymptotic behavior, as $`L`$ is increased, of the decoherence rate $`\mathrm{\Gamma }`$ of a quantum state is directly related to fluctuations of normalized additive operators: $`\mathrm{\Gamma }`$ of a NFS never exceeds $`O(L)`$ in any weak classical noises, whereas $`\mathrm{\Gamma }`$ of an AFS can be either $`O(L^2)`$ or less, depending on the spectral densities of the noises. An AFS with an anomalously great decoherence rate $`\mathrm{\Gamma }=O(L^{1+\delta })`$, where $`\delta >0`$, is said to be fragile. We have shown that AFSs which we have found in Shor’s algorithm become fragile, $`\mathrm{\Gamma }=O(L^2)`$, in long-wavelength noises with a $`1/f`$ spectrum, which simulate noises in some real systems. Therefore, for large $`L`$, the decoherence rate of a quantum computer performing Shor’s factoring algorithm is determined by the decoherence rates of the fragile AFSs that appear during the computation.

Since decoherence of particular states does not necessarily lead to false results of the quantum computation, we examine whether the anomalously fast decoherence of the fragile AFSs leads to anomalously large degradation of the result of computation. To do this, we have investigated effects of the noises on the computational results for each state. We have found that the anomalously fast decoherence, $`\mathrm{\Gamma }=O(L^2)`$, of $`|\psi _{\mathrm{ME}}`$ leads to anomalously large reduction, approximately proportional to $`L^2`$, of the success probability $`T`$, which is defined as the probability of getting the correct result of computation. We have concluded that the anomalously fast decoherence of such crucial AFSs becomes a bottleneck of quantum computers performing Shor’s factoring algorithm.

This does not however mean that all AFSs appearing in the algorithm are crucial. For example, the anomalously fast decoherence, $`\mathrm{\Gamma }=O(L^2)`$, of $`|\psi _{\mathrm{final}}`$ does not lead to large reduction of $`T`$. In this sense, $`|\psi _{\mathrm{final}}`$ is a noncrucial AFS in Shor’s factoring algorithm.

It seems that macroscopic entanglement is necessary for the exponential speedup over classical computers in performing computation with huge inputs, because otherwise the quantum computation would be able to be simulated efficiently by classical computers. Since AFSs have macroscopic entanglement, they seem necessary for the exponential speedup. This does not however mean that all AFSs in an algorithm written naively are necessary. For Shor’s factoring algorithm, our results suggest that a crucial AFS $`|\psi _{\mathrm{ME}}`$ is necessary whereas a noncrucial AFS $`|\psi _{\mathrm{final}}`$ may be able to be replaced with a NFS. In order to realize quantum computers with large $`L`$, one should improve the algorithm in such a way that necessary but fragile AFSs are replaced with other AFSs that are nonfragile in real noises. To do this, formula (14) will be useful, from which one can estimate $`\mathrm{\Gamma }`$ of an AFS. Since error correcting codes and decoherence-free subspaces are not almighty, we think that one must also utilize such optimization to realize a quantum computer that accepts huge inputs.

###### Acknowledgements.

We thank T. Miyadera for fruitful discussions and comments. This work was partly supported by Grant-in-Aid for Scientific Research.


format: text

text:
# Chapter 1 High Energy Tau Neutrinos: Production, Propagation and Prospects of observations

## Chapter 1 High Energy Tau Neutrinos: Production, Propagation and Prospects of observations

### Abstract

High energy tau neutrinos with energy greater than several thousands of GeV may be produced in some astrophysical sites. A summary of the intrinsic high energy tau neutrino flux estimates from some representative astrophysical sites is presented including the effects of neutrino flavor oscillations. The presently envisaged prospects of observations of the oscillated high energy tau neutrino flux are mentioned. In particular, a recently suggested possibility of future observations of Earth-skimming high energy tau neutrinos is briefly discussed.

### 1. Introduction

High energy neutrino astronomy ($`E10^3`$ GeV) holds great promise to unveil the microscopic details of the hitherto unexplored phenomenons occurring in the cosmos around us . In particular, a search for high energy tau neutrinos will not only bring unparalleled new information about the cosmos around us but also will indicate the existence of physics beyond the standard model of particle physics, namely the corroboration of the neutrino flavor mixing . The essentially maximal neutrino flavor mixing implies the existence of high energy tau neutrino flux comparable to high energy muon neutrino flux .

### 2. High energy tau neutrinos

#### 2.1. Production

The high energy tau neutrinos are produced in direct and indirect decays of $`D_S`$ meson in $`p(\gamma ,p)D_S+X`$ considered to be occurring in cosmos around us. Here, the first $`p`$ represents the accelerated cosmic rays. However, the intrinsic high energy tau neutrino flux is rather suppressed during its production relative to intrinsic high energy non tau neutrino flux in above interactions, such as the intrinsic muon neutrino flux produced in the atmosphere of Earth in $`pA`$ interactions.

#### 2.2. Propagation

Neutrino flavor mixing seems to play a dominant role during the propagation of a system of mixed high energy neutrinos over cosmologically large distances.

Fig. 1 summarizes the intrinsic high energy tau neutrinos flux, $`F_{\nu _\tau }\mathrm{d}N_{\nu _\tau }/\mathrm{d}(\mathrm{log}_{10}E)`$ estimates from some representative astrophysical sites including the effect of (two) neutrino flavor oscillations .

A main background in observing high energy muon neutrinos from the cosmos is the atmospheric muon neutrino background. From Fig. 1, we see that this is not the case for high energy tau neutrinos as the oscillated high energy tau neutrino flux from the galactic plane is already above the relevant atmospheric tau neutrino background even for $`E`$ as low as $`10^3`$ GeV. Thus, above around $`10^3`$ GeV, the high energy tau neutrino search can lead to identification of extra-atmospheric neutrino flux, in particular from the direction of galactic plane. This is in contrast to the situation for non tau neutrinos, where the atmospheric background tend to dominate up to $`10^5`$ GeV for the same astrophysical site . Thus, at least approximately a two order of magnitude lower energy tau neutrinos can probe same astrophysical site provided relevant tau neutrinos can be isolated from relevant non tau neutrinos in near future.

### 3. Prospects of possible observations

#### 3.1. Downward going

For $`E510^5`$ GeV, the downward going high energy tau neutrinos can be separated from other two neutrino flavors via event topology characterization in water or ice based high energy neutrino telescopes. It thus might become possible to identify the downward going high energy tau neutrinos through double shower technique. The first shower is from deep inelastic charged current high energy tau neutrino-nucleon interaction, whereas the second shower is from hadronic decay of the associated tau lepton, both showers are considered to occur inside the telescope. Some quantitative details of this idea for under construction km3 ice or water based high energy neutrino telescopes are given in .

#### 3.2. Upward going

High energy tau neutrinos that cross the entire Earth or most part of it before reaching the detector are called upward going high energy neutrinos.

In the case of tau neutrinos, for $`E510^4`$ GeV, the upward going tau neutrino flux is exponentially suppressed .

#### 3.3. Quasi horizontal or Earth-skimming

It might become possible in near future that the dedicated high energy neutrino telescopes can be configured such that the Earth-skimming high energy (tau) neutrinos induced charged leptons as well as their associated radiations can be measured .

Figure 2 gives the tau lepton flux induced by the Earth-skimming high energy GZK tau neutrinos as a representative example. This tau lepton energy spectrum is obtained by solving a coupled set of partial differential equations describing the simultaneous propagation of tau neutrinos and their induced tau leptons inside the Earth. This set of differential equations explicitly take into account the inelasticity of the neutrino-nucleon scattering and the tau lepton energy loss in contrast to previous relevant studies in this context . The high energy GZK tau neutrino flux is given in Fig. 1. The presence of rather small tau lepton pile up around $`10^8`$ GeV is a consequence of specific energy dependence of incident GZK high energy tau neutrino flux (see Fig. 1).

### 4. Conclusions

* The high energy tau neutrino flux can probe the cosmos around us such as the center of our galaxy even with energy starting from $`10^3`$ GeV above the atmospheric high energy tau neutrino flux as a result of neutrino flavor oscillations. This is in contrast to the case for high energy muon neutrino flux.
* The energy spectrum of the tau leptons induced by the Earth-skimming high energy tau neutrinos is calculated by explicitly taking into account the inelasticity of the neutrino-nucleon interactions and the tau lepton energy loss.

H. A. thanks Physics Division of National Center for Theoretical Sciences for support. J. -J. Tseng and G. -L. Lin are supported by the National Science Council of Taiwan under the grant numbers NSC91-2112-M-009-019 and NSC91-2112-M-009-024.

1. Athar H. 2002, arXiv:hep-ph/0209130

2. Athar H. 2002, arXiv:hep-ph/0212387

3. Athar H., Cheung K., Lin G. -L., Tseng J. -J. 2003, Astropart. Phys. 18, 581

4. Athar H. 2002, arXiv:hep-ph/0210244.

5. Protheroe R. J. 1999, Nucl. Phys. Proc. Suppl. 77, 465

6. Athar H., Parente G., Zas E. 2000, Phys. Rev. D 62, 093010

7. Halzen F., Saltzberg D. 1998, Phys. Rev. Lett. 81, 4305

8. Beacom J. F., Crotty P., Kolb E. W. 2002, Phys. Rev. D 66, 021302

9. Fargion D. 2002, Astrophys. J. 570, 909

10. Feng J. L., Fisher P., Wilczek F., Yu T. M. 2002, Phys. Rev. Lett. 88, 161102

11. Tseng. J. -J. et al. 2003, arXiv:astro-ph/0305507 (to appear in Phys. Rev. D)


text:
# Integrable mappings derived from the ΔΔ𝑅𝑠𝐺 equation

## 1 Introduction

In this paper we consider the double discrete related sine-Gordon $`(\mathrm{\Delta }\mathrm{\Delta }RsG)`$ equation we recently introduced in , i.e.

$$V_{l+1,m+1}=V_{l,m}+\frac{ba(V_{l+1,m}+V_{l,m+1})}{c(V_{l+1,m}+V_{l,m+1})+a}.$$
(1)
We investigate the integrability of the mappings derived under the periodicity condition $`V_{l+\zeta _2,m\zeta _1}=V_{l,m}`$, with $`\zeta _1`$ and $`\zeta _2`$ being relatively prime.111For a detailed discussion of mappings derived from partial difference equations under such a periodicity condition see . Under this periodicity condition, we derive the $`(\zeta _1+\zeta _2)`$ dimensional map

$$V_0^{}=V_1,\mathrm{},V_{\zeta _1+\zeta _22}^{}=V_{\zeta _1+\zeta _21},V_{\zeta _1+\zeta _21}^{}=V_0+\frac{ba(V_{\zeta _1}+V_{\zeta _2})}{c(V_{\zeta _1}+V_{\zeta _2})+a},$$
(2)
where $`V_{l,m}=V_n`$ and $`n=\zeta _1l+\zeta _2m`$. When the map (2) is odd dimensional, it can be reduced to an even dimensional map under the reduction $`v_i=V_i+V_{i+1}`$.

The plan of this paper is as follows : in section 2 we show that the mapping (2), when $`\zeta _1`$ odd and $`\zeta _2`$ even or $`\zeta _1`$ even and $`\zeta _2`$ odd, is related to the mapping derived from the double discrete (alternative) Korteweg-de Vries (a $`\mathrm{\Delta }\mathrm{\Delta }KdV`$) equation (given in ) when $`\zeta _1`$ odd and $`\zeta _2`$ or $`\zeta _1`$ even and $`\zeta _2`$ odd, respectively. In section 3 we show that in the special case $`\zeta _1=1`$ and $`\zeta _2`$ even, the mapping (2) is a particular case of the hierarchy of integrable asymmetric mappings222We call a mapping, which possesses at least one cyclic invariant $`n`$-quadratic integral, symmetric if the cyclic invariant integral is invariant under any permutation of the variables, see . We call a mapping asymmetric if the $`n`$-quadratic integral is not invariant under any permutation of the variables. we introduced in .

## 2 Double discrete related sine-Gordon $`(\mathrm{\Delta }\mathrm{\Delta }RsG)`$ equation

Consider the alternative $`\mathrm{\Delta }\mathrm{\Delta }KdV`$ ($`a`$ $`\mathrm{\Delta }\mathrm{\Delta }KdV`$) equation given in , i.e.

$$V_{l+1,m+1}=V_{l,m}+\frac{(ϵ\gamma )(V_{l+1,m}V_{l,m+1})+\xi }{\beta (V_{l+1,m}V_{l,m+1})+\gamma }.$$
(3)
There are three possible cases to consider using the periodicity condition $`V_{l+\zeta _2,m\zeta _1}=V_{l,m}`$, 1) $`\zeta _1`$ odd and $`\zeta _2`$ even, 2) $`\zeta _1`$ even and $`\zeta _2`$ odd, and 3) $`\zeta _1`$ odd and $`\zeta _2`$ odd.

Case 1) When $`\gamma =ϵ=0`$ together with

$$V_{l,m}\{\begin{array}{c}V_{l,m},l\mathrm{even}\\ V_{l,m},l\mathrm{odd}\end{array}$$
(4)
we obtain

$$V_{l+1,m+1}=V_{l,m}+\frac{\xi }{\beta (V_{l+1,m}+V_{l,m+1})}.$$
(5)
Case 2) When $`\gamma =ϵ=0`$ and

$$V_{l,m}\{\begin{array}{c}V_{l,m},m\mathrm{even}\\ V_{l,m},m\mathrm{odd}\end{array}$$
(6)
we obtain

$$V_{l+1,m+1}=V_{l,m}\frac{\xi }{\beta (V_{l+1,m}+V_{l,m+1})}.$$
(7)
In cases 1) and 2) the periodicity condition remains invariant under the transformation (4) and (6) and as a result the mapping derived from (3) (with $`\gamma =ϵ=0`$) is the same as that derived from (5) or (7). In case 3), however, the periodicity condition does not remain invariant under the transformation (4) and (6) and as a result the mapping derived is different. We will not consider case 3) in this paper.

The mapping derived from (5) or (7) under the periodicity condition $`V_{l+\zeta _2,m\zeta _1}=V_{l,m}`$ is

$$V_0^{}=V_1,\mathrm{},V_{\zeta _1+\zeta _22}^{}=V_{\zeta _1+\zeta _21},V_{\zeta _1+\zeta _21}^{}=V_0\pm \frac{\xi }{\beta (V_{\zeta _1}+V_{\zeta _2})},$$
(8)
with $`+`$ sign for case 1) and $``$ sign for case 2). Using the translations $`V_iV_i+a/2\beta `$ and $`V_i^{}V_i^{}+a/2\beta `$ and setting $`(\beta ,\xi )=(c,\pm (a^2/c+b))`$, the mapping (8) becomes the mapping (2).

We now turn to the integrals of the mapping (2). We consider case 1) only, case 2) is similar. Under the periodicity condition $`V_{l+\zeta _2,m\zeta _1}=V_{l,m}`$ and $`\gamma =ϵ=0`$, (3) can be used to derive the $`(\zeta _1+\zeta _2)`$ dimensional map

$$V_0^{}=V_1,\mathrm{},V_{\zeta _1+\zeta _22}^{}=V_{\zeta _1+\zeta _21},V_{\zeta _1+\zeta _21}^{}=V_0+\frac{\xi }{\beta (V_{\zeta _1}V_{\zeta _2})}.$$
(9)
Under the transformations $`V_i(1)^iV_i`$ and $`V_i^{}(1)^iV_i^{}`$ the map (9) becomes

$$V_0^{}=V_1,V_1^{}=V_2,\mathrm{},V_{\zeta _1+\zeta _22}^{}=V_{\zeta _1+\zeta _21},V_{\zeta _1+\zeta _21}^{}=V_0\frac{\xi }{\beta (V_{\zeta _1}+V_{\zeta _2})}.$$
(10)
We note that the map (10) can be written as $`L_{\text{10}}=LL_\text{8}=L_\text{8}L`$, where $`L`$ is defined to be the map with coordinates $`V_i^{}=V_i`$ (for all $`i`$) and $`L_\text{8}`$ is the map (8). Using this, we see that $`L_{\text{10}}L_{\text{10}}=LL_\text{8}LL_\text{8}=LLL_\text{8}L_\text{8}=L_\text{8}L_\text{8}`$, as $`L`$ is an involution, i.e. $`LL=\mathrm{id}`$, where $`\mathrm{id}`$ is the identity map. This shows that for all integrals $`I_i`$ of the map $`L_{\text{10}}`$, we have $`I_i(V_0,\mathrm{},V_{\zeta _1+\zeta _21})=I_i(V_0^{},\mathrm{},V_{\zeta _1+\zeta _21}^{})=I_i(V_0^{\prime \prime },\mathrm{},V_{\zeta _1+\zeta _21}^{\prime \prime })`$ for the map (8). In fact $`I_i(V_0,\mathrm{},V_{\zeta _1+\zeta _21})=I_i(V_0^{},\mathrm{},V_{\zeta _1+\zeta _21}^{})`$, i.e. the actual integrals of the mapping (8) are $`I_i^2`$.

## 3 $`\zeta _1=1`$ and $`\zeta _2`$ even

In this section we show that in the special case $`\zeta _1=1`$ and $`\zeta _2`$ even, the mapping (2) is a particular case of the hierarchy of integrable asymmetric mappings mentioned above. We illustrate this with the four-dimensional case, i.e. $`\zeta _1=1`$ and $`\zeta _2=4`$.

When $`\zeta _1=1`$ and $`\zeta _2=4`$, the mapping (2) becomes

$$V_0^{}=V_1,V_1^{}=V_2,V_2^{}=V_3,V_3^{}=V_4,V_4^{}=V_0+\frac{ba(V_1+V_4)}{c(V_1+V_4)+a}$$
(11)
Under the reduction $`w=V_0+V_1`$, $`x=V_1+V_2`$, $`y=V_2+V_3`$ and $`z=V_3+V_4`$, we obtain the four-dimensional mapping

$$w^{}=x,x^{}=y,y^{}=z,z^{}=w+\frac{c(xy+z)^2+b}{c(xy+z)+a}.$$
(12)
Consider the four-dimensional case of the hierarchy of integrable asymmetric mappings given in , i.e. the mapping

$`w^{}`$ $`=`$ $`w{\displaystyle \frac{\beta (x+y+z)^2+ϵ(x+y+z)+\xi _0}{\beta (x+y+z)+\gamma _0}}`$
$`x^{}`$ $`=`$ $`x{\displaystyle \frac{\beta (w^{}+y+z)^2+ϵ(w^{}+y+z)+\xi _1}{\beta (w^{}+y+z)+\gamma _1}}`$
$`y^{}`$ $`=`$ $`y{\displaystyle \frac{\beta (w^{}+x^{}+z)^2+ϵ(w^{}+x^{}+z)+\xi _2}{\beta (w^{}+x^{}+z)+\gamma _2}}`$
$`z^{}`$ $`=`$ $`z{\displaystyle \frac{\beta (w^{}+x^{}+y^{})^2+ϵ(w^{}+x^{}+y^{})+\xi _3}{\beta (w^{}+x^{}+y^{})+\gamma _3}},`$ (13)
Under the substitutions $`(w,x,y,z)(w,x,y,z)`$ and $`(w^{},x^{},y^{},z^{})(w^{},x^{},y^{},z^{})`$ the mapping (3) becomes

$`w^{}`$ $`=`$ $`w+{\displaystyle \frac{\beta (xy+z)^2ϵ(xy+z)+\xi _0}{\beta (xy+z)\gamma _0}}`$
$`x^{}`$ $`=`$ $`x+{\displaystyle \frac{\beta (w^{}+yz)^2+ϵ(w^{}+yz)+\xi _1}{\beta (w^{}+yz)+\gamma _1}}`$
$`y^{}`$ $`=`$ $`y+{\displaystyle \frac{\beta (w^{}+x^{}+z)^2ϵ(w^{}+x^{}+z)+\xi _2}{\beta (w^{}+x^{}+z)\gamma _2}}`$
$`z^{}`$ $`=`$ $`z+{\displaystyle \frac{\beta (w^{}x^{}+y^{})^2+ϵ(w^{}x^{}+y^{})+\xi _3}{\beta (w^{}x^{}+y^{})+\gamma _3}},`$ (14)
If we set $`\xi _0=\xi _1=\xi _2=\xi _3=\xi `$, $`\gamma _0=\gamma _1=\gamma _2=\gamma _3=\gamma `$ and $`ϵ=0`$ the mapping (3) can be written as $`L_1^4=L_1L_1L_1L_1`$, where $`L_1`$ is given by

$$\stackrel{~}{w}=x,\stackrel{~}{x}=y,\stackrel{~}{y}=z,\stackrel{~}{z}=w+\frac{\beta (xy+z)^2+\xi }{\beta (xy+z)+\gamma },$$
(15)
which is equivalent to (12). The integrals, $`I_1`$ and $`I_2`$ of the mapping (15), can be obtained from the coefficients of the different powers of $`\lambda `$ of the characteristic equation

$$C(h,\lambda )=det(\lambda IL(h))=0,$$
(16)
where $`I`$ is the identity matrix and $`L(h)`$ is the $`L`$ matrix of the Lax pair ($`L,M`$) for the mapping (3), see . We note that the integrals, $`I_1`$ and $`I_2`$, satisfy $`I_i(w,x,y,z)=I_i(w^{},x^{},y^{},z^{})`$, for $`i=1,2`$, i.e the actual integrals for the mapping (15) are $`\overline{I}_i=I_i^2`$. 333The symplectic structure for the mapping (15) is given in . Using this symplectic structure, one can easily show that the two functionally independent integrals, $`\overline{I}_1`$ and $`\overline{I}_2`$, are in involution. The above discussion also shows that (15) has an asymmetric form, i.e. (3), which is equivalent to (3).

This procedure can be applied to any even $`\zeta _2`$ (with $`\zeta _1=1`$). Showing that the mappings obtained from the $`(\mathrm{\Delta }\mathrm{\Delta }RsG)`$, with $`\zeta _1=1`$ and $`\zeta _2`$ even, are special cases of the hierarchy of integrable asymmetric mappings introduced in .

## 4 Conclusion

In this paper we have shown that the mappings derived from the $`(\mathrm{\Delta }\mathrm{\Delta }RsG)`$ equation, when $`\zeta _1`$ odd and $`\zeta _2`$ even or $`\zeta _1`$ even and $`\zeta _2`$ odd, are related to the mappings derived from the $`a`$ $`\mathrm{\Delta }\mathrm{\Delta }KdV`$ equation, when $`\zeta _1`$ odd and $`\zeta _2`$ or $`\zeta _1`$ even and $`\zeta _2`$ odd, respectively. We have also shown that the mappings derived from the $`(\mathrm{\Delta }\mathrm{\Delta }RsG)`$ equation, when $`\zeta _1=1`$ and $`\zeta _2`$ even, are special cases of the hierarchy of integrable asymmetric mappings given in . We note that a similar relationship exists between the asymmetrized mappings444There are two minor errors in \[1, appendix C\] : 1) the transformation reducing the asymmetric ($`2m+1`$)-dimensional mappings to ($`2m`$)-dimensional mappings is actually $`V_i=v_iv_{i+1}`$, and 2) two lines below the previous error, $`v_i=V_iV_{i+1}`$. obtained from the $`a`$ $`\mathrm{\Delta }\mathrm{\Delta }MKdV`$ and $`a`$ $`\mathrm{\Delta }\mathrm{\Delta }sG`$ (when $`\zeta _1=1`$ and $`\zeta _2`$ even) equations, see \[1, Aappendix C\]. An open question is whether a transformation exists relating these two hierarchies? If a transformation relating these two hierarchies does exist, then the hierarchy of asymmetric mappings given in \[1, Aappendix C\] is integrable (which we expect). Another open question is whether the mappings derived from the $`a`$ $`\mathrm{\Delta }\mathrm{\Delta }KdV`$, $`a`$ $`\mathrm{\Delta }\mathrm{\Delta }MKdV`$555See  for the prefix $`a`$., $`a`$ $`\mathrm{\Delta }\mathrm{\Delta }sG^5`$ and $`\mathrm{\Delta }\mathrm{\Delta }RsG`$ equations under an appropriate periodicity condition are special cases of the hierarchy of integrable asymmetric mappings given in .

## Appendix A. Intermediate forms

In  we showed how to determine intermediate forms (i.e. where some symmetry in the variables exists) that are integrable using nonautonomous mappings. In this appendix we show another way of obtaining such forms, but this time using the hierarchy of autonomous integrable asymmetric mappings. We illustrate with the four dimensional case.

Consider (3) when $`\xi _2=\xi _0`$, $`\xi _3=\xi _1`$, $`\gamma _2=\gamma _0`$ and $`\gamma _3=\gamma _1`$, i.e.

$`w^{}`$ $`=`$ $`w{\displaystyle \frac{\beta (x+y+z)^2+ϵ(x+y+z)+\xi _0}{\beta (x+y+z)+\gamma _0}}`$
$`x^{}`$ $`=`$ $`x{\displaystyle \frac{\beta (w^{}+y+z)^2+ϵ(w^{}+y+z)+\xi _1}{\beta (w^{}+y+z)+\gamma _1}}`$
$`y^{}`$ $`=`$ $`y{\displaystyle \frac{\beta (w^{}+x^{}+z)^2+ϵ(w^{}+x^{}+z)+\xi _0}{\beta (w^{}+x^{}+z)+\gamma _0}}`$
$`z^{}`$ $`=`$ $`z{\displaystyle \frac{\beta (w^{}+x^{}+y^{})^2+ϵ(w^{}+x^{}+y^{})+\xi _1}{\beta (w^{}+x^{}+y^{})+\gamma _1}}.`$ (17)
The mapping (Appendix A. Intermediate forms) can be written as $`L=L_2^2=L_2L_2`$, where $`L_2`$ is given by

$`\widehat{w}`$ $`=`$ $`y`$
$`\widehat{x}`$ $`=`$ $`z`$
$`\widehat{y}`$ $`=`$ $`w{\displaystyle \frac{\beta (x+y+z)^2+ϵ(x+y+z)+\xi _0}{\beta (x+y+z)+\gamma _0}}`$
$`\widehat{z}`$ $`=`$ $`x{\displaystyle \frac{\beta (y+\widehat{y}+z)^2+ϵ(y+\widehat{y}+z)+\xi _1}{\beta (y+\widehat{y}+z)+\gamma _1}}.`$ (18)
This mapping is equivalent to the mapping (D.4) of . In fact, if we make the substitutions $`(w,x,y,z)(w,y,x,z)`$ and $`(\widehat{w},\widehat{x},\widehat{y},\widehat{z})(\widehat{w},\widehat{y},\widehat{x},\widehat{z})`$ in the mapping (Appendix A. Intermediate forms) we obtain the mapping (D.4). The integrals of (D.4) can be obtained in the same way, noting that the integrals of (Appendix A. Intermediate forms) can be obtained from the Lax pair given in .

More generally, the intermediate forms can be determined in the following way : find the possible integers $`i`$ that divide $`n`$, e.g for $`n=16`$ we have $`i=1,2,4,8,16`$. Set the $`\gamma _k`$’s and $`\xi _k`$’s to $`\gamma _l`$ and $`\xi _l`$ $`(l=0,\mathrm{},i1)`$ in such a way that we have $`i`$ of each666This is achieved by setting the first $`i`$ $`\gamma _k`$’s and $`\xi _k`$’s $`(k=0,\mathrm{},i1)`$ to $`(\gamma _0,\mathrm{},\gamma _{i1})`$ and $`(\xi _0,\mathrm{},\xi _{i1})`$, respectively, and then repeating the process another $`i1`$ times for the remaining $`\gamma _k`$’s and $`\xi _k`$’s, see example above. and the resulting asymmetric map can be written as $`L=L_i^{n/i}`$. The intermediate form is $`L_i`$. 777This way of constructing intermediate forms can also be applied to the asymmetric mappings given in \[1, appendix C\].

The advantages in this method are 1) the mappings obtained need not be in general complex, whereas the mappings obtained using the method given in  are, and 2) the intermediate forms are easily obtained.

## Appendix B. Involutions

In this appendix we show that all the mappings given in this paper, and the mappings given in  and , can be written as a product (composition) of involutions.

First, we note that the cyclic shift, $`L_c`$, i.e.

$$v_0^{}=v_1,\mathrm{},v_{n1}^{}=v_n,v_n^{}=v_0$$
(19)
can be written as a product of involutions, i.e. $`L_c=L_{12}L_{01}L_{03}L_{04}\mathrm{}L_{0n}`$ (for $`n3`$) 888The three-dimensional case is $`L_c=L_{12}L_{01}`$., where the involution $`L_{ij}`$ is defined as $`v_k^{}=v_k`$ ($`ki,j`$) together with $`v_i^{}=v_j`$ and $`v_j^{}=v_i`$ ($`i<j`$).

The mapping (15) can be written as $`L_1=L_zL_c=L_zL_{12}L_{01}L_{03}`$, where

$$w^{}=w,x^{}=x,y^{}=y,z^{}=z+\frac{\beta (wx+y)^2+\xi }{\beta (wx+y)+\gamma }$$
(20)
and $`w=v_0`$, $`x=v_1`$, $`y=v_2`$ and $`z=v_3`$.

The mapping (Appendix A. Intermediate forms) can be written as $`L_2=L_zL_yL_{02}L_{13}`$, where $`L_z`$ is defined as

$$w^{}=w,x^{}=x,y^{}=y,z^{}=z\frac{\beta (w+x+y)^2+ϵ(w+x+y)+\xi _1}{\beta (w+x+y)+\gamma _1},$$
(21)
$`L_y`$ is defined as

$$w^{}=w,x^{}=x,y^{}=y\frac{\beta (w+x+z)^2+ϵ(w+x+y)+\xi _0}{\beta (w+x+z)+\gamma _0},z^{}=z$$
(22)
and $`w=v_0`$, $`x=v_1`$, $`y=v_2`$ and $`z=v_3`$.

The mappings given in the papers  and  can be written as a product of involutions or as an involution composed with a cyclic shift. For the latter, the above discussion shows that these mappings can be written as a product of involutions. Finally, for the mapping given in , i.e.

$$x^{}=y,y^{}=z,z^{}=x+\frac{A(yz)}{Byz+C}$$
(23)
we have $`L_3=L_zL_cL_{}=L_zL_{12}L_{01}L_{}`$, where $`L_z`$ is given by

$$x^{}=x,y^{}=y,z^{}=z+\frac{A(xy)}{Bxy+C},$$
(24)
$`L_{}`$ is given by

$$x^{}=x,y^{}=y,z^{}=z$$
(25)
and $`x=v_0`$, $`y=v_1`$ and $`z=v_2`$. We note that $`L_{}`$ is an involution.

All of the above mappings are invertible since they are a product of involutions, i.e. $`L=L_0L_1\mathrm{}L_{m1}L_m`$ (where the $`L_i`$ are involutions). Their inverse is $`L^1=L_mL_{m1}\mathrm{}L_1L_0`$.