text:
# Efficiency through disinformation

## Abstract

We study the impact of disinformation on a model of resource allocation with independent selfish agents: clients send requests to one of two servers, depending on which one is perceived as offering shorter waiting times. Delays in the information about the servers’ state leads to oscillations in load. Servers can give false information about their state (global disinformation) or refuse service to individual clients (local disinformation). We discuss the tradeoff between positive effects of disinformation (attenuation of oscillations) and negative effects (increased fluctuations and reduced adaptability) for different parameter values.

Competition for limited resources occurs in many different situations, and it often involves choosing the resource least popular among competitors – one can think of drivers who want to take the least crowded road, investors who want to buy hot stocks before other buyers drive the price up, computers that send requests to the least busy servers, and many more. From an individual perspective, agents in these scenarios act selfishly – they want to achieve their particular aims. At the same time, this selfish behavior can be beneficial for the system as a whole, insofar as it leads to effective resource utilization Smith (1904); however, this is not always the case. From the point of view of the system, the problem then becomes one of distribution of resources, rather than competition.

The most commonly studied model in this context, the Minority Game (MG) Challet and Zhang (1997); Challet and Marsili (1999); MGH , has agents choose one of two alternatives, basing their decision on a short history of the global state of the system. A multitude of possible strategies for the agents can be conceived. One recurring theme in many of the MG’s variations is oscillations of preferences: in some cases, preferences oscillate in time Nakar and Hod (2002); Reents et al. (2001), whereas in others, a reaction of the system to a given history pattern will be followed by the opposite of that reaction the next time this pattern occurs Marsili and Challet (2000); Savit et al. (1999). The presence of oscillations indicates suboptimal resource utilization. Their source is the fact that agents make their decision based on obsolete data, i.e., there is a delay between the time that the information underlying their decision is generated and the time their decision is evaluated. This is often obscured by the use of discrete time steps in most variations of the MG. In this paper, we study a continuous-time MG-like scenario with an explicit time delay, which was inspired by the competition of computers for network server service, but can serve as a model case for other problems.

We also introduce a new way to think about controlling the dynamics of the system. In previous papers, possible ways to improve efficiency were explored from the point of view of agents’ strategies: how should an agent behave to achieve maximum payoff? The result, however, was measured as an aggregate quantity – the total degree of resource utilization. In this paper, we assume that the agents are selfish and short-sighted, and their strategy is not accessible to modification. Responsibility for system efficiency lies with the servers, who can influence behavior by providing incorrect information. We first introduce the system, study its native dynamics, and determine under what circumstances control measures can improve efficiency. We then present various possible scenarios of influencing the global behavior.

The model – The system we consider Klein and Bar-Yam (2003) consists of two servers $`R_1`$ and $`R_2`$, which offer the same service to a number $`N`$ of clients. Clients send data packets to one of the servers. After a travel time $`\tau _T`$, the packets arrive at the server, and are added to a queue. Servers need a time $`\tau _P`$ to process each request. We choose the time scale such that $`t_P=1`$. When a client’s request is completed, the server sends a “done” message (which takes another $`\tau _T`$ to arrive) to the client. The client is then idle for a time $`\tau _I`$, after which it sends a new packet. Clients receive information about the state of each server. They decide which server offers shorter waiting times based on this information, and send their packets to the respective server. However, for various reasons, the information they receive is obsolete – they have access to the length of the queues a delay time $`\tau _D`$ ago.

The system can be solved simply, if both servers accept all incoming requests and demand is distributed uniformly enough, such that both servers are busy at all times. The only relevant variables are $`N_1(t)`$ and $`N_2(t)`$, the number of clients whose data is in the queue or being processed by $`R_1`$ and $`R_2`$, respectively, at time $`t`$; we treat them as continuous variables. Idle clients do not have to be taken into account explicitly; neither do clients who are waiting for their “done” message from the server – for our purposes, they are the same as idle agents. We will first solve the problem neglecting agents whose message is travelling to the server, then include non-vanishing travel times.

There are only two processes which change the length of the queues: (a) Due to processed requests, both $`N_1`$ and $`N_2`$ decrease by 1 per time unit. (b) In the same time span, two clients (whose data was processed by $`R_1`$ and $`R_2`$ a time $`\tau _T+\tau _I`$ ago) compare the obsolete values $`N_1(t\tau _D)`$ and $`N_2(t\tau _D)`$ and add their requests to the queue according to this information. We write delay-differential equations for $`N_i`$:

$`{\displaystyle \frac{dN_1}{dt}}`$ $`=`$ $`2\mathrm{\Theta }(N_2(t\tau _D)N_1(t\tau _D))1;`$
$`{\displaystyle \frac{dN_2}{dt}}`$ $`=`$ $`2\mathrm{\Theta }(N_1(t\tau _D)N_2(t\tau _D))1,`$ (1)
where $`\mathrm{\Theta }`$ stands for the Heaviside step function. This can be simplified even more by introducing $`A(t)=N_1(t)N_2(t)`$, the difference in queue lengths:

$$\frac{dA}{dt}=2\text{sign}(A(t\tau _D)).$$
(2)
This has a steady-state solution

$$A(t)=2\tau _D\text{tri}\left(\frac{t}{4\tau _D}+\varphi \right),$$
(3)
where $`\text{tri}(x)`$ is the triangle function

$$\text{tri}(x)=\{\begin{array}{cc}4x1\hfill & \text{ for }0x<1/2,\hfill \\ 4(x1/2)+1\hfill & \text{ for }1/2x<1,\text{ periodic in 1,}\hfill \end{array}$$
(4)
and $`\varphi `$ is a phase determined by initial conditions.

Eq. (3) shows that the solution is oscillatory. The frequency of oscillation is only determined by the delay, and the amplitude by the ratio of delay time to processing time – the total number of clients does not play a role. Clients typically spend much of their time with their request in the queue, and adding more clients only makes both queues longer. Also, if the delay goes to zero, so does the amplitude of oscillations: the minority game is trivial if agents can instantaneously and individually respond to the current state. Fig. 1 shows that computer simulations are in good agreement with Eq. (3) and in particular that the treatment of $`N_i`$ as continuous variables works well even for small amplitudes.

Introducing a non-vanishing travel time $`\tau _T`$ has the same effect on $`A(t)`$ as increasing the delay time: it leads to the delay-differential equation

$$\frac{dA}{dt}(t+\tau _T)=2\text{sign}(A(t\tau _D)).$$
(5)
The solution is given by Eq. (3) with $`t_D`$ replaced by $`t_D+t_T`$.

The impact of idle servers – The case where oscillations become so strong that servers go idle periodically ($`2\tau _D>N`$) can be treated in a similar framework, for $`t_T=0`$: once the difference in queue lengths reaches the value $`\pm N`$, one queue ceases to process requests. Hence, the rate of requests at the other server drops from $`2`$ to $`1`$ – exactly the rate at which it keeps processing them. The queue length at the active server therefore stays constant for some time $`\tau _L`$. An example of the resulting curve can be seen in Fig. 1 (bottom). Starting from the time where $`A(t)`$ crosses the zero line, it will take a time $`\tau _D`$ for clients to realize that they are using the “wrong” server, so $`\tau _D=\tau _L+N/2`$, or $`\tau _L=\tau _DN/2`$. The period $`T`$ of the oscillations is then $`T=2\tau _L+2N=2\tau _D+N`$, which is smaller than $`4\tau _D`$. Data throughput of the system drops from $`2`$ to $`1+N/(2\tau _D)`$ (in units of $`1/\tau _P`$). All of this is again in good agreement with simulations.

The results above specify the system parameters for which oscillations affect throughput, and how strong the impact is. We now consider ways for the servers to reduce oscillations. Two methods suggest themselves: global disinformation from both servers and individual rejection by each server.

Global disinformation – If the servers have control over the information that clients receive on the servers’ status, they can intentionally make the information unreliable. Let us assume clients have a probability $`p`$ of receiving the wrong answer, and accordingly choose the “wrong” server. The update equations are:

$`{\displaystyle \frac{dN_1}{dt}}`$ $`=`$ $`2[(1p)\mathrm{\Theta }(A(t\tau _D))+p\mathrm{\Theta }(A(t\tau _D))]1;`$
$`{\displaystyle \frac{dN_2}{dt}}`$ $`=`$ $`2[(1p)\mathrm{\Theta }(A(t\tau _D))+p\mathrm{\Theta }(A(t\tau _D))]1,`$ (6)
leading to

$$\frac{dA}{dt}=2(12p)\text{sign}(A(t\tau _D)).$$
(7)
This equation has the form of Eq. (2) with a prefactor of $`12p`$, and has a steady-state solution

$$A(t)=2\tau _D(12p)\text{tri}\left(\frac{t}{4\tau _D}+\varphi \right),$$
(8)
for $`p<1/2`$. At $`p=1/2`$, no information is available: clients’ decisions are random, and queue lengths perform a random walk, whose fluctuations are not captured by the deterministic framework we are using. Even for values $`p<1/2`$, fluctuations may become larger than the typical amplitude of oscillations, and thus dominate the dynamics. For $`p>1/2`$, users migrate systematically from the less busy to the busier server, until one is idle much of the time, and the other has almost all clients in its queue.

The trade-off between reduced oscillations and increased fluctuations can be seen in Fig. 2. Rather than measuring the amplitude of oscillations, the root mean square $`A_{rms}=A^2^{1/2}`$ of $`A(t)`$ is shown. For a pure triangle function of amplitude $`a`$, one gets $`A_{rms}=a/\sqrt{3}`$. For small $`p`$, the amplitude is reduced linearly; for larger $`p`$, fluctuations increase, dominating the dampened oscillations. When the amplitude of the undisturbed system is small, fluctuations have a large impact. As the amplitude of oscillations gets larger, the impact of fluctuations becomes smaller, and the value of $`p`$ where fluctuations dominate moves closer to $`1/2`$.

Under the influence of randomness, $`A`$ performs a biased random walk: let us assume that server $`R_2`$ is currently preferred. In each unit of time, $`A/4`$ increases by $`1`$ with probability $`p^2`$ (the two clients processed both go to $`R_1`$), stays constant with probability $`p(1p)`$, and decreases by 1 with probability $`(1p)^2`$ (both clients move from $`R_1`$ to $`R_2`$). To reproduce quantitatively the effects of fluctuations, one can numerically average $`A^2`$ over such a random walk that takes place in two phases: the first phase lasts until $`A=0`$ is reached; the second takes another $`\tau _D`$ steps until the direction of the bias is reversed. The probability distribution of $`A`$ at the beginning of the half-period has to be chosen self-consistently such that it is a mirror-image of the probability distribution at the end; the proper choice for $`A/4`$ is a Gaussian restricted to positive values with mean $`(12p)\tau _D`$ and variance $`2p(1p)\tau _D`$. The numerical results are shown in Fig. 2; they agree well with values from the simulation. Note that in the above treatment, we neglected complications like multiple crossings of the $`A=0`$ line.

Adaptability –  Another aspect that determines what degree of disinformation should be chosen is adaptability of the system. The reason to have public information about the servers in the first place is to be able to compensate for changes in the environment: e.g., one server might change its data throughput due to hardware problems, or some clients might, for whatever reason, develop a strong preference for one of the servers. If the other agents can respond to these changes, global coordination remains good; if their ability to understand the situation is too distorted by disinformation, global efficiency suffers.

Let us assume that a fraction $`b`$ of agents decide to send their requests to server 1, regardless of the length of queues. Under global disinformation, out of the fraction $`1b`$ that is left, another fraction $`d`$ will send their requests to the wrong server, and yet another fraction $`d`$ is needed to compensate for that. So a fraction $`(1b)(12d)`$ is left to compensate for the action of the biased group, and the maximum level of disinformation that still leads to reasonable coordination is $`p=(12b)/(22b)`$ – larger levels lead to large differences in queue length, and finally to loss of data throughput by emptying a queue. That estimate is confirmed by simulations (see Fig. 2). Similar arguments hold if the preferences vary slowly compared to oscillation times. On the other hand, if the preferences of the biased agents oscillate in time with a period smaller than the delay time, they average out and have little effect on the dynamics.

A similar argument also applies if the servers have different capacity. Let us say $`R_1`$ has a processing time $`\tau _{P1}`$, whereas $`R_2`$ has $`\tau _{P2}>\tau _{P1}`$. A fraction $`f=\tau _{P2}/(\tau _{P1}+\tau _{P2})>1/2`$ of clients should choose $`R_1`$ – if $`p`$ is smaller than $`1f`$, the queue of $`R_1`$ will not become empty; otherwise it will.

Individual rejection – Even if servers cannot influence the public information on queue status, they can influence the behavior of clients directly: they claim they are not capable of processing a request, and reject it – let us say, with a constant probability $`r`$. Compared to global disinformation, a new possibility arises that a request bounces back and forth several times between the servers, but that adds nothing new in principle: the fraction of requests that end up at the server that they tried at first is $`(1r)+r^2(1r)+r^4(1r)+\mathrm{}=1/(r+1)`$, whereas a fraction $`r/(r+1)`$ will be processed at the other server. This is equivalent to setting $`p=r/(1+r)`$ in the “global disinformation” scheme, and gives equivalent results. Choosing $`r`$ close enough to $`1`$ reduces the amplitude of oscillations dramatically; however, each message is rejected a large number of times on average, generating large amounts of extra traffic.

Load-dependent rejection – Rather than setting a constant rejection rate, it seems intuitive to use a scheme of load-dependent rejection (LDR), in which $`r_i`$ depends on the current length of the queue. This is being considered for preventing the impact of single server overload in Ref. Braden et al. (1998). For example, let us consider the case where $`r_i=cN_i`$ if $`cN_i<1`$, and $`1`$ otherwise, with some appropriately chosen constant $`c`$. The analysis from the “indiviual rejection” section can be repeated with the additional slight complication of two different rejection rates $`r_1`$ and $`r_2`$. A fraction $`(1r_1)/(1r_1r_2)`$ of agents who initially try server 1 ends up being accepted by it, whereas a fraction $`r_1(1r_2)/(1r_1r_2)`$ finally winds up at server 2, and vice versa for clients who attempted $`2`$ first. Combining the resulting delay-differential equations for $`N_1`$ and $`N_2`$ into one for $`A`$, one obtains

$$\frac{dA}{dt}=\frac{2}{1r_1r_2}(\mathrm{\Theta }(A(t\tau _D))(12r_1+r_1r_2)\mathrm{\Theta }(A(t\tau _D))(12r_2+r_1r_2)).$$
(9)
We can now substitute the load-dependent rates. We write them as follows: $`r_1=\overline{r}+c^{}A`$, $`r_2=\overline{r}c^{}A`$, with $`\overline{r}=(r_1+r_2)/2`$ and $`c^{}=c/2`$.

For small amplitudes $`A`$ relative to the total number of players $`N`$, the deviation from $`\overline{r}`$ does not play a significant role, and it is $`\overline{r}`$ that determines behavior, yielding the same results as a constant rejection rate. For larger relative amplitudes, the oscillations are no longer pure triangle waves, but have a more curved tip. Figure 3 shows $`A_{rms}`$ for load-dependent rejection, compared to constant-rate rejection with $`r=\overline{r}`$. These nonlinear effects make LDR more efficient at suppressing oscillations, at least if $`2\tau _D`$ is not small compared to $`N`$. They also provide for a restoring force that suppresses fluctuations effectively. It follows that LDR is better at improving data throughput in parameter regimes where servers empty out, which is confirmed by simulations.

We note one problem with LDR: if $`c>2/N`$, both servers have the maximal number $`1/c<N/2`$ clients in their queue most of the time, while the rest of clients are rejected with probability 1 from both servers. For effective operation, this means that the constant $`c`$ in LDR should chosen smaller than $`2/N`$, which requires knowledge of $`N`$.

Discussion – We have introduced a model for the coordination of clients’ requests for service from two equivalent servers, found the dependencies of the resulting oscillations on the parameters of the model, and determined when and how these oscillations decrease data throughput.

We have then suggested a number of server-side ways to dampen the oscillations, which involve purposely spreading wrong information about the state of the servers. All of these schemes can achieve an improvement, showing that the presence of faulty or incomplete information can be beneficial for coordination. The margins for improvement are higher in the regime of large numbers, when the amplitude is on the order of many tens or hundreds rather than a few individuals – in the latter case, increased fluctuations can outweigh the benefits of reduced oscillation. While some disinformation generally improves performance, monitoring of the average load and amplitude is necessary to choose the optimal degree of disinformation.

The basic ingredients of the server-client scenario (delayed public information and minority-game-like structure) appear in many circumstances. One can think of traffic guidance systems that recommend one of two alternative routes, stock buying recommendations in magazines, career recommendations by employment centers, and others. Exploring the impact of disinformation on these problems is certainly worthwhile.


format: text

text:
# Untitled Document

%auto-ignore

This paper has been withdrawn by the author. The central result is now included in quant-ph/0309056 (as in the journal publication!). An erratum on the Heisenberg perturbation series estimate is also included therein.


text:
# An exact effective two-qubit gate in a chain of three spins

## I Introduction

One of the most important resources in quantum information processing is the interaction between different quantum systems, such as those possessed by remote parties or registers of a quantum computer. These systems evolve jointly according to some interaction Hamiltonian. Good methods to convert such interaction into other useful resources, using a well motivated set of control operations, are of paramount importance.

A common framework for studying such conversions involves a system of $`n`$ qubits (or higher dimensional registers) with unlimited local control. Sophisticated methods for various tasks were developed. For example, in a system coupled by simultaneous arbitrary pairwise interactions, one can extract the interaction on a select pair of qubits decoupling , which can be used to provide a coupling gate or entanglement. These methods typically approximate the desired task by interspersing the free Hamiltonian evolution with local operations. The required amount of local resources can be reflected by the frequency of manipulations, and an error parameter is given by the interval between them. In general, the task is approximated to first order of this time interval, though sometimes the exact task can be performed without excessive local resources (for examples, see Leung99 ; Jones99  for logic gate construction, and Bose03 ; Subrahmanyam03 ; Christandl03  for state transfer and entanglement generation).

In this paper, we consider a simple but nontrivial system in which several tasks can be accomplished perfectly almost without local manipulations. We consider a spin chain with nearest neighbor coupling; the two end spins are data qubits and other spins are mediating the indirect coupling between the data qubits. Furthermore, we restrict local control to the data qubits only. The Hamiltonian is given by

$$H=\underset{i,j}{}\omega _{ij}\left(\sigma _{+i}\sigma _j+\sigma _i\sigma _{+j}\right),$$
(1)
where $`\sigma _+=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right)`$ and $`\sigma _{}=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)`$ are the raising and lowering operators respectively, $`i,j`$ are spin labels; subscripts of operators indicate the spins being acted on, and the sum is over neighboring spin-pairs denoted by $`i,j`$. Expressing $`\sigma _\pm `$ in terms of the Pauli matrices $`\{\sigma _{x,y,z}\}`$, we have $`\sigma _\pm =\frac{1}{2}(\sigma _x\pm i\sigma _y)`$ and

$$H=\underset{i,j}{}\frac{\omega _{ij}}{2}\left(\sigma _{xi}\sigma _{xj}+\sigma _{yi}\sigma _{yj}\right).$$
(2)
Our main result is for the case of a $`3`$-spin chain (Fig.1). We show how to turn the free evolution into an exact effective quantum gate acting on the two data qubits without affecting the mediating spin. This gate can be used to transfer an unknown quantum state between the data spins, to create a maximally entangled state, and to communicate classical information. We also explore applications and extensions to this simple basic result.

### I.1 Related works

Before presenting our main result, we discuss some related works. Our work is motivated by Bose03 ; Subrahmanyam03  that study quantum state transfer and entanglement distribution in a spin chain of $`N`$ spins under the free evolution according to the Hamiltonian

$$H_G=\frac{J}{2}\underset{i,j}{}\stackrel{}{\sigma }_i\stackrel{}{\sigma }_jB\underset{i}{}\sigma _{zi},$$
(3)
where $`\stackrel{}{\sigma }_i\stackrel{}{\sigma }_j\sigma _{xi}\sigma _{xj}+\sigma _{yi}\sigma _{yj}+\sigma _{zi}\sigma _{zj}`$. Perfect (near perfect) state transfer between the remotest spins are only allowed for a 4-spin closed (open) chain Bose03 , apart from the trivial case of 2 spins.

Our work is also motivated by Cubitt03 , which considers a similar $`3`$-spin chain with only nearest neighbor coupling. They found mixed separable initial states such that the two remote spins become entangled by the Hamiltonian without ever entangling the mediating spin. They also proved that such phenomenon is impossible for pure states. In our system, the mediating spin is entangled during the process, but is completely disentangled from the data qubits at the end, leaving the data qubits maximally entangled.

Our work can also find application in the quantum computation scheme in Benjamin03 . Reference Benjamin03  investigated effective gates between non-neighboring spins in a Heisenberg spin chain (3) with untunable couplings. Our result is an analog in the XY model (1), and has the merit of producing a much simpler two-qubit gate (the composition of a swap gate and a controlled-phase gate) compared to Benjamin03 .

Time optimal construction of indirect $`2`$-qubit gates, such as swap or cnot, is considered in Khaneja03 . Our approach is different in requiring no local manipulations, and also in obtaining an exact implementation of the gate.

During the initial preparation of our manuscript, related works Christandl03  were reported independently by Christandl et al. They considered perfect quantum state transfer over more general spin networks (besides linear chains) under the same Hamiltonian (1). When the interaction strength is homogeneous, i.e. $`\omega _{ij}=\omega `$, they found that perfect state transfer is possible only between the two ends of an $`N=2`$ or $`3`$ linear chain, or between the antipoles for a hypercube. When the coupling strength can be suitably tuned, perfect state transfer is possible for any linear chain. Extensions to a Heisenberg chain (3) was considered when a tunable, local magnetic field can be applied to each spin. Our motivating scheme in Sec. II.1 coincides with the $`N=3`$ case of Christandl03 , which also motivated some extensions in Sec. III for longer chains. Our work differs in explicitly considering the evolution on all three spins (instead of a subspace relevant to quantum state transfer as considered in Christandl03 ). We exploit different initial configurations that result in more flexibility and better efficiencies in tasks other than state transfer, beyond immediate implications of the ability to perform state transfer.

## II An effective two-qubit gate

### II.1 Motivating scheme

The Hamiltonian for our $`3`$-spin chain (1) is simply

$$H=\omega \left(\sigma _{+1}\sigma _2+\sigma _1\sigma _{+2}\right)+\lambda \left(\sigma _{+2}\sigma _3+\sigma _2\sigma _{+3}\right).$$
(4)
We first motivate our result by considering quantum state transfer, say, from the first to the last spin:

$$|\phi _1|0_2|0_3|0_1|0_2|\phi _3.$$
(5)
Suppose the initial state of the first spin is $`|\phi _1=\alpha |0_1+\beta |1_1`$, where $`\left|\alpha \right|^2+\left|\beta \right|^2=1`$. The initial state of the three spins can be written in the form,

$`|\psi \left(0\right)`$ $`=`$ $`\left(\alpha |0_1+\beta |1_1\right)|0_2|0_3`$
$`=`$ $`\alpha |000+\beta |100.`$
The state will evolve, under the Hamiltonian (4), as

$$|\psi \left(t\right)=\alpha |000+\beta \mathrm{exp}\left(iHt\right)|100,$$
(7)
where the first term is not affected by the Hamiltonian because $`H|000=0`$. The second term can be evaluated analytically. To do this, we make use of the special properties of the raising and lowering operators to obtain

$$\begin{array}{c}H|100=\omega |010,\hfill \\ H|010=\omega |100+\lambda |001,\hfill \\ H|001=\lambda |010.\hfill \end{array}$$
(8)
Using (8), the Taylor series expansion can be evaluated explicitly

$$\begin{array}{c}\mathrm{exp}\left(iHt\right)|100=\left(1+\frac{\omega ^2}{\gamma ^2}\left(\mathrm{cos}\gamma t1\right)\right)|100\hfill \\ +\left(\frac{\omega \lambda }{\gamma ^2}\left(\mathrm{cos}\gamma t1\right)\right)|001i\frac{\omega }{\gamma }\mathrm{sin}\gamma t|010,\hfill \end{array}$$
(9)
where $`\gamma =\sqrt{\omega ^2+\lambda ^2}`$. When $`\lambda =\omega `$ and $`t=\tau \frac{\pi }{\sqrt{2}\omega }`$, we have

$$\mathrm{exp}\left(iH\tau \right)|100=|001,$$
(10)
and

$`|\psi \left(\tau \right)`$ $`=`$ $`\alpha |000\beta |100`$
$`=`$ $`|0_1|0_2\left(\alpha |0_3\beta |1_3\right).`$
Perfect state transfer (5) is then obtained by applying the local unitary operator $`\sigma _{z\mathrm{\hspace{0.17em}3}}`$ to the last spin.

### II.2 The effective two-qubit gate

To obtain our key result and to better understand the above scheme, we examine the full matrix representation of the unitary operator $`U\mathrm{exp}(iH\tau )`$, with the basis ordered as $`|000`$, $`|001`$, $`|100`$, $`|101`$, $`|010`$, $`|011`$, $`|110`$, $`|111`$,

$`U`$ $`=`$ $`\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right).`$ (20)
The subspaces spanned by $`|0_2`$ and $`|1_2`$ are invariant under $`U`$. Thus restricting $`U`$ to either subspace forms an effective two-qubit gate for the remote spins $`1`$ and $`3`$. In particular, we can consider the restriction $`\stackrel{~}{U}`$ of $`U`$ to the “$`|0_2`$ subspace,”

$$\stackrel{~}{U}_{13}=\left(\begin{array}{cccccccccccccccccccc}1& 0& 0& 0& & & & & & & & & & & & & & & & \\ 0& 0& 1& 0& & & & & & & & & & & & & & & & \\ 0& 1& 0& 0& & & & & & & & & & & & & & & & \\ 0& 0& 0& 1& & & & & & & & & & & & & & & & \end{array}\right),$$
(21)
which is a composition of the swap gate and a “joint-phase-gate” Diag$`(1,1,1,1)`$ that is equivalent to the controlled-$`\sigma _z`$ acting on spins $`1`$ and $`3`$ (up to renaming of basis states and an overall sign).

In the scheme discussed in Sec. II.1, spin $`3`$ is initialized as $`|0_3`$; the effect of the joint-phase-gate can be reverted by the local $`\sigma _{z\mathrm{\hspace{0.17em}3}}`$, so that the net effect is to swap spins $`1`$ and $`3`$, resulting in perfect state transfer.

### II.3 State transfer using $`\stackrel{~}{U}_{13}`$

Equation (21) shows that perfect state transfer (up to an irrelevant overall “$``$” sign) can be performed without the final local gate $`\sigma _{z\mathrm{\hspace{0.17em}3}}`$, if spin $`2`$ and spin $`3`$ are initialized to be $`|0_2|1_3`$ instead of $`|0_2|0_3`$. (Alternatively, we can also initialize them to be $`|1_2|0_3`$.) Thus, barring initialization of spins $`2`$ and $`3`$, no local manipulation is required at all! As a final remark, state transfer due to (21) is coherent, thus it is entanglement-preserving and in particular, $`|\varphi _{a1}|01_{23}|10_{12}|\varphi _{a3}`$ for any joint state $`|\varphi _{a1}`$ on spin 1 and an ancillary system $`a`$ of arbitrary dimension.

### II.4 Classical communication and entanglement generation

The ability to transfer a certain amount of quantum information from one end of a spin chain to another obviously implies the ability to transfer at least as much classical communication, and to share at least as much entanglement (in units of ebit) between the two ends when the transfer is entanglement preserving. In this section, we present communication and entanglement sharing or generation schemes (they differ by whether entanglement is distributed or created) that outperform the above obvious methods.

Equation (21) suggests a simple method for bidirectional classical communication BHLS03  between spins $`1`$ and $`3`$. Suppose spins $`1`$ and $`3`$ are in the possession of Alice and Bob respectively. Spin $`2`$ is in the control of the communication company who initializes the spin to $`|0_2`$ but does nothing otherwise. Since $`\stackrel{~}{U}`$ acts exactly as a swap gate on classical states, Alice and Bob can each send one classical bit to the other. Note that the combined communication rate is twice the rate of quantum state transfer and that the qualitative ability to communicate simultaneously in both direction is not implied from the ability to perform quantum state transfer.

Equation (21) also suggests an obvious method for creating entanglement between spins $`1`$ and $`3`$ – the gate $`\stackrel{~}{U}`$ creates one ebit starting from the initial product state $`|+_1|+_3`$, where $`|\pm =\frac{1}{\sqrt{2}}(|0\pm |1)`$. As $`\stackrel{~}{U}`$ acts like the swap gate followed by the joint-phase-gate, the swap leaves the state invariant, and the joint-phase-gate takes $`|+_1|+_3`$ to $`\frac{1}{\sqrt{2}}(|0_1|_3|1_1|+_3)`$, which is maximally entangled. Spin $`2`$ is invariant under $`U`$ and is disentangled from spins $`1`$ and $`3`$ at the end. Finally, $`\stackrel{~}{U}`$ can be used to share two ebits if applied to an initial state $`|\mathrm{\Phi }_{a1}|\mathrm{\Phi }_{3b}`$ where $`|\mathrm{\Phi }=\frac{1}{\sqrt{2}}(|00+|11)`$ and $`1,a`$ and $`3,b`$ are possessed by Alice and Bob respectively.

The above methods are optimal if $`\stackrel{~}{U}`$ is a fixed given resource and they require no local control besides local state initialization. Exactly one of the swap and the phase-gate components of $`\stackrel{~}{U}`$ are used in each protocol.

More generally, given the Hamiltonian $`H`$, there are alternative schemes for the various tasks that do not involve implementing $`\stackrel{~}{U}`$ and are more efficient. For example, let $`\sqrt{U}\mathrm{exp}(iH\frac{\tau }{2})`$, which can be written explicitly (again in the basis $`|000`$, $`|001`$, $`|100`$, $`|101`$, $`|010`$, $`|011`$, $`|110`$, $`|111`$) as

$`\sqrt{U}=\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 0& 0& 0\\ 0& \frac{1}{2}& \frac{1}{2}& 0& \frac{i}{\sqrt{2}}& 0& 0& 0\\ 0& \frac{1}{2}& \frac{1}{2}& 0& \frac{i}{\sqrt{2}}& 0& 0& 0\\ 0& 0& 0& 0& 0& \frac{i}{\sqrt{2}}& \frac{i}{\sqrt{2}}& 0\\ 0& \frac{i}{\sqrt{2}}& \frac{i}{\sqrt{2}}& 0& 0& 0& 0& 0\\ 0& 0& 0& \frac{i}{\sqrt{2}}& 0& \frac{1}{2}& \frac{1}{2}& 0\\ 0& 0& 0& \frac{i}{\sqrt{2}}& 0& \frac{1}{2}& \frac{1}{2}& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right).`$ (30)
The fourth and the fifth columns imply that

$`\sqrt{U}|0_2|11_{13}=i|1_2\frac{1}{\sqrt{2}}\left(|01+|10\right)_{13},`$ (31)
$`\sqrt{U}|1_2|00_{13}=i|0_2\frac{1}{\sqrt{2}}\left(|10+|01\right)_{13}.`$ (32)
Applying $`H`$ for a period of time $`\frac{\tau }{2}`$, half of that required for implementing $`\stackrel{~}{U}`$, one can create a maximally entangled state from a product state, without ancillas, and with spin $`2`$ disentangled at the end.

More amusingly, Alice and Bob can repeat the procedure indefinitely without resetting the mediating spin: Let spin $`2`$ be in $`|0_2`$ initially. Alice and Bob input the states $`|1_1|1_3`$, apply $`H`$ for time $`\frac{\tau }{2}`$, extract the maximally entangled state (using (31)), and then input the state $`|0_1|0_3`$ instead. By now, spin $`2`$ has evolved to $`|1_2`$, and according to (32), another maximally entangled state can be created after time $`\frac{\tau }{2}`$, and so on. This requires only one initialization of the mediating spin and the ability to prepare $`|0`$ and $`|1`$ locally by Alice and Bob, and to input/output a quantum state of the data qubits at intervals separated by $`\frac{\tau }{2}`$.

### II.5 Effective two-qubit gate in a network

With the spin chain in Fig. 1 as a basic unit, an effective two-qubit gate can be obtained in a larger network of spins. For example, consider a network (see Fig. 2) with three different homogeneous chains, evolved by a Hamiltonian $`H_3=H_a+H_b+H_c`$ where each of $`H_{a,b,c}`$ acts on one chain and has the form of (4), and $`\omega _a=\lambda _a`$, $`\omega _b=\lambda _b`$, and $`\omega _c=\lambda _c`$, but $`\omega _a`$, $`\omega _b`$ and $`\omega _c`$ can be different. Let $`|\stackrel{~}{0}_2|0_{2a}|0_{2b}|0_{2c}`$, and $`|\stackrel{~}{1}_2\left(\omega _a|1_{2a}+\omega _b|1_{2b}+\omega _c|1_{2c}\right)/\omega `$, where we re-define $`\omega (\omega _a^2+\omega _b^2+\omega _c^2)^{1/2}`$. The joint evolution is then analogous to the single chain case, and an effective two-qubit gate $`\stackrel{~}{U}_{13}`$ in (21) can be obtained at $`t=\tau `$. Similar argument applies to any number of chains. Each extra chain simply increases the coupling strength. We note that similar techniques has been used in the context of quantum walk, see for example Childs01 .

## III Spin chains with $`N>3`$ spins

In this section, we extend the above results to spin chains with $`N>3`$ spins. We first consider generating or sharing entanglement in inhomogeneous chains and then consider quantum state transfer for homogeneous chains.

### III.1 Inhomogeneous chains

We first consider inhomogeneous chains in which the coupling strength $`\omega _{jj+1}`$ can be tuned for different pairs of spins. Our entanglement generating or sharing schemes borrow techniques from Christandl et al Christandl03 . Our scheme takes about half of the time required for quantum state transfer.

Consider a chain of $`N`$ spins. We want to prepare a maximally entangled state $`\frac{1}{\sqrt{2}}\left(|0_1|1_N+|1_1|0_N\right)`$ between the data spins $`1`$ and $`N`$ at the two ends. When $`N`$ is odd, we find an entanglement generating scheme with a simple initial spin configuration. When $`N`$ is even, we find an entanglement sharing scheme that requires preexisting entanglement in the chain and a local magnetic field. We are going to discuss these two cases separately.

#### III.1.1 Odd number of spins

We use a more convenient basis defined as $`\frac{1}{\sqrt{2}}\left(|100\mathrm{}+|\mathrm{}001\right)`$, $`|\stackrel{~}{2}\frac{1}{\sqrt{2}}\left(|010\mathrm{}+|\mathrm{}010\right)`$, and similarly for $`|\stackrel{~}{j}`$, $`j=1,\mathrm{},n1`$, and $`|\stackrel{~}{n}|0\mathrm{}010\mathrm{}0`$. Here, $`n=\frac{1}{2}(N+1)`$ is the position of the middle spin. Suppose the initial state is $`|\stackrel{~}{n}`$. Then, Hamiltonian in (2) acts in the basis $`|\stackrel{~}{1},|\stackrel{~}{2},\mathrm{},|\stackrel{~}{n}`$ as

$$H_{\mathrm{odd}}=\left(\begin{array}{cccccccccccccccccccc}0& \omega _{12}& 0& \mathrm{}& 0& & & & & & & & & & & & & & & \\ \omega _{12}& 0& \omega _{23}& \mathrm{}& 0& & & & & & & & & & & & & & & \\ 0& \omega _{23}& 0& \mathrm{}& \mathrm{}& & & & & & & & & & & & & & & \\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \sqrt{2}\omega _{n1n}& & & & & & & & & & & & & & & \\ 0& 0& \mathrm{}& \sqrt{2}\omega _{n1n}& 0& & & & & & & & & & & & & & & \end{array}\right).$$
(33)
The task to generate entanglement is the same as to rotate $`|\stackrel{~}{n}`$ into $`|\stackrel{~}{1}`$, and it is equivalent to transferring a quantum state in a chain of length $`n=\frac{1}{2}(N+1)`$ as solved by Christandl et al Christandl03 . When the matrix elements $`\omega _{j,j+1}`$ are chosen such that

$$\omega _{j,j+1}\{\begin{array}{cccccccccccccccccccc}\sqrt{j\left(nj\right)},& & & & & & & & & & & & & & & & & & & \\ \sqrt{n1}/\sqrt{2},& & & & & & & & & & & & & & & & & & & \end{array}\begin{array}{cccccccccccccccccccc}\mathrm{for}jn1,& & & & & & & & & & & & & & & & & & & \\ \mathrm{for}j=n1,& & & & & & & & & & & & & & & & & & & \end{array}$$
(34)
$$\left|\stackrel{~}{1}\left|\mathrm{exp}\left(iH_{\mathrm{odd}}t\right)\right|\stackrel{~}{n}\right|=1$$
(35)
when $`t=\pi /\lambda `$ for a constant $`\lambda `$ described in Christandl03 . This concludes the entanglement generation scheme.

Note that the time for the above scheme is constant, while the coupling strengths $`\omega _{j,j+1}`$ is a function of $`n`$ (and most are roughly proportional to $`n`$). The resource in this framework can be identified as $`\omega _{j,j+1}t`$ or simply $`\omega _{j,j+1}`$. Thus, our scheme creates entanglement using roughly half of the resource needed in the obvious method of entanglement sharing via quantum state transfer.

#### III.1.2 Even number of spins

We describe a similar scheme for an even number of spins, which requires an initially entangled state, and a time independent local magnetic field. (It is thus an entanglement sharing scheme.) Let $`|\stackrel{~}{j}`$ be as defined before, except now $`|\stackrel{~}{n}\frac{1}{\sqrt{2}}\left(|0\mathrm{}10\mathrm{}0+|0\mathrm{}01\mathrm{}0\right)`$. Again, we initialize our state to $`|\stackrel{~}{n}`$, and entanglement sharing is achieved by rotating $`|\stackrel{~}{n}`$ to $`|\stackrel{~}{1}`$. The nontrivial part of the Hamiltonian in this basis is

$$H_{\mathrm{even}}=\left(\begin{array}{cccccccccccccccccccc}0& \omega _{12}& 0& \mathrm{}& 0& & & & & & & & & & & & & & & \\ \omega _{12}& 0& \omega _{23}& \mathrm{}& 0& & & & & & & & & & & & & & & \\ 0& \omega _{23}& 0& \mathrm{}& 0& & & & & & & & & & & & & & & \\ \mathrm{}& \mathrm{}& \mathrm{}& \mathrm{}& \omega _{n1n}& & & & & & & & & & & & & & & \\ 0& 0& \mathrm{}& \omega _{n1n}& \omega _{nn+1}& & & & & & & & & & & & & & & \end{array}\right).$$
(36)
$`H_{\mathrm{even}}`$ differs from $`H_{\mathrm{odd}}`$ only in the extra term $`\omega _{n,n+1}`$ in the lower right corner. The extra term can be removed by applying a static magnetic field of strength $`\frac{1}{2}\omega _{n,n+1}`$ to the middle two spins. Mathematically, this adds a local Hamiltonian $`H_B=\frac{1}{2}\omega _{n,n+1}\left(\sigma _{z,n}+\sigma _{z,n+1}\right)`$, and since $`H_B|\stackrel{~}{n}=0`$, $`H_B|\stackrel{~}{j}=\omega _{n,n+1}|\stackrel{~}{j}`$ for all $`j<n`$, the diagonal terms in $`H_{\mathrm{even}}+H_B`$ are all equal to $`\omega _{n,n+1}`$ and contribute an irrelevant phase only. The rest follows from the odd case.

As a side remark, for a homogeneous chain when the coupling constants $`\omega _{ij}`$ are equal, an even chain entangles slightly better. The two extra factors of $`\sqrt{2}`$ in $`H_{\mathrm{odd}}`$ causes perfect entanglement to be possible only for $`N=3`$, while it is possible for $`N=4`$ and $`6`$ in the even case.

### III.2 Homogeneous chains

For homogeneous spin chains, we study the fidelity of quantum state transfer

$$|\phi _1|0_2\mathrm{}|0_N|0_1|0_2\mathrm{}|\phi _N.$$
(37)
where the fidelity (averaged over inputs) Bose03  is defined as

$`F`$ $`=`$ $`{\displaystyle \frac{f\left(t\right)}{3}}+{\displaystyle \frac{f\left(t\right)^2}{6}}+{\displaystyle \frac{1}{2}},\mathrm{where}`$ (38)
$`f\left(t\right)`$ $``$ $`|10\mathrm{}0\left|\mathrm{exp}\left(iHt\right)\right|0\mathrm{}01|`$ (39)
and a maximization over $`t`$ is then taken.

In Fig. 3, we plotted numerical maximization of $`f(t)`$ over a sufficient long but finite range of $`t`$. A comparison with similar numerical maximization for the Heisenberg chain (with Hamiltonian given by (3)) suggests that the XY chain (with Hamiltonian given by (1)) is more effective in quantum state transfer.

For asymptotically large $`N`$, using an expression for $`f(t)`$ in Ref. Christandl03  for the XY chain,

$$f\left(t\right)=\left|\frac{2}{N+1}\underset{m=1}{\overset{N}{}}\mathrm{sin}\frac{\pi m}{N+1}\mathrm{sin}\frac{\pi mN}{N+1}e^{iE_mt}\right|,$$
(40)
where $`E_m=2\omega \mathrm{cos}\frac{m\pi }{N+1}`$. Let $`J_k`$ be the Bessel functions. The Jacobi-Anger expansion Arfken ; mathca  states that

$`e^{iz\mathrm{cos}\theta }={\displaystyle \underset{k=\mathrm{}}{\overset{\mathrm{}}{}}}i^kJ_k(z)e^{ik\theta }.`$ (41)
Applying this to (40), taking $`N`$ to be large and $`t_0`$ to be of order $`N`$, and neglecting the terms with $`kN`$ or $`kN`$, we have,

$$f(t_0)2\left|J_N(2\omega t_0)+J_{N+2}(2\omega t_0)\right|.$$
(42)
Since $`N+2+\xi (N+2)^{1/3}N+\xi N^{1/3}`$ for all $`\xi `$, and $`J_N(N+\xi N^{1/3})(2/N)^{1/3}A(2^{1/3}\xi )`$ abramowitz , where $`A()`$ is the Airy function, applying $`2\omega t_0=N+0.8089N^{1/3}`$ gives a lower bound on the fidelity

$$f(t_0)2.6998N^{1/3}.$$
(43)
This is twice the value of $`f(t_0)`$ for a Heisenberg chain (3) for the same $`t_0`$ Bose03 .

Although perfect state transfer is possible only for $`N=2`$ and $`N=3`$, fidelities very close to 1 are obtainable for sufficiently long evolution times. Such long evolution times can be shortened using a non-homogeneous magnetic field applied to individual spins. For example, for an $`N=4`$ XY chain, the maximum fidelity obtained is $`0.99997`$ at $`t=53.4/\omega `$, in the time interval of ($`0,100/\omega `$). However, if we apply a magnetic field of strength $`B=0.625\omega `$ on the two middle spins only, the fidelity is $`0.99991`$ at $`t=6.25/\omega `$, see Fig. 4.

## IV Conclusion

We have demonstrated how to obtain an exact effective two-qubit gate in a chain of three spins without local manipulations, and discussed various applications of it, including quantum state transfer, classical communication, and entanglement generation and distribution. We also discuss some extensions to longer chains. Other observations of the system can be found in the Appendix.

###### Acknowledgements.

We thank Andrew Landahl for help comments on an earlier manuscript. This work is partially supported from the US National Science Foundation under grant no. EIA-0086038. DWL thanks the Richard C. Tolman Endowment Fund at Caltech for partial support. SB thanks for a postdoctoral scholarship at the Caltech Institute for Quantum Information, during which this work started.

## Appendix: Miscellaneous results

Here we explore more applications of the gate $`U`$ and other results. In a chain of three spins, the gate $`U`$ can actually entangle any pair of spins. For example, to entangle spin 1 and 2, while leaving spin 3 unentangled, we can initialize the state to be $`|0_1|+_2|+_3`$. The final state is $`\frac{1}{\sqrt{2}}\left(|0_1|_2|1_1|+_2\right)|0_3`$. On the other hand, the gate $`U`$ can also act as an effective one-qubit gate, $`\sigma _{z2}`$, for the middle spin if we initialize the state to be $`|0_1\left(\alpha |0_2+\beta |1_2\right)|0_3`$, for any $`\alpha `$ and $`\beta `$.

Together with an application of a single-qubit rotation, we can readily generate a three-qubit entangled state, the $`W`$ state DVC00 , $`\frac{1}{\sqrt{3}}\left(|101+|011+|110\right)`$, by a free evolution under the Hamiltonian in (4). More explicitly, $`\mathrm{exp}\left(iHt\right)|101=\mathrm{cos}\gamma t|101i\frac{\omega }{\gamma }\mathrm{sin}\gamma t|011i\frac{\lambda }{\gamma }\mathrm{sin}\gamma t|110`$. When $`\omega =\lambda `$ and $`t=\mathrm{tan}^1\left(\sqrt{2}\right)/\sqrt{2}\omega `$, we obtain the $`W`$ state after applying the phase gate $`|00\left|+i\right|11|`$ to the middle spin.


text:
# Brillouin scattering studies in Fe3O4 across the Verwey transition

## I Introduction

Magnetite has attracted renewed attention in recent years because of its interesting electronic, magnetic, and transport properties as well as potential applications in the magnetic multilayer devices . Stoichiometric Fe3O4 shows a first order metal-insulator (MI) transition, referred to as Verwey transition, with the reduction in the electrical conductivity of nearly two orders of magnitude at the transition temperature ($`T_V`$). The cubic inverse spinel structure (F3dm) of Fe3O4 may be written as Fe3+\[Fe2+Fe3+\]O4, where the tetrahedrally coordinated Fe3+ ions (A-site) is differentiated from the bracketed Fe2+ and Fe3+ octahedral sites (B-sites). The spins of the two B-site cations are antiparallel to the single A-site Fe3+ cation, giving rise to ferrimagnetic order, with a transition temperature of 850 K . Cubic magnetite at room temperature changes to a monoclinic structure below $`T_V`$, containing four rhombohedrally distorted cubic cells . However, there is also an evidence of a triclinic structure at low temperatures . The question of charge ordering (CO) of the Fe2+ and Fe3+ states on the B sites in the low temperature phase is a matter of continued controversy. The recent experimental data on Mössbauer , neutron , x-ray diffraction  and 57Fe NMR  studies are not consistent with the expected CO. On the other hand, the high-energy transmission electron diffraction studies show charge ordering below the Verwey transition . Also, the high resolution x-ray and neutron powder diffraction data has revealed charge ordering, two Fe ions with a charge of +2.4 and the other two of +2.6, as evidenced by the presence of two types of BO6 octahedra and the distribution of B-B distances .

The effect of nonstoichiometry, either by oxygen deficiency or impurities has been studied recently . Nonstoichiometry shifts the Verwey transition to lower temperatures as well as broadens the transition . The nature of the transition also changes from first order to higher order beyond a certain doping level . The influence of the linear magnetoelastic interaction on the ultrasonic sound velocity and attenuation in Fe3O4 was investigated by Moran and Lüthi . Of the three elastic constants, only C44 showed a significant softening from room temperature to $`T_V`$, whereas C11 and C12 showed an increase as $`T`$ was lowered, with a jump at $`T_V`$ .

The role of lattice in the Verwey transition in Fe3O4 has been discussed in the literature . Recent Raman studies have revealed a strong electron phonon coupling for the T2g optical phonon . The motivation of the present work is to study the behavior of acoustic phonons across the Verwey transition using Brillouin scattering experiments. In this paper, we present the temperature dependence of the surface as well as bulk acoustic phonons in pristine Fe3O4 from 300 to 30 K. A pronounced softening of the surface acoustic phonon velocity as $`T`$ is lowered to $`T_V`$, and its subsequent significant hardening below the transition, is observed in our experiments. On the other hand, there is no appreciable change in the bulk acoustic phonon velocity with temperature along both  and  directions. However, a large change in the intensity for the bulk mode is observed near $`T_V`$, with a hysteresis of about 45 K. This non-monotonic behavior of the intensity is may be due to the large domain wall movements expected close to $`T_V`$ as well as stress induced ordering of the ions.

## II Experimental Details

Single crystals of magnetite used in this study were grown by the standard skull melting technique . Standard four probe resistivity measurements show the MI Verwey transition to occur at 123 K . The crystals were mechanically polished using diamond suspension to obtain a highly reflecting surface. After polishing, the crystals were cleaned in methanol, followed by acetone, using an ultrasonic bath. The measurements have been performed on the  and  faced crystals of the undoped Fe3O4. Brillouin spectra were recorded in the oblique-incidence as depicted  180-back-scattering geometry, with an incident angle of $`\theta =45^{}`$ relative to the surface normal. Ideally $`\theta `$ should be $`70^{}`$ for an oblique-incidence experiment. In our experiment, the horizontal plane defines the scattering plane and the sample is mounted with its surface perpendicular to the scattering plane. The optical windows in our cryostat used for the temperature dependent studies are placed at $`90^{}`$ to each other. Thus the angle of incidence has to be $`45^{}`$, in order to avoid hitting the reflected light inside the cryostat. The scattered light was analyzed using a JRS Scientific instruments (3+3)-pass tandem Fabry-Perot interferometer equipped with a photo avalanche diode detector. The 532 nm ($`\lambda `$) line of Nd:YAG single mode solid-state diode-pump frequency doubled laser (Model DPSS 532-400, Coherent Inc. USA) was used as the excitation source. The temperature-dependent measurements with a temperature accuracy of $`\pm 1`$ K were carried out inside a closed cycle helium cryostat (CTI Cryogenics, USA). The incident laser power was kept at $``$ 25 mW focused to a spot of diameter $``$ 30 $`\mu `$m. The typical time required per spectrum is 1.5 h. The lineshape parameters - peak position, full-width at half maximum (FWHM), and area were extracted by non-linear least square fitting of the data with Lorentzian functions, together with appropriate background corrections.

## III Results and Discussion

Figure 1 shows the room temperature Brillouin spectrum of Fe3O4 , displaying two well resolved peaks, at 8 GHz and 60 GHz. The 8 GHz mode shows a linear dependence of its frequency on the wavevector component parallel to the surfaces, $`q_{}`$ ($`=4\pi `$sin$`\theta /\lambda `$, where $`\theta `$ is the scattering angle), expected for a surface Rayleigh wave (SRW) (as shown in inset (a) of Fig. 1). Further, the frequency of the 8 GHz mode shows a sinosidal dependence (see inset (b) of Fig. 1) on the azimuthal angle $`\varphi `$ (angle of rotation with respect to the scattering plane about the normal), confirming it to be a SRW mode. For the  oriented crystal, the high frequency mode appears in HH polarization, showing it to be a bulk longitudinal acoustic (LA) mode. Here H stands for horizontal polarization, which lies in the scattering plane. The surface Rayleigh wave velocity (obtained from the slope of the curve shown in inset (a) of Fig. 1) is 3200 m/sec, and the bulk longitudinal acoustic velocity is 6600 m/sec, in close agreement with the earlier reported longitudinal sound velocity along  direction . We point that a very weak mode is seen at 13 GHz in unpolarized spectrum, which can be attributed to the magnon. This mode could not be observed with the sample inside the cryostat. We further note that transverse acoustic phonons, though seen in oblique incidence Brillouin scattering experiments  are too week to be observed in our backscattering experiments. We believe that the strong absorption at 2.32 eV excitation energy  broadens the Brillouin line making it difficult to observe.

The temperature-dependence of the SRW frequency, $`\nu _s`$, along  direction of Fe3O4 is shown in Fig. 2(a) . Upon cooling below 250 K, there is a large softening in $`\nu _s`$ ($``$ 6 %) till $`T_V`$. Below $`T_V`$ there is a steep increase in $`\nu _s`$ ($``$ 10 %). The temperature-dependence of SRW along  direction is similar to that observed in  direction as shown in Fig. 2(b), though the magnitude of softening is smaller compared to the  crystal. The magnitude of anisotropy in $`\nu _s`$ in the two directions  and  is shown as a function of temperature in the inset of Fig. 2(b). The full width at half maxima (FWHM) as well as intensity of the SRW mode for both directions  and  show changes near $`T_V`$. The FWHM of the surface mode is comparable to that of the instrumental broadening and hence cannot be qualitatively interpreted. However, we note that below $`T_V`$, the full width at half maxima of the SRW increases, which is still to be understood. The intensity of the SRW mode decreases as the temperature is lowered due to the Bose-Einstein population factor. The SRW mode could not be observed below 50 K in the cooling cycle, but it reappears upon heating the sample above 50 K.

The bulk LA velocity does not undergo any observable change with temperature, i.e., there is no appreciable change in the Brillouin peak position (as shown in Fig. 3(a)) or FWHM. However, the peak intensity shows a strong anomaly around $`T_V`$ for both the  as well as the  directions, as can be seen in Fig. 3(b) (for the  direction). In the cooling run, the intensity gradually increases with a decrease in temperature and shows a maximum at $``$ 120 K, followed by a sharp drop below $`T_V`$ (see filled circles in Fig. 3(b)); the mode cannot be observed below 70 K. In the heating run, the LA mode reappears at $``$ 70 K and its intensity is a maximum at 165 K (see open circles in Fig. 3(b)), displaying a considerable hysteresis of $``$ 45 K (Fig. 3(b)). The hysteresis is approximately double that which is measured in the magnetization measurements . We now explain our observations.

### A Surface Rayleigh wave

For the cubic crystal, the SRW frequency depends on the elastic constants C11, C12 and C44 . Using Green’s function method  we have calculated surface mode spectra for different temperatures in the  direction with the elastic constants C11, C12 and C44 taken from Ref. , and shown by dotted lines in the inset of Fig. 2(a). The values of $`\nu _s`$ thus calculated are plotted as dotted line in Fig. 2(a). Though the temperature dependence of the calculated $`\nu _s`$ is similar to our observation, the quantitative agreement is not so good. It is important to note that the values of the elastic constants shown in the inset of Fig. 2(a) were obtained in a magnetic field of 0.5 T. In order to obtain a better fit of the calculated $`\nu _s`$ with the data, we adjusted the value of C44, keeping the values of C11 and C12 as before. This was done because the temperature dependence of $`\nu _s`$ is similar to that of C44. The solid line in Fig. 2(a) shows the calculated $`\nu _s`$, in very good agreement with the data. The value of C44 needed to get this good fit are shown by filled circles in the inset of Fig. 2(a).

We will now address the softening of C44 between 250 K and $`T_V`$. This behavior of C44 has been attributed to a bilinear coupling of the shear strain, $`ϵ`$, with the order parameter, $`\eta `$, related to the charge ordering processes . A similar behavior of the elastic constant C44 has been observed in other charge ordered systems Yb4As3  and $`\alpha ^{}`$-NaV2O5 . Taking the usual Landau free energy expansion in terms of an order parameter $`\eta `$, along with the additional strain-order parameter coupling term $`F_C`$ leads to the free energy expression $`F=F_0+\alpha \eta ^2+\beta \eta ^4+F_C+F_{el}`$. Here $`F_0`$ is the part of the free energy which remains constant through the phase transition, $`F_{el}`$ is due to the elastic energy, and $`F_C=gϵ\eta `$, where $`g`$ is the coupling constant between the strain and the charge fluctuation order parameter. This coupling leads to the softening of the shear elastic constant

$$C_{44}(T)=C_{44}^0(TT_0)/(T\mathrm{\Theta })$$
(1)
where $`\mathrm{\Theta }`$ is the transition temperature without the strain-order parameter coupling, and

$$T_0=\mathrm{\Theta }+0.5g^2\alpha ^{}C_{44}$$
(2)
with the usual Landau term $`\alpha =\alpha ^{}(T\mathrm{\Theta })`$. The difference of the two characteristic temperatures $`(T_0\mathrm{\Theta })`$ corresponds to the coupling strength of the strain and the order parameter . The values of C44, obtained by the fit of the SRW frequency at various temperatures shown by the filled circle in the inset of Fig. 2(a) were fitted to give $`T_0`$ = 57 K and $`\mathrm{\Theta }`$ = 40 K, showing the coupling strength between strain and order parameter to be around 17 K, which is somewhat higher than that estimated ($``$ 10 K) by Schwenk et al . Since the contribution of C44 to $`\nu _s`$ in  and  directions are different, the anisotropy parameter plotted in the inset in Fig. 2(b), will also reflect the temperature dependence of C44. The gradual decrease in intensity with temperature is expected from the usual thermal population factor.

### B Bulk LA mode

Unlike transparent materials, absorbing materials have a complex refractive index, $`n=\eta +i\kappa `$ and the optical field falls off exponetially in the medium. This results in the uncertainity in the wavevector transfer $`q`$ , leading to broadening of the Brillouin lines, over and above the lifetime broadening. The full-width at half maximum (FWHM), $`\mathrm{\Gamma }=4vk_{}\kappa `$ and the peak position at $`\omega =2\eta vk_{}`$ gives $`\frac{\mathrm{\Gamma }}{\omega }=2\frac{\kappa }{\eta }`$; where $`v`$ is the sound velocity, $`k_{}`$ is the incident wavevector . For Fe3O4, $`\alpha `$ has been measured only up to 0.75 eV and its value is $`3.5\times 10^3`$ cm-1 . Unfortunately, there is no measurement of $`\alpha `$ at 2.32 eV. Extrapolating the results of Balberg et al , we find $`\alpha 10^5`$ cm-1 at 2.32 eV. This gives $`\mathrm{\Gamma }=14`$ GHz, which is close to the observed value of 16 GHz in our experiments. Hence, most of the width of the bulk LA mode is due to the large absorption coefficient of Fe3O4.

Schwenk et al.  have shown that the change in C11 is $``$3 % between 300 to 80 K (see inset in Fig. 2(a)), which implies a change of 1.5 % ($``$ 0.9 GHz) in LA frequency, since the change in density is negligible . This is within the resolution limit of 1 GHz in our Brillouin experiments and is consistent with the temperature dependence shown in Fig. 3(a). Now we give a plausible explaination of the non-monotonic variation of intensity of the LA mode with temperature (Fig. 3(b)). The intensity of the scattered light by the LA mode is related to the Pockels coefficients $`p_{11}`$ and $`p_{12}`$, which are related to the derivatives of the dielectric function with respect to the strain $`ϵ`$. In the case of Fe3O4, the strains are not completely elastic. There are two sources of non-elastic strains; one is a stress-induced domain wall motion $`ϵ_d`$ (magnetostriction) , and the other is stress-induced ordering of Fe2+ and Fe3+ among the octahedral sites, $`ϵ_{order}`$. Hence the total strain $`ϵ`$ is the sum of $`ϵ_{elastic}`$, $`ϵ_d`$ and $`ϵ_{order}`$. Fine et al.  have found that the Young’s modulus $`Y`$ ($`Y`$ = stress/$`ϵ`$) of magnetite shows a minimum near $`T_V`$ (see inset of Fig. 3(b)), which is absent in a magnetic field. Since a magnetic field should have no effect on elastic strains and should not prevent ordering, the anomaly in the Young’s modulus is attributed to the contribution of the domain wall motion to the strain. Bickford et al.  suggested that if a single crystal of Fe3O4 is cooled through the transition in absence of magnetic field, it is not a true single crystal below $`T_V`$ . Furthermore, the regions may be twinned, since the a and b crystal axes can be interchanged. In some of the earlier experiments the domain size has been found to be around 0.5 up to 2 $`\mu `$m . This is much smaller compared to the laser spot of 30 $`\mu `$m diameter. However, the crystal reverts to the single crystalline cubic phase upon heating above $`T_V`$ . An increase in strains around $`T_V`$ is expected to result in an increase in the value of the Pockel coefficients and hence, the intensity of the LA mode. It would be interesting to measure the intensity of the mode in the presence of magnetic field, which will make the sample single domain.

In conclusion, Brillouin scattering studies on Fe3O4 reveal that there is a large change in the surface Rayleigh wave velocity associated with the Verwey transition, which is driven by a bilinear coupling of shear strains with the charge ordering. The transition temperatures T0 and $`\mathrm{\Theta }`$ are found to be 57 K and 40 K, showing the coupling strength to be 17 K. The temperature behavior of the intensities of the longitudinal acoustic mode may be understood in terms of non-elastic strains due to domain wall motion and charge ordering.

Mr. Seikh would like to thank Council of Scientific and Industrial Research (CSIR), India for a research fellowship. We like to acknowledge the continued support, encouragement and fruitful discussions with Prof. C.N.R. Rao. Thanks are due to Department of Science and Technology (India) for financial support.