text:
# Fungible dynamics: there are only two types of entangling multiple-qubit interactions

## I Introduction

One of the main goals of quantum information science is to characterize the physical resources that are *universal* for quantum computation and simulation. Recently, the role of entangling quantum dynamics has been studied in depth, and it has been shown that a fixed two-body entangling Hamiltonian evolution acting on a system, plus the ability to intersperse local unitary operations, can be used to efficiently simulate any other two-body Hamiltonian and hence is universal for quantum computation (see, for example Dodd et al. (2002); Wocjan et al. (2002a); Bennett et al. (2002); Leung (2001); Dür et al. (2001); Nielsen et al. (2002); Wocjan et al. (2002b, c); Vidal and Cirac (2002a, b), and references therein.)

We extend this study to Hamiltonians containing interaction terms involving more than two qubits at a time. Using results from quantum control theory, we determine what dynamics can be simulated with an *arbitrary* fixed $`n`$-qubit Hamiltonian, and complete local control in the form of one-qubit unitary operations. In particular, we derive a simple criterion determining which Hamiltonians are universal given local unitary operations.

In contrast to two-body entangling Hamiltonians, which are always universal given local operations Dodd et al. (2002); Wocjan et al. (2002a); Bennett et al. (2002); Leung (2001); Dür et al. (2001); Nielsen et al. (2002); Wocjan et al. (2002b, c); Vidal and Cirac (2002a, b), we will see that not all many-body entangling Hamiltonians are universal, given arbitrary one-qubit operations as the only additional resource. This was previously noted for a specific example by Vidal and Cirac Vidal and Cirac (2002a). Thus, unlike two-body Hamiltonians, many-qubit entangling Hamiltonians are not all equivalent up to local operations. The situation is somewhat analogous to the study of multi-party entangled states, where it has been shown that there exist different types of entanglement, inequivalent up to local operations and classical communication Dür et al. (2000); Linden et al. (1999); Bennett et al. (2001) (LOCC). For example, it is now well known that the “GHZ” and “W” states are not equivalent up to LOCC.

Consider the following illustrative example. Suppose we are given a Hamiltonian acting on three qubits, $`H=XXI+IXX`$, where $`X`$ is the usual Pauli $`\sigma _x`$ operator. Then, if we can perform arbitrary local unitary operations on each of the qubits, it has been shown in Dodd et al. (2002); Wocjan et al. (2002a); Bennett et al. (2002); Leung (2001); Dür et al. (2001) that it is possible to simulate any other Hamiltonian interaction on three qubits, such as $`H^{}=XXX`$. We call such a Hamiltonian *universal*. On the other hand, given $`H^{}`$ and arbitrary local unitaries, it turns out that it is not possible to simulate $`H`$, and thus $`H^{}`$ is not universal. A proof of this is given in Vidal and Cirac (2002a); both these results will also follow from the general results given in this paper.

We address the problem of universality in full generality by giving a necessary and sufficient condition for a Hamiltonian to be universal. Our condition is dependent only on simple properties of the Hamiltonian’s decomposition into tensor products of Pauli operators. The proof of this condition is constructive, in the sense that it provides, in principle, an algorithm for using a universal Hamiltonian to simulate any other interaction. However, the techniques used in our construction are not especially practical, especially in the presence of noise, and it remains to be seen if more practical constructions are possible.

In addition to our criterion for universality, we also examine what can be done when a given Hamiltonian is not universal. In particular, we show that there always exists a simple encoding scheme to make these Hamiltonians universal.

Let us make a more precise statement of our results. Suppose we are given a Hamiltonian $`H`$ acting on $`n`$ qubits, which can be written uniquely in terms of its Pauli operator expansion

$$H=\underset{j_1,\mathrm{},j_n=0}{\overset{3}{}}h_{j_1\mathrm{}j_n}\sigma _{j_1}\mathrm{}\sigma _{j_n},$$
(1)
where the $`h_{j_1\mathrm{}j_n}`$ are real numbers and $`\sigma _1,\sigma _2,\sigma _3`$ are the Pauli sigma matrices $`X,Y,Z`$, respectively, with $`\sigma _0I`$ the identity. We say that a subset $`S`$ of the qubits is *coupled* by this Hamiltonian if there is a non-zero term in $`H`$ coupling those specific qubits.

When is $`H`$ universal? An obvious condition is that the set of qubits coupled by $`H`$ must be *connected*. That is, it should not be possible to partition the qubits into non-trivial sets, $`S`$ and $`\overline{S}`$, such that every term in the Pauli operator expansion couples either a subset of $`S`$ or a subset of $`\overline{S}`$. If this were the case then $`H`$ could not be used to generate entanglement between the qubits in $`S`$ and the qubits $`\overline{S}`$, and thus would not be universal. We say that a Hamiltonian connecting all the qubits in this way is an *entangling* Hamiltonian. Note that this definition may be restated in the language of graph theory: if qubits correspond to vertices in a hypergraph, and couplings between qubits correspond to hyper-edges, then the condition that the Hamiltonian is entangling corresponds to the condition that the hypergraph is connected.

With this background, our main results are easily stated. Our first result is that an entangling Hamiltonian and local unitaries is universal if and only if the Pauli operator expansion for the Hamiltonian contains a term coupling an even number of qubits. This result provides a simple, easily checkable criterion to determine whether or not a Hamiltonian is universal. Returning to our previous examples $`H=XXI+IXX`$ and $`H^{}=XXX`$, this criterion tells us that $`H`$ is universal when assisted by local unitaries, while $`H^{}`$ is not, in agreement with the earlier claims.

Our second result concerns what happens when the Pauli operator expansion contains only odd terms, and thus is not universal. We say that such a Hamiltonian is an *odd* entangling Hamiltonian. We will prove that an odd entangling Hamiltonian acting on $`n`$ qubits is capable of simulating any other odd Hamiltonian acting on those qubits. Thus, the odd entangling Hamiltonians are a fungible physical resource, since having any one is equivalent to having any other, up to local unitary operations. Furthermore, we show that an odd Hamiltonian, together with local unitaries, generates either the simple Lie algebra $`𝔰𝔬(2^n)`$ or $`𝔰𝔭(2^n)`$, depending on the number of qubits $`n`$ that are connected by the Hamiltonians.

Our third result also concerns odd Hamiltonians. We prove that, with appropriate encoding, an odd entangling Hamiltonian and local unitaries is universal on a set of $`n1`$ logical qubits. Thus, there is not too great a loss in space efficiency when one attempts to use such a Hamiltonian to simulate an arbitrary interaction.

Our results thus completely classify what can be achieved with an $`n`$-qubit Hamiltonian and local unitary operations. They demonstrate that there are essentially only two types of Hamiltonians up to local unitary operations: those whose Pauli operator expansion contains only odd parity terms, and those with at least one even term.

An important caveat to our results concerns *efficiency*. When we state that a set of interactions is *universal* on a set of qubits, we mean simply that those interactions can be used to simulate any other interaction, without any claim as to whether the simulation procedure is efficient, or otherwise. We will say such a set of interactions is *dynamically universal*. By contrast, in the context of quantum computing, a set of resources is said to be *universal for quantum computation* if it can be used to simulate a standard set of universal gates, such as the controlled-not and one-qubit unitary gates, *with an overhead that is at most polynomial in the number of qubits*.

Our results thus concern dynamic universality, and do not directly address the question of universal quantum computation. However, some general observations may be made about the efficiency of our constructions. When the number of qubits that are directly coupled by the Hamiltonian is bounded above by some constant $`k`$, then our simulation techniques for gates such as the controlled-not only incur an overhead polynomial in the total number of qubits. Thus, when the coupling size is bounded, our results give criteria not only for dynamic universality, but also for universal quantum computation. By contrast, when the number of qubits involved in couplings is unbounded, our simulation technique is not polynomial, and thus our results cannot be applied to deduce anything about universal quantum computation. Indeed, we conjecture that the two concepts of universality do not, in general, coincide.

For the remainder of this paper, when we speak of a set of couplings being universal, we mean dynamically universal, unless otherwise stated. The only exception is in Section VI, which contains the proof that when the terms in the Hamiltonian couple only a bounded number of qubits, our techniques can be made efficient.

What is the significance of our findings? It is tempting to conclude that the main significance is for the design of quantum computers. However, we do not believe our results are especially significant for such questions. Not only are our constructions impractical, but it is an empirical fact that most interactions occurring in nature are two-body interactions, and thus are adequately dealt with by earlier work.

We believe our results are interesting for two other, less obvious, reasons. The first is the intrinsic interest in obtaining general insights into quantum dynamics. The fact that, given local unitary control, there are only two different classes of Hamiltonian evolution, seems to us a significant insight into the complicated space of possible dynamical evolutions. It tells us that dynamics within each of these classes are *fungible* physical resources. In the case of two-party interactions this insight has led to the beginnings of a quantitative theory of the *strength* Nielsen et al. (2003); Childs et al. (2003) of dynamical operations, much as the theory of entanglement dilution and concentration Bennett et al. (1996a) led to the quantitative theory of entanglement Bennett et al. (1996b, c).

An interesting contrast is to the situation with state entanglement, where the multipartite structure is complex and only partially understood. The number of classes of states which are inequivalent under local operations and classical communication (LOCC) is enormous — for four-qubit states, there are already at least 9 inequivalent classes Verstraete et al. (2002). Our results thus demonstrate that there are no direct analogies between multiparty state entanglement and multiparty entangling dynamics — in fact, the situation is substantially simpler for dynamics than it is for states.

A second reason for interest is possible indirect applications. For example, although four-qubit interactions may not occur in nature, it is certainly the case that interactions involving two objects with four-dimensional state spaces may occur in nature. Such systems can naturally be mapped onto our problem by considering a single four-dimensional system as being, effectively, a system of two qubits. Constructions like this may make our results of interest, at least in principle, for realistic physical systems.

The paper is structured as follows. Section II provides background and definitions. Section III establishes a body of general techniques for simulating one Hamiltonian with another. These techniques are applied in Section IV to prove our first main result, the characterization of when a Hamiltonian is universal, assisted by one-qubit unitaries. Section V studies the non-universal case, proving that any odd entangling Hamiltonian may be used to simulate any other odd Hamiltonian. We then describe an encoded universality scheme that allows an odd entangling $`n`$-qubit Hamiltonian to act universally on $`n1`$ qubits, and provide a Lie-algebraic classification of this case. In Section VI we show that our techniques can be made efficient under certain conditions of bounded coupling size, and finally in Section VII we summarize our results.

## II Background and definitions

This section contains definitions and background material for the remainder of the paper. We begin with some notation and definitions, followed by a discussion of what it means to simulate one Hamiltonian with another, and finally we review some previous work on the universality of two-body Hamiltonians.

We now introduce some notational conventions. As stated in the introduction, an arbitrary Hamiltonian $`H`$ on $`n`$ qubits can be uniquely written in terms of Pauli operators via the Pauli operator expansion

$$H=\underset{j_1,\mathrm{},j_n=0}{\overset{3}{}}h_{j_1\mathrm{}j_n}\sigma _{j_1}\mathrm{}\sigma _{j_n},$$
(2)
where the $`h_{j_1\mathrm{}j_n}`$ are real numbers and $`\sigma _1,\sigma _2,\sigma _3`$ are the Pauli sigma matrices $`X,Y,Z`$, respectively, with $`\sigma _0I`$ the identity. Let the index $`\alpha `$ denote each different combination $`j_1\mathrm{}j_n`$ corresponding to non-zero terms in equation (2). So for each non-zero term in the Pauli expansion of $`H`$ we write $`H_\alpha =h_{j_1,\mathrm{},j_n}\sigma _{j_1}\mathrm{}\sigma _{j_n}`$ and thus $`H=_\alpha H_\alpha `$.

###### Definition 1.

Let $`C_\alpha `$ denote the set of all Pauli product Hamiltonians that couple the same set of qubits as $`H_\alpha =h_{j_1,\mathrm{},j_n}\sigma _{j_1}\mathrm{}\sigma _{j_n}`$, that is $`C_\alpha =\{\sigma _{k_1}\mathrm{}\sigma _{k_n}|k_i=0\text{iff }j_i=0\}`$. We call each set $`C_\alpha `$ a *coupling* set.

For example if $`H_\alpha =XIYY`$, then $`C_\alpha `$ is the set of all products of Paulis acting non-trivially on the same qubits, or $`\{XIXX,XIXY,\mathrm{},ZIZZ\}`$.

###### Definition 2.

The set $`S_\alpha `$ is the set of qubits coupled by $`H_\alpha `$, or, equivalently, all elements of $`C_\alpha `$.

In the example above $`S_\alpha =\{1,3,4\}`$. Note that different $`H_\alpha `$’s can give rise to the same $`C_\alpha `$ and $`S_\alpha `$. We will use the notation $`|S_\alpha |`$ to denote the number of qubits in the set $`S_\alpha `$.

Now, what does it mean to simulate one Hamiltonian with another? If we can approximately induce evolution according to a Hamiltonian $`H`$ on an arbitrary state $`|\psi `$ for an arbitrary time $`t`$ without actually using $`H`$, then we can simulate $`H`$, provided the approximation can be made arbitrarily good. This concept of simulation is motivated by quantum computation which uses a universal set of gates to simulate arbitrary unitary evolutions on a set of qubits.

Our approach to the question of whether a Hamiltonian is universal is to exhaustively build up the repertoire of different evolutions simulatable with the Hamiltonian, in such a way that it becomes clear whether or not the repertoire is a universal set of gates.

A first observation is that, given a term $`H_\alpha =h_{j_1\mathrm{}j_n}\sigma _{j_1}\mathrm{}\sigma _{j_n}`$ we can simulate $`xH_\alpha `$ for any real non-zero $`x`$ by adjusting the amount of time we evolve according to $`H_\alpha `$. Therefore, we can always simulate $`\stackrel{~}{H}_\alpha \pm \sigma _{j_1}\mathrm{}\sigma _{j_n}`$ with the sign given by the sign of $`h_{j_1\mathrm{}j_n}`$. If it is negative, then we can make it positive by conjugating $`\stackrel{~}{H}_\alpha `$ by a one-qubit unitary $`U`$ which anticommutes with it. Thus, we can always obtain $`\sigma _{j_1}\mathrm{}\sigma _{j_n}`$. For the remainder of the paper, we will always assume that terms like $`H_\alpha `$ have this form.

A simple, but important, observation is that, given the ability to evolve according to some Hamiltonian $`J`$ and to perform a unitary operation $`U`$ and its inverse $`U^{}`$, we can evolve according to

$$Ue^{iJt}U^{}=e^{iUJU^{}t}.$$
(3)
That is, we can simulate evolution according to the Hamiltonian $`J^{}=UJU^{}`$.

This result can be used to show, for example, that given a Pauli product Hamiltonian $`H_\alpha `$, we can simulate any other coupling in $`C_\alpha `$, simply by performing local changes of basis on each of the qubits to interchange the role of the $`x,y`$ and $`z`$ axes. This is done by conjugating by one of the following three rotations:

$$e^{i\frac{\pi }{4}X},e^{i\frac{\pi }{4}Y},e^{i\frac{\pi }{4}Z}.$$
(4)
Now, suppose we can evolve according to two Hamiltonians $`J_1`$ and $`J_2`$. Then for small times $`\mathrm{\Delta }`$ the following identity holds approximately:

$$e^{iJ_1\mathrm{\Delta }}e^{iJ_2\mathrm{\Delta }}e^{i(J_1+J_2)\mathrm{\Delta }}.$$
(5)
That is, we can simulate evolution according to the Hamiltonian $`J_1+J_2`$. Equation (5) is important because it tells us that if we are able to evolve a system according to a set of different Hamiltonians, then it is possible to simulate arbitrary linear combinations of elements of the set. We will treat this identity as though it is exact for the remainder of the paper. This is justified for small $`\mathrm{\Delta }`$. (See Dodd et al. (2002) for an analysis of the errors induced by this approximation, and the overhead required to reduce them). The above identities are used extensively in this paper, as they were in Dodd et al. (2002); Nielsen et al. (2002); Wocjan et al. (2002a, b, c); Bennett et al. (2002); Leung (2001); Vidal and Cirac (2002a, b); Dür et al. (2001).

It is also possible to simulate the commutator of two Hamiltonians Deutsch et al. (1995); Lloyd (1995), since

$$e^{iJ_1\mathrm{\Delta }}e^{iJ_2\mathrm{\Delta }}e^{iJ_1\mathrm{\Delta }}e^{iJ_2\mathrm{\Delta }}e^{i(i[J_1,J_2])\mathrm{\Delta }^2}$$
(6)
for small $`\mathrm{\Delta }`$. The error in this approximation is of order $`\mathrm{\Delta }^3`$, and can be made insignificant by choosing $`\mathrm{\Delta }`$ sufficiently small. This completes the basic set of tools that we use to build up our repertoire of simulatable Hamiltonians. The reason for this is that given a set of Hamiltonians $`L=\{J_1,\mathrm{},J_\zeta \}`$ the set of all simulatable Hamiltonians is given by the Lie algebra generated by the set $`L`$ Wilcox (1967) which can in turn be generated with linear combinations and $`i`$ times commutators of elements from $`L`$.

We can thus refine the central question of this paper to be: how does the structure of the given Hamiltonian $`H`$ determine the Lie algebra that can be generated by $`H`$ and arbitrary one-qubit evolutions? This is the question that we address in the remainder of this paper.

## III Methods

In the previous section we introduced some notation and basic tools. This section is concerned with building up more sophisticated simulation methods for the proofs of our main results, in later sections. In particular, there are two interesting simulation ideas — term isolation and commutator restriction — that we will examine in separate subsections. These ideas may be more fully described as follows:

* Term isolation: Given that we can simulate $`H`$ and perform arbitrary local unitaries, we can simulate an arbitrary term $`H_\alpha `$ in the expansion of $`H`$. Recall that we write $`H=_\alpha H_\alpha `$ where each $`H_\alpha `$ is a Pauli product Hamiltonian.
* Commutator restrictions: We examine the restrictions placed on the simulation of commutators of coupling terms in $`H`$.

### III.1 Term isolation

In this section, we show that given $`H`$ we can simulate each term $`H_\alpha `$ in $`H`$ using one-qubit unitaries and the composition identities given in equations (3) and (5). Thus the capacity to simulate $`H`$ is equivalent up to one-qubit unitaries to being able to simulate each $`H_\alpha `$.

For simplicity in the proof we now note that we can use one-qubit unitaries to simulate the Hamiltonian $`H^{(1)}=V_1\mathrm{}V_nHV_1^{}\mathrm{}V_n^{}`$ where the one-qubit unitaries $`V_1,\mathrm{},V_n`$ are chosen so that the term $`H_\alpha `$ has all $`X`$ and $`Y`$ operators in its expansion taken to $`Z`$ and all $`Z`$ and $`I`$ operators left alone. Thus in the Hamiltonian $`H^{(1)}`$ every $`\sigma _jI`$ in $`H_\alpha `$ is now $`Z`$. Let us denote this term in $`H^{(1)}`$ by $`H_{\alpha _Z}`$. This term, equivalent to $`H_\alpha `$, is the term that we wish to isolate. ¿From now on we use the convention that the superscript on a simulated Hamiltonian indicates a step in the algorithm, so $`H^{(j)}`$ would be the Hamiltonian simulated after the $`j^{\text{th}}`$ step. We will also use subscripts on non-trivial one-qubit operators to indicate which qubit they are acting on. For example, $`X`$ acting on the third qubit is written $`X_3IIXI\mathrm{}`$.

We now use $`H^{(1)}`$ to simulate $`H^{(2)}=Z_1H^{(1)}Z_1+H^{(1)}`$. Noting that $`ZZZ=Z`$, $`ZXZ=X`$ and $`ZYZ=Y`$, we see that the term $`H_{\alpha _Z}`$ is replaced in $`H^{(2)}`$ by $`2H_{\alpha _Z}`$, but any term in $`H^{(1)}`$ which has $`X`$ or $`Y`$ acting on the first qubit is cancelled out. We then simulate $`H^{(3)}=Z_2H^{(2)}Z_2+H^{(2)}`$ and so on until we obtain $`H^{(n+1)}=Z_nH^{(n)}Z_n+H^{(n)}`$. In this Hamiltonian, $`H_{\alpha _Z}`$ has been replaced by $`2^nH_{\alpha _Z}`$ and it consists only of terms containing $`Z`$ or $`I`$.

Now we wish to remove all interactions that act on qubits outside of $`S_\alpha `$. We do this by conjugating with $`X`$ on each of these qubits. If $`H_{\alpha _Z}`$ has an $`I`$ acting on the $`q^{\text{th}}`$ qubit, then we simulate $`H^{(n+2)}=X_qH^{(n+1)}X_q+H^{(n+1)}`$. This takes $`2^nH_{\alpha _Z}`$ to $`2^{n+1}H_{\alpha _Z}`$ and cancels any terms that have a $`Z`$ acting on the $`q^{\text{th}}`$ qubit. Let $`k|S_\alpha |`$. Since there are $`nk`$ qubits upon which $`H_{\alpha _Z}`$ doesn’t act, if we perform this style of simulation $`nk`$ times on different qubits, then we will have removed all interactions acting on qubits outside of $`S_\alpha `$. So the simulated Hamiltonian $`H^{(2nk+1)}`$ has interactions that only act on subsets of $`S_\alpha `$, and $`H_{\alpha _Z}`$ has become $`2^{2nk}H_{\alpha _Z}`$.

At this point, we wish to eliminate all remaining terms except $`H_{\alpha _Z}`$. Denote one of these undesirable terms by $`H_{\beta _Z}`$. We know that $`H_{\beta _Z}`$ couples a set of qubits $`S_\beta `$ that is strictly contained in $`S_\alpha `$. Thus, there must be some qubit $`q`$ which is in $`S_\alpha `$ and not in $`S_\beta `$. Noting that $`X_pX_q`$ commutes with $`Z_pZ_q`$ but anticommutes with $`Z_pI_q`$ for $`pq`$, we see that conjugating by $`X_pX_q`$ leaves $`H_{\alpha _Z}`$ invariant but takes $`H_{\beta _Z}`$ to $`H_{\beta _Z}`$ if we choose $`p`$ to be in $`S_\beta `$. Thus, if we simulate $`H^{(2nk+2)}=X_pX_qH^{(2nk+1)}X_pX_q+H^{(2nk+1)}`$ we eliminate $`H_{\beta _Z}`$. Iterating this procedure for every combination of $`p`$ and $`q`$ in $`S_\alpha `$, we are can eliminate every remaining undesirable term. There are $`\left(\begin{array}{c}k\\ 2\end{array}\right)`$ such possible combinations, so we finally obtain

$$H^{\left(2nk+1+\left(\begin{array}{c}k\\ 2\end{array}\right)\right)}=2^{2nk+\left(\begin{array}{c}k\\ 2\end{array}\right)}H_{\alpha _Z}.$$
(7)
Summarizing, we can isolate any term in $`H`$, and thus can simulate all elements of $`C_\alpha `$ for every $`H_\alpha `$ appearing in $`H`$, as well as all linear combinations of the elements of $`C_\alpha `$.

We note in passing a group-theoretic interpretation Viola et al. (1999); Zanardi (1999) of the term isolation procedure described above. A particular term $`H_\alpha `$ that we wish to isolate forms, along with the identity, an order two group $`𝒢`$ which is a subgroup of the full Pauli group $`𝒫`$ on our system. In particular $`H_\alpha `$ and $`I`$ are a representation of this subgroup $`𝒢`$. Denote the commutant of $`𝒢`$ in $`𝒫`$ (the set of all group elements in $`𝒫`$ which commute with $`𝒢`$) as $`𝒢^{}`$. If we map the elements of $`𝒢^{}`$ to Pauli operators, then we have a faithful representation of $`𝒢^{}`$. Let us denote the elements of this representation by $`D(g^{})`$, where $`g^{}𝒢`$. From Schur’s lemma it then follows that by averaging over all elements in this representation of $`𝒢^{}`$ we obtain only elements in the representation of $`𝒢`$ given by $`H_\alpha `$ and $`I`$:

$$\frac{1}{|𝒢^{}|}\underset{g^{}𝒢^{}}{}D(g^{})HD(g^{})^{}=aI+bH_\alpha $$
(8)
for some constants $`a`$ and $`b`$. Thus we can isolate a term by performing the appropriate group average over the commutant subgroup. In fact, since $`𝒢`$ is abelian, we can average over elements in $`𝒢^{}`$ which are not in $`𝒢`$. The term isolation procedure we described above is a concrete realization of this group average.

### III.2 Commutator restrictions

We now turn to the simulation of Hamiltonians using commutators, focusing on the possible forms of Hamiltonians simulated in this manner. The restrictions we obtain will be vital for the results of the next section.

Consider two different elements of the coupling set $`C_\alpha `$, $`H_\alpha `$ and $`H_\alpha ^{}`$. It is straightforward to verify from the commutation relations for the Pauli matrices that *the commutator $`[H_\alpha ,H_\alpha ^{}]`$ is non-zero if and only if there is an odd number of locations in $`S_\alpha `$ where the couplings $`H_\alpha `$ and $`H_\alpha ^{}`$ differ*. For example, consider the commutator of $`H_\alpha =XXX`$ and $`H_\alpha ^{}=YXY`$, both of which couple the same qubits:

$$\begin{array}{cc}\hfill i[H_\alpha ,H_\alpha ^{}]=& i(XYIXYYXIYX)\hfill \\ \hfill =& i(XYIXYXYIXY)=0.\hfill \end{array}$$
(9)
We see that in this case an even number — two — of the qubits are acted on by different Paulis, and so the commutator is zero. However if $`H_\alpha ^{}=YXX`$, the commutator is non-zero, indeed it is $`i[H_\alpha ,H_\alpha ^{}]=2ZII`$. We see from this example that given an initial coupling, we can generate terms which couple a different set of qubits.

Suppose now that $`C_\alpha `$ and $`C_\beta `$ are two different coupling sets. If they act on nonoverlapping sets of qubits, then any commutator between an element of $`C_\alpha `$ and an element of $`C_\beta `$ will always be zero. The commutators between two particular Hamiltonians $`H_\alpha `$ and $`H_\beta `$ depend only on their actions on qubits in the intersection of the sets $`S_\alpha `$ and $`S_\beta `$. Recall that the commutator of two terms is nonzero if there is an odd number of pairs that disagree. Thus $`H_\alpha `$ and $`H_\beta `$ must differ on an odd number of qubits from the intersection of $`S_\alpha `$ and $`S_\beta `$ in order to have a nonzero commutator. To summarize, a commutator of Hamiltonians from $`C_\alpha `$ and $`C_\beta `$ can generate a Hamiltonian coupling a set of qubits $`S_\gamma `$ precisely when $`S_\gamma `$ is in $`S_\alpha S_\beta `$, $`S_\gamma `$ contains an odd number of qubits from $`S_\alpha S_\beta `$, and $`S_\gamma `$ contains all the qubits from both $`S_\alpha `$ and $`S_\beta `$ which are not in $`S_\alpha S_\beta `$.

This becomes clearer with an example. Suppose $`H_\alpha =XXXX`$ and $`H_\beta =ZXXI`$. We find that the commutator is $`i[H_\alpha ,H_\beta ]=2YIIX`$. So we see that we have simulated a two-qubit entangling Hamiltonian, with a four- and a three-qubit coupling.

Combining all of our results about simulation so far, we see that given $`H=_\alpha H_\alpha `$ and arbitrary one-qubit unitaries, we can isolate any term $`H_\alpha `$. This can then be used to simulate any Hamiltonian coupling the same set of qubits. All of these terms can be combined in arbitrary linear combinations. Finally, we can use pairs of couplings $`C_\alpha `$ and $`C_\beta `$ to simulate a coupling on a different set of qubits $`S_\gamma `$ when the conditions stated above hold. The coupling $`C_\gamma `$ can be added to our repertoire of simulatable couplings, and can be used in turn to generate new couplings. How many different couplings are there? Since we assume that there is a finite number of qubits $`n`$ there are no more than $`2^n`$ different coupling sets, so the process of generating new couplings and adding them to the repertoire must terminate.

Once all of the simulatable couplings have been enumerated, the complete set of simulatable Hamiltonians consists of those whose Pauli operator expansion contains only terms that belong to one of the simulatable couplings. Of course, this procedure of exhaustive enumeration for determining which Hamiltonians are simulatable is not especially efficient or insightful. In the next section we provide a surprisingly simple procedure that enables us to determine when a Hamiltonian is universal.

## IV Structure of simulated couplings and dynamic universality

In the previous section we identified various simulation methods for Hamiltonians acting on qubits. In this section we use these methods to classify which many-qubit Hamiltonians are universal given local unitary operations, assuming throughout that the Hamiltonians under consideration are entangling. In order to find this classification we use properties of the Pauli operator expansion of a qubit Hamiltonian as given by equation (2). In particular, we will see that the parities of the couplings in this expansion determine whether or not $`H`$ is universal.

We know from subsection III.1 that given $`H=_\alpha H_\alpha `$ and local unitaries we can simulate any particular coupling term $`H_\alpha `$. If we had as our base set of operations each $`H_\alpha `$ in the expansion of $`H`$, and local unitaries, we could simulate $`H`$. Thus, having $`H`$ and local unitaries is equivalent to having $`\{H_\alpha \}`$ and local unitaries. In this section we focus on the simulating capacity of particular coupling terms $`H_\alpha `$ as this will be sufficient for analyzing the universality of $`H`$.

In section II we defined the coupling set $`C_\alpha `$ as being the complete set of Pauli product Hamiltonians that couple the set of qubits $`S_\alpha `$. We also noted that a single element of $`C_\alpha `$ and arbitrary one-qubit unitary control generates all elements of $`C_\alpha `$. In this section we will often use the coupling set $`C_\alpha `$ and any single element of that set interchangeably. For convenience, we write $`LU`$ to represent all local unitaries, that is, products of one-qubit unitaries. We also define the *parity* of a Pauli-product Hamiltonian $`H_\alpha `$ to be odd if it acts non-trivially on an odd number of qubits, or, equivalently, if $`S_\alpha `$ contains an odd number qubits. Otherwise, we say that $`H_\alpha `$ has even parity. We will see that dynamic universality of $`H`$ is completely determined by the parities of the terms in $`H`$.

For convenience, we restate a previous result that we will use frequently.

###### Theorem 1 (Bipartite Hamiltonian theorem Dodd et al. (2002); Wocjan et al. (2002a); Bennett et al. (2002); Leung (2001); Dür et al. (2001)).

Suppose $`H`$, acting on $`n`$ qubits, has only one- and two-qubit terms in its Pauli-product expansion, and that $`H`$ is entangling, i.e., all $`n`$ qubits are connected, possibly indirectly, by the terms in $`H`$. Then $`H`$, together with local unitaries, is universal for quantum computation on $`n`$ qubits.

We now prove a series of lemmas leading to our first new theorem.

###### Lemma 1.

If Hamiltonians $`H_\alpha `$ and $`H_\beta `$ act on sets of qubits $`S_\alpha `$ and $`S_\beta `$ such that $`S_\beta S_\alpha `$ and $`|S_\alpha |=|S_\beta |+1`$ then the set $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha `$.

Before giving the proof, consider the example $`H_\alpha =XXXX`$ and $`H_\beta =YXXI`$. Their commutator is

$$i[H_\alpha ,H_\beta ]=2ZIIX$$
(10)
which means that we can simulate arbitrary couplings between qubits 1 and 4. On the other hand, the commutator of $`XYXIC_\beta `$ with $`H_\alpha `$ generates a coupling between qubits 2 and 4. Similarly, we can couple qubits 3 and 4. Using Theorem 1 we see that $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on the set of qubits $`S_\alpha `$.

Proof: Assume without loss of generality that the qubits are numbered so that the first $`n1`$ of them are in $`S_\beta `$. Then $`X^nC_\alpha `$ and $`X^{n2}YIC_\beta `$, where $`Y`$ acts on the $`(n1)^{\text{th}}`$ qubit. We can simulate the commutator of these Hamiltonians

$$i[X^n,X^{n2}YI]=2I^{n2}ZX.$$
(11)
and thus we can couple the $`(n1)^{\text{th}}`$ and $`n`$th qubits. We can perform similar simulations where $`Y`$ acts on each qubit in the range 1 to $`n1`$. This generates two-qubit couplings connecting all of $`S_\alpha `$, and Theorem 1 implies that $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha `$. $`\mathrm{}`$

###### Lemma 2.

If a Hamiltonian $`H_\alpha `$ has even parity then $`\{H_\alpha ,LU\}`$ is universal on $`S_\alpha `$.

Proof: This result follows almost immediately from Lemma 1. Let $`n=|S_\alpha |`$. Notationally, it will be convenient to omit qubits outside the set $`S_\alpha `$ in the following; in all cases there is an implied identity action on the omitted qubits. Since $`X^nC_\alpha `$ and $`Y^{n1}XC_\alpha `$, we can simulate the commutator

$$i[X^n,Y^{n1}X]=2i(iZ)^{n1}I$$
(12)
as $`n1`$ is an odd number. Since $`2i(iZ)^{n1}I`$ acts on $`n1`$ qubits, Lemma 1 allows us to conclude that $`\{H_\alpha ,LU\}`$ is universal on $`S_\alpha `$. $`\mathrm{}`$

###### Corollary 1.

If $`H_\alpha `$ and $`H_\beta `$ both have even parity and $`S_\alpha S_\beta Ø`$, then $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha S_\beta `$.

Proof: Lemma 2 tells us that $`H_\alpha `$ is universal on $`S_\alpha `$ and $`H_\beta `$ is universal on $`S_\beta `$. Since they have a non-empty intersection, they can simulate a set of two-qubit Hamiltonians connecting every qubit in $`S_\alpha S_\beta `$ which implies that $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha S_\beta `$. $`\mathrm{}`$

###### Lemma 3.

If $`H_\alpha `$ has odd parity, $`n`$, $`H_\beta `$ has even parity, and $`S_\beta S_\alpha `$, then $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha `$.

Consider the following example. Let $`H_\alpha =X^5`$ and $`H_\beta =I^3YX`$. The commutator of these Hamiltonians is a four-qubit coupling, and therefore, by Lemma 1, they are universal on $`S_\alpha `$:

$$i[H_\alpha ,H_\beta ]=2XXXZI$$
(13)
Let’s now generalize this example to prove Lemma 3.

Proof: Using $`H_\alpha `$ and $`LU`$ we can simulate the Hamiltonian $`X^n`$, and by Lemma 2 $`H_\beta `$ and $`LU`$ can be used to simulate the Hamiltonian $`I^{n2}YX`$ (assuming we number the qubits so that the $`n^{\text{th}}`$ and $`(n1)^{\text{th}}`$ qubits are in $`S_\alpha `$). Then we can simulate the Hamiltonian

$$i[X^n,I^{n2}YX]=2X^{n2}ZI,$$
(14)
which acts on $`n1`$ qubits in $`S_\alpha `$. Therefore, Lemma 1 implies that $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha `$. $`\mathrm{}`$

###### Corollary 2.

If $`H_\alpha `$ has odd parity and we have a universal set of gates $`U_\beta `$ acting on a set of qubits $`S_\beta `$ such that $`S_\beta S_\alpha `$ and $`|S_\beta |>1`$, then the set $`\{H_\alpha ,U_\beta ,LU\}`$ is universal on $`S_\alpha `$.

A simple example of such a set of universal gates on three qubits is $`\{X^3,\text{CNOT}I,LU\}`$.

Proof: If we have a universal set of gates $`U_\beta `$ on $`S_\beta `$, then it is possible to simulate a unitary operator equivalent to a Hamiltonian evolution by $`H_\gamma `$ acting on an even number of qubits $`|S_\gamma |`$ with $`1<|S_\gamma ||S_\beta |`$. Then by Lemma 3 the corollary is true. $`\mathrm{}`$

###### Lemma 4.

If $`H_\alpha `$ has even parity, $`n`$, $`H_\beta `$ has odd parity, $`m`$, and $`S_\alpha S_\beta Ø`$, then $`\{H_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha S_\beta `$.

Proof: First, consider the case where $`|S_\alpha S_\beta |=1`$. Label the qubits so that $`S_\alpha `$ contains the first $`n`$ qubits from the left and $`S_\beta `$ contains the first $`m`$ qubits from the right. Thus $`X^nI^{m1}C_\alpha `$ and $`I^{n1}Y^mC_\beta `$. We can simulate the commutator

$$i[X^nI^{m1},I^{n1}Y^m]=2X^{n1}ZY^{m1}.$$
(15)
Now, this commutator acts on $`|S_\alpha S_\beta |=m+n1`$ qubits which is an even number, and therefore by Lemma 2 this Hamiltonian and $`LU`$ are universal on these qubits.

The case $`|S_\alpha S_\beta |>1`$ is even simpler to prove. Since $`n`$ is even, $`H_\alpha `$ is universal on $`S_\alpha `$ by Lemma 2. Now, when $`|S_\alpha S_\beta |>1`$ we have a universal set of gates acting on $`S_\alpha S_\beta `$, so Corollary 2 proves that we have a universal set on $`S_\beta `$, and therefore we have a universal set on $`S_\alpha S_\beta `$. $`\mathrm{}`$

###### Lemma 5.

If we have a universal set of gates $`U_\alpha `$ acting on $`S_\alpha `$ such that $`|S_\alpha |2`$, and $`H_\beta `$ acting on $`S_\beta `$ such that $`S_\alpha S_\beta Ø`$, then $`\{U_\alpha ,H_\beta ,LU\}`$ is universal on $`S_\alpha S_\beta `$.

Proof: The proof follows simply by considering the four possible parity combinations for $`|S_\alpha |`$ and $`|S_\beta |`$:

* Case: $`|S_\alpha |`$ even, $`|S_\beta |`$ odd. The result follows from Lemma 4.
* Case: $`|S_\alpha |`$ even, $`|S_\beta |`$ even. The result follows from Corollary 1.
* Case: $`|S_\alpha |`$ odd, $`|S_\beta |`$ even. The result follows from Lemma 4, with the roles of $`\alpha `$ and $`\beta `$ interchanged.
* Case: $`|S_\alpha |`$ odd, $`|S_\beta |`$ odd. Pick an even parity subset $`S_{\mathrm{ev}}`$ of $`S_\alpha `$ which has a non-trivial overlap with $`S_\beta `$. Since we have universality on $`S_\alpha `$ we must also have universality on $`S_{\mathrm{ev}}`$. Lemma 4 therefore implies universality on $`S_{\mathrm{ev}}S_\beta `$. Universality on $`S_\alpha S_\beta `$ now follows from Theorem 1. $`\mathrm{}`$

Lemma 5 gives us a composition rule for determining whether or not a Hamiltonian is universal on a given set of qubits. It tells us that if we have a set qubits coupled by even-parity coupling terms (and thus a universal set of gates on the set), then any other qubits that they are connected to, even indirectly, will also have a universal set defined on them. We will see from the following lemma that this is the only way a universal set of gates can be derived.

###### Lemma 6.

If $`H_\alpha `$ and $`H_\beta `$ both have odd parity, then their commutator $`H_\gamma =i[H_\alpha ,H_\beta ]`$ is either $`0`$ or it has odd parity.

Proof: If $`S_\alpha S_\beta =Ø`$ then $`i[H_\alpha ,H_\beta ]=0`$, and the lemma is trivially true. In the case where $`S_\alpha S_\beta Ø`$ let $`u=|S_\alpha S_\beta |`$. Now, $`H_\gamma 0`$ only when $`|S_\gamma (S_\alpha S_\beta )|=d`$ is odd. By definition we find that $`|S_\gamma |=|S_\alpha |+|S_\beta |2u+d`$. Since $`|S_\alpha |+|S_\beta |`$ and $`2u`$ are even, but $`d`$ is odd, $`|S_\gamma |`$ must be odd for any non-zero $`H_\gamma `$. $`\mathrm{}`$

The conclusions of these lemmas can be succinctly expressed in the following theorem.

###### Theorem 2.

An entangling Hamiltonian acting on $`n`$ qubits, together with local unitary operations, is dynamically universal if and only if the Pauli operator expansion of the Hamiltonian contains a term with an even number of entries.

Proof: From Lemma 6 we know that an entangling Hamiltonian whose Pauli operator expansion contains only odd-parity terms, together with local unitaries, can only generate other odd-parity Hamiltonians, which shows that it is not universal. Conversely, from Lemmas 2 and 6, we see immediately that an entangling Hamiltonian with at least one even-parity term is universal. $`\mathrm{}`$

We now know that in order for a general $`n`$-qubit Hamiltonian to be universal when aided by one-qubit unitaries, it must fulfill two conditions. The first condition is that the Hamiltonian must be entangling, in the sense explained in the introduction, i.e., all $`n`$ qubits must be connected, either directly or indirectly, by coupling terms in the Hamiltonian. The second condition is that at least one of the coupling terms must have even parity. Thus, our result reduces the problem of determining when a Hamiltonian is universal to that of counting the parity of terms in its Pauli operator expansion.

Let’s look at a couple of examples. It was suggested in the preprint version of Dodd et al. (2002) (but not the published version) that it might be possible to construct many-body Hamiltonians which are not universal by using results from the theory of entanglement. For example, the GHZ state $`|GHZ=(|000+|111)/\sqrt{2}`$ and $`W`$-state $`(|001+|010+|100)/\sqrt{3}`$ are distinct types of entanglement which cannot be interconverted Dür et al. (2000), even stochastically, by local operations and classical communication. This led Dodd et al. (2002) to conjecture that Hamiltonians such as $`H_{GHZ}=|GHZGHZ|`$ and $`H_{GHZ^{}}=|GHZ000|+|000GHZ|`$ are not universal, when assisted by local unitaries. This conjecture turns out to be incorrect. Expanding in the Pauli basis and omitting $``$ for brevity, we obtain:

$`H_{GHZ}`$ $``$ $`III+ZZI+ZIZ+IZZXYY`$ (16)
$`YXYYYX`$
$`H_{GHZ^{}}`$ $``$ $`III+ZII+IZI+IIZ+ZZI`$ (17)
$`+ZIZ+IZZ+ZZZXXX.`$
In both cases, we simply check that each qubit is coupled by one of the two- or three-qubit terms, so the Hamiltonian is entangling, and note that there are terms with even parity, so by Theorem 2 both these Hamiltonians are universal when assisted by local unitaries.

## V Hamiltonians with all-odd parity

In the previous section we showed that the only non-universal entangling Hamiltonians are the odd Hamiltonians, i.e., those whose couplings all act on an odd number of qubits. In this section we study what dynamical operations can be achieved using such Hamiltonians, together with local unitary operations. We prove two main results.

The first result is that an odd entangling Hamiltonian can be used to simulate any other odd Hamiltonian on the system of $`n`$ qubits. This result, in combination with the results of the previous section, shows that there are essentially only two types of entangling Hamiltonian on $`n`$ qubits: Hamiltonians that are odd, and those that are not. Within these two classes all the Hamiltonians are essentially inter-convertible, in the sense that any one can be used to simulate the other. Furthermore, the entangling Hamiltonians that are not odd are intrinsically more powerful than the odd Hamiltonians, since they can be used to simulate any odd Hamiltonian, but not vice versa.

The second result is to show that odd Hamiltonians can be made universal, by using an appropriate *logical basis* of qubits for our system, similar to the ideas used in quantum error-correction. In particular, we show that such an interaction on $`n`$ qubits is universal on a set of $`n1`$ logical qubits. In fact, we will see that the encoding is as simple as it could be: each of the $`n1`$ logical qubits corresponds directly to one of the original $`n`$ qubits, while the single qubit left over is not used.

To obtain our results we first need a simple lemma allowing us to use an odd Hamiltonian coupling a set of qubits to generate odd Hamiltonians acting on a subset of those qubits.

###### Lemma 7.

If $`H_\alpha `$ has odd parity then we can simulate any other odd-parity Hamiltonian $`H_\beta `$ provided $`S_\beta S_\alpha `$.

Proof: Let $`|S_\alpha |2m+1`$. We prove this lemma using induction on $`m`$. The lemma is trivially true for the case $`m=1`$ (that is, $`|S_\alpha |=3`$). Now, we make the inductive assumption that the lemma holds for the $`m^{\text{th}}`$ case and prove that it holds for the $`(m+1)^{\text{th}}`$ case. Given $`H_\alpha ^{}`$ acting on a set of $`|S_\alpha ^{}|=2m+3`$ qubits, we need only show that we can simulate a Hamiltonian acting on any subset of $`S_\alpha ^{}`$ containing $`2m+1`$ qubits. By assumption, we can simulate the $`(2m+3)`$-qubit Hamiltonians $`X^{2m+3}`$ and $`X^2Y^{2m+1}`$ and thus their commutator

$$i[X^{2m+3},X^2Y^{2m+1}]=2iII(iZ)^{2m+1}.$$
(18)
Therefore we can simulate a Hamiltonian acting on the final $`2m+1`$ qubits of $`S_\alpha `$. Similarly, we can simulate a Hamiltonian acting on any subset of $`S_\alpha `$ containing $`2m+1`$ qubits, which proves the inductive hypothesis and thus the lemma. $`\mathrm{}`$

It turns out that both the main results of this section are corollaries of this lemma and a second result that is motivated by the following example. Suppose we have the ability to simulate the odd Hamiltonian $`H=ZZZII+IIZZZ`$ (where we have omitted both subscripts and tensor products). We already know that we can therefore simulate $`ZZZII`$ and $`IIZZZ`$ separately. Suppose further that we wish to simulate another odd Hamiltonian, $`ZIIZZ`$. We can see that this is possible, using our intuition about non-odd Hamiltonians, by “isolating” one of the qubits, say the fifth qubit, and considering the Hamiltonians that we can simulate on the first four qubits. So, let’s alter our example and give ourselves the ability to to perform $`ZZZI`$ and $`IIZZ`$ on the first four qubits, and we will attempt to simulate $`ZIIZ`$. Notice that now we have an odd and an even term that connect the first four qubits, so by Theorem 2, there must be a sequence of commutators and linear combinations that allow us to simulate $`ZIIZ`$. Here is such a sequence, where in each step we generate a new coupling to add to our set of allowed couplings:

$$\begin{array}{cc}\hfill i[ZZYI,IIXZ]& =2ZZZZ,\hfill \\ \hfill i[XZXX,YZYY]& =2ZIZZ,\hfill \\ \hfill i[ZIZY,IIZX]& =2ZIIZ.\hfill \end{array}$$
(19)
Now, if we consider the original problem on five qubits, we see that the odd parity restriction shows that this procedure generates the desired coupling $`ZIIZZ`$:

$$\begin{array}{cc}\hfill i[ZZYII,IIXZZ]& =2ZZZZZ,\hfill \\ \hfill i[XZXXZ,YZYYZ]& =2ZIZZI,\hfill \\ \hfill i[ZIZYI,IIZXZ]& =2ZIIZZ.\hfill \end{array}$$
(20)
In a similar vein, suppose that we wish to simulate an even-parity coupling $`ZIIZI`$. We know that this is not possible directly (otherwise $`H`$ would be dynamically universal), but it is possible using a very simple encoding. If we place the fifth qubit in the $`Z`$-eigenstate $`|0`$, then our procedure above for simulating $`ZIIZZ`$ allows us to simulate $`ZIIZ`$ on the first four qubits. Thus, $`H`$ is dynamically universal on the first four qubits.

Our main results of this section generalize these two examples. Both examples rely crucially on the fact that there was a qubit that could be *isolated*, that is, acted on by only a single member of the set of couplings that we used to do our simulation. For example, suppose we tried to use the same approach to show that $`H`$ can simulate $`ZIIZ`$ on four of the five qubits by placing the third qubit in the state $`|0`$. Then the two couplings that we have at our disposal on the remaining four qubits are $`ZZII`$ and $`IIZZ`$, which do not connect the four qubits, and thus cannot be universal on them. We formalize this intuition in the following lemma.

###### Lemma 8.

Let $`H=H_\alpha `$ be an odd entangling $`n`$-qubit Hamiltonian, and $`=\{H_\alpha \}`$ be the set of all terms in $`H`$. Then there exists a set $``$ that (a) connects all $`n`$ qubits in such a way that (b) at least one of the qubits is only acted on by a single element of $``$. We call such a qubit an *isolated qubit*, and $``$ an *isolating set* for that qubit.

Proof: We prove this lemma by giving a constructive procedure to generate an appropriate set $``$. For convenience, define $`n_\alpha |S_\alpha |`$ for all $`\alpha `$.

1. Choose a term $`H_1`$ from the set $``$. Without loss of generality, we may number the qubits so that it acts on the first $`n_1`$ qubits. Add $`H_1`$ to the set $``$.
2. Search for a second term in the set $``$ that overlaps with $`H_1`$ and also acts on at least one qubit outside of $`S_1`$. If there is no such term, then $`H_1`$ must couple all of the qubits, in which case $`=\{H_1\}`$ satisfies the conditions above and we are done.
3. Otherwise, choose such a term and call it $`H_2^{}`$. Define $`n_{S_1S_2^{}}`$ to be the number of qubits in $`S_1S_2^{}`$. Without loss of generality, we may assume that these qubits are strung out in a line, with the $`n_1`$ left-most qubits in $`S_1`$ and the $`n_2^{}`$ right-most qubits in $`S_2^{}`$, and the $`n_{S_1S_2^{}}`$ overlapping qubits in the middle.
4. If $`n_{S_1S_2^{}}`$ is odd, then use $`H_2^{}`$ to simulate a Hamiltonian $`H_2`$ that acts on qubits $`n_1,\mathrm{},n_1+n_2^{}n_{S_1S_2^{}}`$ (where we number from the left, starting at 1). $`H_2`$ acts on the right-most $`n_2n_2^{}n_{S_1S_2^{}}+1`$ qubits, overlapping with $`H_1`$ on just a single qubit (the $`n_1`$th qubit). This is possible since $`n_2`$ is odd and $`S_2S_2^{}`$, satisfying the conditions of Lemma 7. Add $`H_2`$ to $``$.
5. On the other hand, if $`n_{S_1S_2^{}}`$ is even, then we use $`H_2^{}`$ to simulate a Hamiltonian $`H_2`$ that acts on qubits $`n_11,\mathrm{},n_1+n_2^{}n_{S_1S_2^{}}`$. This $`H_2`$ acts on the right-most $`n_2n_2^{}n_{S_1S_2^{}}+2`$ qubits, overlapping with $`H_1`$ on just two qubits, in positions $`n_11`$ and $`n_1`$. Again, $`n_2`$ is odd and $`S_2S_2^{}`$, satisfying the conditions of Lemma 7. Add $`H_2`$ to $``$.
6. Now, if there are no other terms that overlap $`H_2`$, then the right-most qubit in $`S_2`$ must be isolated since $`H_2`$ acts on at least three qubits, and overlaps with $`H_1`$ on at most two. If we then add the remaining Hamiltonians from $``$ (i.e., all except for $`H_1`$ and $`H_2^{}`$) to $``$, then $``$ must couple all $`n`$ qubits and contain an isolated qubit, satisfying the conditions above, and so we are done.
7. Otherwise, repeat steps 2 to 5 to generate a Hamiltonian $`H_3`$ that overlaps only with $`H_2`$ on one or two qubits, and add it to $``$. Repeat this process, adding a Hamiltonian to $``$ each time, until it becomes impossible to find a term that both overlaps with the previous term and acts on at least one more qubit than it. When the process terminates (which must happen eventually since there is only a finite number of qubits), the last term that was added must contain an isolated qubit. If $``$ connects all $`n`$ qubits then we are done, otherwise add the remaining Hamiltonians from $``$ to $``$ to complete the construction.

$`\mathrm{}`$

Using this lemma, we can prove our two main results.

###### Theorem 3.

Let $`H`$ be an odd $`n`$-qubit entangling Hamiltonian. Then $`H`$ and $`LU`$ can simulate any odd Hamiltonian on the $`n`$ qubits.

Proof: Let $``$ be an isolating set for a qubit, which, without loss of generality, we may choose to be the $`n^{\text{th}}`$ qubit. Suppose we consider the set of couplings $`^{}`$ on the first $`n1`$ qubits that arises by simply taking the couplings in $``$, and omitting the Pauli acting on the final qubit. Then by construction of $``$ we see that this set (a) connects the first $`n1`$ qubits, and (b) contains an element that acts on an even number of these qubits, corresponding to the element of $``$ that couples to the isolated qubit. By Theorem 2 it follows that $`^{}`$, together with local unitaries, is universal on the first $`n1`$ qubits.

Lifting back up to the full set of $`n`$ qubits, we see that $``$ must generate the set of all odd couplings on the $`n`$ qubits. To see this a little more explicitly, suppose that we wish to generate an odd coupling $`\sigma `$. Let $`\sigma ^{}`$ be the corresponding coupling on the first $`n1`$ qubits. By an appropriate sequence of commutators of elements of $`^{}`$ we can generate $`\sigma ^{}`$. The corresponding sequence of commutators in $``$ must generate $`\sigma `$, up to possible relabeling on the final qubit, which can be accomplished via appropriate local unitaries. $`\mathrm{}`$

###### Theorem 4.

Let $`H`$ be an odd $`n`$-qubit entangling Hamiltonian. Then $`H`$ and $`LU`$ are universal on a set of $`n1`$ logical qubits.

Before proving this theorem, let’s consider another example. Consider the Hamiltonian $`H_\alpha =ZZZ`$. We know from the previous section that this Hamiltonian and local unitaries do not form a universal set of operations on three qubits. However, if we prepare the third qubit in the $`|0`$ eigenstate of $`Z`$ at the beginning of the procedure, then any succession of evolutions of $`H_\alpha `$ and local unitaries acting only on the first two qubits will leave the third qubit invariant throughout the evolution. So if, for instance, we trace over the third qubit we find that the reduced system evolves according to $`ZZ`$. We know that this Hamiltonian is universal on the reduced system, so in effect we have a universal set of gates on the first two qubits. Essential to this example is our ability to identify a qubit that can be prepared in a local eigenstate of the Hamiltonian that entangles the other qubits.

Proof: The proof is simply to number the qubits $`1,\mathrm{},n`$, and to prepare the $`n^{\text{th}}`$ qubit in a fixed state $`|0`$. Suppose now that we wish to simulate an arbitrary Pauli $`\sigma `$ acting on the first $`n1`$ qubits. If $`\sigma `$ has odd parity, then we can use the results of Theorem 3 to simulate $`\sigma `$ directly. If $`\sigma `$ has even parity then we use the results of Theorem 3 to simulate $`\sigma Z`$, which leaves the state of the final qubit unchanged, and evolves the first $`n1`$ qubits according to the Hamiltonian $`\sigma `$. Thus, we can use this construction to simulate any interaction on the first $`n1`$ qubits. $`\mathrm{}`$

We now understand that odd $`n`$-qubit Hamiltonians, in contrast to the non-odd Hamiltonians, do not generate the algebra $`𝔰𝔲(2^n)`$. What algebra do they generate?<sup>1</sup><sup>1</sup>1This question was originally posed to us by Greg Kuperberg. It turns out that the answer depends on whether $`n`$ is odd or even.

To state and prove our results, it is helpful to be a little more precise about the various Lie algebras we are considering. We define $`𝔤`$ to be the real Lie algebra generated by odd parity Paulis acting on $`n`$ qubits. More precisely, $`𝔤`$ is a real vector space whose basis elements are of the form $`i\sigma `$, where $`\sigma `$ is an odd parity Pauli. We have shown that this is the relevant Lie algebra associated with an entangling Hamiltonian on $`n`$ qubits, plus one-qubit unitaries. The following theorem relates $`𝔤`$ to the standard classification of Lie algebras:

###### Theorem 5.

If $`n`$ is even, then $`𝔤`$ is isomorphic to $`𝔰𝔬(2^n)`$. If $`n`$ is odd, then $`𝔤`$ is isomorphic to $`𝔰𝔭(2^n)`$. Furthermore the representation of $`𝔤`$ provided by tensor products of odd parity Paulis on $`n`$ qubits is the fundamental (defining) representation of these Lie algebras.

Amusingly, the $`n=2`$ case of this theorem is a well-known result from Lie theory, the isomorphism between $`𝔰𝔬(4)`$ and $`𝔰𝔲(2)𝔰𝔲(2)`$. This result has received wide use in quantum information theory in a different guise — it is just the fact that local (special) unitary operations on two qubits correspond to real orthogonal transformations in the so-called “magic basis”.

Proof: We consider the $`n`$ even case first. Let us define an operation $`f(\sigma )(1)^{\mathrm{wt}(\sigma )}\sigma `$ on Pauli matrices, where $`\mathrm{wt}(\sigma )`$ is the weight of $`\sigma `$. This operation can be extended by linearity to all matrices. Observe that:

$`f(A)=Y^nA^TY^n.`$ (21)
Then the Lie algebra $`𝔤`$ consists of all matrices $`A`$ such that:

$`f(A)=A,\mathrm{and}A^{}=A.`$ (22)
The Lie algebra $`𝔰𝔬(2^n)`$ can be defined similarly. Recall that the defining representation of the Lie algebra $`𝔰𝔬(2^n)`$ consists of $`2^n\times 2^n`$ matrices $`B`$ which satisfy Georgi (1999); Cornwell (1997)

$$B^T=B,\mathrm{and}B^{}=B,$$
(23)
where $`T`$ denotes the transpose operation.

We aim to find a unitary $`U`$ such that $`B`$ satisfies Eq. (23) if and only if $`A=UBU^{}`$ satisfies Eq. (22). It is easy to see that for any $`U`$, $`A^{}=A`$ if and only if $`B^{}=B`$, so we need only find a $`U`$ such that $`f(A)=A`$ if and only if $`B^T=B`$. Straightforward algebraic manipulation shows that $`U=(IiY^n)/\sqrt{2}`$ satisfies this requirement.

The $`n`$ odd case is very similar. The defining representation of the Lie algebra $`𝔰𝔭\left(2^n\right)`$ consists of $`2^n\times 2^n`$ matrices which satisfy Georgi (1999); Cornwell (1997)

$$J^{}B^TJ=B,\mathrm{and}B^{}=B,$$
(24)
where $`J=Y_1I`$ is the Pauli $`Y`$ acting on the first qubit alone. Setting $`U=I(IiY^{n1})/\sqrt{2}`$, we see that Eq. (24) is equivalent to Eq. (22) if we set $`A=UBU^{}`$. $`\mathrm{}`$

An interesting consequence of Theorem 5 occurs for odd parity Paulis acting on an odd number of qubits, $`n`$. Suppose we are given some known pure state, $`|\psi `$. We can then ask the question of whether we can transform this state into any other state, $`|\varphi `$. Clearly if we have control over $`𝔰𝔲(2^n)`$ we can perform this task. A theorem from the study of the controllability of quantum systems Schirmer et al. (2002a, b) shows that this task can be performed for all states $`|\psi `$ and $`|\varphi `$ if and only if one has control over the Lie algebra $`𝔰𝔲(2^n)`$ or the Lie algebra $`𝔰𝔭(2^n)`$. Thus, while we do not have full unitary control when we have odd parity Paulis acting on an odd number of qubits (except when $`n=1`$), we can transform any state into any other state using these operations.

## VI Efficiency

We have examined the problem of Hamiltonian simulation across sets of qubits that are coupled by a fixed natural Hamiltonian. However, our results appear to be limited by the fact that our simulation techniques are manifestly exponential in the total number of qubits $`n`$. The problem is that our procedure for isolating a single term of an arbitrary Hamiltonian requires on the order of $`2^n`$ local unitaries to be interspersed in the evolution at different times (see equation (7)). This is in sharp contrast to the case of Hamiltonians whose Pauli expansions contain only two-qudit couplings, and simulation techniques are polynomial in the number of qudits. This defect could be fixed if we were to find efficient techniques for term isolation, for all other steps in our procedure were efficient, at least in principle.

It is not surprising that, in this very general situation, we have not obtained efficient simulation techniques. Suppose, for example, that we have a family of Hamiltonians that has the property that the member of the family that acts on $`n`$ qubits has a decomposition containing a tensor product of $`X`$s acting on every subset of those $`n`$ qubits:

$$\begin{array}{cc}\hfill H_{(2)}& =X_1X_2\hfill \\ \hfill H_{(3)}& =X_1X_2+X_1X_3+X_2X_3+X_1X_2X_3\hfill \\ \hfill H_{(4)}& =X_1X_2+\mathrm{}+X_1X_2X_3+\mathrm{}+X_1X_2X_3X_4\hfill \\ & \mathrm{}\hfill \end{array}$$
(25)
where the subscripts in brackets indicate the number if qubits acted on by each Hamiltonian. These Hamiltonians are not at all natural since every possible coupling of qubits is represented, regardless of how “far away” the qubits are from one another. With such a large number of couplings ($`2^nn1`$ for the $`n`$-qubit member of the family), it is not surprising that we have not found a method to efficiently simulate a set of gates that is universal for quantum computation, since it is difficult to “turn off” enough unwanted interactions, while retaining computational universality, even though these Hamiltonians are dynamically universal. As mentioned in the introduction, we conjecture that a generic entangling Hamiltonians will not be universal for quantum computation.

On the other hand, it would be surprising if the following family of Hamiltonians could not be used simulate a universal set of gates:

$$\begin{array}{cc}\hfill H_{(2)}& =X_1X_2\hfill \\ \hfill H_{(3)}& =X_1X_2+X_2X_3+X_1X_2X_3\hfill \\ \hfill H_{(4)}& =X_1X_2+X_2X_3+X_3X_4+X_1X_2X_3+X_2X_3X_4\hfill \\ \hfill H_{(5)}& =X_1X_2+\mathrm{}+X_4X_5+X_1X_2X_3+\mathrm{}+X_3X_4X_5\hfill \\ & \mathrm{}\hfill \end{array}$$
(26)
In these Hamiltonians, each qubit is directly coupled to at most four other qubits by terms acting on at most three qubits. For example, qubit 3 only ever couples directly to qubits 1, 2, 4, and 5. Furthermore, the number of coupling terms is linear in the number of qubits — the Hamiltonian on $`n`$ qubits has only $`2n3`$ terms in its decomposition. This number is sufficiently small, by contrast with the general case, that we might hope that it is possible to turn off most (but not all) of these couplings in an efficient fashion. We call a Hamiltonian (or, more precisely, a family of Hamiltonians) *$`k`$-local* if the maximum number of qubits coupled by any term in its decomposition is $`k`$ and if the absolute values of the non-zero coefficients multiplying each coupling in $`H`$ (the $`h_{j_1,\mathrm{},j_n}`$ in the expansion of H in equation (2)) are bounded below by a constant. This family of Hamiltonians is thus 3-local.

Motivated by these examples, we now describe a randomized algorithm which shows that a single term in a $`k`$-local Hamiltonian can be isolated with high probability in a number of steps that is exponential in $`k`$ but polynomial in $`n`$. Thus, given a family of $`k`$-local Hamiltonians, for some fixed $`k`$, we have a procedure to efficiently simulate a set of gates that is universal for quantum computation.

More precisely, suppose we wish to isolate a single term $`H_\alpha `$ in the expansion of $`H`$ using local unitaries. We give a procedure to use a randomly chosen set of local unitaries $`\{U_j\}`$ to isolate $`H_\alpha `$ with failure probability bounded above by $`N/2^m`$, where $`N`$ is an upper bound on the number of terms in $`H`$ and $`m`$ is the number of local unitaries in the set $`\{U_j\}`$.

If $`H`$ is $`k`$-local, then $`N`$ is polynomial in $`n`$ — a simple bound on $`N`$ is $`n^k`$ — and hence the probability of failure is polynomial in $`n`$ and decreases exponentially in the number of local unitaries. More precisely, to bound the probability of failure to be less than $`ϵ`$, it turns out to be sufficient to choose $`m\mathrm{log}(N/ϵ)`$. The number of timesteps required increases by a factor of two for each extra unitary, so the number of timesteps is bounded above by $`2^m=N/ϵ`$. Provided $`N`$ is a polynomial function of $`n`$, as is the case if $`H`$ is $`k`$-local, the number of timesteps is also polynomial in $`n`$.

Algorithm: To explain the algorithm, we begin by explaining how to eliminate a single unwanted term from $`H`$, without worrying about keeping our desired term. (We will see later that a simple modification of this procedure eliminates the unwanted term and keeps the desired term.) Suppose, without loss of generality, that the unwanted term has the form $`H_\beta =Z_1Z_2\mathrm{}Z_lI_{l+1}\mathrm{}I_n`$. In order to eliminate this term, we choose a set of local unitaries $`\{U_j\}`$, each of which is a tensor product of $`n`$ unitaries each chosen independently with equal probability from the set $`\{I,X,Y,Z\}`$. We then do the following conjugations:

$$\begin{array}{cc}\hfill H^{(1)}& =U_1HU_1+H,\hfill \\ \hfill H^{(2)}& =U_2H^{(1)}U_2+H^{(1)},\hfill \\ & \mathrm{}\hfill \\ \hfill H^{(m)}& =U_jH^{(m1)}U_j+H^{(m1)}\hfill \end{array}$$
(27)
The probability that $`H^{(m)}`$ still contains the unwanted term $`H_\beta `$ is the probability that each $`U_j`$ commutes with $`H_\beta `$. The probability that a particular $`U_j`$ commutes with $`H_\beta `$ is simply the probability that the total number of $`X`$ and $`Y`$ terms in $`U_j`$ that act on the first $`l`$ qubits is even. So, if $`l`$ is 1, then the probability that $`U_j`$ commutes with $`H_\beta =Z_1`$ is just the probability that $`U_j`$ has a $`Z`$ or an $`I`$ on the first qubit, which is $`1/2`$. Similarly, if $`H_\beta `$ acts nontrivially on the first 2 qubits, then the probability that $`U_j`$ commutes with it is the probability that its first two terms are $`I_1I_2`$, $`Z_1Z_2`$, $`X_1X_2`$, $`X_1Y_2`$, $`X_1Z_2`$, $`Y_1X_2`$, $`Y_1Y_2`$, or $`Y_1Z_2`$, which is again $`1/2`$. It is not hard to see that this pattern holds for any choice of $`H_\beta `$ — the probability that it commutes with a randomly chosen $`U_j`$ is always $`1/2`$. Thus, the probability that all $`m`$ of the $`U_j`$ commute with $`H_\beta `$ is simply $`1/2^m`$.

Now impose the constraint that we wish to keep a particular term $`H_\alpha `$ while eliminating $`H_\beta `$ in this way. Instead of choosing $`U_j`$ completely randomly, we instead generate a random product of Paulis, and then check to see if it commutes with our desired term, $`H_\alpha `$. If it does, which happens with probability $`\frac{1}{2}`$, then we add it to the set $`\{U_j\}`$, otherwise we repeat the process. A simple case analysis now shows that the probability of a given $`U_j`$ in this set commuting with $`H_\beta `$ is $`\frac{1}{2}`$. Thus, the probability that all $`m`$ of the $`U_j`$ chosen in this fashion commute with $`H_\beta `$ is again $`1/2^m`$.

In general there will be many terms in the expansion of $`H`$ that we wish to eliminate while isolating $`H_\alpha `$. The probability that $`H^{(m)}`$ contains a term other than $`H_\alpha `$ (i.e., our procedure has failed) is certainly no greater than the sum of the probabilities that the procedure failed to eliminate each term $`H_\beta `$, that is $`N/2^m`$ where $`N`$ is the number of terms in $`H`$ that must be eliminated. $`\mathrm{}`$

## VII Summary and future directions

We have examined the problem of simulating Hamiltonians using a fixed multi-qubit Hamiltonian and local unitary operations. We have provided a classification scheme for the simulations that are possible given these resources. In particular, we have demonstrated that there are only two physically distinct classes of entangling Hamiltonians up to local unitary operations. One class, the class of odd entangling Hamiltonians, when assisted by local unitary operations, can simulate all odd Hamiltonians but nothing else. The other class, the class of non-odd entangling Hamiltonians, can simulate all Hamiltonians and are thus dynamically universal. We have also demonstrated that all odd entangling Hamiltonians can be made universal through the use of a simple encoding scheme. Furthermore, the Lie algebras generated by the odd entangling Hamiltonians together with local unitary operations were shown to be isomorphic to either $`𝔰𝔬(2^n)`$ or $`𝔰𝔭(2^n)`$, depending on whether $`n`$ is even, or odd, respectively.

In this paper we have made a distinction between sets of resources that are universal for quantum computation and those that are dynamically universal. This distinction has been necessary because we can not find an efficient means to simulate the Hamiltonians used in quantum computation with an arbitrary fixed entangling Hamiltonian and local unitaries. We have demonstrated that when restricted to $`k`$-local Hamiltonians with lower-bounded coefficients dynamic universality is equivalent to universality for quantum computation. The resolution of when this equivalence holds in general would be an interesting contribution to the study of quantum dynamics.

###### Acknowledgements.

We thank Andrew Childs, Andrew Doherty, Charles Hill, Andrew Hines, Greg Kuperberg and John Preskill for valuable discussions. MJB, JLD, and MAN thank the Institute for Quantum Information for their hospitality. This work was supported in part by the National Science Foundation under grant EIA–0086038.


format: text

text:
# Electronic structures and ferromagnetism in transition metals codoped ZnO

## I Introduction

Electronics utilizing the spin degree of freedom of electrons, namely “spintronics”, becomes an important emerging field. The spintronics is expected to overcome the limits of traditional microelectronics, such as non-volatility, data processing speed, electric power consumption, and integration densitiesWolf . Diluted magnetic semiconductors (DMSs) will play a core role in spintronics as semiconductors do in electronics due to easy integration into existing electronic devices. Two types of DMS families have been well studied: II-VI type such as Mn-doped CdTe and ZnSeFurdyna , and III-V type such as Mn-doped GaAsOhno . In particular, the latter attracts great attention, because it becomes a ferromagnetic (FM) DMS having the Curie temperature $`T_C110K`$. Recent research effort has been focused on developing a new FM-DMS operating at room temperatureDietl ; Sato ; Medvedkin ; Matsumoto ; Ando ; SCho .

Along this line, attempts have been made to fabricate ZnO based DMS. ZnO is a wide-gap (Eg $``$ 3.44eV) II-VI semiconductor, and so it can be used for ultraviolet light emitting devices. Jin et al.Jin  fabricated 3$`d`$ transition metal (TM) doped epitaxial ZnO thin films using the combinatorial laser molecular-beam epitaxy method. However, they have not detected any indication of ferromagnetism. In contrast, Ueda et al.Ueda  observed the FM behaviors in some of the Co-doped ZnO films made by using the pulsed-laser deposition technique with TC higher than the room temperature. The reproducibility, however, was less than 10$`\%`$. Hence the realization of the FM long range order in Co-doped ZnO films is controversial.

On the other hand, there were also trials to make ZnO based DMS by co-doping two TM elements: (Fe,Co) or (Fe,Cu). $`\mathrm{Zn}_{1\mathrm{x}}(\mathrm{Co}_{0.5}\mathrm{Fe}_{0.5})_\mathrm{x}\mathrm{O}`$ films were fabricated by using the reactive magnetron co-sputtering techniqueCho , which seemed to have the single phase of the same wurtzite structure as pure ZnO up to $`x`$=0.15. The room temperature ferromagnetism was observed and the rapid thermal annealing under vacuum leads to increases in $`T_C`$, magnetization, and the carrier concentration. Also Cu-doped $`\mathrm{Zn}_{1\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{O}`$ bulk samples were fabricatedHan . The bulk sample has the advantage of insensitivity to the detailed process conditions, over the film sample fabricated under the nonequilibrium condition. They observed the FM behaviors with TC$``$550K and the saturation magnetic moment of 0.75$`\mu _B`$ per Fe in $`\mathrm{Zn}_{0.94}\mathrm{Fe}_{0.05}\mathrm{Cu}_{0.01}\mathrm{O}`$. The saturation magnetic moment increases, as the Cu doping ratio increases up to 1$`\%`$. In addition, the large magnetoresistance was observed below 100K.

Motivated by these reports of ferromagnetism in TM codoped ZnO, we have studied electronic structures and magnetic properties of (Fe, Co) and (Fe, Cu) codoped ZnO: $`\mathrm{Zn}_{0.875}(\mathrm{Fe}_{0.5}M_{0.5})_{0.125}\mathrm{O}`$ (M=Co or Cu). We have used the linearized muffin-tin orbital (LMTO) band method in the local spin-density approximation (LSDA). To explore the Coulomb correlation and the spin-orbit (SO) effect in TM-doped ZnO, we have also employed the LSDA+$`U`$(+SO) method incorporating the Coulomb correlation interaction $`U`$ and the SO interactionKwon . ZnO has the wurtzite structure in which anions and cations form hexagonal close-packed lattices. The wurtzite ZnO is composed of tetrahedrons formed by four O anions. For $`\mathrm{Zn}_{0.875}(\mathrm{Fe}_{0.5}M_{0.5})_{0.125}\mathrm{O}`$, we have considered an orthorhombic supercell containing sixteen formula units in the primitive unit cell by replacing two Zn atoms by Fe and M atoms ($`\mathrm{Zn}_{14}\mathrm{Fe}_1M_1\mathrm{O}_{16}`$). For the lattice constants, we assumed those of pure ZnO with $`a=6.4998,b=11.2580,c=5.2066`$ $`\mathrm{\AA }`$.

## II ZnO, Fe- and Co-doped ZnO

First, we have checked the electronic structure of pure wurtzite ZnO without doping elements. The overall band structure of the present LMTO result is consistent with existing results Schroer ; Arya ; Usuda . As usual in the LSDA calculations, the obtained energy gap $`0.7`$ eV is only about 20$`\%`$ of the experimental value. Also the position of Zn 3$`d`$ band ($`3.05.0`$ eV with respect to the valence band top) is much shallower than the Zn 3d spectrum obtained by photoemission experiment ($`9.0`$ eV) Ruckh . The LSDA+$`U`$ band method improves the results of LSDA, but not so satisfactorily. As shown in Fig. 1, the energy gap is increased to $`1.0`$ eV, and the position of Zn 3$`d`$ band becomes deeper ($`6.07.0`$ eV). The LSDA+$`U`$ result for Zn 3$`d`$ position is consistent with result obtained by the GW band calculationArya ; Usuda . Still the energy gap and Zn 3$`d`$ position are smaller and shallower than experimental values.

We then have performed the LSDA band calculations for single TM-element doped ZnO: Fe- and Co-doped ZnO with 6.25$`\%`$ concentration of TM element. Due to heavy computational load, we have not considered the Coulomb correlation $`U`$ for Zn $`3d`$ electrons in the supercell calculations of doped ZnO systemsSuper . Note that electronic structures of TM doped ZnO have already been reported for 25$`\%`$ concentration of TM element by using the Korringa-Kohn-Rostoker band method combined with the coherent potential approximationSato . They found that V-, Cr-, Fe-, Co-, and Ni-doped ZnO would have the FM ground states rather than the spin-glass states. With this background, we thus consider below only the FM states for Fe-, and Co-doped ZnO with more realistic TM doping concentration.

Figure 2 shows the LSDA total density of states (DOS) and TM 3$`d`$ projected local DOS (PLDOS) for $`\mathrm{Zn}_{1\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{O}`$ and those for $`\mathrm{Zn}_{1\mathrm{x}}\mathrm{Co}_\mathrm{x}\mathrm{O}`$ $`(x=0.0625)`$. For both Fe- and Co-doped ZnO, we have obtained nearly $`half`$-$`metallic`$ electronic structures, that is, the conduction electrons at the Fermi level $`E_F`$ are almost 100$`\%`$ spin polarized. The minority spin $`3d`$ states of both Fe and Co near $`E_F`$ are seen to be hybridized slightly with the conduction band (see Fig. 3). Both for Fe-doped and Co-doped ZnO, the Fermi level cuts the sharp minority spin $`e_g`$ states. Note that Fe and Co are located at tetrahedral centers formed by O ions, and so $`e_g`$ states are lower in energy than $`t_{2g}`$ states. Since there is nearly one more $`d`$-electron in Co-doped ZnO, the Fermi level is located near the valley between Co $`e_g`$ and $`t_{2g}`$ minority spin state. The exchange splittings are larger than the crystal field splittings, reflecting high spin states of Fe and Co in ZnO. Especially, the exchange splitting in Fe-doped ZnO is very large to locate both $`e_g`$ and $`t_{2g}`$ states deep in energy, and so the majority spin Fe $`t_{2g}`$ states become fully hybridized with O $`2p`$ states to yield a broad band. In contrast, the $`t_{2g}`$ states in Co-doped ZnO are shallow and located above the O $`2p`$ valence band and so the hybridization becomes weak.

The total magnetic moments 4.44 and 3.25 $`\mu _B`$ for Fe- and Co-doped ZnO come mostly from Fe (4.11 $`\mu _B`$) and Co (2.92 $`\mu _B`$) ions, respectively. These results suggest electron occupancies of $`d^6`$ (Fe2+) and $`d^7`$ (Co2+), respectively. Figure 3 provides the band structure of $`\mathrm{Zn}_{0.9375}\mathrm{Co}_{0.0625}\mathrm{O}`$ near $`E_F`$. Note that the size of circle represents the amount of Co 3$`d`$ component in the wave function. It is seen that the rather flat majority spin Co $`3d`$ states are located by $`1.0`$ eV below the conduction band consisting of mainly Zn 4$`s`$ states. The minority spin Co $`3d`$ states are located near and above $`E_F`$ manifesting hybridization with the Zn 4$`s`$ conduction band states. However, we do not expect that either Fe- or Co-doped ZnO in nature has a stable metallic ferromagnetic ground state, as obtained above. The high DOSs at $`E_F`$ for both Fe- and Co-doped ZnO would drive the possible structural instability or become reduced substantially by the Coulomb correlation interaction between TM $`3d`$ electrons. Indeed, LSDA+$`U`$ band calculation with $`U`$=5.0eV for Co $`3d`$ electrons yields the insulating ground state for Co-doped ZnO, distinctly from the LSDA band resultsFeZno .

## III (Fe,Co) codoped ZnO

Now we have performed the LSDA band calculations for (Fe, Co) codoped ZnO: $`\mathrm{Zn}_{0.875}(\mathrm{Fe}_{0.5}\mathrm{Co}_{0.5})_{0.125}\mathrm{O}`$. We have examined magnetic properties of supercell by varying the separation between Fe and Co: 3.2499, 5.6055, and 6.4998 $`\mathrm{\AA }`$. 3.2499 $`\mathrm{\AA }`$ corresponds to a nearest Fe-Co separation with Fe-O-Co configuration in the a-b plane of the orthorhombic supercell, while 5.6055 and 6.4998 $`\mathrm{\AA }`$ to farther Fe-Co separations with Fe-O-Zn-O-Co configurations along the diagonal direction and in the a-b plane, respectively. Total energies are nearly the same among three cases: the shortest 3.2499 $`\mathrm{\AA }`$ case has the lowest total energy by only $``$ 3 mRy. This result reflects that there will not be any noticeable TM clustering effect in the (Fe, Co) codoped ZnO. Further we have found that the FM configuration of Fe and Co spins are found to be slightly more stable than the antiferromagnetic (AFM) configuration for all three cases.

Figure 4 shows the LSDA DOS of $`\mathrm{Zn}_{12\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{Co}_\mathrm{x}\mathrm{O}`$ $`(x=0.0625)`$ for a Fe-Co separation of 5.6055 $`\mathrm{\AA }`$. The 3$`d`$ PLDOS in the codoped case looks as if it is just a simple sum of Fe and Co PLDOSs of Fig. 2. There is no indication of charge transfer between Fe and Co, and so Fe2+ and Co2+ valence configurations are retained in the (Fe, Co) codoped ZnO. Hence most properties are similar to each Fe- and Co-doped case, such as the degree of hybridization, nearly half-metallic nature, and the local magnetic moments. This suggests that the $`double`$-$`exchange`$ mechanismZener  will not be effective in $`\mathrm{Zn}_{12\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{Co}_\mathrm{x}\mathrm{O}`$, because the kinetic-energy gain through the hopping of spin-polarized carriers between Fe and Co ions does not seem to occur. Thus to explain the observed FM ground state in $`\mathrm{Zn}_{12\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{Co}_\mathrm{x}\mathrm{O}`$, one needs to invoke another exchange mechanism between Fe and Co, such as the RKKY-type exchange interaction mediated by Zn $`4s`$ carriers or conduction carriers induced by oxygen vacancies. However, one cannot rule out the formation of separated Fe or Co metallic clusters in $`\mathrm{Zn}_{12\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{Co}_\mathrm{x}\mathrm{O}`$ which would exhibit the ferromagnetism. Also the possible formation of impurity phases such as spinel CoFe2O4 is worthwhile to be checked carefully. These features remain to be resolved more in the experiments.

## IV Cu-doped ZnO

Before discussing (Fe, Cu) codoped ZnO, we have examined electronic structure of Cu only doped ZnO: $`\mathrm{Zn}_{0.9375}\mathrm{Cu}_{0.0625}\mathrm{O}`$. Interestingly, as shown in Fig. 5, we have obtained the stable FM and half-metallic ground state for Cu-doped ZnO in the LSDA. The total magnetic moment is 1 $`\mu _B`$ and the local moment of Cu is 0.81 $`\mu _B`$, corresponding to the Cu2+ ($`d^9`$) valence state. The Cu 3$`d`$ PLDOS in Fig. 5(b) indicates that Cu has the DOS of an intermediate spin state. In contrast to Fe- or Co-doped case, the empty Cu 3$`d`$ states are located in the gap region without the hybridization with the Zn $`4s`$ conduction band, and thus Cu 3$`d`$ states are strongly localized. We presume that this would be the reason why the Cu solubility in ZnO is so low: $`1\%`$ at most.

Since the Cu 3$`d`$ states near $`E_F`$ correspond to partially occupied atomic-like $`t_{2g}`$ states, Cu ions would have large orbital magnetic moment. Indeed the LSDA+$`U`$+SO calculation yields the substantial orbital magnetic moment of 1.05$`\mu _B`$ with the insulating electronic structureUjcu . The large orbital moment arises from occupied minority spin $`t_{2g}`$ states split by the Coulomb correlation and the spin-orbit interactionMspark . The orbital moment is polarized in parallel with the spin moment, and so the total magnetic moment amounts to 1.85$`\mu _B`$/Cu.

In general, an ion at the tetrahedral center with low spin $`d^9`$ state would be Jahn-Teller active. In fact, there was a report that the account of the dynamical Jahn-Teller effect is necessary to explain the observed paramagnetic susceptibility for Cu-doped ZnOBrumage . To examine the Jahn-Teller effect in Cu-doped ZnO, we have considered the local distortion of a tetrahedron around Cu by tilting oxygen ions at the corners. The oxygen ions are tilted by $`13^{}`$ toward the $`xy`$-plane with retaining Cu-O separations (here $`xyz`$ coordinates represent the local principle axis). The LSDA band calculation for this system yields a more stable insulating ground state with enhanced spin magnetic moment of 0.99$`\mu _B`$/Cu. That is, due to the Jahn-Teller distortion, Cu $`3d`$ electrons become more localized and the system becomes insulating. The orbital moment in this case would be quenched due to the Jahn-Teller effect.

## V (Fe,Cu) codoped ZnO

As is done for (Fe, Co) codoped case, we have studied magnetic properties of (Fe, Cu) codoped $`\mathrm{Zn}_{12\mathrm{x}}\mathrm{Fe}_\mathrm{x}\mathrm{Cu}_\mathrm{x}\mathrm{O}`$ $`(x=0.0625)`$ with varying the separation between Fe and Cu: 3.2499, 5.6055, and 6.4998 Å. For all three cases, the FM configurations of Fe and Cu spins are found to be more stable than the AFM configurations, as for the (Fe, Co) codoped case. In contrast to the (Fe, Co) codoped case, however, we have found that the shortest Fe-Cu configuration becomes much more stable with respect to other two cases by $``$ 30 mRy. This total energy difference is very large when comparing with $``$ 3 mRy difference for the (Fe, Co) codoped case. This result indicates that Fe and Cu ions in (Fe, Cu) codoped ZnO have a tendency to form the Fe-O-Cu clusters. For 1 $`\%`$ Cu-doped $`\mathrm{Zn}_{0.95}\mathrm{Fe}_{0.05}\mathrm{O}`$ bulk sample, Han et al.Han  observed rather small saturated magnetic moment of 0.75 $`\mu _B`$ per Fe. This value corresponds to only about 1/5 of ideal Fe2+ local moment 4 $`\mu _B`$. Incidentally, the value 1/5 is matched with Cu/Fe doping ratio, suggesting a possibility that the only Fe’s forming the Fe-O-Cu clusters would give rise to the FM moment, that is, other Fe ions do not produce the long range FM order. As shown below, the FM ground state in (Fe, Cu) codoped ZnO can be understood based on the enhanced double-exchange-like interaction through the Fe-O-Cu clustering effect.

Figure 6 presents the LSDA DOS of $`\mathrm{Zn}_{0.875}\mathrm{Fe}_{0.0625}\mathrm{Cu}_{0.0625}\mathrm{O}`$ for the shortest 3.2499 $`\mathrm{\AA }`$ configuration. Above all, one can notice the strong hybridization between Fe and Cu $`3d`$ states. Further, it is clearly seen in Fig. 6(c) that some new states emerge in the Cu 3$`d`$ minority spin PLDOS between $`e_g`$ and $`t_{2g}`$. The new states have $`d_{xy}`$-like characters directing toward Fe ionsLocal . Cu $`3d`$ PLDOS has a reduced exchange splitting, manifesting the DOS characteristic of the low spin state. This feature is different from other two configurations with larger Fe-Cu separation, which have an intermediate spin state as in Cu only doped ZnO. For all three cases, the hybridization between Cu $`3d`$ and the conduction band exists, which is again distinct from Cu only doped ZnO. Due to this hybridization, the conduction carriers of mostly Zn $`4s`$ states become reduced. Noteworthy from PLDOSs of Fig. 6 is that there occurs charge transfer from Fe to Cu, and accordingly Fe and Cu are likely to have nominal Fe3+ ($`d^5`$) and Cu1+ ($`d^{10}`$) configurations, respectively. As a result, the electron occupancy at Cu site increases, and so Cu has the reduced spin magnetic moment of 0.51 $`\mu _B`$ as compared to 0.81 $`\mu _B`$ in Cu only doped ZnO. This feature explains the experimental result of the reduced number of carriers in (Fe, Cu) codoped ZnO with respect to that in Fe only doped ZnO Han . The charge transfer from Fe to Cu is expected to disturb the Jahn-Teller distortion at Cu sites and concomitantly make a system metallic. Further, it will cause the mixed-valent occupancies for Fe (Fe2+-Fe3+) and Cu (Cu2+-Cu1+) ions, and the consequent double-exchange-like interaction is expected to induce the ferromagnetism in (Fe, Cu) codoped ZnO.

## VI Conclusion

We have investigated electronic structures of (Fe, Co) and (Fe, Cu) codoped ZnO together with those of Fe-, Co-, and Cu-doped ZnO. We have also explored origins of observed ferromagnetism in (Fe, Co) and (Fe, Cu) codoped ZnO. The single TM-doped systems would not have stable metallic ferromagnetic ground states, due to large Coulomb correlation or other structural instability effects in Fe- and Co-doped ZnO and the Jahn-Teller effect in Cu-doped ZnO, respectively. For (Fe, Co) codoped ZnO, we have found no indication of charge transfer between Fe an Co, suggesting that the double-exchange mechanism will not be effective for the observed ferromagnetism in (Fe, Co) codoped ZnO. Therefore one needs to invoke another exchange mechanism between Fe and Co, or the possible formation of impurity phases is to be checked carefully. In contrast, for (Fe, Cu) codoped ZnO, there is a tendency to form the Fe-O-Cu clusters and so to give rise to charge transfer from Fe to Cu ion. This tendency causes the mixed-valent occupancies between Fe and Cu, and accordingly the double-exchange-like interaction is expected to induce the ferromagnetism in (Fe, Cu) codoped ZnO. The FM and nearly half-metallic ground state is obtained for (Fe, Cu) codoped ZnO.

###### Acknowledgements.

This work was supported by the KOSEF through the eSSC at POSTECH and in part by the KRF (KRF–2002-070-C00038). Helpful discussions with Y. H. Jeong and S. J. Han are greatly appreciated.


text:
# Polarimetry in the Visible and Infrared: Application to CMB Polarimetry

## 1 Some Basics

Polarization due to magnetically aligned dust grains in the Milky Way galaxy is subject to both coherent and random processes (see Jones, 1996 for a review of grain alignment). Most observations of interstellar polarization have been at visual wavelengths, with a modest contribution at near-infrared (NIR) wavelengths. At these wavelengths the polarization is due to selective extinction by aspherical dust grains. In the far-infrared (FIR), these same grains are in emission. This emission is polarized and consequently a foreground contaminant for CMB polarimetry. A few simple facts about interstellar polarization should be noted.

* Fractional polarization P is very probably NOT a function of magnetic field strength (Jones, Klebe & Dickey, 1991).
* Polarization in emission (Pe) behaves differently than polarization in transmission (Pa).
* Pa starts low, then increases with increasing optical depth and contains information on the random component of the aligning magnetic field.
* Pe starts high, then decreases with increasing optical depth. CMB polarimetry will sample the low optical depth regime.

CMB polarization measurements will be concerned with contamination from fluctuations in Stokes vectors Q and U caused by variations in interstellar polarization in emission. Recall that Q and U are intensities, not fractions. Specifically:

$`I_P`$ $`=`$ $`P_{frac}I_{tot}`$
$`I_P`$ $`=`$ $`\sqrt{Q^2+U^2}`$
$`Q`$ $`=`$ $`I_P\mathrm{cos}(\theta )`$
$`U`$ $`=`$ $`I_P\mathrm{sin}(\theta )`$
$`\theta `$ $`=`$ $`{\displaystyle \frac{1}{2}}\mathrm{tan}^1\left({\displaystyle \frac{U}{Q}}\right)`$
Thus, Variations in Q and U can be due to fluctuations in fractional polarization, fluctuations in position angle, and fluctuations in total intensity. For example, a region of sky with the same fractional polarization in emission (uniform grain alignment across the sky) will still show fluctuations in Q and U if the intensity is varying across the region. At high latitudes, this effect will turn out to be the major source of contamination.

Polarimetry at FIR and sub-mm wavelengths would seem the best source of observations for characterizing the CMB polarized foreground. These observations measure polarized emission from grains, and in the sub-mm extend to wavelengths close to those to be observed in upcoming and proposed CMB polarimetry experiments. However, FIR and sub-mm observations require significant optical depth to achieve detectable emission, and consequently have largely been confined to dense regions in the galactic plane. At high latitudes, where CMB polarimetry will be most effective, the emission is very optically thin and nearly impossible to observe in polarization. The reader should see Hildebrand et al.  (2000) for a thorough discussion of FIR polarimetry.

## 2 Observations of Interstellar Polarization

Optical polarimetry can, however, measure polarization in transmission (Pa) at high latitudes because dust extinction is so strongly wavelength dependent. We need to relate optical, NIR and FIR polarimetric observations in order to predict the characteristics of foreground polarized emission at high latitudes. This work is in its infancy, but some useful conclusions can be made.

Jones, Klebe & Dickey (1991) present a simple model of grain alignment by the interstellar magnetic field that they use to explain the general trend of polarization (Pa) with optical depth ($`\tau `$) observed at optical and NIR wavelengths. They assume the magnetic field is strong enough everywhere to fully align the grains and that any departure from a simple linear relation between Pa and $`\tau `$ is due to fluctuations in the magnetic field geometry. Their results are shown in Figure 1. The upper model line is the case for a perfectly uniform magnetic field geometry, the lower model line is for a totally random magnetic field geometry. The data clearly lie between these two extremes. The solid middle line is the model result with a 50/50 mix of random and uniform components and a decorrelation length for the random component of $`\tau _K=0.1`$.

Similar results have been obtained by Fosalba et al.  (2002) using a much larger optical data set. These model results show that fluctuations in $`P_a`$ will be strongly influenced by fluctuations in the magnetic field geometry only for optical depths greater than $`\tau 0.030.1`$ at 2.2 µm (about $`A_V=0.31.0`$). At high galactic latitudes, where the optical depth is much less than this, we would expect the magnetic geometry to be relatively smooth, and therefore not a significant factor influencing fluctuations in Q and U in emission at FIR wavelengths.

This conclusion can be seen more clearly by using the parameters from the JDK model to predict the polarization in emission. The results of this exercise are shown in Figure 2, where the predicted fractional polarization at FIR wavelengths is plotted vs. the number of decorrelation cells along the line of sight. The model computes the predicted average polarization for an ensemble of lines of sight. Note that $`P_e`$ is highest at the low optical depths, since all of the grains are emitting with the same alignment geometry. This is the regime in which CMB observations will be most useful.

Based on the results from NIR polarimetry (Figure 1), one decorrelation cell corresponds roughly to $`A_V=0.31`$, or in physical distance units about 200-500 pc in the diffuse ISM. This corresponds to a greater optical depth than seen at high latitudes and one such cell would cover several degrees across the sky. Thus, the JKD model predicts that the CMB foreground contamination will most likely have a high intrinsic fractional polarization but a relatively uniform projected geometry over many degrees at high latitudes.

In Figure 2 we have assumed the maximum polarization of completely aligned grains is 7%, a tyical upper bound for FIR measurements in dense star forming regions. More recent observations in regions with lower optical depth and observations at sub-mm wavelengths strongly suggest that 10% would be a more appropriate choice for the maximum fractional polarization warm dust would have at the wavelengths of CMB experiments (Hildebrand et al. , 2000).

Direct optical polarimetry in regions of the sky a few degrees across at high latitudes confirms this prediction. For example, the region from $`l=275\mathrm{°}295\mathrm{°},b=60\mathrm{°}70\mathrm{°}`$ shown in Figure 3 has optical polarimetry for over 25 stars in the compilation by Heiles (1996). In this region we find a very uniform position angle $`(\theta _{rms}=0.25rad)`$. The observed fluctuations in fractional polarization $`(P_{rms}/<P>=0.4)`$ are about a factor of two higher than expected given the observed $`\theta _{rms}`$. This is presumably due to fluctuations in optical depth across the region, not fluctuations in magnetic field geometry.

## 3 FIR Surface Brightness

This leaves fluctuations in total intensity as the major source of fluctuations in Q and U from emission of aligned dust at high latitudes. Using the 100 µm map from Schlegel, Finkbeiner & Davis (1998) and the predicted average fractional polarization from Figure 2 for one decorrelation cell, we can predict the fluctuations in Q and U due to fluctuations in total intensity at FIR wavelengths. To make a prediction at a frequency of 150 GHz, we use the following input parameters:

1. Assume $`<P_e>`$ and $`\theta `$ are both constant with $`<P_e>=5\%`$.
2. The measured fluctuations of the intensity in the central $`40\mathrm{°}\times 40\mathrm{°}`$ region of the 100 µm map is $`I_{rms}=0.4`$MJy/sr using 10’ bins.
3. Extrapolate the intensity from 100 µm to 150 GHz using a power law index of 1.75 for the emissivity.
4. Arbitrarily assign Q to lie along the magnetic field direction. In this configuration the average value of U will be 0.

With these parameters, we find that $`Q_{rms}10^7I_{CMB}`$ due to fluctuations in total intensity alone.

We can improve this estimate somewhat if we include the lesser effects of fluctuations in the magnetic field geometry. Taking the observed dispersion in position angle for the region of sky shown in Figure 3 $`(\theta _{rms}=0.25rad)`$ and using the JKD model to predict the fluctuations in $`P_a`$, we find $`P_{rms}/<P>=0.2`$, about half the observed value. Combining the effects of fluctuations in intensity at 150 GHz with fluctuations in magnetic field geometry for this one piece of the sky, we obtain the predicted values for $`Q_{rms}`$ and $`U_{rms}`$ given in Table 1.