text:
# Game-theoretic discussion of quantum state estimation and cloning

## Abstract

We present a game-theoretic perspective on the problems of quantum state estimation and quantum cloning. This enables us to show why the focus on universal machines and the different measures of success, as employed in previous works, are in fact legitimite.

The topic of quantum games is a new area of study within quantum information, and its potential usefulness and consequences are still being explored and understood . Early on in its development, Meyer  discussed a connection between quantum games and quantum information processing. However the majority of the research carried out on quantum games to date, has lacked a direct connection to quantum information processing.

In this paper, we discuss two quantum games which are of fundamental interest to quantum information processing and specifically to quantum crytopgraphy: the quantum state estimation game and the quantum cloning game. These two quantum games are no strangers to physicists, and have been investigated extensively. However there are still some significant questions waiting to be addressed. First: most work in these two areas focused on universal machines, and it was typically assumed that the initial pure state to be measured or cloned had a uniform distribution according to the corresponding unitary group. But why are these assumptions legitimate? Second: the measure of success in the cloning game was not unique, and researchers used different measures to facilitate their expositions. So why did they end up with the same answers? The purpose of this paper is to answer these two questions by means of a unifying game-theoretic scenario which describes these two games.

We start with a description of the two games concerned:

Quantum state estimation game Suppose there are two players, I and II, with a referee presiding over the game. Player II chooses an arbitrary pure state $`|\psi `$ where $`=𝐂^d`$. He then sends $`|\psi ^N`$ to player I and $`|\psi `$ to the referee. Player I’s task after receiving the $`N`$ qubits from player II, is to perform a measurement on them. Based on the outcome, player I sends a pure state $`|\varphi `$ to the referee. For example, if player I decides to use the set of POVM operators $`\{M_m\}`$ to do the measurement, and if he associates state $`|\varphi _m`$ to measurement outcome $`m`$, the final state that he sends back to the referee will be $`_m\mathrm{tr}[M_m\rho M_m^{}]|\varphi _m\varphi _m|`$ where $`\rho =(|\psi \psi |)^N`$. After receiving the two qubits from player I and player II, the referee applies the SWAP-test  on them: if the test says that the two states are equal, he awards a payoff of 1 to player I and $`1`$ to player II. Otherwise, player I gets a payoff of $`1`$ and player II a payoff of 1.

Quantum cloning game In this game, player II chooses a pure state $`|\psi `$ where $`=𝐂^d`$. He sends the state $`(|\psi \psi |)^N`$ to player I and the state $`(|\psi \psi |)^M`$ to the referee. After receiving the state from player II, player I designs a device that takes as input $`(|\psi \psi |)^N`$ and outputs a state $`\sigma `$ such that $`\sigma `$ is a density operator in $`^M`$. He then sends $`\sigma `$ to the referee. Finally, the referee applies the SWAP-test on $`(|\psi \psi |)^M`$ and $`\sigma `$. If they pass the test, he awards a payoff of 1 to player I and $`1`$ to player II. Otherwise he awards $`1`$ to player I and 1 to player II.

The above games are generalizations of the quantum games considered in Refs. . However, one fundamental difference from the games of Refs.  is that these games involve communication via qubits. Moreover, comparing to the strategy sets discussed in Ref. , we are placing a severe restriction on the players’ strategy sets. This is justifiable because only one particular quantum operation is of interest. We also note that the quantum state estimation and quantum cloning games that we consider here, are equivalent to the games discussed in Ref.  and Ref.  respectively. The game-theoretic analysis which follows below, however, is new.

Before deducing any general theorems for these games, we will review some basic definitions in game theory for completeness. Further details are given in Ref. . For a vector $`\stackrel{}{v}=(v_i)_{iN}`$ where the $`k`$-th entry corresponds to the $`k`$-th player’s choice of strategy, we set $`\stackrel{}{v}_k`$ to be $`(v_i)_{iN\{k\}}`$ and we denote $`(v_1,\mathrm{},v_{k1},v_k^{},v_{k+1},\mathrm{},v_N)`$ by $`(\stackrel{}{v}_k,v_k^{})`$. We also define the set of so-called best replies for player $`k`$ to be $`B_k(\stackrel{}{\chi }_k):=\{\chi _k\mathrm{\Omega }_k:P_k(\stackrel{}{\chi }_k,\chi _k)P_k(\stackrel{}{\chi }_k,\chi _k^{}),\chi _k^{}\mathrm{\Omega }_k\}`$ where $`P_k(\stackrel{}{\chi })`$ is the payoff for the $`k`$-th player given profile $`\stackrel{}{\chi }`$. We note that a strategy $`\chi _kB_k(\stackrel{}{\chi }_k)`$ means that adopting $`\chi _k`$ renders the optimal payoff to player $`k`$ if all the other players have chosen strategies according to the strategy profile $`\stackrel{}{\chi }_k`$. Using this notion of best reply, we can easily define what a Nash equilibrium is: an operator profile $`\stackrel{}{\chi }`$ is a Nash equilibrium if $`\chi _kB_k(\stackrel{}{\chi }_k)`$ for all $`k`$.

We are now ready to state and prove two theorems for these games:

###### Theorem 1

For the quantum state estimation and cloning games,

$$\underset{\chi \mathrm{\Omega }_\mathrm{I}}{\mathrm{max}}\underset{\xi \mathrm{\Omega }_{\mathrm{II}}}{\mathrm{min}}P(\chi ,\xi )=\underset{\xi \mathrm{\Omega }_{\mathrm{II}}}{\mathrm{min}}\underset{\chi \mathrm{\Omega }_\mathrm{I}}{\mathrm{max}}P(\chi ,\xi )$$
(1)
where $`\mathrm{\Omega }_\mathrm{I}`$ and $`\mathrm{\Omega }_{\mathrm{II}}`$ are the strategic sets for player I and player II respectively and $`P(\chi ,\xi )`$ is the payoff for player I.

Proof: We use the formalism developed in Ref.  where the same theorem was proved. The only difference here is that we have allowed an exchange of qubits between the two players, i.e. the payoff matrix now has entries of the form:

$$\mathrm{tr}[R(\underset{\mathrm{I}^{}\mathrm{s}\mathrm{operators}}{\underset{}{\stackrel{~}{E}\stackrel{~}{E}I}})(\underset{\mathrm{II}^{}\mathrm{s}\mathrm{operators}}{\underset{}{I\stackrel{~}{E}\stackrel{~}{E}}})\rho (\underset{\mathrm{II}^{}\mathrm{s}\mathrm{operators}}{\underset{}{I\stackrel{~}{E}^{}\stackrel{~}{E}^{}}})(\underset{\mathrm{I}^{}\mathrm{s}\mathrm{operators}}{\underset{}{\stackrel{~}{E}^{}\stackrel{~}{E}^{}I}})]$$

with the summation indices omitted for clarity. We note that $`R`$ corresponds to the SWAP-test by the referee. Although the overall operation on the initial state is no longer a direct product of the two players’ strategy sets, this detail is inessential with regards the theorem for the following reason: once a basis for the vector space of operators is fixed, $`\{\stackrel{~}{E}\}`$ in this case, then all the coefficients attached to the operators commute to the front. Hence one can see that the resulting payoff function is again bilinear with respect to the vector spaces of the strategy sets of the two players. Also, since we have allowed mixed strategies for the two players, the resulting strategy sets are convex. Compactness of the strategy sets also follows from a similar discussion in Ref. . We can therefore deduce the theorem by invoking the Minmax theorem of Ref.  because the strategy sets are compact and convex, and $`P(\chi ,\xi )`$ is linear and continuous in $`\chi `$ and $`\xi `$. Q.E.D.
The above proof is almost identical to the classical version, but one should note that the two players’ strategy spaces no longer form a direct product of operator spaces.

The next theorem is more general than we need and it highlights the similarity of the quantum state estimation and quantum cloning games. In fact, the same proof shows that in the well-known children’s game of rock-paper-scissors, the best strategy is to adopt the three options with uniform probability.

###### Theorem 2

Consider a two-player zero-sum game with pure strategy sets $`\mathrm{\Omega }_\mathrm{I}`$ and $`\mathrm{\Omega }_{\mathrm{II}}`$ for players I and II respectively, such that the Minmax theorem applies. Suppose that $`\mathrm{\Omega }_{\mathrm{II}}`$ is a compact topological group with the property that for each $`e\mathrm{\Omega }_\mathrm{I}`$, there is an $`e_f^{}\mathrm{\Omega }_\mathrm{I}`$ such that the payoff $`P(e_f^{},f)=P(e,f^{}f)`$ for all $`f\mathrm{\Omega }_{\mathrm{II}}`$. Then the strategy $`\xi ^{}`$ which corresponds to adopting a specific strategy with uniform probability with respect to the unique Haar measure, is a strategy at a Nash equilbrium for player II.

Proof: We let $`\chi ^{}B_\mathrm{I}(\xi ^{})`$ where $`B_\mathrm{I}(\xi ^{})`$ is the set of best replies of player I with respect to $`\xi ^{}`$. $`\chi ^{}`$ can be represented by the probability ensemble $`\{Q(e)de,e\}`$ where $`Q(e)de`$ is the probability for choosing the pure strategy $`e`$. We now define $`\overline{\chi }^{}`$ to be the probability ensemble $`\{Q(e)dedf^{},e_f^{}\}`$ where $`df^{}`$ is a uniform probability distribution corresponding to the Haar measure of $`\mathrm{\Omega }_{\mathrm{II}}`$. Then

$`P(\overline{\chi }^{},\xi ^{})`$ $`=`$ $`{\displaystyle 𝑑e𝑑f𝑑f^{}Q(e)P(e_f^{},f)}`$ (2)
$`=`$ $`{\displaystyle 𝑑e𝑑f𝑑f^{}Q(e)P(e,f^{}f)}`$ (3)
$`=`$ $`{\displaystyle 𝑑e𝑑fQ(e)P(e,f)}`$ (4)
$`=`$ $`P(\chi ^{},\xi ^{}).`$ (5)
Hence, $`\overline{\chi }^{}`$ is also in $`B_\mathrm{I}(\xi ^{})`$ but with the extra property that $`P(\overline{\chi }^{},f^{})=P(\overline{\chi }^{},f^{\prime \prime })`$ for all $`f^{},f^{\prime \prime }\mathrm{\Omega }_{\mathrm{II}}`$. Borrowing the terminology from the cloning literature, we call $`\overline{\chi }^{}`$ universal. Now, suppose $`\xi ^{}`$ is not at a Nash equilibrium but $`\widehat{\xi }`$ is (its existence is guaranteed by the Minmax theorem). Then

$$P(\overline{\chi }^{},\widehat{\xi })<P(\overline{\chi }^{},\xi ^{}).$$

However this is impossible because $`\widehat{\xi }`$ is itself a probability ensemble of $`\mathrm{\Omega }_{\mathrm{II}}`$. The theorem therefore follows. Q.E.D.
We can also deduce the following corollary from the above theorem:

###### Corollary 3

Consider a game as depicted in Theorem 2. Any universal strategy $`\overline{\chi }^{}`$, such that $`P(\overline{\chi }^{},\xi ^{})`$ is optimal and where $`\xi ^{}`$ is the same strategy as defined in Theorem 2, is therefore at a Nash equilibrium. Q.E.D.

The quantum state estimation and quantum cloning games fall within the realm of the previous theorems. We are therefore ready to discuss the two questions we set out to answer. First: the assumption of having an initial pure state distributed with uniform probability, is legitimate because this corresponds to a strategy at Nash equilibrium for player II. Subsequently, optimizing the estimation or cloning operation with respect to this strategy gives us the value of the corresponding game. Furthermore, if the resulting operation is universal, then the operations are themselves guaranteed to be at Nash equilibrium using the above corollary. The reason why Werner obtained an identical result  to Gisin and Massar , despite the fact that they adopted different measures of success, is as follows: the quantity Gisin and Massar identified for optimization (with $`\chi \mathrm{\Omega }_\mathrm{I}`$) was

$$P(\chi ,\xi ^{}),$$
(6)
while that of Werner was

$$\underset{\xi \mathrm{\Xi }}{inf}P(\chi ,\xi )$$
(7)
where $`\mathrm{\Xi }`$ is the set of strategies whereby player II can only choose one particular pure state rather than a probabilistic mixture of many. Hence using Theorem 1 and Theorem 2, we can see that the bound that they arrived at is actually the value of the cloning game. Furthermore, since Werner’s optimization was with respect to all unitary states, the operation found is guaranteed to be at Nash equilibrium by Theorem 1. On the other hand, since the operation found by Gisin and Massar is universal, it is also at Nash equilibrium due to Theorem 2.

For completeness, we now give the Nash equilibria for the quantum state estimation and quantum cloning games:
The quantum state estimation game with $`N`$ initial qubits has a Nash equilibrium $`(\chi ^{},\xi ^{})`$ where $`\chi ^{}`$ corresponds to the following strategy:

1. Measure the initial set of qubits with the set of measurement operators $`\left\{_{m,n}c_re^{i\psi _r(mn)}d_{m,N/2}^{N/2}(\theta _r)d_{n,N/2}^{N/2}(\theta _r)|mn|\right\},1rN+1`$ where the $`c_r`$’s are such that

$$\underset{r}{}c_re^{i\psi _r(mn)}d_{m,N/2}^{N/2}(\theta _r)d_{n,N/2}^{N/2}(\theta _r)=\delta _{m,n}.$$
(8)
Here $`|m`$ is short-hand for $`|\frac{N}{2},m`$ with the principal axis adopted with uniform probability according to the corresponding unitary group, and with $`d_{m,N/2}^{N/2}(\theta )`$ being the rotation operator of a spin-$`N/2`$ particle .
2. Upon measurement $`s`$, submit to the referee the qubit $`|\varphi _s`$ where $`|\varphi _s^N=_me^{i\psi _sm}d_{m,N/2}^{N/2}(\theta _s)|m`$.

For player II, $`\xi ^{}`$ corresponds to adopting a pure state with uniform probability with respect to the Haar measure of the unitary group. The value of the game is $`\frac{N+1}{N+2}`$.
The $`NM`$ quantum cloning game in a $`d`$-dimensional Hilbert space has a Nash equilibrium $`(\chi ^{},\xi ^{})`$ where $`\chi ^{}`$ corresponds to the mapping :

$$\rho \frac{d[N]}{d[M]}s_M(\rho \mathrm{𝟏}^{(MN)})s_M.$$
(9)
Here $`s_M`$ is the orthogonal projection of $`^M`$ onto its Bose space and $`\xi ^{}`$ corresponds to adopting a pure state with uniform probability with respect to the Haar measure of the unitary group. The value of the game is $`d[N]/d[M]`$ where $`d[N]=\left(\begin{array}{c}d+N1\\ N\end{array}\right)`$.
Although we have only succeeded in finding one particular strategy profile at Nash equilibrium, this is in fact sufficient as far as playing the game is concerned due to the following theorem:

###### Theorem 4

In a two-player zero-sum game, let $`(\chi _1,\xi _1)`$ and $`(\chi _2,\xi _2)`$ be two equilibrium pairs. Then

1. $`(\chi _1,\xi _2)`$ and $`(\chi _2,\xi _1)`$ are also equilibrium pairs, and
2. $`P(\chi _1,\xi _1)=P(\chi _2,\xi _2)=P(\chi _1,\xi _2)=P(\chi _2,\xi _1)`$.

Proof: The proof can be found in Ref. . Q.E.D.
In contrast to general games where one should worry about multiple Nash equilibria, a strategy at equilibrium is as good as any other in a two-player zero-sum game. Therefore, finding one such equilibrium is enough.

We note that there is, in fact, more than one version of a quantum cloning game: these versions differ according to how the referee determines the payoffs. For example, the referee may perform a one-particle test or multiple-particle test on the qubits he/she receives. However it turns out that the strategies at the Nash equilibrium are equivalent . Unfortunately, their equivalence cannot be deduced from game-theoretic arguments since the payoff vectors $`R`$ differ for these two games, and consequently they are distinct in the game-theoretic formalism. However, we can in fact deduce a bound on asymmetric cloning from the Minmax theorem by considering the one-particle-test game. In this game, the referee is going to apply the SWAP-test on $`|\psi \psi |`$, which is sent by player II, together with a reduced density matrix $`\sigma `$ obtained by tracing out all but the $`k`$-th Hilbert space $``$ where $`k`$ is chosen by player II. In a similar way to the above argument, one can see that Keyl and Werner have shown that the mapping in Eq. 9 is the strategy at Nash equilibrium, and the value of a $`NM`$ cloning game is $`\frac{N(d+M)+MN}{(d+N)M}`$. Hence if there exists an asymmetric cloner such that the sum of the fidelity of the $`M`$ output states with respect to the original input state is greater than $`\frac{N(d+M)+MN}{(d+N)}`$, then it will violate Theorem 1. Therefore given a $`NM`$ cloner, the sum of the fidelity of the $`M`$ output states with respect to the original input state is less than or equal to $`\frac{N(d+M)+MN}{(d+N)}=N+𝒪(1/d)`$. This bound thus limits the flow of information from one system to another. We note that the above bound on asymmetric cloning is also implicit in Ref. : however in that work the authors proceeded by symmetrizing the asymmetric cloning machine.

In summary we have discussed the problems of quantum state estimation and cloning using a game-theoretic perspective, and have found the corresponding Nash equilibria. We also justified the focus to date on universal machines, and the different measures of success employed. The fact that the theorems that we deduced are more general than we needed, implies that they have potential use in other adversary-type scenarios. We also note that although we have restricted the referee’s action to be physical, hence rendering some situations impossible , this need not be the case. In fact, the Minmax theorem holds as long as the payoff function is rendered linear with respect to $`\chi `$ and $`\xi `$. We conclude by noting that it is well-known among computer scientists that bounds on classical computing can be proved by classical game-theoretic techniques . So could quantum games pay back this debt by passing similar benefits back over to quantum computation? The answer awaits further investigation.

CFL thanks NSERC (Canada), ORS (U.K.) and the Clarendon Fund (Oxford) for financial support.


format: text

text:
# The Size of the Extragalactic Source J1801-231 and the Association of Pulsar PSR B1758-23 with the Supernova Remnant W 28

## 1 Introduction

The W 28 supernova remnant (SNR) lies in the direction of the Galactic Center: $`(l,b)=(6.8,0.06)`$. The distance to W 28 is somewhat uncertain. Since the distance to the SNR is important to the conclusions of the current study, it is useful to examine previous estimates of the distance found in the literature. Many authors have used the $`\mathrm{\Sigma }D`$ relation to derive a distance to W 28 near $``$2 kpc (Milne 1970; Clark & Caswell 1976; Goudis 1976; Milne 1979); however, as discussed by Kaspi et al. (1993), this method is extremely uncertain. The furthest distance estimated in the literature is 3.6 kpc by Lozinskaya (1974), based on H$`\alpha `$ measurements and assuming an LSR velocity near +18 km s-1 for W 28. Velazquez et al. (2002) estimate a distance of 1.9$`\pm `$0.3 kpc adopting +7 km s-1 for the LSR velocity, and assuming a standard circular rotation model (this is the near kinematic distance; 15 kpc is the far kinematic distance). Frail, Kulkarni, & Vasisht (1993) adopt a distance of 3 kpc, based on HI absorption, assuming an LSR velocity of 17.6 km s-1. While the weight of the evidence for distance estimates to W 28 favors a lower distance ($``$ 2 kpc; the argument of Velazquez et al. 2002 for an LSR velocity of +7 km s-1is especially strong), we adopt a conservative estimate for the distance to W 28 of 2.5$`\pm `$0.7 kpc.

The 60,000 year old pulsar PSR B1578$``$23 lies in the same direction as W 28 but is located outside the SNR, approximately three arcminutes to the north of its bright radio continuum edge. A radio continuum source, J1801$``$231 (also known as 1758$``$231), lies within two arcminutes of this pulsar. J1801$``$231 is assumed to be an extragalactic source, coincidentally along the line of sight to the pulsar, based on measurements of neutral hydrogen absorption (Frail, Kulkarni, & Vasisht 1993). Using observations of the pulsar and the neighboring extragalactic source, Frail et al. argued in favor of the association of the pulsar and the SNR. Kaspi et al. (1993) disagreed, suggesting that the pulsar was much more distant. The discussion of Frail et al. was based upon the similarity of HI absorption profiles toward the pulsar and extragalactic source. Kaspi et al. base their conclusion on the high dispersion measure of the pulsar (1074 pc cm-3), and the argument that no compact HII region or cloud appears to lie along the line of sight to the pulsar which could account for such a high dispersion measure.

Several OH (1720 MHz) masers associated with the W 28 SNR (Frail, Goss, & Slysh 1994) have been studied at high angular resolution with the Very Long Baseline Array (VLBA) and MERLIN by Claussen et al. (1999a). Though there have been only a few OH(1720 MHz) masers in W 28 observed at 10 mas resolution, those masers are resolved and have sizes ranging from 50 to 100 milliarcseconds (mas). Claussen et al. discussed the effects of interstellar scattering on the sizes of the masers and the constraints that could be placed on such scattering sizes based on available information about the size of J1801$``$231, the pulsar, and the pulse broadening of the pulsar. Interstellar scattering of an extragalactic source results in angular broadening while interstellar scattering of a pulsar’s radio emission can also result in pulse broadening, an increase in the apparent width of a pulsar’s average pulse profile beyond its intrinsic width. The degree of angular broadening for the masers and the extragalactic source and the degree of pulse broadening for the pulsar all depend in different ways upon the relative geometry of the observer, scattering material, and sources. Measurements of these scattering effects can constrain the distribution of the scattering material and can be used to estimate, for example, the unscattered sizes of the masers.

In this paper, we present angular broadening measurements of the extragalactic source J1801$``$231 as a function of observing frequency from 1285 MHz to 4885 MHz. We used the NRAO Very Large Array (VLA) in its most extended configuration (A) linked, in real time, with the Pie Town (Pt) antenna of the Very Long Baseline Array (VLBA). The questions to be addressed by these measurements are (1) the relative distances of the pulsar and the supernova remnant (which we assume harbors the OH masers), (2) the effects of scattering on the observed size of the masers and the pulsar, and (3) the distance to the scattering screen.

## 2 Observations and Data Reduction

### 2.1 Observations

The VLBA Pie Town (Pt) antenna has been linked in real time via fiber-optic cable with the VLA (Claussen et al. 1999b; Beresford 2000). For purposes of scientific observations, the data from the Pt antenna is sent to the VLA correlator just like any other VLA antenna. For sources with declinations $`>`$ 40 , the angular resolution in two dimensions is improved by approximately a factor two compared with using the VLA in the A configuration. As the declination of sources tends to the south, the increase in resolution is realized in only one dimension.

We observed the extragalactic source J1801$``$231 on January 15, 2001, with the VLA+Pt link. We performed five snapshots of the source of approximately 10 minutes each on source at six frequencies: 1285, 1315, 1365, 1665, 1715, and 4885 MHz. The five snapshots covered an hour angle range of about $`\pm `$1.5 hours. At the frequencies 1285 to 1715 MHz, we employed 25 MHz front-end filters to help avoid radio-frequency interference and minimize the radial smearing due to the effects of finite bandwidth (see e.g. Bridle & Schwab 1999, and references therein). At 4885 MHz the filters were set at 50 MHz. Two independent circular polarizations were observed at each frequency, and subsequently averaged in the imaging process. The data were edited, calibrated, and imaged in the standard manner, using the NRAO Astronomical Image Processing System (AIPS). Absolute flux calibration was provided assuming that 3C 286 has flux densities of 15.44, 15.27, 15.01, 13.63, 13.43, and 7.46 Jy beam-1 at 1285, 1315, 1365, 1665, 1715, and 4885 MHz respectively.

Uniform weighting of the u,v data was used in the imaging to allow the data from Pt baselines to contribute to the image. The AIPS task JMFIT was used to fit two-dimensional gaussians to the brightness distribution of J1801$``$231, and to deconvolve the synthesized beam from those fits. Table 1 shows a summary of the observations, imaging, and gaussian fits to the images of J1801$``$231. Since the sizes of the radio source measured by fitting and deconvolving the observed size are nearly circular, the deconvolved sizes reported in Table 1 are the geometric mean of the two-dimensional gaussian fits. We also detected the pulsar B1758$``$23; the image of the pulsar suffers from severe bandwidth smearing, since it is two arcminutes from the phase center. Accurate size measurements of the pulsar are thus compromised. However, we attempted to correct the measured sizes of the pulsar by estimating the magnitude of the smearing. At all frequencies, the best estimate of the size of the pulsar is $`<`$ 0.5 arcseconds.

## 3 Results and Discussion

Figure 1 shows the results of our angular size measurements of J1801$``$231: a log-log plot of the deconvolved size $`\theta `$ versus observing frequency. A well-known frequency scaling relation exists for the measured angular size of a source whose structure is dominated by interstellar scattering effects (Rickett 1977):

$$\theta _{scattered}\nu ^\gamma ,$$

where $`\gamma `$ takes on a value between $``$2 and $``$2.2 . For reference, we have drawn a line with slope $`2`$ in Figure 1; it is clear that the measured sizes shown are consistent with the effects of interstellar scattering.

Under the assumption that the intervening turbulence is confined to a single thin screen, scattering measurements of galactic and extragalactic compact sources can completely constrain the location of the screen. The assumption that the scattering screen is thin is equivalent to the statement that the scattering screen has a thickness which is much less than the distance to the extragalactic source (e.g. Trotter, Moran, & Rodríguez 1998). Since the extragalactic source is likely to be at least several megaparsec away, a thickness of several pc for the screen is consistent with this assumption. Temporal broadening of the pulsed emission from a pulsar and angular broadening of pulsars and masers depend differently upon the distribution of scattering material along the line of sight. Additionally, angular broadening of the extragalactic source J1801$``$231 is sensitive only to the strength of the turbulence, not to its distribution along the line of sight.

In addition to the angular size measurements of J1801$``$231 and the pulsar PSR B1758$``$23 reported here, we also use the measured size of the OH masers (Claussen et al. 1999a), and the measured temporal broadening of the pulse of the pulsar (Kaspi et al. 1993; Frail, Kulkarni, & Vasisht 1993) in order to estimate 1) the distance to the pulsar, 2) the distance to the scattering screen, and 3) the unscattered size of the OH masers. In order to make these estimates, we make the further assumption that the scattering screen is uniform across both the pulsar and the extragalactic source (the two radio sources are separated by about 2 arcminutes). At a distance of 10 kpc, 2 arcminutes corresponds to about 6 pc. On pc scales, it is not unreasonable to expect that the scattering medium is at least somewhat uniform. Lazio et. al (1999) find that the Galactic center scattering region (covering Sgr A\*, OH masers, and extragalactic sources) is inhomogeneous on scales of order 10 pc, whereas Fey, Spangler, & Mutel (1989) find that scattering in the Cygnus region changes by factors of two to five over angular separations of a few degrees (100—200 pc).

If we denote the measured sizes of the extragalactic source, the pulsar, and the OH(1720 MHz) masers as $`\theta _e,\theta _p,`$ and $`\theta _m,`$ respectively, the distance to the scattering screen, the masers, and the pulsar as $`d_s`$, $`d_m`$, and $`d_p`$, respectively, and the temporal broadening of the pulsar as $`\tau _p`$, then three relevant relations can be derived (e. g. Britton, Gwinn, & Ojeda 1998; Frail, Kulkarni, & Vasisht 1993):

$$\theta _e=\theta _p(1+f_p)$$
(1)
$$\theta _e=\theta _m(1+f_m)$$
(2)
$$1+f_p=(\theta _e)^2d_s/(8c\mathrm{ln2}\tau _p),$$
(3)
where

$$f_p=\frac{d_s}{(d_pd_s)},f_m=\frac{d_s}{(d_md_s)},$$

and $`f_p`$ and $`f_m`$ are dimensionless while $`\theta _e,\theta _m`$, and $`\theta _p`$ are in radians, $`\tau _p`$ is in seconds, and $`c`$ is the speed of light.

We can rearrange these equations to obtain:

$$\frac{\theta _p}{\theta _e}+\frac{d_s}{d_p}=1$$
(4)
$$\frac{\theta _m}{\theta _e}+\frac{d_s}{d_m}=1$$
(5)
$$\frac{d_s}{d_p}+\frac{(8c\mathrm{ln2}\tau _p)}{(\theta _e^2d_s)}=1.$$
(6)
In distance units of kpc, time units of seconds, and angular units of arcseconds, Equation 6 becomes:

$$\frac{d_s}{d_p}+2.292\frac{\tau _p}{(\theta _e^2d_s)}=1$$
(7)
and Equation 4 becomes

$$\theta _p=\frac{2.292\tau _p}{\theta _ed_s}.$$
(8)
Measurements of the three angular sizes $`\theta _e,\theta _p`$, and $`\theta _m`$ and the broadening time $`\tau _p`$, will thus lead to a determination of $`d_s,d_m`$, and $`d_p`$.

In practice, the angular sizes and the broadening time are measured at different frequencies. Since scattering quantities are frequency dependent, we must transform the measurements to a common frequency. The choice of frequency is obviously the frequency of the maser angular size measurement, 1720 MHz. The size measurement of the OH masers is subject to two different interpretations: scattering due to interstellar turbulence or large intrinsic maser sizes (Lockett et al. 1999). We therefore scale all measurements to 1720 MHz and apply the above relations at that single frequency.

Theoretically, $`\tau _p`$ scales with $`\nu ^{2\gamma }`$ while $`\theta _e,\theta _m,\theta _p`$ scale with $`\nu ^\gamma `$. As mentioned earlier, $`\gamma `$ can take on a value between $``$2.0 and $``$2.2 — the exact value used for $`\gamma `$ will have a substantial effect on the derived quantities. Uncertainties in the measurement of the sizes and the pulse broadening, along with the uncertainty in $`\gamma `$, lead to a range of possible estimates of the distances to the pulsar and the scattering screen and the size of the pulsar.

Although there is considerable uncertainty as mentioned above, a clear result can be obtained if we consider the direct measurement of the size of J1801$``$231 at 1715 MHz ($`\theta _e=`$220 mas). A plot of the distance to the pulsar vs the distance to the scattering screen, using this value for $`\theta _e`$ in Equation 7 is shown in Figure 2. The pulse broadening time $`\tau _p`$ in Equation 7, necessary for the plot, was estimated by Frail et al. to be 0.07 seconds at 1670 MHz. The 1520 MHz pulse profile in Kaspi et al. is consistent with a slightly smaller 1670 MHz value in the range 0.055 to 0.057 seconds. Both of these measurements taken together would suggest a value for $`\tau _p`$ at 1720 MHz in the range 0.048 to 0.051 seconds. In our analysis we find that there are no significant differences in our conclusions using this range of values for $`\tau _p`$. The plot in Figure 2 uses the mean of pulse broadening times, 0.0495 seconds. Dashed lines in Figure 2 show the same relation for pulsar distance — screen distance for $`\theta _e=180`$ and $`\theta _e=260`$ mas. For $`\theta _e=220`$ mas, Figure 2 shows a clear minimum for the pulsar distance of about 9.4 kpc, which requires the scattering screen to be at a distance of 4.7 kpc. The SNR distance of 2.5 kpc is also plotted on Figure 2, for reference.

The solid line in Figure 2 is determined directly from Equation 7 with $`\tau _p=0.0495`$ seconds and $`\theta _e=220`$ mas, so we can analytically determine where the minimum pulsar distance occurs. Equation 7 can be written as a quadratic equation in $`d_s`$,

$$d_{s}^{}{}_{}{}^{2}d_pd_s+\beta d_p=0,$$
(9)
where

$$\beta =2.292\frac{\tau _p}{\theta _{e}^{}{}_{}{}^{2}}.$$

The solutions (for $`d_s`$) to this quadratic equation are

$$d_s=\frac{d_p\pm \sqrt{d_p^24\beta d_p}}{2}.$$
(10)
We can determine a minimum value for $`d_p`$ by taking the derivative $`\frac{dd_p}{dd_s}`$. This leads to the well-known relation

$$d_{p,min}=2d_s$$

(e.g. Gwinn, Bartel, & Cordes 1993). This minimum value of $`d_p`$ occurs when $`d_p=4\beta `$ and $`d_p=0`$. Since $`d_p=0`$ is not an acceptable solution, we find that the minimum value for $`d_p`$ is $`4\beta `$. Table 2 lists a few values for $`d_{p,min}`$ and the value of $`d_s`$ where $`d_{p,min}`$ occurs, using values of $`\theta _e`$ which bracket the errors of our measurements. The entries in Table 2 show that, even for values of $`\theta _e`$ outside our one-sigma errors, the minimum distance for the pulsar is well beyond the distance to the W 28 SNR. Based on these values in Table 2, we can estimate the uncertainty in the minimum pulsar distance to be $`\pm `$2.4 kpc, with a corresponding uncertainty in the screen distance to be $`\pm `$1.2 kpc.

With an estimate of the minimum distance to the pulsar and a corresponding distance to the screen established, we can use Equation 8 to estimate the scattered size of the pulsar. This estimate is 110$`\pm `$15 mas at 1720 MHz, well below our upper limit for the size of the pulsar. Table 2 also lists the values of the pulsar scattered sizes ($`\theta _p`$) for different values of $`\theta _e`$.

It is clear from Figure 2 that smaller values of the screen distance are possible for a given value of $`\theta _e`$, as the pulsar distance increases (to the left of the minimum pulsar distance in Figure 2). We can use the solid curve in Figure 2, in conjunction with Equation 2, to estimate the size of the OH(1720 MHz) masers ($`\theta _m`$), based on an extreme value for the pulsar distance. Selecting a pulsar distance of 15 kpc, the screen distance would have to be 2.9 kpc, and thus the ratio of the extragalactic source size to the maser source size ($`1+f_m`$) would be $``$33, predicting a maser scattering size of $`<`$ 7 mas. Placing the screen closer to the Earth along the line of sight (in order to decrease $`f_m`$ and increase the scattering size of the masers) requires that the pulsar be even more distant, likely outside the Galaxy.

These estimates for the distances of the scattering screen and the pulsar have two immediate ramifications: (1) the pulsar is not associated with the W 28 SNR; and (2) the OH(1720 MHz) masers are unscattered, since placing the screen at 4.7 kpc puts it beyond the distance to the supernova remnant (2.5 kpc). Thus the measured angular sizes of the W 28 masers as reported by Claussen et al. (1999a) (50 — 100 mas) are intrinsic to the maser rather than due to interstellar scattering. Finally, our estimate of the distance to the pulsar is more consistent with the dispersion measure of the pulsar as measured by Kaspi et al. (1993) than with a closer distance ($`d>`$ 9.5 kpc).

## 4 Conclusions

We have measured the size of the extragalactic source J1801$``$231 at six frequencies, and find that our size measurements are consistent with angular broadening due to turbulence in the interstellar medium. Together with the size measurements of OH(1720 MHz) masers, assumed to be associated with the W 28 supernova remnant (Claussen et al. 1999a), and the temporal broadening of the pulsar B1758$``$23 (Frail, Kulkarni, & Vasisht 1993; Kaspi et al. 1993), the results of the new size measurements of J1801$``$231 imply:

$``$ The minimum distance for the pulsar is 9.4$`\pm `$2.4 kpc and it is not associated with the SNR. The distance to a single scattering screen for this minimum pulsar distance is 4.7$`\pm `$1.2 kpc, and is also beyond the SNR.

$``$ The scattering screen can be moved placed closer to the Earth by increasing the pulsar distance. Even with an extreme distance to the pulsar, this leads to a negligible scattering contribution to the size of the OH masers.

$``$ In either of the two possibilities above, the maser sizes must be little affected by interstellar scattering, and the sizes measured for the masers must therefore be intrinsic to the masers.

$``$ When the pulsar is placed at the minimum distance of 9.4 kpc, the scattering size of the pulsar, estimated from the J1801$``$231 size measurements, is about 110 mas at 1720 MHz, consistent with our upper limit to the pulsar size of 500 mas.

We thank Walter Brisken for estimating the size of the pulsar in the presence of bandwidth smearing, and we also thank an anonymous referee for a careful reading of the manuscript and suggestions which improved the paper. The National Radio Astronomy Observatory is a facility of the National Science Foundation, operated under cooperative agreement by Associated Universities, Inc.


text:
# A practical scheme for quantum computation with any two-qubit entangling gate

## Abstract

Which gates are universal for quantum computation? Although it is well known that certain gates on two-level quantum systems (*qubits*), such as the controlled-not (cnot), are universal when assisted by arbitrary one-qubit gates, it has only recently become clear precisely what class of two-qubit gates is universal in this sense. Here we present an elementary proof that *any* entangling two-qubit gate is universal for quantum computation, when assisted by one-qubit gates. A proof of this important result for systems of *arbitrary* finite dimension has been provided by J. L. and R. Brylinski \[arXiv:quant-ph/0108062, 2001\]; however, their proof relies upon a long argument using advanced mathematics. In contrast, our proof provides a simple *constructive* procedure which is close to *optimal* and experimentally practical \[C. M. Dawson and A. Gilchrist, online implementation of the procedure described herein (2002), http://www.physics.uq.edu.au/gqc/\].

A great deal of work has been done to determine what physical resources are capable of universal quantum computation. It is well known that certain gates on two-level quantum systems such as the controlled-not, are universal when assisted by arbitrary one-qubit gates Barenco et al. (1995). It has also been shown that *almost any* gate on two $`d`$-level quantum systems (*qudits*), together with its swapped version, is universal for quantum computation without the aid of one-qudit gates Lloyd (1995); Deutsch et al. (1995). However, this result does not explicitly specify which two-qudit gates are universal, requires the ability to apply the given gate in two different ways, and the resulting procedure is not practical, requiring large numbers of gates.

Recently, several authors have considered conditions for universality when only a single fixed multi-qudit interaction, together with one-qudit gates, is allowed Dodd et al. (2002); Dür et al. (2001); Wocjan et al. (2002); Bennett et al. (2001); Vidal and Cirac (2001); Nielsen et al. (2001). They have shown that any interaction that can create entanglement between any pair of qudits is universal for quantum computation. Theoretical schemes for quantum computation based on this have been found, but they are not of practical utility. In order to make the simulations exact the given interaction is modified by one-qubit gates which must be applied so that the period of evolution between them is infinitesimal. To simulate evolution for some non-infinitesimal time $`t`$ the error is controlled by concatenating a large number $`n`$ of periods of evolution for a small time $`t/n`$. Although some such schemes minimize the amount of time required to do the simulation Bennett et al. (2001); Vidal and Cirac (2001), the required number of one-qubit gates is enormous; an optimistic example of simulating a cnot to accuracy only $`10^3`$ requires approximately $`10^4`$ one-qubit gates Dodd et al. (2002). Thus, the one-qubit gates must be performed with rapidity and accuracy which are vastly more demanding than the standard requirements for quantum computation. We note, however, that Hammerer, Vidal, and Cirac Hammerer et al. (2002) have obtained a practical scheme for a restricted class of symmetric Hamiltonians with no self-energy.

In contrast, the model we consider does not allow an interaction to be interrupted by one-qubit gates at arbitrary times. We allow only a fixed entangling two-qubit *gate* $`U`$ and arbitrary one-qubit gates between applications of $`U`$. Our proof that any such gate is universal provides an explicit method Dawson and Gilchrist (2002) for implementing a cnot exactly, using a small number of one-qubit gates which is *fixed* for any given gate $`U`$. For the optimistic example mentioned above, this method requires only approximately $`10`$ one-qubit gates. This represents a saving of a factor of $`10^3`$; typical savings will be much greater. The only limit to the accuracy achieved in practice is due to the accuracy with which the required one-qubit gates are calculated. This limit is inherent in any procedure for computation, but because of the constant number of one-qubit gates required by our scheme, the induced errors will depend only in a constant way on these inaccuracies. Combined with the fact that the number of uses of $`U`$ is near-optimal, this suggests that our scheme will be of practical utility.

We begin the description of our construction with some convenient definitions:

* We say that a gate is *universal* if it can be used to perform universal quantum computation on two qubits when assisted by arbitrary one-qubit gates.
* Suppose $`U=(A_1B_1)V(A_2B_2)`$. Since we have the ability to do arbitrary one-qubit gates, being able to perform $`U`$ allows us to perform $`V`$, and vice versa. Whenever this is the case, we say that $`U`$ and $`V`$ are *equivalent* and write $`UV`$.
* A gate $`U`$ is *entangling* if it can create entanglement between two systems initially in a product state.
* Following Brylinski and Brylinski (2001), we define $`U`$ to be *primitive* if $`U`$ is a product of one-qubit gates or if $`U`$ is equivalent to the gate interchanging the two qubits (swap); otherwise $`U`$ is *imprimitive*. We will see that, for two qubits, the class of imprimitive gates is exactly the class of entangling gates.

We now prove the qubit case of the result in Brylinski and Brylinski (2001):

> A two-qubit gate $`U`$ is universal if and only if it is imprimitive, or, equivalently, if and only if it is entangling.

Proof: A brief summary of our proof is as follows: We use two non-trivial facts. The first is that cnot is universal Barenco et al. (1995). The second is the *canonical decomposition* Khaneja et al. (2001); Kraus and Cirac (2001) for any two-qubit gate $`U`$:

$$U=(A_1B_1)e^{i(\theta _xXX+\theta _yYY+\theta _zZZ)}(A_2B_2),$$
(1)
where $`X,Y,Z`$ are the Pauli sigma matrices, $`A_j,B_j`$ are one-qubit gates, and $`\frac{\pi }{4}<\theta _\alpha \frac{\pi }{4}`$ (see Kraus and Cirac (2001) for a simple proof). Both of these facts have proofs which are somewhat detailed but elementary and constructive. Our strategy is to show that any imprimitive gate $`U`$, together with one-qubit gates, can be used to implement $`W=e^{i\varphi ZZ}`$ where $`0<|\varphi |<\frac{\pi }{2}`$. We then show that $`W`$ can be used, together with one-qubit gates, to exactly implement cnot, which proves that $`W`$, and therefore $`U`$, is universal. Finally, since any universal gate is entangling, and any entangling gate is imprimitive, it follows that the class of entangling gates is exactly the class of imprimitive gates.

We define $`V=e^{i(\theta _xXX+\theta _yYY+\theta _zZZ)}U`$. First, note that primitive gates have either $`\theta _x=\theta _y=\theta _z=0`$ (corresponding to $`U`$ being a product of one-qubit gates), or $`\theta _x=\theta _y=\theta _z=\frac{\pi }{4}`$ (corresponding to $`U\text{swap}`$), so we need not consider these cases.

Suppose $`U`$ is imprimitive, in which case at least one of the $`\theta _\alpha `$ is non-zero. We will show that in all cases $`V`$, and hence $`U`$, may be used with one-qubit gates to implement a cnot and is therefore universal. In each case, we use $`V`$ to obtain a gate of the form $`W=e^{i\varphi ZZ}`$, $`0<|\varphi |<\frac{\pi }{2}`$. Note that we may assume $`|\theta _z||\theta _x||\theta _y|`$ since the $`\theta _\alpha `$ may be relabeled by conjugating $`V`$ by the primitive gates $`HH`$ and $`SS`$ where $`H=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& 1\end{array}\right]`$ and $`S=\left[\begin{array}{cc}1& 0\\ 0& i\end{array}\right]`$.

First, consider the two special cases where either one or two of $`\theta _x,\theta _y,\theta _z`$ are $`\frac{\pi }{4}`$ and the remainder are 0. Suppose that $`\theta _z=\frac{\pi }{4}`$ and $`\theta _y=\theta _x=0`$. Then $`V=e^{i\frac{\pi }{4}ZZ}`$ and is hence already of the required form. For the second special case, $`\theta _z=\theta _x=\frac{\pi }{4}`$ and $`\theta _y=0`$. Noting that $`V^8=I`$, and thus $`V^7=V^{}`$, we use the one-qubit gate $`e^{i\frac{\pi }{4}XI}`$ to obtain $`Ve^{i\frac{\pi }{4}XI}V^7=e^{i\frac{\pi }{4}VXIV^{}}=e^{i\frac{\pi }{4}YZ}e^{i\frac{\pi }{4}ZZ}`$, which is of the required form.

Secondly, consider the more general case, $`\theta _z\frac{\pi }{4}`$. Now

$$(IZ)V(IZ)V=e^{2i\theta _zZZ}=e^{i\varphi ZZ}=W$$
(2)
where $`0<|\varphi |<\frac{\pi }{2}`$, as required.

Simple algebra shows that $`W`$ is equivalent to a controlled rotation about the $`z`$-axis:

$`e^{i\varphi ZZ}`$ $`=`$ $`|00|e^{i\varphi Z}+|11|e^{i\varphi Z}`$ (3)
$``$ $`|00|I+|11|e^{2i|\varphi |Z}.`$
Note that, if necessary, we can obtain a positive exponent in the last line by conjugating by $`IX`$. We introduce the following notation for a controlled rotation about an arbitrary axis $`𝐧`$,

$$U_𝐧|00|I+|11|e^{i𝐧(X,Y,Z)}.$$
(4)
In particular, the controlled rotation (3) above is denoted $`U_{(0,0,2|\varphi |)}`$. Conjugation by one-qubit gates on the second qubit changes the *axis* of rotation but not the *angle* of rotation: Given $`𝐧^{}`$ such that $`|𝐧|=|𝐧^{}|`$, we can find a one-qubit gate $`A`$ such that $`(IA)U_𝐧(IA^{})=U_𝐧^{}`$. A product of two rotations $`U_𝐧`$ and $`U_𝐧^{}`$ is clearly another controlled rotation $`U_𝐦`$. Both the direction of $`𝐦`$ and its magnitude vary depending on $`𝐧`$ and $`𝐧^{}`$.

In order to implement a cnot, we need to use $`U_{(0,0,2|\varphi |)}`$ to obtain a total rotation $`U_{(0,0,\pi /2)}\text{cnot}`$. The first step is to use $`U_{(0,0,2|\varphi |)}`$ a number of times $`q=\frac{\pi /2}{2|\varphi |}`$. If $`\pi /2`$ is an exact multiple of $`2|\varphi |`$, then we are done. Otherwise, we must generate a gate to make up the difference; i.e. we need to obtain $`U_𝐦`$ with $`0<|𝐦|=\frac{\pi }{2}2q|\varphi |<2|\varphi |`$. To do this, we note that we can easily obtain the following controlled rotations: the zero rotation, $`U_{(0,0,0)}=U_{(0,0,2|\varphi |)}U_{(0,0,2|\varphi |)}`$, and $`U_{(0,0,4|\varphi |)}=U_{(0,0,2|\varphi |)}U_{(0,0,2|\varphi |)}`$. Choose $`𝐧`$ such that $`|𝐧|=2|\varphi |`$ in which case $`U_𝐧`$ is equivalent to $`U_{(0,0,2|\varphi |)}`$. The product $`U_{(0,0,2|\varphi |)}U_𝐧`$ gives another controlled rotation $`U_𝐦`$. $`|𝐦|`$ varies continuously as a function of $`𝐧`$ and so, by the Intermediate Value Theorem, it must pass through all the angles between 0 and $`4|\varphi |`$. As a consequence it is possible to choose $`𝐧`$ such that $`|𝐦|=\frac{\pi }{2}2q|\varphi |`$. For any given angle $`\varphi `$, $`𝐧`$ can be calculated numerically as the solution to a small set of equations (these can be found in exercise 4.15 in Nielsen and Chuang (2000), see also Preskill (1998)) endnote17 . Therefore, since $`U_{(0,0,|𝐦|)}U_𝐦`$, the final sequence is

$$U_{(0,0,\pi /2)}=U_{(0,0,2|\varphi |)}^q(IA)U_𝐦(IA^{}),$$
(5)
where $`A`$ is an appropriate one-qubit gate.

This completes our proof, since it demonstrates that the imprimitive gate $`U`$ together with one-qubit gates can be used to implement a cnot, which, in turn, can be used to perform universal quantum computation endnote18 $`\mathrm{}`$

It is easy to explore some examples of our procedure using Dawson and Gilchrist (2002). As an example, suppose we had a gate whose canonical decomposition yielded $`U=e^{i\frac{\pi }{6}ZZ}`$. Then $`A_1UA_2UA_3=\text{cnot}`$ where the gates $`A_j`$ are *primitive*:

$`A_1`$ $`=`$ $`\left[\begin{array}{cc}1& 0\\ 0& i\end{array}\right]\left(e^{i\gamma B}e^{i\beta Y}\right),A_2=I\left(e^{i\frac{\pi }{6}Z}e^{i\beta Y}\right),`$
$`A_3`$ $`=`$ $`I\left(e^{i\frac{\pi }{6}Z}e^{i\gamma B}\right),B=\left(\sqrt{\frac{3}{5}}Z\sqrt{\frac{2}{5}}Y\right),`$ (6)
where $`\beta =\frac{1}{2}\mathrm{cos}^1\frac{1}{3}`$ and $`\gamma =\frac{1}{2}\mathrm{cos}^1\frac{1}{\sqrt{6}}`$.

We conclude with a discussion of the optimality of the scheme for universal quantum computation described in our proof. We need to answer two questions: What is the “optimal” use of a given gate $`U`$? How optimal is our scheme? We define a scheme to be *optimal* if it uses $`U`$ the minimal number of times required to implement a cnot, with arbitrary one-qubit gates. We will see that, although our scheme is slightly non-optimal in usage of the two-qubit interaction, the number of one-qubit gates used by our scheme is many orders of magnitude smaller than the number required by the Hamiltonian simulation schemes described at the beginning of this Letter.

It follows from Hammerer et al. (2002) (section D1) that the number of uses of $`U`$ required to implement the cnot in *any* protocol using only $`U`$ and one-qubit gates is bounded below by $`\frac{\pi }{4\theta _{\mathrm{max}}}`$ where $`\theta _{\mathrm{max}}=\mathrm{max}\{|\theta _x|,|\theta _y|,|\theta _z|\}`$.

To compare with our scheme, we obtain an estimate of the number of uses of $`U`$ required to implement a cnot using our scheme. Recall that we use a controlled rotation $`U_{(0,0,2|\varphi |)}`$ $`q=\frac{\pi }{8\theta _{\mathrm{max}}}`$ times to implement a cnot. (Recall that we take $`\theta _z=\theta _{\mathrm{max}}`$.) Each controlled rotation uses $`U`$ twice in general (the special cases follow along similar lines with small changes in the number of uses of $`U`$), and the corrections at the end can require up to four uses of $`U`$. Thus the cnot uses $`U`$ $`2q+4`$ times. The ratio of the number of uses of $`U`$ required by our scheme to the minimum possible number is therefore less than $`1+16\theta _{\mathrm{max}}/\pi `$, which is between 1 (for small $`\theta _{\mathrm{max}}`$) and 5 (for large $`\theta _{\mathrm{max}}`$).

Returning to the comparison of our result with those on optimal simulation of Hamiltonians Bennett et al. (2001); Vidal and Cirac (2001), note that our fixed given gate $`U`$ can be thought of as a fixed given Hamiltonian which always evolves for the same amount of time between applications of one-qubit gates. Although our procedure is slightly non-optimal in the number of uses of $`U`$ for large $`\theta _{\mathrm{max}}`$, the pay-off in terms of error-control is enormous. In general, we require only approximately $`6q`$ one-qubit gates, and $`q`$ depends only on the gate $`U`$, not on the desired accuracy. In the example given above, only 4 one-qubit gates are required, compared to the unbounded number required to achieve arbitrary accuracy in the Hamiltonian simulation procedures.

We have given a simple algorithm Dawson and Gilchrist (2002) which provides a near-optimal way of using an *arbitrary* two-qubit entangling interaction to do universal quantum computation. Our scheme makes relatively undemanding requirements on local control, and thus is likely to be experimentally practical. Our scheme inverts the usual challenge facing the designer of a quantum computer: Instead of having to do delicate, system-specific theoretical calculations to engineer systems to perform gates such as the cnot, it will now be possible for physicists to experimentally determine the character of the available interaction and then apply our algorithm to use that interaction to do universal quantum computation.

###### Acknowledgements.

We thank Tamyka Bell, Carl Caves, Tim Ralph, and Rüdiger Schack for helpful comments and suggestions. A.W.H thanks the Centre for Quantum Computer Technology at the University of Queensland for its hospitality and acknowledges support from Army Research Office. A.G. was supported by The New Zealand Foundation for Research, Science and Technology.


text:
# Untitled Document

IF-UFRJ/Mar-02

String Cosmology in the Jackiw-Telteiboim Model with Quantum Corrections  111Work supported in part by Fundação Universitária José Bonifácio, FUJB.

M. Alvesa

Instituto de Física

Universidade Federal do Rio de Janeiro

Caixa Postal 68528 Rio de Janeiro 21970-970 Brazil

ABSTRACT

This note deals with the possibility of non-trivial cosmological solutions given by quantum corrections in the framework of the Jackiw-Telteiboim model to the bidimensional gravity. The resulting model shows that the quantum corrections transform, in some cases, the classical solution into a more interesting one with initial singularity.

PACS: 04.60.+n; 11.17.+y; 97.60.Lf

$`(a)`$msalves@if.ufrj.br

1-Introduction

It is widely recognized that two-dimensional models of gravity can give us a better understanding of the gravitational quantum effects. These models, derived from the string motivated effective action  or from the dimensional reduction of the Einstein equations  have a rich structure in spite of their relative simplicity. Gravitational collapse, black holes and quantum effects are examples of subjects whose description is rather complicated in four dimensional gravity while their lower-dimensional version turns to be more treatable, sometimes completely solved.

By two-dimensional gravity we mean a relativistic theory of the metric tensor in two-dimensions (1+1) space-time so, besides the above mentioned interpretations, we can realize some properties of the string theory by considering these models as a theory that describe the evolution of the string in terms of the two parameters, embedded in a higher dimension space-time .

In a series of previous works we show that the black hole solutions are modified when quantum corrections are considered in the JT and the CGHS models. In the first model, black hole solutions arise from the quantum correction even when we have no mass nor cosmological constant  and for the second theory, we have a modification of the expression of the Hawking radiation .

In this note we work out a bidimensional cosmology in the framework of the Jackiw-Teiltelboim theory to gravitation (JT) when quantum effects are considered via a generalized expression to the trace anomaly (we will clarify these points soon). The scale factors found show nontrivial behavior even in the absence of source of matter with cosmological interpretation and we note that these effects are dominant near the singularity. These are the main results of the work.

The paper is organized as follows: we present the JT theory and the cosmological model that we will use to derive the solutions. After that, we discuss the trace anomaly and the required generalized expression as well. In the following section, the modified model is presented and solved to a few cases of interest. General comments and remarks are in the last section.

2-The Jackiw-Teiltelboim Model and Bidimensional Cosmology

The well known difficulty of the bidimensional gravity due to the absence of dynamics of the Einstein-Cartan action in (1+1) space-time can be circumvent by using the JT model: We start directly from the equation of motion

$$R\mathrm{\Lambda }=T,$$
(1)
where $`R`$ is the scalar curvature, $`\mathrm{\Lambda }`$ is the 2d version of the cosmological constant and $`T=T_\mu ^\mu `$ the trace of energy-momentum tensor (TEM) of the matter source.

The solutions that we are interested on is given by the general Robertson-Walker metric line element,

$$ds^2=dt^2+a(t)^2dx^2$$
(2)
with a(t) being the scale factor.

A fundamental quantity here is the scalar curvature that, with the metric (2), is

$$R=2\frac{\ddot{a}(t)}{a(t)},$$
(3)
and contains the essential geometric informations in two dimensions.

Just to compare results, lets us solve the simplest two cases of (1) namely , the massless case, with $`\mathrm{\Lambda }=0`$ and $`\mathrm{\Lambda }0`$. The first one is the flat spacetime with

$$a(t)=At+B$$
(4)
and a de Sitter type solution with $`\mathrm{\Lambda }0`$,

$$a(t)=Ae^{\mathrm{\Lambda }t}+Be^{\mathrm{\Lambda }t},$$
(5)
with $`A`$ and $`B`$ constants that can be adjusted. In this case, to $`A=1`$ and $`B=0`$, there is a coincidence with the four dimensional solution, which is the common limiting case for $`t0`$ of all the models.

The next step is the introduction of the quantum corrections to investigate the possibility of modifications of the solutions (4) and (5), for instance. The most natural procedure in this direction is to consider the matter source, given for the right side of (1), quantized on a classical background space time, $`<T>=g_{\mu \nu }<T^{\mu \nu }>`$. The signal of this contribution is the trace anomaly: the fact that the expected value of the TEM of any massless field is non zero, in contrary to the classical value. However, as mentioned in , the renormalized value of the anomaly is just the scalar curvature $`R`$, and we conclude that this will leave (2) essentially the same, modulo a rescaling of the constants. Fortunately this is not the end of the history: as a matter of consistency, the semiclassical theory must to satisfy the so called Wald axioms . The first one is that the expected value of the TEM must be covariantly conserved and it is ensured by using a modified expression for the anomaly which introduces non-trivial contributions. In the next section we will discuss these points in detail.

3 -A Generalized Expression of the Trace Anomaly

The modified expression of the 2d trace anomaly is derived in a series of recent papers . The exact expressions are not the same in some of them, but these discrepancies are essentially in the numerical coefficients and will not affect both results and discussions here.

Using the notation adopted by us in , the above mentioned generalization of the anomaly is

$$<T>=R+^\mu A_\mu +A^\mu A_\mu $$
(6)
with

$$A_\mu =(g)^{1/4}_\mu (g)^{(1/4)}=\frac{1}{2}\frac{\dot{a}}{a}$$
(7)
using (2). Some of the new terms in (6) can be reabsorbed in the expression of $`<T>`$, resulting

$$<T>=\frac{\ddot{a}}{a}+\alpha (\frac{\dot{a}}{a})^2,$$
(8)
where $`\alpha `$ is to point us the quantum correction in the model and it is this term that gives us the non-trivial contribution in the JT model:

$$R\mathrm{\Lambda }=<T>=\frac{\ddot{a}}{a}+\alpha (\frac{\dot{a}}{a})^2,$$
(9)
or, using (3) and redefining again the constants,

$$\frac{\ddot{a}}{a}+\alpha (\frac{\dot{a}}{a})^2=\mathrm{\Lambda }.$$
(10)
This is our basic equation and it will be valid to all massless matter fields. In the following we will analyze the solutions of (10) and compare with those found in the classical cases (4) and (5).

4- The Solutions with Quantum Corrections

i) $`\mathrm{\Lambda }`$ =0

This is the modified version of the trivial case (4) and the solution is easily found to be, from (10),

$$a(t)=\left(A(1+\alpha )t+B(1+\alpha )\right)^{\frac{1}{1+\alpha }}$$
(11)
that is, for small $`\alpha `$,

$$a(t)=(At+B)+\alpha (At+B)(1ln(At+B))+O(\alpha ^2).$$
(12)
The corresponding curvature scalar is, using (3),

$$R=2\frac{A^2\alpha }{((At+B)(At+B+(At+B)(1ln(At+B))\alpha ))}$$
(13)
that, to small $`\alpha `$, results

$$R=2\alpha \frac{A^2}{(At+B)^2}$$
(14)
So, the anomaly, indicated by $`\alpha `$, adds a non-zero value to the curvature scalar. Moreover, the new term has a singularity at the (shifted) initial time $`t^{^{}}=t+\frac{B}{A}`$. Note that this is the expression for the four-dimensional Einstein-De Sitter model, the behavior of all big bang models, in (1+3), at the early stages ($`R1/t^2`$).

ii) $`\mathrm{\Lambda }`$ $`0`$

The solution with $`\mathrm{\Lambda }>0`$ can cast, without lost of generality, as

$$a(t)=A(1\alpha )\frac{e^{\left(\frac{\sqrt{G(1+\alpha )}t}{1+b}\right)}}{\sqrt{G(1+\alpha )}}.$$
(15)
This solution, however, does not introduce any modification to the behavior of the classical version (5): the curvature scalar is given by

$$R=\frac{G}{1+\alpha }=G^{^{}}$$
(16)
and makes just a rescaling of the cosmological constant.

The same does not occur when we consider the anti-DeSitter case to wit, $`\mathrm{\Lambda }<0`$ or

$$\frac{\ddot{a}}{a}+\alpha (\frac{\dot{a}}{a})^2=\mathrm{\Lambda }$$
(17)
with a solution as

$$a(t)=\left(\frac{Acos(G\sqrt{1+\alpha }t)}{G}\right)^{\frac{1}{1+\alpha }}.$$
(18)
Differently of the DeSitter solution (15), here the quantum correction gives a non trivial term to $`R`$ , that is, to small $`\alpha `$ (and $`A=1`$),

$$R=\mathrm{\Lambda }\alpha tan(Gt)^2.$$
(19)
A few comments is in order here: the quantum corrections does not affect the (2d) de Sitter solution (5) and the $`t0`$ behavior remains the same. In the Anti-de Sitter case, the solution remains oscillatory but now there is a divergence in $`R`$ to some values of $`t`$. Both solutions have the same limit at early times. The Einstein-de Sitter semiclassical case (12) turns out to be like the four dimensional one since now we have a mass scale arising from the trace anomaly.

5- Conclusion

In this paper , we worked out the semiclassical version to the JT model for 2d gravity for massless field as the matter source. We made use of the improved version of the trace anomaly otherwise the model would be transparent to the quantum nature of the fields.

The solutions found here show us that the quantum correction implies the possibility of non trivial cosmologies. The solution without cosmological constant and that with negative value are drastically transformed. The solution to the de Sitter case remains the same.

It is recognized that quantum effects must be relevant in situations with high values of the curvature. An example of this phenomenon is the Hawking-Bekestein radiation of the black-hole. The results derived in this note, in spite of the simplicity of the model, are in the same direction: in eqs (14) and (19) the contribution of the anomaly, signalized by $`\alpha `$, turns out to be dominant close to the singularity independently of the value of this parameter. It is worth to mention, that these results are derived from a semiclassical theory and must be taken as approximated, first order, ones since in these regions a full quantized theory would be necessary.

4- References

1. R.Jackiw, in Quantum Theory of Gravity, ed. S.Christensen (Adam Hilger, Bristol, 1984),p.403; C.Teiltelboim, ibid.,p.327. R.Mann, A.Shiekm and L.Tarasov, Nucl. Phys. B341,134 (1992).

2. C.G.Callan, S.B.Giddings and J.A.Strominger, Phys.Rev.D45,R1005(1992); J.A.Strominger, in Les Houches Lectures on Black Holes (1994), hep-th/9501071.

3. A.Polyakov, Mod.Phys.Lett.A2,89391987); Gauge Fields and Strings (Harwood, New York,NY,1987).

4. M.Alves, Class.Quantum Grav. 13,171(1996).

5. M.Alves, Int.J.Mod.Phys.D8,6,687(1999).

6. R.M.Wald, Commun. Math. Phys.,54,1(1977);N.D.Birrel and P.C.Davies, in Quantum Fields in Curved Spacetime (Cambridge University Press, Cambridge,1984) .

7. M.Alves and C.Farina, Class. Quantum Grav. 9, 1841 (1992); W.Kummer, H.Liebl and D.V.Vassilevich, Mod.Phys.Lett A 12 , 2683 (1997); S.Hawking and R.Boussos, hep-th/9705236; J.S.Dowker, hep-th/9802029; S.Ichinoise and S.Odintsov, hep-th/9802043.


text:
# Single Curve Collapse of the Price Impact Function for the New York Stock Exchange

## Abstract

We study the average price impact of a single trade executed in the NYSE. After appropriate averaging and rescaling, the data for the 1000 most highly capitalized stocks collapse onto a single function, giving average price shift as a function of trade size. This function increases as a power that is the order of $`1/2`$ for small volumes, but then increases more slowly for large volumes. We obtain similar results in each year from the period 1995 - 1998. We also find that small volume liquidity scales as a power of the stock capitalization.

Although supply and demand are perhaps the most fundamental concepts in economics, finding any general form for their behavior has proved to be elusive. Here we build on earlier studies of how trading affects prices Hausman92 ; Chan95 ; Hasbrouck96 ; Farmer96 ; Torre97 ; Kempf98 ; chordia ; Dufour2000 ; Rosenow01 ; Plerou01 . Our study adds to these previous efforts by using huge amounts of data, by looking at the short term response to a single trade, and by measuring the market activity in units of transactions rather than seconds, so that we can more naturally aggregate data for many different stocks. This allows us to find regularities in the response of prices to new orders that have previously been hidden by the extremely high noise levels that dominate financial prices. We study the 1000 largest stocks of the New York Stock Exchange, from (1995-1998), and find that, by appropriate averaging and rescaling, it is possible to collapse the price shift caused by a transaction onto a single curve. The price shift grows slowly with transaction size, growing very roughly as the 1/2 power in the small volume limit, and much more slowly in the large volume limit. The fact that such consistent results are seen across many stocks and for four different years suggests regularities in supply and demand. Orders can be viewed as expressions of changes in supply and demand, and the existence of a master price impact curve reflects the fact that fluctuations from the supply and demand equilibrium for a large number of financial assets, differing in economic sectors of activity and market capitalization, are governed by the same statistical rule.

The response of prices to orders is a key property of a market. If an attempt to buy or sell results in a small change in price, then the market is considered liquid; otherwise it is considered illiquid. One expects liquidity to depend on properties of the asset, such as trading volume, or for stocks, the market capitalization (the total worth of the company, i.e. the total number of shares times their price). The data collapse that we observe here gives a clearer understanding of how liquidity depends on volume and market capitalization.

The study is based on the Trades And Quotes (TAQ) database, which contains the prices for all transactions as well as price quotations (the best offers to buy and sell at a given price at any given time) for the US equity markets. We analyze data for the period 1995-1998 for the 1000 stocks with the largest market capitalization traded in the New York Stock Exchange. The analysis is based on roughly 113 million transactions and 173 million quotes.

Our goal is to understand how much the price changes on average in response to an order to buy or sell of a given size. Of course, in each trade there is both a buyer and a seller. Nonetheless, one often loosely refers to a trade as a “buy” or a “sell” depending on whether the initiator of the trade was buying or selling. By initiator we mean the agent who placed the more recent order. Buy orders tend to drive the price up, and sell orders tend to drive it down. It is this price impact that we are interested in.

Based on only transactions and quotes it is not possible to know with certainty whether trades are initiated by buyers or sellers. However, we can infer this indirectly using an algorithm developed by Lee and Ready Lee91 . This algorithm identifies the correct sign of trades by comparing the prices of transactions with recent quotes. The Lee and Ready algorithm is able to classify the sign of approximately $`85\%`$ of the trades of our database. An order by a single party may trigger transactions with multiple counterparts; from the TAQ database we can only see transactions. To cope with this, we lump together all transactions with the same timestamp and treat them as a single trade.

We study the shift in the midquote price caused by the most recent transaction. For each transaction of volume $`\omega `$ occurring at time $`t`$ we observe two cases: (i) When the next event is a quote revision, we compare the next quote to the previous (prevailing) quote, and compute the difference in the logarithm of the midquote price. Letting the logarithm of the midquote price be $`p(t)`$, we compute the price shift $`\mathrm{\Delta }p(t_i+1)=p(t_{i+1})p(t_i)`$, where $`t_i`$ is the time of the prevailing (previous) quote and $`t_{i+1}`$ is the time of the next quote following the transaction; (ii) When the next event is a new transaction we set the price shift $`\mathrm{\Delta }p(t_i)`$ to zero NoteA . We then investigate the average price shift as a function of the transaction size $`\omega `$ measured in dollars, doing this separately for buys and sells.

To investigate the average behavior we bin the data based on transaction size and compute the average price shift for the data in each bin. To put all stocks on roughly the same footing, we normalize the transaction size by dividing by its average value for each stock in each year. The results of doing this for two representative stocks are shown in figure 1.

For one of the highest cap stocks (General Electric) the average price impact increases roughly as $`\omega ^{0.6}`$ throughout almost the entire volume range . In contrast, for a mid-cap stock such as International Rectifier Corp. (IRF), for small $`\omega `$ ($`\omega <1`$) the price impact increases as $`\omega ^{0.5}`$, but for larger values of $`\omega `$ it increases roughly as $`\omega ^{0.2}`$. The behavior is roughly the same for both buy and sell trades.

To understand more systematically how this behavior varies with market capitalization, we group the 1000 stocks of our sample into 20 groups. The groups are ordered by market cap, and the number of stocks in each group is chosen to keep roughly the same number of transactions in each group. The groups are labeled with letters from A to T. The group size varies from the highest market cap group (T) with 9 stocks, to the least capitalized group (A) with 290 stocks Groups . We then bin each transaction based on size, choosing bin widths to maintain roughly the same number of transactions in each bin (18,000 in 1995, 22,000 in 1996, 33,000 in 1997 and 46,000 in 1998), and plot the average price impact vs. transaction size for each group. The results obtained for 1995 are shown in figure (2).

The price impact functions naturally stratify themselves from top to bottom in increasing order of market capitalization. The slope of each curve varies from roughly $`0.5`$ (for small transactions in higher cap stocks) to $`0.2`$ for larger transactions in lower cap stocks). When we repeat this for 1996, 1997 and 1998, we see similar results, except that the slopes are somewhat increasingly flatter, ranging roughly from $`0.4`$ to $`0.1`$ in 1998.

It is clear from these results that higher market cap stocks tend to have smaller price responses for the same normalized transaction size. Naively, one might have expected liquidity to be proportional to volume; the fact that the price impact for higher cap stocks is lower, even though we are normalizing the $`x`$-axis by average transaction size, says that larger cap stocks are even more liquid than one would expect. To gain a better understanding of this, we perform a best fit of the impact curves for small values of the normalized transaction size with the functional form $`\mathrm{\Delta }p=sign(\omega )|\omega |^\beta /\lambda `$. In figure (3) we plot the parameter liquidity parameter $`\lambda `$ as a function of the mean market capitalization of the group.

Surprisingly, for all four years the liquidity of each group increases as roughly $`C^{0.4}`$, where $`C`$ is the average market cap of each group (the individual values of the exponent are $`0.40`$, $`0.42`$, $`0.37`$, and $`0.37`$ for each year, respectively.)

We now make use of this apparent scaling to collapse the data of figure (2) onto a single curve. We rescale the $`x`$ and $`y`$ axes of each group according to the transformations

$$xx/C^\delta yyC^\gamma $$
(1)
We then search for the values of $`\delta `$ and $`\gamma `$ that do the best job of placing all the points on a single curve. To do this we divide the $`x`$ axis into bins, and find values that minimize the mean of the two dimensional variance $`ϵ=(\sigma _y/\mu _y)^2+(\sigma _x/\mu _x)^2`$, where $`\sigma `$ denotes the standard deviation and $`\mu `$ denotes the mean, and $`y`$ is the renormalized return and $`x`$ is the renormalized transaction size. In all investigated years there is a clear minimum for $`\delta \gamma 0.3`$ (to be precise $`\gamma =0.3\pm 0.05`$ for all years and $`\delta =0.3\pm 0.05`$ for 1995, 1997 and 1998 whereas $`\delta =0.4\pm 0.05`$ for 1996). The resulting rescaled price impact curves for buys in the investigated years are shown in Figure (4).

In all cases the collapse is quite good. The resulting master function spans three decades. It increases slower than a power law, and decreases more slowly in 1998 than in 1995. The data from 1996 and 1997 show similar behavior, with the slopes decreasing steadily from year to year.

This slow rate of increase of the price impact function shown here is surprising. Naive arguments predict that it should increase at least exponentially for positive $`\omega `$. In contrast, many previous empirical studies of price impact suggest concave behavior Hausman92 ; Farmer96 ; Torre97 ; Kempf98 ; Rosenow01 ; Plerou01 . However, this result has not been observed universally Maslov01 , and none of these studies have given a clear indication as to functional form. We have solved the problems by focusing on the most elementary response, which is the price impact following a single trade, by analyzing a huge amount of data, aggregating across different stocks and by scaling the data based on market capitalization.

The traditional approach in economics to deriving demand curves is to assume that agents maximize their utility under assumptions about cognitive ability and access to information. The standard interpretation of our results would be that the size dependence of price impact is due to differences in the information content of trades. In other words, some trades are based on more information than others, and this is known by market participants and factored into the price setting process. This hypothesis suffers from the problem that the information content of trades is difficult to assess a priori, making the hypothesis unfalsifiable. In contrast, an alternative approach is to study the mechanism for making transactions in detail, under the hypothesis that order placement and cancellation are largely random. This results in predictions of price impact that are qualitatively consistent with those seen here Daniels01 ; Smith02 . If these predictions are born out quantitatively it will be significant in demonstrating that it is important to model financial institutions in detail, and that for some purposes it is may be more useful to model human behavior as random rather than rational.

In summary, we have demonstrated a remarkable regularity in the immediate response of stock prices to fluctuations in supply or demand. In each year we are able to get a good data collapse with similar parameters. This scaling holds for stocks with trading volumes and market capitalizations that differ by 6 and 4 orders of magnitude respectively. The resulting data collapse is useful because it tells us how the liquidity of stocks varies with their market cap, increasing as powers of market cap, in a way that is not obvious a priori.