2 ∑ j n$_{j}$ , which would contribute only a linear phase [21], With V = 0, Eq. (1) is the XX Hamiltonian, while Eq. (2) then represents free fermions. We can obtain V = 0, for example, by taking t$_{g}$ = t$_{s}$ = t and U$_{gg}$ = U$_{ss}$ = 2 U$_{sg}$ = U , so that J = 4 t $^{2}$/U [19]. When all three scattering lengths are similar in size, as e.g. in some ground-state alkali atoms, U$_{sg}$ can be reduced by shifting the s and g lattices relative to each other [22]. The free fermion ( V = 0) case can be diagonalized, ignoring boundaries, by going to k -space: actly π (other errors are still possible, as discussed be- low). This attractive feature of our gate relies on the capability of using the presence and absence of a fermion as a qubit [18, 19], which is in turn enabled by the inter- conversion between bosonic photons and fermionic spin waves [2]. This interconversion is achieved in two steps. First, photon storage and retrieval techniques [12–15] are used to interconvert between photons and bosonic spin waves, and, second, hard-core interactions between spin waves effectively endow them with fermionic character. The first step requires strong collectively enhanced cou- pling between photons and atoms [12–15], which can be achieved in recently demonstrated waveguides that trans- versely confine both atoms and photons to dimensions on the order of a wavelength [8–10]. The second step is achieved by means of strong atom-atom interactions [11, 16]. Our proposal thus bears a similarity to those of Refs. [5, 6], which also rely on strong interatomic inter- actions, but contrasts with methods where atom-photon interactions alone suffice [2, 7]. At the same time, our proposal is fundamentally different from Refs. [5, 6] in that it relies on the robustness and conceptual simplicity of fermionic exchange for achieving the nonlinear phase. where k takes N values in the first Brillouin zone from − π to π at intervals of 2 π/N , c † k = (1 $_{/}$√$_{N}$$_{)}$ ∑ j e $^{ikj}$c † $_{j}$, and the dispersion ϵ ( k ) = − 2 J cos( k ) is shown in Fig. 1(c). With all atoms in | g 〉 (denoted as | vac 〉 ) and tunnel- ing turned off, two counterpropagating photonic modes, labeled as R and L in Fig. 1(a), are incident on our 1D chain of atoms near resonance with the g - e transition [see Fig. 1(b)]. The wave packets carry photonic qubits, in which | 0 〉 ( | 1 〉 ) corresponds to the absence (presence) of a single photon in the mode. The goal is to implement a two-qubit phase gate, which puts a π phase on the state | 1 〉| 1 〉 , leaving the other three basis states ( | 0 〉| 0 〉 , | 0 〉| 1 〉 , and | 1 〉| 0 〉 ) unchanged [21]. We use two control fields Ω (one for R and one for L ) near resonance with the s - e transition [see Fig. 1(b)] applied at different angles from the side of the chain [see Fig. 1(a)] to store [12–15] the two photons into the s - g coherence over two spatially sep- arated regions. As shown below, by appropriately choos- ing the angle of incidence of the control fields, we can arrange for the R and L spin waves to be centered in k -space around k = π/ 2 and k = − π/ 2, respectively, as shown in Fig. 1(c). This ensures that the two spin waves will move through each other with maximum speed [largest possible difference of first derivatives of ϵ ( k )] and with minimal distortion [vanishing second derivative of ϵ ( k )]. Photonic band gap effects coming from the peri- odicity of atomic positions [23] can be avoided if light of different wavelengths is used for the lattice and the photons, which is typically the case in experiments [24]. The XX Hamiltonian is then turned on. Since H is diagonal in the Fourier basis [Eq. (3)], it is convenient to define, for any function q ( j ) on the sites j , its Fourier transform ˜ q ( k ) = (1 $_{/}$√$_{N}$$_{)}$ ∑ j q ( j ) e − ikj together with the usual inverse relation q ( j ) = (1 $_{/}$√$_{N}$$_{)}$ ∑ k ˜ q ( k ) e $^{ikj}$. Us- ing Eq. (3) and S + j | vac 〉 = c † j | vac 〉 , it is then easy to check that the R spin wave alone evolves in time τ as ∑ j R ( j, τ ) S j + | vac 〉 , where ˜ R ( k, τ ) = ˜ R ( k, 0) e − iτϵ ( k $^{)}$. We now assume that R ( j, 0) is centered around j = N/ 4 where V = 2 t 2 $_{g}$+ t 2 s U$_{sg}$ − 4 t 2 g U$_{gg}$ − 4 t 2 s U$_{ss}$ and J = 2 t$_{g}$t$_{s}$ U$_{sg}$ . Here ⃗ S$_{j}$ = ⃗ σ$_{j}$/ 2, where ⃗ σ$_{j}$ are Pauli operators in the { s, g } basis and S ± j = S x j ± iS y $_{j}$. It is convenient to use the Jordan-Wigner transformation [17] to map the spins onto fermions with creation operators c † $_{j}$: S + j = c † j exp ( iπ ∑ j − 1 k $_{=1}$n$_{k}$ ) and S z j = n$_{j}$ − 1 $_{2}$, where n$_{j}$ = c † $_{j}$c$_{j}$ . Then, dropping the term H = N − 1 ∑ j =1 [ − J ( S + j S − j +1 + S − j S + j $_{+1}$) + V S z $_{j}$S z j +1 ] , (1) Details of the protocol. —We begin with a bosonic two- component single-band Hubbard model in a 1D lattice, with the transverse motion frozen. There are N sites with nearest-neighbor spacing a , yielding a total length Na . The tunneling amplitudes are t$_{α}$ for species α ( α = g , s ), while the s-wave interaction energies are U$_{αα}$ for two α atoms and U$_{sg}$ for an s atom with a g atom [11]. As- suming one atom per each of N sites in the weak tun- neling limit t$_{g}$, t$_{s}$ ≪ U$_{gg}$, U$_{ss}$, U$_{sg}$ , ignoring edge effects, and dropping the term ∑ j S z j (which would contribute a simple linear phase [21]), the superexchange XXZ Hamil- tonian is ( ℏ = 1 throughout the Letter) [11, 16] Before proceeding, we note that fermionic exchange in spin chains, including their cold atom realization [19], has been suggested for use as an entangling gate in Refs. [19, 20]. The advantage of our approach is that we require neither spatially inhomogeneous coupling nor single-site addressiblity and that we extend the gate from spins to photons via photon storage techniques [12–15]. H = − J ∑ j ( c † $_{j}$c$_{j}$$_{+1}$ + c † j $_{+1}$c$_{j}$ ) + V ∑ j n$_{j}$n$_{j}$$_{+1}$. (2) H = ∑ k ϵ ( k ) c † $_{k}$c$_{k}$ , (3)