text:
# A switchable controlled-NOT gate in a spin-chain NMR quantum computer

## I Introduction

A quantum computer (QC) is a Turing machine which performs information processing based on the principles of quantum mechanics. It makes the best use of the features of the quantum mechanics, such as superposition and entanglement of quantum states. These features enable us to perform parallel computation for all the possible states simultaneously, which makes it possible to deal with the problems that are formidable for classical (conventional) computers. New algorithms recently discovered Deutsch (1985); Shor (1997); Grover (1998) have shown the great promise of the QC’s, which has accelerated the attempts to implement the QC’s in actual physical systems.

A QC is composed of a set of two-level systems called qubits. The qubits need to be isolated enough from the environment, and controllable from outside to deal with the information. In this respect, nuclear spin systems in a matter are the promising candidates, because they are only weekly coupled with the environment (electron systems) through hyperfine couplings, and controllable by the well-established technique of the nuclear magnetic resonance (NMR). Actually, the first 2-qubit QC’s were implemented by solution NMR Chuang et al. (1998); Jones and Mosca (1998). The quite successful implementations proved the great promise of the NMR-QC’s. It is unfortunate, however, that the solution NMR-QC has a difficulty in its scalability. The number of available qubits in solutions is limited because of the limited number of nuclei in one molecule. The required number of qubits with which QC can surpass its classical analogue is estimated to be more than $`10^3`$, so that it is a primary concern to increase the number of qubits.

So far, two models have been proposed to systematically increase the number of qubits in the NMR-QC’s. Kane proposed a multi-qubit NMR QC model, which utilizes 31P nuclei embedded in a Si matrix Kane (1998). This model provides us with a chance to extend the number of qubits systematically, whereas it requires fine structures to be fabricated and controlled, realization of which is a challenge to the current state-of-the-art nano-technology. On the other hand, Yamaguchi and Yamamoto proposed to utilize nuclei as they are in nature, i.e., in crystals Yamaguchi and Yamamoto (1999). The 31P nuclei in CeP are placed in the magnetic field gradient, so that each nucleus (qubit) can be accessed by adjusting the NMR frequency. The proposal is very attractive because of its simple structure, although it still has some technical obstacles to be cleared Hashi et al. (2000). We have pursued this possibility checking the key issues.

One of the key issues is how to provide an inter-qubit (inter-nuclear) coupling, which is used for a controlled NOT (c-NOT) gate shown in Fig. 1. So far, a nuclear dipole (direct) coupling has been supposed to be a potential inter-qubit coupling Yamaguchi and Yamamoto (1999); Ladd et al. (2000). It is unfortunate, however, that the dipolar coupling is always present whenever qubits are put close to each other, so that one should continue applying the decoupling sequences to remove unwanted couplings. Apparently, these sequences consume a great deal of time, causing a longer computation time. Moreover, as the number of qubits is increased, the number of inter-nuclear couplings is increased accordingly, so that the decouplings become more and more complicated, and they eventually become formidable. So, a decoupling-free QC is highly desired, i.e., the inter-nuclear coupling should be able to be switched on when, and only when necessary.

Another key issue is the method of distinguishing, in the frequency domain, each nucleus (qubit) separated by a distance of the order of a lattice constant. Even the field gradient of 1T/$`\mu `$m Goldman et al. (2000) is still marginal for this purpose Ladd et al. (2000). The larger inter-nuclear (qubit) distance in the real space makes the distance between the adjacent NMR lines wider in the frequency domain, which relieves this constraint. Hence, the inter-nuclear coupling should be able to reach rather long distance. Unfortunately, the direct nuclear dipole coupling reaches at most a few lattice points Goto et al. (2002a).

These facts motivate us to seek for the possibility of the long range indirect couplings mediated by electrons. The indirect couplings include the J-coupling due to the covalent bondings, the RKKY interaction in metals Ruderman and Kittel (1954), and the Suhl-Nakamura (SN) interaction in magnets Suhl (1958); Nakamura (1958). Among them, the SN interaction has the characteristics preferable for the present purpose, such as the long-range nature of the coupling and the external controllability of the coupling strength.

In this paper, we present details of the model of a solid-state NMR-QC with an inter-qubit coupling provided by the SN interaction Goto et al. (2002b). A singlet-triplet transition in a quantum spin chain (1D antiferromagnet) provides us with a switch for the inter-qubit coupling. The model has the following advantages over the other existing models. (1) It is intuitive because the computation starts in the silent environments rather than the turbulence of interactions, which makes the designs of the logic gates simpler. (2) The long-range nature of the SN interaction allows us to place qubits apart farther from one another, which facilitates distinguishment of the qubits in the frequency domain. (3) The presence of the spin gap in the quantum spin chains allows simple operation of the gate switching compared to that proposed for the Kane’s type NMR-QC Khitun et al. (2001). We also present the scheme of qubit initializer, an effective nuclear polarizer comprising the optical pumping and the polarization transfer methods. The scheme enables us to separate the materials responsible for the initialization and computation, so that one can optimize the computation part without being restricted by the initialization scheme.

## II Model

Here, we present the outline of the model. The main idea is illustrated in Fig. 2. The system consists of a one-dimensional array of electron spins (quantum spin chain) placed in a magnetic field gradient, which is produced by a micromagnet fabricated outside the spin chain Goldman et al. (2000). Suppose that the electron spins are paired into singlets in the ground state ($`ss_z`$=$`00`$) with a finite gap to the lowest triplet branch ($`11`$) of the $`k=0`$ magnon modes because of some quantum effects. Examples of such situations can be found in spin ladder, Haldane, dimer and spin-Peierls systems. Also suppose that nuclei ($`I=1/2`$) serving as qubits can be placed periodically, e.g., every ten lattice points, each of which has a hyperfine coupling with the electron spins.

Since there are no unpaired electron spins in the ground state, the nuclear spins are well-isolated from the environment. The nuclei are also decoupled from the charge and lattice properties of the electrons because $`I=1/2`$. The rather long distance between qubit nuclei is effective both to diminish the direct nuclear dipole couplings between qubits and to distinguish one qubit from another in the NMR frequency domain, because the longer inter-qubit distance leads to larger interval between NMR lines in the given field gradient.

It is known that virtual exchanges of magnons between nuclear spins result in the inter-qubit interaction called the Suhl-Nakamura (SN) interaction Suhl (1958); Nakamura (1958). Since it is not necessarily accompanied by actual excitations of magnons, it can exist even at temperatures well beneath the excitation gap. Nevertheless, the transverse component of the SN interaction with a form of $`I_i^+I_j^{}`$ is always absent in the field gradient because of the detuning effect, i.e., a mismatch in the Zeeman energies prevents the nuclei from exchanging magnons. On the other hand, the longitudinal component ($`I_i^zI_j^z`$) of the SN interaction can survive even at low temperatures, which is characterized by the antiferromagnetic spin-spin correlation function in the ground state (see §IV) Itoh et al. (1996); Sandvik et al. (1996); Kishine (1997). This interaction, however, is short-ranged because the spin-spin correlation function decays exponentially as a function of the distance, so that the interaction can reach only a few lattice points White et al. (1994). As a result, the interactions between nuclei apart from each other by the order of ten lattice points are completely switched-off at low temperatures.

In order for the system to work as a QC, one has to provide logic gates. A QC is complete if it is equipped with arbitrary rotation (R) and controlled-NOT (c-NOT) gates. Barenco et al. (1995) The R gate is a single qubit operation, which can be accomplished by an NMR pulse with an appropriate pulse width at the corresponding frequency. On the other hand, the c-NOT gate is a two-qubit operation, which works in such a way that a target qubit changes its logic according to the state of the control qubit, which can be realized by the pulse sequence shown in Fig. 1. Since the c-NOT gate between any combination of qubits apart from each other along the chain can be realized by a series of c-NOT gates between adjacent qubits Collins et al. (2000), the QC is complete with the inter-nuclear coupling with the form $`I_{iz}I_{jz}`$ between adjacent nuclear spins. This coupling is provided by the longitudinal component of the SN interaction via the $`k=0`$ magnon mode composed of the spin triplet state Zevin and Kaplan (1975), which is selectively excited at a specific part of the chain where the c-NOT gate is to be performed.

The transition between singlet and triplet states by a microwave irradiation can be used to create the triplet $`k=0`$ magnons. Although the excitation is primarily forbidden for the usual electric dipolar transition, it often becomes possible in the actual systems because of some higher order terms in the electron-photon interaction Hamiltonians Brill et al. (1994); Lu et al. (1991). The position of the excited magnons along the chain can be specified by the applied microwave frequency, which is uniquely given in the field gradient. The energy diagrams of the $`k=0`$ magnon excitations in the magnetic field is shown in Fig. 3 Tachiki and Yamada (1970); Brill et al. (1994). In the field gradient, the magnetic field at each part of the chain is unique so that the excitation energy to the lowest triplet state ($`11`$) is also uniquely given, which provides us with a spatial resolution of the excitation, i.e., one can specify the position of the magnon excitations by adjusting the frequency of the applied microwave. The region and the amplitude of the excited magnons can be controlled by the frequency resolution and the power of the microwave.

Since the two upper states ($`10`$, $`11`$) irrelevant to the transition of interest can be ignored, one can introduce effective spins within the $`00`$ and $`01`$ subspace Tachiki and Yamada (1970). These spins are rotated by the microwave, creating a packet of superpositions of $`00`$ and $`11`$ along the chain Brill et al. (1994), corresponding to the magnon excitations with the wave number $`k0`$. The packet is localized along the chain due to the magnetic field gradient (see §III). The number of excited spins is given by the balance between the excitation to the $`11`$ state and the relaxation (with the lifetime of $`T_s`$) to the ground state.

The triplet states make an additional field ($`H_{\mathrm{tr}}`$) associated with the “shift” at the qubit site, which should be distinguished from the additional field from the adjacent qubit via the SN interaction ($`H_{\mathrm{SN}}`$). Assuming the hyperfine coupling $`A_{}`$ = 100 kOe/$`\mu _B`$ and the rotation of the spins: $`n(0)`$ 1 % , $`H_{\mathrm{tr}}`$ is estimated to be $``$ 1 kOe, which corresponds to $``$ 1 % shift of the NMR frequency in the magnetic field of 10 T. In practice, the exact value of $`H_{\mathrm{tr}}`$ can be measured by the following method; under the microwave irradiation, one observes the shift of the NMR frequency of the target qubit while saturating the control qubit by applying the corresponding NMR rf field continuously. The saturation of the control qubit results in $`H_{\mathrm{SN}}=0`$ at the target qubit, so that the observed shift directly corresponds to $`H_{\mathrm{tr}}`$.

Then, the c-NOT gate is achieved as follows (see Fig. 1). (a) In the beginning, the target qubit ($`I_{N+1}`$) is assumed to be pointing to the Z direction. The $`\pi /2`$ pulse with the rf frequency $`\omega =\gamma _nH(x_{N+1})`$ is applied in the negative X direction in the rotating frame of the target qubit. (b) A microwave is applied to the chain. The SN interaction is switched on, and the target qubit starts to rotate in the XY plane of the rotating frame with $`\omega =\gamma _n(H(x_{N+1})+H_{tr})`$. The direction of the rotation with respect to the frame depends on the state of the control qubit ($`I_N`$). (c) By the time $`t=\pi /(2\gamma _nH_{\mathrm{SN}})`$, the target qubit reaches either positive or negative X. (d) The SN interaction is shut off by shutting off the microwave, and the second $`\pi /2`$ pulse with $`\gamma _nH(x_{N+1})`$ is applied in the negative Y direction, which rotates the target qubit upward or downward according to the control qubit. This sequence allows us to perform the c-NOT gate.

## III Singlet-triplet excitations in the quantum spin chain

One of the key phenomena in the present model is the selective excitations of the triplet states shown in Fig. 3 Brill et al. (1994). Let us see the excitation in detail. We consider the ladder case shown in Fig. 4 as an example, and follow the description in Ref. Tachiki and Yamada, 1970. The effective spin is introduced within the subspace consisting of the ground state $`00`$ and the lowest excited state $`11`$. This treatment is helpful to visualize the transition as a rotation of the spin.

The Hamiltonians which govern the system are,

$`H`$ $`=`$ $`H_0+H_1,`$ (1)
$`H_0`$ $`=`$ $`J{\displaystyle \underset{i}{}}𝐬_{i1}𝐬_{i2}+g\mu _B{\displaystyle \underset{i}{}}𝐇(x_i)(𝐬_{i1}+𝐬_{i2}),`$ (2)
$`H_1`$ $`=`$ $`J_1{\displaystyle \underset{nn}{}}𝐬_{i1}𝐬_{j1}+J_1{\displaystyle \underset{nn}{}}𝐬_{i2}𝐬_{j2},`$ (3)
Here, $`J`$ and $`J_1`$ are the intra- (rung) and inter-pair (leg) exchange interactions, respectively. $`𝐇(x_i)`$ is the external field at the $`i`$-th site and “$`nn`$” means the nearest neighbor sites. By introducing the operators $`\text{S}_i=\text{s}_{i1}+\text{s}_{i2}`$ and $`\text{T}_i=\text{s}_{i1}\text{s}_{i2}`$, Eqs. (1)$``$(3) are rewritten as,

$`H_0`$ $`=`$ $`{\displaystyle \frac{1}{2}}J{\displaystyle \underset{i}{}}\text{S}_i^2+g\mu _B{\displaystyle \underset{i}{}}𝐇(x_i)𝐒_i`$ (4)
$`H_1`$ $`=`$ $`{\displaystyle \frac{1}{2}}J_1{\displaystyle \underset{nn}{}}(\text{S}_i\text{S}_j+\text{T}_i\text{T}_j),`$ (5)
where some constant terms are dropped.

We further rewrite these Hamiltonians in terms of the Pauli spin components in the following manner.

$`𝐒_i^2=1\sigma _i^z,`$ $`S_i^x=S_j^x=0,`$ $`S_i^z={\displaystyle \frac{1}{2}}(\sigma _i^z1),`$
$`T_i^x={\displaystyle \frac{1}{\sqrt{2}}}\sigma _i^x,`$ $`T_i^y={\displaystyle \frac{1}{\sqrt{2}}}\sigma _i^y,`$ $`T_i^z=0.`$ (6)
As a consequence of these transformations, the two states of $`00`$ and $`11`$ can be treated as the two spin states represented by the Pauli spin matrices. The total Hamiltonian, Eq. (1) is expressed by these spin matrices as,

$`H`$ $`=`$ $`{\displaystyle \frac{N}{2}}(J+{\displaystyle \frac{J_1}{4}}g\mu _B{\displaystyle \underset{i}{}}H(x_i))`$ (7)
$``$ $`{\displaystyle \frac{1}{2}}{\displaystyle \underset{i}{}}\{J+{\displaystyle \frac{J_1}{4}}g\mu _BH(x_i)\}\sigma _{zi}`$
$`+`$ $`{\displaystyle \frac{J_1}{8}}{\displaystyle \underset{nn}{}}\{2(\sigma _i^x\sigma _j^x+\sigma _i^y\sigma _j^y)+\sigma _i^z\sigma _j^z\}`$
This describes the system of the spins coupled through anisotropic exchange interactions. The microwave rotates these spins.

The small-angle rotations of the spins in a small region create a packet of $`k0`$ magnons like a soliton. The packet is localized on the chain due to the magnetic field gradient. A mismatch in the magnon excitation energies between adjacent regions along the chain prohibits the packet from moving to the lower field region. On the other hand, the continuum excitations near the one-magnon excitations at $`k`$=0 is absent, so that it is difficult for the packet to move to the higher field region Augier and Poilblanc (1998); Uhrig and Schulz (1996); Garrett et al. (1997); Yu and Haas (2000); Grenier et al. (2000) unless the process of the energy release by phonon emissions is considerable. Consequently, the magnons are confined in the region where they are excited, and the SN interaction is produced only between the qubit pair of interest.

The population of the magnons with $`k=0`$ ($`n(0)`$) is determined by the balance between excitation and relaxation,

$$\frac{dn(0)}{dt}=W_{\mathrm{ex}}\frac{n(0)}{T_s},$$
(8)
where $`W_{\mathrm{ex}}`$ is the transition probability of $`0011`$ per unit time by the microwave irradiation, and $`T_s`$ is the magnon lifetime. At the steady state, $`dn(0)/dt=0`$, so that $`n(0)=W_{\mathrm{ex}}T_s`$. As the microwave irradiation is shut off, the spins start to relax to the ground state ($`\sigma _z=1`$) with the relaxation time given by $`T_s`$.

We end up this section with some remarks on the nature of the excited states. One is about the lifetime of the excited states ($`T_s`$); it could be rather long because the excitation is primarily forbidden for the usual electric dipolar transition. Although the forbiddance itself is usually lifted by some additional interactions such as the Dzyaloshinsky-Moriya interaction Brill et al. (1994); Lu et al. (1991), the primarily forbidden transition is expected to lead to rather long lifetime of the excited triplet states and narrower transition line, which is favorable for the selective excitation. Another is about the wave number of the triplet states; they should have $`k`$=0 and the transition to the staggered component ($`k=a/\pi `$) is forbidden, because only the transitions with the momentum transfer $`qkk^{^{}}=0`$ are allowed by the microwave, and the ground state ($`|00`$) is a uniform singlet state ($`k`$=0). This fact is quite favorable for the long-range inter-nuclear coupling with $`q0`$. Note that the magnons excited by the microwave are in the non-equilibrium states far from the thermal equilibrium where the $`k=a/\pi `$ magnons are primarily excited.

## IV Inter-nuclear couplings mediated by magnons

We next look into the details of the longitudinal component of the SN interaction caused by a packet of spin triplet states. For simplicity, we assume the following on-site anisotropic hyperfine Hamiltonian in the $`i`$-th site,

$$H_{hf}=\{A_{}s_{i1}^zI_i^z+\frac{1}{2}A_{}(s_{i1}^+I_i^{}+s_{i1}^{}I_i^+)\},$$
(9)
which can be rewritten using the spin introduced in Eq. (6) as,

$$H_{hf}=\frac{1}{4}A_{}(I_i^z\sigma _i^zI_i^z)+\frac{1}{2\sqrt{2}}A_{}(\sigma _i^+I_i^{}+\sigma _i^{}I_i^+).$$
(10)
Hence, besides the term, $`\frac{1}{4}A_{}I_i^z`$, which can be incorporated into the Zeeman term in the nuclear Hamiltonian, the nuclear interaction with the spin $`\sigma `$ can be expressed by the anisotropic hyperfine interaction. The first term creates the shifts at the nuclear sites corresponding to $`H_{tr}`$ and the SN interactions, and the other terms give rise to the spin-lattice relaxation Beeman and Pincus (1968); Pieper et al. (1993); Ivanov and Lee (1999). The effect of the spin lattice relaxation is discussed in the next section.

Since the transverse component of the SN interaction due to $`\sigma ^\pm `$ vanishes in the field gradient, we can restrict ourselves to the longitudinal component. The longitudinal component of the SN interaction is given by,

$$H_{SN}=W_{ij}I_i^zI_j^z,$$
(11)
where,

$$W_{ij}=\left(\frac{\gamma _nA_{}}{N}\right)^2\underset{k,k^{^{}},kk^{^{}}}{}\frac{n_kn_k^{^{}}}{ϵ_k^{^{}}ϵ_k}\mathrm{cos}\{(kk^{^{}})r_{ij}\}.$$
(12)
Here, $`n_k`$ and $`ϵ_k`$ are, respectively, the population and the energy of the magnon with the wave number $`k`$, and $`r_{ij}`$ is the distance between the two nuclei of interest. In the equilibrium states, $`n_k`$ is given by the Bose function for the given temperature.

Actually, eq. (11) is a special case of the general formulas for the indirect spin-spin interaction,

$$H_{ind}=\mathrm{\Phi }(r_{ij})I_i^zI_j^z,$$
(13)
with the range function,

$$\mathrm{\Phi }(r_{ij})=\gamma _n^2A_{}^2\underset{q}{}\chi (q)\mathrm{exp}(iqr_{ij}).$$
(14)
Here, $`\chi (q)`$ is the zero energy component of the generalized susceptibility, and $`q=kk^{^{}}`$. In the present case, the electronic state is not in the equilibrium state, so that $`\chi (q)`$ is different from that in the thermal equilibrium. Note in particular, that the magnons with the wave numbers other than $`k0`$, such as $`k=\pi /a`$, are not excited here.

The range to which this interaction reaches depends on the range function, which is determined by the form of $`\chi (q)`$ as a function of $`q`$. For the pair of nuclei far from each other, the most important interaction comes from the uniform part of the susceptibility, i.e. $`q0`$ caused by the scatterings of the magnons with $`k0`$.

In the case of the transverse component of the SN interaction in a 3-D system, the range function can be calculated only from the magnon dispersions and has the form $`a/r\mathrm{exp}(r/3a)`$ ($`a`$ is a lattice constant) Nakamura (1958). In our case, however, the situation is completely different from this case, and the interaction reaches rather long distance because of the following reasons. Firstly, in the longitudinal component, the number of excited magnons, as well as the magnon dispersions, are responsible for the range function (see Eq. (12)). Secondly, the system is 1-D so that a qualitative difference exists in the structures of $`\chi (q)`$. Thirdly, the system is not in the equilibrium state. Since $`\chi (q)`$ is enhanced at $`q0`$ in the present case, a rather long distance interaction is expected between the nuclei of interest. Note again that the contribution from the magnons with $`k\pi /a`$ to $`\chi (q0)`$, which exists in the equilibrium state, does not exist in the present case.

Here, we make a rough estimation of the range function for the case of Fig. 4 using Eq. (12). The magnon dispersion of the triplet state in this situation is given by Muller and Mikeska (2000),

$`ϵ(k_n)`$ $`=`$ $`C+J(j_1{\displaystyle \frac{1}{4}}j_2^3)\mathrm{cos}(k_n)+\mathrm{}`$ (15)
where $`k_n=n\pi /N`$, $`j_1=J_1/J`$ and $`C`$ is the part independent of $`k_n`$. Here, the magnetic field is assumed to be uniform in this region. Using Eq. (15) and recalling that the microwave irradiation excites only the $`k=0`$ component of the magnons, i.e., $`n(k)=0`$ for $`k0`$, one can calculate the range function $`W_{ij}`$ in Eq. (12),

$`W_{ij}`$ $`=`$ $`\left({\displaystyle \frac{\gamma _nA_{}}{N}}\right)^2{\displaystyle \underset{n=1}{\overset{N}{}}}{\displaystyle \frac{2n(0)}{ϵ(k_n)ϵ(0)}}\mathrm{cos}(k_nr_{ij})`$ (16)
$`=`$ $`{\displaystyle \frac{2\gamma _n^2A_{}^2\{n(0)/N\}}{J(j_1\frac{1}{4}j_1^3)N}}{\displaystyle \underset{n=1}{\overset{N}{}}}{\displaystyle \frac{\mathrm{cos}(k_nr_{ij})}{\mathrm{cos}(k_n)1}}.`$
Assuming $`N`$ = 20, $`r_{ij}`$ = 10 (in units of $`a`$), $`A_{}`$ = 100 kOe/$`\mu _B`$, $`\gamma _n/(2\pi )`$ = 4.3 MHz/kOe (1H as an example), $`J`$ = 50 K, $`j_2`$ = 0.2 and $`n(0)/N=0.01`$, one obtains $`W_{ij}`$ = 15 kHz, which is the same order of magnitude as the nuclear dipole coupling acting between nuclei 3 Å apart from each other Yamaguchi and Yamamoto (1999); Ladd et al. (2000), and one to three orders of magnitude greater than the J-couplings used in the solution NMR-QC’s Chuang et al. (1998); Jones and Mosca (1998).

The estimation here is for the ideal case, because the population difference may be underestimated ($`n(k0)`$ may be populated somewhat in the actual situation). Moreover, the realistic magnon dispersions as well as the conditions of the microwave excitation such as $`n(0)/N`$ and $`N`$ may affect the value of $`W_{ij}`$. Nevertheless, this estimation indicates that the longitudinal component of the SN interaction could be large enough to serve as a c-NOT gate. Note that the strength of the coupling, $`W_{ij}`$ can be controlled by the microwave intensity via $`n(0)`$, because it is determined by the balance between excitation and relaxation, and in the steady state, $`n(0)=W_{\mathrm{ex}}T_s`$.

## V Decoherence

Decoherence is one of the serious concerns in this model. On the one hand, the excited triplet states can create inter-qubit couplings, but on the other hand, they inevitably activate the scattering channels of the nuclear spins and reduce the spin-lattice relaxation time $`T_1`$ Beeman and Pincus (1968); Pieper et al. (1993); Ivanov and Lee (1999). Although this is unavoidable, it is still possible to reduce the chances of decoherence.

Let us see the scattering process of magnons by a nucleus in detail. Since the direct one-magnon process is prohibited because of the mismatch between nuclear and electron excitation energies, the possible lowest order process is the two-magnon (Raman) process. This process can be the major cause of $`T_1`$ relaxation when the number of excited magnons is increased. The process is known, however, to require highly anisotropic exchange interactions because of the conservation of the angular momentum before and after the scattering. Hence, the process can be reduced in the system with isotropic exchange interactions Beeman and Pincus (1968); Pieper et al. (1993). The three-magnon process is the next possible process, where two incident magnons are scattered by a nucleus and one magnon is emitted. This process is active even in the case of isotropic exchange interactions.

In general, the spin-lattice relaxation time is given by,

$$\frac{1}{T_1}=\frac{2\gamma _n^2A_{}^2k_BT}{g^2\mu _B^2}\underset{q}{}\frac{\mathrm{Im}\chi ^+(q,\omega _n)}{\omega _n}.$$
(17)
here, $`\chi ^+(q,\omega )`$ is the transverse component of the dynamical susceptibility and $`\omega _n`$ is the NMR frequency. (Note again, that the present situation is not a thermal equilibrium state, so that $`\chi (q,\omega )`$ is different from those in the thermal equilibrium.) As seen in Eq. (17), $`1/T_1`$ is proportional to $`A_{}^2`$. Recalling that $`A_{}`$ is the only necessary component of the hyperfine coupling for the longitudinal component of the SN interaction, the highly anisotropic hyperfine coupling ($`A_{}/A_{}1`$) may be used to reduce $`1/T_1`$ without reducing the longitudinal component of the SN interaction. Such highly anisotropic hyperfine interaction can be realized by transfered hyperfine couplings Mila and Rice (1989).

Even with such effects, however, it might be inevitable to invoke the quantum error correction method for the unavoidable nuclear spin flips in the end Shor (1995); Steane (1996). Even so, the chain structure is fortunate for the error correction process. The error correction requires three equivalent QC’s, which are entangled like $`\alpha _{l1}\alpha _{l2}\alpha _{l3}`$ at each qubit $`l`$, where $`\alpha _{li}`$ is an eigenstate (e.g. spin-up state) at the qubit $`l`$ of the i-th QC. Such set of nuclei can be provided by the three consecutive chains. It is possible to align the qubit nuclei (see §VI) and once they are aligned, the inter-chain nuclear dipole couplings keep them entangled. (For this purpose, only the $`I^zI^z`$ component is needed. Since $`I^+I^{}`$ components make the NMR line broad, they should be eliminated by applying a small field gradient in this direction.)

## VI Nuclear alignments

So far, we have described the model for a single QC. Unfortunately, the sensitivity of the conventional NMR method is not high enough to detect signals from a single QC, so that one needs to integrate many equivalent QC’s to obtain the results of computations. In this process, the nuclear alignment can help us to reduce the number of equivalent nuclei required for each qubit. It is also advantageous for obtaining a narrower NMR line.

The nuclear alignment is also associated with the qubit initialization. Although the qubit initialization may be achieved by the pseudo-pure state technique Gershenfeld and Chuang (1997) and/or the algorithmic cooling Schulman and Vazirani (1999); Ladd et al. (2001), aligning nuclear spins, even partially, can assist the methods to work in the systems with the large number of qubits ($`N`$), because the number of QC’s which happen to be in the pure state in the thermal equilibrium is proportional to $`(\mathrm{}\omega _n/2k_BT)N/2^N`$, which becomes smaller and smaller as increasing $`N`$. The nuclear alignment can relieve this problem.

Here, we propose a possible configuration of a “qubit initializer”, which partially aligns the qubits in the spin chains by the optical pumping technique Tycko (1998). The scheme enables us to separate the materials responsible for the initialization and computation, so that one can optimize the computation part without being restricted by the initialization scheme. The schematic illustration is shown in Fig. 5. Films made of spin chains are sandwiched by Si single crystals and placed in a field gradient and at a low temperature. The electrons in the semiconducting Si matrix are polarized by a circularly polarized near-infrared laser light with an energy corresponding to the semiconducting gap of Si Lampel (1968); Meier and Zakharchenya (1984), and the polarizations of the electrons are transfered to the nuclear spin systems of the spin chains through the hyperfine couplings Michal and Tycko (1998, 1999); Farah et al. (1998), or the cross-polarization /coherent transfer techniques Slichter (1990). Here, the films and the Si matrix are not necessarily bonded chemically but contacted mechanically, because the direct dipolar couplings are available for the polarization transfer process Tycko (1998).

After the nuclear alignment is completed, the laser light is shut off. The excited electrons in the Si matrix will die out quickly and the Si matrix will return to the silent environment. Here, the Si matrix is selected because the abundant nuclei (28Si) have no spins ($`I=0`$). Since the optical pumping is effective in most of the semiconductors Meier and Zakharchenya (1984), other semiconductors with no nuclear spins can be used as well. For example, CdTe enriched by the isotopes with no nuclear spins, such as 110,112,114Cd and 126,128,130Te is also available.

## VII Practical issues in the implementation

We have shown an ideal model for the NMR QC so far, but one might notice some practical issues to implement this model. First of all, one should find a suitable spin chain system with a singlet ground state, containing more than two stable isotopes for one element, one of which has $`I=1/2`$. Moreover, the periodical placements of the 1/2 nuclear spins may require some ingenious techniques.

One of the possible candidates for the QC would be a film made of some organic materials with spin gaps. They contain 1H and 13C having $`I=1/2`$. They also have large unit cells, which are useful to reserve large spacial distances between qubits. Moreover, one could utilize a well-established chemical technique of the selective isotope replacement of 1H by 2D ($`I=1`$) Aonuma et al. (1993) or 12C ($`I=0`$) by 13C ($`I=1/2`$). The periodic placements of the qubits may be achieved with the epitaxial growth Schuerlein et al. (1995) and/or the Langmuir-Blodgett methods as follows. One prepares two sets of molecules with the same chemical formulas but different isotopes by the selective isotope replacement technique, for example, all deuterized samples and those having 1H’s at one of the hydrogen sites. These two sets of molecules could be layered epitaxially using the MBE or the Langmuir-Blodgett method so as for 1H’s or 13C’s to be placed periodically.

In order to avoid unnecessary nuclear couplings, the nuclei other than qubits are preferable to have no spins ($`I=0`$). In this sense, it is fortunate that major abundant isotopes in organic materials such as 12C and 16O have no spins. The Haldane systems such as NENP and NINO are also fortunate because they contain 58Ni, an abundant isotope with no spins. In addition, a high power decoupler and/or a decoupling sequence between unlike-spins using a train of $`\pi `$-pulses can counteract the effects of the nuclei with $`I0`$ such as 2D.

###### Acknowledgements.

We wish to acknowledge helpful advices by G. Kido and M. Kitagawa. This work has been supported by CREST of JST (Japan Science and Technology Corporation).


format: text

text:
# Detection of Topological Patterns in Complex Networks: Correlation Profile of the Internet

## Abstract

A general scheme for detecting and analyzing topological patterns in large complex networks is presented. In this scheme the network in question is compared with its properly randomized version that preserves some of its low-level topological properties. Statistically significant deviation of any measurable property of a network from this null model likely reflect its design principles and/or evolutionary history. We illustrate this basic scheme on the example of the correlation profile of the Internet quantifying correlations between connectivities of its neighboring nodes. This profile distinguishes the Internet from previously studied molecular networks with a similar scale-free connectivity distribution. We finally demonstrate that clustering in a network is very sensitive to both the connectivity distribution and its correlation profile and compare the clustering in the Internet to the appropriate null model.

89.75.-k, 89.70.+c, 05.10.-a, 05.65.+b

Keywords: Random networks, scale free networks, correlation profile, cliquishness, metropolis, network motifs.

Networks have emerged as a unifying theme in complex systems research. It is in fact no coincidence that networks and complexity are so heavily intertwined. Any future definition of a complex system should reflect the fact that such systems consist of many mutually interacting components. These components are not identical as say electrons in condensed matter physics. Instead each of them has a unique identity separating it from others. The very basic question one may ask about a complex system is which other components a given component interacts with? Systemwide this information can be visualized as a graph whose nodes correspond to individual components and edges to their mutual interactions. Such a network can be thought of as a backbone of the complex system along which propagate various signals and perturbations.

Living organisms provide us with a quintessential paradigm for a complex system. Therefore, it should not be surprising that in biology networks appear on many different levels: from genetic regulation and signal transduction in individual cells, to neural system of animals, and finally to food webs in ecosystems. However, complex networks are not limited to living systems: in fact they lie at the foundation of an increasing number of artificial systems. The most prominent example of this is the Internet and the World Wide Web being correspondingly the “hardware” and the “software” of the network of communications between computers.

An interesting common feature of many complex networks is an extremely broad, often scale-free, distribution of connectivities (defined as the number of immediate neighbors) of their nodes . While the majority of nodes in such networks are each connected to just a handful of neighbors, there exist a few hub nodes that have a disproportionately large number of interaction partners. The histogram of connectivities is an example of a low-level topological property of a network. While it answers the question about how many neighbors a given node has, it gives no information about the identity of those neighbors. It is clear that most of non-trivial properties of networks lie in the exact way their nodes are connected to each other. However, such connectivity patterns are rather difficult to quantify and measure. By just looking at many large complex networks one gets the impression that they are wired in a rather haphazard way. One may wonder which topological properties of a given network are indeed random, and which arose due to evolution and/or fundamental design principles and limitations? Such non-random features can then be used to identify the network and better understand the underlying complex system.

In this work we propose a universal recipe for how such information can be extracted. To this end we first construct a proper null randomized model of a given network. As was pointed out in , broad distributions of connectivities in most real complex networks indicate that the connectivity is an important individual characteristic of a node and as such it should be preserved in any meaningful randomization process. In addition to connectivities one may choose to preserve some other low-level topological properties of the network. Any higher level topological property, such as e.g. the pattern of correlations between connectivities of neighboring nodes, the number of loops of a certain type, the number and sizes of components, the diameter of the network, spectral properties of its adjacency matrix, can then be measured in the real complex network and separately in an ensemble of its randomized counterparts. Dealing with the whole ensemble allows one to put error bars on any quantity measured in the randomized network. One then concentrates only on those topological properties of the complex network that significantly deviate from the null model, and, therefore, are likely to reflect its basic design principles and/or evolutionary history.

The local rewiring algorithm that randomizes a network yet strictly conserves connectivities of its nodes  consists of repeated application of the elementary rewiring step shown and explained in detail in Fig.1.

It is easy to see that the number of neighbors of every node in the network remains unchanged after an elementary step of this randomization procedure. The directed network version of this algorithm separately conserves the number of upstream and downstream neighbors (in- and out-degrees) of every node.

Another simple numerical algorithm generating such a random network “from scratch” was proposed in . It starts with assigning to each node a number $`k_i`$ of “edge stubs” equal to its desired connectivity. A random network is then constructed by randomly picking two such edge stubs and joining them together to form a real edge connecting these two nodes. One of the limitations of this “stub reconnection” algorithm is that for broad distribution of connectivities, which is usually the case in complex networks , the algorithm generates multiple edges joining the same pair of hub nodes. This problem cannot be avoided by simply not allowing multiple edges to form during the reconnection process as in this case the whole algorithm would get stuck in a configuration in which the remaining edge stubs have no eligible partners. Fortunately the local rewiring algorithm  instead of completely deconstructing a network and then randomly putting it back together, only gradually changes its wiring pattern. Hence, any topological constraint such as e.g. that of no multiple edges, or no disconnected components, can be maintained at each step of the way.

Once an ensemble of randomized versions of a given complex network is generated, the abundance of any topological pattern is compared between the real network and characteristic members of this ensemble. This comparison can be quantified using two natural parameters: 1) the ratio $`R(j)=N(j)/\overline{N_r(j)}`$, where $`N(j)`$ is the number of times the pattern $`j`$ is observed in the real network, and $`\overline{N_r(j)}`$ is the average number of its occurrences in the ensemble of its random counterparts; 2) the Z-score of the deviation defined as $`Z(j)=[N(j)\overline{N_r(j)}]/\mathrm{\Delta }N_r(j)`$, where $`\mathrm{\Delta }N_r(j)`$ is the standard deviation of $`N_r(j)`$ in the randomized ensemble. This general idea was recently applied to protein networks in yeast  and E. coli .

We now illustrate our general methods using the example of the Internet, defined on the level of Autonomous Systems (AS). Autonomous Systems are large groups of workstations, servers, and routers usually belonging to one organization such as e.g. a university, or a business enterprise. The data on direct connections between Autonomous Systems is regularly updated and is available on the website of the National Laboratory for Applied Network Research . Such coarse-grained structure of the Internet was a subject of several recent studies . In the following analysis we use the millennium snapshot of the Internet (data from January 2, 2000), when $`N=6474`$ Autonomous Systems were linked by $`E=12572`$ bi-directional edges.

It was recently reported  that the Internet is characterized by a scale-free distribution of AS connectivities $`p(K)1/K^\gamma =1/K^{2.1\pm 0.2}`$. One can show that for such a scale-free network the above mentioned constraint of no multiple connections between nodes is extremely important. Indeed, the connectivity of two largest connected hubs in a scale-free networks scales as $`k_{max}N^{1/(\gamma 1)}`$. In an uncorrelated random network with no constraints on edge multiplicity the expected number of edges connecting these two hubs scales as $`k_{max}^2/(2E)N^{2/(\gamma 1)1}`$ and increases indefinitely for $`\gamma <3`$ (here we assumed that $`EN`$). For the Internet that corresponds to two largest hubs with connectivities of respectively $`K_0=1458`$ and $`K_1=750`$ being connected by a swooping $`K_0K_1/(2E)=1458750/(212572)=43.5`$ edges! Hence, in this case a random network ensemble generated by our local rewiring algorithm is very different from the one generated by the stub reconnection algorithm and analytically studied in .

Fig.2 shows the average connectivity $`K_1_{K_0}`$ of neighbors of nodes with the connectivity $`K_0`$ in the real Internet (squares) as well as in a typical random network with no multiple connections between nodes generated by our local rewiring algorithm (circles). From this figure it is clear that most of the $`K_1_{K_0}K_0^{0.5}`$ dependence reported in Ref.  is reproduced in our random ensemble and hence can be attributed to the effective repulsion between hubs due to the constraint of having no more than one edge directly connecting them to each other. In the absence of correlations between node connectivities by definition $`K_1_{K_0}=\mathrm{const}=K^2/K`$ . This expression, shown as a horizontal line in Fig.2, applies only to a randomized network in which multiple edges are allowed. In an ensemble of random scale-free networks with no multiple edges the conditional probability distribution $`P(K_1|K_0)`$ crosses over between $`K_1/K_1^\gamma `$ for $`K_1K_1^{}=2E/K_0`$ to $`1/K_1^\gamma `$ power law tail for $`K_1K_1^{}`$. This makes $`K_1_{K_0}`$ to asymptotically scale as $`K_0^{\gamma 3}`$. We have confirmed numerically that $`P(K_1|K_0)`$ in our randomized ensemble has a very similar shape to that observed in the real Internet .

From the above discussion one may get the impression that the topology of the Internet is in perfect agreement with its randomized version. This is however not true. Let $`N(K_0,K_1)`$ to denote the total number of edges connecting nodes with connectivities $`K_0`$, and $`K_1`$. This is an example of a higher level topological property of a complex network, which can be compared to its typical value $`\overline{N_r(K_0,K_1)}`$ in the appropriate null-model network. By comparing $`N(K_0,K_1)`$ and $`\overline{N_r(K_0,K_1)}`$ one measures the correlation profile of the complex network, formed by correlations in connectivities of neighboring nodes. In Fig.3 we visualize the correlation profile of the Internet by plotting the ratio $`R(K_0,K_1)=N(K_0,K_1)/\overline{N_r(K_0,K_1)}`$. Regions on the $`K_0K_1`$ plane, where $`R(K_0,K_1)`$ is above (below) 1 correspond to enhanced (suppressed) connections between nodes with these connectivities in the Internet compared to its randomized counterpart. The statistical significance of these deviations, measured by the Z-score $`Z(K_0,K_1)=(N(K_0,K_1)\overline{N_r(K_0,K_1)})/\mathrm{\Delta }N_r(K_0,K_1)`$, is shown in Fig.4 Our analysis is based on an ensemble of 1000 randomized networks with connectivities logarithmically binned into two bins per decade. In Figs.3,4 one can see several prominent features:

* Strong suppression of edges between nodes of low connectivity $`3K_0,K_11`$.
* Suppression of edges between nodes that both are of intermediate connectivity $`100>K_0,K_110`$,
* Strong enhancement of the number of edges connecting nodes of low connectivity $`3K_01`$ to those with intermediate connectivity $`100>K_110`$.

On the other hand any pair among 5 hub nodes with $`K_0,K_1>300`$ was found to be connected by an edge, both in the real network, and in a typical random sample. Hence $`R(K_0,K_1)`$ is close to 1 in the upper right corner of Fig.3.

The strong suppression of connections between pairs of nodes of low connectivity can in part be attributed to the constraint that all AS on the Internet have to be connected to each other by at least one path. We have explicitly checked that there are indeed no isolated clusters in our data for the Internet. However, when we used an ensemble of random networks in which the formation of isolated clusters was prevented at every rewiring step, we found very little change in the observed correlation profile. The division of all nodes on the Internet into three distinct groups of low-, intermediate-, and highly-connected ones visible in its correlation profile may be due to its hierarchical structure of, correspondingly, users, low-level (possibly regional) Internet Service Providers (ISP), and high-level (global) ISP. Similar hierarchical picture was recently suggested in Ref.  on the basis of the traceroute data.

It is worthwhile to note that the correlation profile of the Internet measured in this work makes it qualitatively different from yeast protein networks analyzed by us earlier . Those molecular networks are characterized by suppressed connections between nodes of very high connectivity, and increased number of links between nodes of intermediate connectivity. Thus correlation profile allows one to differentiate between otherwise very similar scale-free networks in various complex systems.

The correlation profile is by no means the only topological pattern one can investigate in a given complex network, with other examples being its spectral dimension , the betweenness of its edges and nodes , feedback, feed-forward loops, and other small network motifs . In the rest of this paper we analyze the level of clustering  of the Internet, quantified by its number of loops of length 3 (triangles). The real Internet contains $`6584`$ such loops, while its random counterparts, generated by our local rewiring algorithm, have $`8636\pm 224`$ triangles (this and all future results were measured in an ensemble of 100 randomized networks.) Thus the clustering of the real Internet is some 9 standard deviations below its value in a randomized network! This result is surprising because there are good reasons for the Internet to have above average level of clustering. Indeed, one expects its nodes to preferentially link according to their geographical location , general type of business or academic enterprises they represent, etc. All these factors usually tend to increase clustering . On the other hand, the correlation profile of the Internet visualized in Fig.3 naturally leads to the reduction in clustering. Indeed, the suppression of connections between nodes of intermediate connectivity in favor of nodes of low connectivity should reduce the number of triangles in the network.

In order to explore the interplay between the level of clustering in the network and its correlation profile we studied two “extremal” random networks with the same connectivities of nodes as the real Internet. The first network contained no triangles, while the second one had a swooping 59144 triangles. Both networks were generated using a simple modification of our basic local rewiring algorithm in which a rewiring step was accepted only if it did not increase (in the first case) or decrease (in the second case) the number of triangles in the network. In the first case after some transient time all triangles have disappeared from the network, at which point we measured its correlation profile (Fig.5). In the second case our algorithm was designed to generate a network with the largest possible number of triangles . Computer time limitations have forced us to stop the program when we reached 59144 triangles, which as will be shown later is rather close to the absolute maximum of 63844 triangles for a given set of node connectivities. The correlation profile of this very clustered network is shown in Fig.6. From Fig.5 one concludes that the correlation profile in which connections between hubs are suppressed in favor of connections between hubs and nodes of low connectivity favors a reduced number of triangles. If instead nodes with similar connectivities (including hubs) prefer to connect to each other (the light-colored area on or around the diagonal in Fig.6) the number of triangles is typically increased. This in fact can be also demonstrated analytically. Consider an edge connecting a pair of nodes with connectivities $`K_0`$ and $`K_1`$. The maximal number of triangles containing this edge is $`\mathrm{min}(K_01,K_11)`$. Indeed, in the best case scenario all $`K1`$ remaining neighbors of the smaller connectivity node are also neighbors of the larger connectivity node. Therefore, given a correlation profile specified by $`N(K_0,K_1)`$ \- the number of edges connecting nodes with connectivities $`K_0,K_1`$ \- the absolute maximum number of triangles in the network is given by $`N_\mathrm{\Delta }^{\mathrm{max}}=_{K_0,K_1}N(K_0,K_1)\mathrm{min}(K_01,K_11)/6`$. Here the factor 1/6 corrects for the fact that in our counting scheme each triangle would be counted 2 times along each of its three sides. Using identities $`\mathrm{min}(K_01,K_11)=(K_01+K_11)/2|K_0K_1|`$ and $`_{K_0,K_1}N(K_0,K_1)(K_01)=_{K_0,K_1}N(K_0,K_1)(K_11)=NK(K1)`$ one finally gets:

$`N_\mathrm{\Delta }^{\mathrm{max}}`$ $`=`$ $`{\displaystyle \frac{NK(K1)}{6}}`$ (1)
$``$ $`{\displaystyle \frac{1}{6}}{\displaystyle \underset{K_0,K_1}{}}N(K_0,K_1)|K_0K_1|.`$ (2)
The first part of this expression corresponds to a hypothetical situation of the maximal cliquishness in which all neighbors of every node are connected to each other. It is easy to see that except for some very special cases of the distribution of connectivities such maximal cliquishness can never be realized. Indeed, whenever a pair of nodes of unequal connectivities $`K_0,K_1`$ are connected to each other the second term in the Eq. 2 decreases the maximal number of triangles. Given the set of node connectivities $`K_i`$, one can easily construct the network with the largest possible number of triangles. One starts by connecting the largest hub node to other nodes in the order of decreasing connectivities. In the second round of this algorithm one selects the remaining neighbors of the second largest hub in the order of decreasing connectivity. The process continues round by round until neighbors of all nodes are specified. When a node reaches its desired connectivity it will be simply skipped during later rounds of this algorithm. One can show that the network generated by this algorithm has the smallest value of $`_{K_0,K_1}N(K_0,K_1)|K_0K_1|`$ and the largest number of triangles among all networks with a given set of node connectivities. In case of the Internet such network has $`63,884`$ triangles just below the $`N_\mathrm{\Delta }^{\mathrm{max}}=64,702`$ specified by its correlation profile. These numbers of triangles are an order of magnitude below the naive estimate $`NK(K1)/6690,000`$ traditionally used as a normalization factor in the formula for the clustering coefficient of a network . Hence, based on their definition even the loopiest network with the same node connectivities as the Internet has a clustering coefficient of only 0.09! For the “native” correlation profile of the Internet Eq. 2 predicts the maximal number of triangles close to $`24,000`$, which sets the observed level of clustering (6584 triangles) around $`27\%`$ of its maximal value for this correlation profile.

In order to check if connectivity correlations visible in the correlation profile of the internet (Fig.3) can fully account for its number of triangles we generated an ensemble of random networks that preserves not only connectivities but also the correlation profile of the complex network. To this end we used a modification of our main local rewiring algorithm. There are two principal ways in which this can be done. In the first scheme, reminiscent of generating a microcanonical ensemble in statistical physics, one allows only for those local rewiring steps that strictly conserve the number of edges $`N(K_0,K_1)`$ between nodes with connectivities $`K_0,K_1`$. This is achieved by constraining the selection of pairs of edges for the rewiring step of Fig.1 only to those connecting nodes with connectivities $`K_0,K_1`$, and $`K_0,K_1^{}`$. It is easy to see that such a local rewiring step strictly conserves $`N(K_0,K_1)`$. In practice we softened randomization constraints by coarse-graining the logarithm of connectivity to half-decade bins. Using this “microcanonical algorithm” we generated an ensemble of networks with $`4132\pm 75`$ loops. The fact that the number of loops in the real Internet (6584) is now significantly larger than in these random networks, confirms the intuitive notion that the Internet is indeed characterized by a significant degree of clustering. We have also found that this 60% increase in the level of clustering is equally spread over the whole spectrum of connectivities.

As is always the case with microcanonical algorithms one should worry if the above algorithm is ergodic. In other words there is no guarantee that in this algorithm the system does not get trapped in a disconnected component of the phase space. This is easily checked by annealing the network using a canonical Metropolis algorithm  with an energy function or Hamiltonian, which in our case can be defined as $`H=_{K_0,K_1}[N(K_0,K_1)N_r(K_0,K_1)]^2/N(K_0,K_1)`$, and sampling networks at a finite temperature $`T`$. Local moves lowering the Hamiltonian are always accepted, while those increasing it by $`\mathrm{\Delta }H`$ are only accepted with the probability $`\mathrm{exp}(\mathrm{\Delta }H/T)`$. As seen in Fig.7 the above algorithm nicely extrapolates between the microcanonical algorithm for small $`T`$ and the unrestricted local rewiring algorithm for large $`T`$. This confirms that our microcanonical algorithm is indeed ergodic.

Another conceivable use of the Metropolis algorithm described above is to generate an artificial network with a given distribution of connectivities $`p(K)`$ and a given correlation profile $`R(K_0,K_1)`$. To achieve this one first generates a seed network with a given $`p(K)`$, e.g. by the stub reconnecting algorithm of Ref.. This network is first annealed using the Metropolis algorithm with the energy functional punishing multiple connections between nodes. The resulting network, containing no multiple connections is subsequently annealed with another energy functional favoring the desired correlation profile. This results in an ensemble of random networks with no multiple connections between nodes and the desired correlation profile.

In summary we have proposed a general algorithm to detect characteristic topological features in a given complex network. In particular, we introduced the concept of the correlation profile, which allowed us to quantify differences between different complex networks even when their connectivity distributions are similar to each other. Applied to the Internet, this profile identifies hierarchical features of its structure, and helps to account for the level of clustering in this network.

Work at Brookhaven National Laboratory was carried out under Contract No. DE-AC02-98CH10886, Division of Material Science, U.S. Department of Energy.