Abstract
The effect of the inevitable coupling to external degrees of freedom of a quantum computer are examined. It is found that for quantum calculations (in which the maintenance of coherence over a large number of states is important), not only must the coupling be small but the time taken in the quantum calculation must be less than the thermal time scale,h/k B T . For longer times the condition on the strength of the coupling to the external world becomes much more stringent.
I. INTRODUCTION
Quantum computers have recently raised a lot of interest. A number of papers [1] have argued that quantum computers can solve certain problems much more efficiently than can classical computers. Shor [2] has shown that a quantum computer could solve the problem of finding discrete logs (mod N) and of finding the factors of a large number N in a time which is a polynomial function of the length L of the number. For factoring the best known algorithm, the Number Field Sieve [3] takes a time of order exp(c(L)
where c(L) is roughly constant and approximately equal to 2 for large L. Although this is subexponential, it is worse than any polynomial for large N. A crucial feature of the ability of quantum computers to be more efficient in certain problems involves having the computer be placed in the coherent superposition of a very large number (exponential in L) of "classical states", and having the outputs interfere in such a way that there is a very high probability that on the appropriate reading of the output, one would obtain the required answer. One is replacing exponentiallity in time with exponentiallity in quantum coherence. This requires that the computer be able to maintain the coherence during the course of the calculation.
This paper examines this requirement, and examines the constraints placed on the ability to maintain this coherence in the face of coupling to external heat baths. Landauer [4] has long emphasized the necessity of examining the effect of both imperfections and of the coupling to the external world of any realistic device on the ability of quantum computers to realize their promise. This paper is thus a first step in that direction.
II. DECOHERING NOISE
I will look at only the simplest model, in which I ask about the maintenance of coherence in a memory of length L. This does not take into account the effect that the course of the computation itself would have on the rate of loss of coherence, but I would expect that only to increase the problem. Thus let us assume that that the number is represented in the computer as a string of binary digits of length of the order of L = ln(N). The memory cells will each be taken to be two level systems, with each of the two levels having the same energy. The two states will be take to be the eigenstates of a "spin" operator σ z .
In a conventional computer, the way in which the calculation is "kept on track" is by including dissipation in order to damp out any attempt by the system to make a transition ( except of course those driven by the computation) [5] . I will therefore assume that the interaction with the environment has the two desired eigenstates of the memory as eigenstates of the interaction. The environment will be modeled by a massless scalar field [6] derivatively coupled to the memory cell, so that the the full Hamiltonian is
(The associated lagrangian has the simple derivative coupling form
Here h(x) is some interaction range function, and π is the momentum conjugate to φ
The Heisenberg equations of motion areπ
The exact solutions for the Heisenberg equations of motion for φ are
Since in the model, σ z is a constant of the motion (recall that I am not taking into account the effects of the operation of the computer) the solution for φ is thus
I will however be working in the Schroedinger representation in the following.
L assume that the initial state of the environment is a thermal density matrix R T with temperature T , and the initial state of the spin is a density matrix ρ(0). The total state is assumed to be a product state of these two initial states. The reduced state of the spin system at any time (t) after tracing out over the state of the environment is a density matrix given by
where ρ(t) is a time dependent vector of length less that or equal to unity. ρ(t) is given by
where the trace is over all of the degrees of freedom of spin system and bath.
We can write H as
is just the translation operator taking π(0, x)to π(0, x) + ǫ h(x)φ(0, x)dxσ z , and since σ z commutes with H 0 .
Thus
whereφ(t) = e iH 0 t φ(0, x)e −iH 0 t is the time development of the free field with the same initial conditions φ(0) and π(0), i.e.,
Using σ 2 z = 1 and the fact that R T is diagonal in the energy representation, we can write
(Note that the extra terms from the Cambell-Baker-Hausdorf formula cancel out.) This can furthermore be written as
+sin( (φ(t) − φ(0))ǫhdx)) e z × σR T where e z is the unit vector in the z direction. Because R T is symmetric in φ and π, the sin term is zero, and
We are thus left with
For later use, let us examine J(t) in various regimes. Let us take h(x) such that h(k), the Fourier transform of h(x) is of the form e
Γk . Γ is a cutoff parameter typical of interactions with the environment. I will assume that Γ >> 1/T . We then get
We can approximate coth(
.). This gives us
There are essentially three regimes for the time dependence of J(t) given by the conditions t < Γ, Γ < t < 1/T and t > 1/T . In the first regime, t < Γ, we have approximately
For the intermediate regime, Γ < t < 1/T ,the quantum regime, we have
Finally, for the long time regime t >> 1/T , the thermal regime, we have
The important feature of these asymptotic formula is that for the intermediate regime,
which I call the quantum regime since the behaviour is dominated by the vacuum state of the environment, ln(J) increases only logarithmically with t. In contrast, the third regime, the thermal regime, it increases linearly with t. This will be important in determining the ultimate size of a number which can be say factored with a quantum computer, because of the dependence of the computing time on the length of the number being factored.
This was for the most familiar case of an "ohmic" coupling to the heat bath. In the case of superohmic (h(k(ω)) = ω s e ( − Γω) for s > 0), the function ln(J(t)) is essentially constant for times less than 1/T and grows as t 1−s in the thermal regime for s < 1. For s > 1, J is constant in both regimes, although it is smaller in the thermal regime than in the quantum regime. ( and is essentially constant even for such times if s > 1) In the subohmic case, −1 < s < 0, on the other hand, lnJ(t) grows roughly as t −s in the quantum regime and as t 1−s in the thermal regime. Again, in the thermal regime the growth in decoherence is a factor of t larger than in the quantum regime.
The above analysis was carried out for a single bit in the memory of the quantum computer. Let us examine the situation in which our memory has some large number L of bits. Each bit is assumed to couple to its own heat bath of exactly the above type. The 
The probability that after time t the memory remains in the the state ψ is given by
where (n i ⊗ n ′ i ) is the XOR of the ith bits of n and n ′ .
This expression tells us how the coherent sum over the various states of the memory representing various numbers decoheres as a function of time. As an example, let us chose the completely coherent state in which each of the numbers of length L has an equal probability.
This state is typical of the state required in performing quantum calculations of the sort in which a quantum computer is much faster than a classical computer. Ie, I choose |α n | 2 = 2 −L .
Furthermore let me assume that each bit is coupled to the environment in exactly the same way so that J i (t) = J(t). Then we have the probability that the coherence will be maintained over time t as
To evaluate this first fix the number n. The number of numbers n' which differ from n in 1 bit is L. The number which differ in 2 bits is L(L − 1)/2 and the number which differ in r bits is L! r!(L−r)! . Thus the above becomes
If we assume that 1 − J is very small (which is the only case in which the system has any hope at all of acting like a quantum computer), this is well approximated by 
as long as
The strength of the quantum computer is that the time required to perform the calculation is a polynomial in the length L of the number. This time I will designate by τ (L).
Since the quantum calculation is polynomial in L we can write τ (L) ≈ L a for a > 1. We thus have that the probability of maintaining coherence over the time of the calculation is of the order of
in the quantum regime while it is of order
with a smooth transition between the two regimes. In order to have a reasonable probability of obtaining the correct answer, one needs the probability of obtaining the quantum coherent answer to be of order 1. This implies that one must have a sufficiently small ǫ 2 , the coupling parameter between the heat bath and the system. As long as one is in the quantum regime, the relation between the coupling ǫ 2 and the maximum length of the number one can handle is essentially inverse linear, no matter what the polynomial dependence of the calculation.
However, once one has entered the thermal regime, a decrease in the coupling buys one only a small increase in the length of the number L that one can use. I.e., in the presence of a coupling to the heat bath, the thermal time scale 1 T ≡h k B T plays a crucial role. As long as the calculation can be completed in a time less than this, one can imagine decreasing the coupling to the heat bath for the memory cells so as to achieve the maximum L. If however the time for the calculation is longer than the thermal time scale, it becomes very difficult to decrease the coupling to the bath sufficiently to achieve the necessary coherence.
Is it possible to use the computer even if the quantum state looses coherence? I cannot answer this in general, but can show that one strategy does not work. One could imagine trying to make up for the loss of coherence by increasing the number of times the program is run. (This is in fact a crucial factor in the Shor algorithm for factoring, not because of decoherence, but because the calculation itself has a finite probability of not giving the correct outcome.) After a sufficient number of attempts, one should by chance have a system which has maintained coherence. In the factoring problem, one can test ones answer ( does it give the factors of the number), and simply keep repeating the experiment until one gets the right answer. However, in M trials, the probability of never finding a coherent outcome
The number of trials required to make this small (i.e., so that one has a high probability of having had a coherent run) is thus , the required number of attempts is M ≈ 1/P rob ≈ e O(1)Lln(L) in the quantum regime, which is exponential in the length. In the thermal regime, this time scale is even worse. One will thus have lost all advantages of the quantum nature of the computer. We see that one must make sure that coherence is maintained during the calculation.
In order to maintain coherence, one must have a small value for ǫ 2 . At first as one decreases ǫ 2 , the gain in the maximum length number one can factor is roughly inversely proportional to the value of ǫ 2 . However, once ǫ is sufficiently small that the time scale of computation for the maximum length which can maintain coherence approaches the inverse thermal time 1/T , one reaches a bottleneck. Further reductions in ǫ 2 now have little effect on the maximum length. The decoherence due to the rapidly increasing time spent in computation cancels out the effect of the smaller ǫ 2 . Thus the thermal time scale 1/T sets an effective limit to the time of the calculation, and thus a weak limit on the maximum length of the numbers one can compute with.
If one imagines factoring a 1000 bit number, and one assumes that the quantum factoring time can be made to be of order L 2 (probably the slowest rate imaginable), we find that one must carry out at least 10 6 calculation in the thermal time scale. Since the thermal time scale for a temperature of 1K is of the order of 10 −9 sec, this would imply that one would have to use a computer which ran at optical frequencies.
III. OTHER NOISE
The above coupling to the heat bath is "error free" in the sense that if one is in a number eigenstate (ie, is in a state |n >), the system will remain in that state throughout.
The environment does not cause spin flips. What about the situation in which there is also some probability of a state flip-ie of the system making a transition between the two eigenstates of σ z ? One could approximate this by assuming that the coupling to the heat bat is via say
, with small θ.
The above analysis is exactly the same for this case, where we replace σ z everywhere by σ θ . Writing the number eigenstates with respect to σ θ so that
The probability of remaining in the state |n > under the coupling to the heat bath is then
where S(n, m) is the number of bits in which n and m are the same. Again using the arguments above as to the number of terms where the S has a given value, we get
For small θ this gives
Thus θ must be kept very small in order to ensure that the probability of error remains small. However we note that the probability of error is vastly suppressed with respect to the decoherence probability, which is in accord with the observation that the decoherence effects are in general much larger and more rapid than are transition effects.
This has assumed that the process causing spin flips is the same as the one causing loss of coherence in a superposition of the two spin states. In general, the environmental degrees of freedom which cause decoherence are not the same as those causing bit flips. I will therefore look at the alternative situation in which the single bit Hamiltonian is of the form
Since we want the single bit decoherence and bit flip probabilities to be small ( or else the quantum computer is useless from the start), I will assume that the ǫ k are all sufficiently small. Furthermore, for simplicity I will take ǫ 2 = ǫ 3 , so that the spin flip processes are of equal strength. I cannot solve this problem exactly, but since the probabilities are assumed to be very small, one can calculate the transition probability to lowest order in the various epsilons. The Hamiltonian can be written as
where σ i = (σ z , σ x , σ y ). The reduced density vector ρ(t) is given by
To zeroth order, since H = H 0 is independent of σ, we have ρ(t) = ρ(0). To first order, one obtains terms which are linear in the πs and the φs. However in the thermal state, all of these are zero, because the thermal state (of H 0 ) is symmetric in the fields. To second order the results are non-zero. However all of the cross terms ǫ i ǫ j for i = j will again be zero because the fields are by assumption independent and thus the cross correlations between terms linear in each of the fields will again be zero. Thus the only terms surviving will be the terms proportional to ǫ 2 i . But each of these terms are independent of the other ǫs. I.e., each of these terms are the same as those obtained by setting the other two epsilons to zero.
These are however just the same as the second order terms calculated above in the first part.
We thus get
Note that since all of the fields are of the same form and at the same temperature, the T r(R T ( φ i (t) − φ i (0))hdx) 2 ) are the same for all i. The probability of bit flip then becomes
while the probability of decoherence for a state which is the coherent sum over all the integers of length L is given by
If ǫ 1 >> ǫ 2 , the decoherence will again be much more rapid that the probability of "error" due to bit flip.
ACKNOWLEDGMENTS
I would especially like to thank the Santa Fe Institute and the organizers of the May 1994 conference on Complexity, Entropy, and the Physics of Information where the issue of quantum computing was a key theme, and which incited my interest in the problems thereof.
IV. CONCLUSION
Quantum computation places the demand on the system that the coherence of the initial state be maintained throughout the computation. In order to maintain this coherence in the presence of a heat bath, the reduction in the coupling to the heat bath buys one a proportional increase in the size of the computation only in the computation can be completed within a thermal time scale. For computation times longer than the thermal time scale, a decrease in the coupling gives one relatively little change in the size of the possible coherent computation. The thermal time scale thus sets a (weak) limit on the length of time that a quantum calculation can take.

{'paper_id': '13980886', 'title': 'Maintaining Coherence in Quantum Computers', 's2_url': 'https://api.semanticscholar.org/CorpusID:13980886', 'source': 'S2ORC'}