Boson sampling with ultracold atoms in a programmable optical lattice

PHYSICAL REVIEW A 110, 012615 (2024) Boson sampling with ultracold atoms in a programmable optical lattice Carsten Robens,1,2Iñigo Arrazola ,3,4Wolfgang Alt ,1Dieter Meschede ,1Lucas Lamata ,5,6 Enrique Solano,7,8,9and Andrea Alberti 1,10,11,12,* 1Institut für Angewandte Physik, Universität Bonn, Wegelerstr. 8, 53115 Bonn, Germany 2MIT-Harvard Center for Ultracold Atoms, Research Laboratory of Electronics, and Department of Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA 3Department of Physical Chemistry, University of the Basque Country UPV/EHU, Apartado 644, 48080 Bilbao, Spain 4Vienna Center for Quantum Science and Technology, Atominstitut, TU Wien, 1040 Vienna, Austria 5Departamento de Física Atómica, Molecular y Nuclear, Universidad de Sevilla, 41080 Sevilla, Spain 6Instituto Carlos I de Física Teórica y Computacional, Universidad de Granada, 18071 Granada, Spain 7Kipu Quantum, Greifswalderstrasse 226, 10405 Berlin, Germany 8IKERBASQUE, Basque Foundation for Science, Plaza Euskadi 5, 48009 Bilbao, Spain 9International Center of Quantum Artificial Intelligence for Science and Technology (QuArtist) and Physics Department, Shanghai University, 200444 Shanghai, China 10Fakultät für Physik, Ludwig-Maximilians-Universität München, 80799 München, Germany 11Max-Planck-Institut für Quantenoptik, Hans-Kopfermann-Straße 1, 85748 Garching, Germany 12Munich Center for Quantum Science and Technology, 80799 München, Germany (Received 30 January 2024; accepted 5 June 2024; published 19 July 2024) Sampling from a quantum distribution can be exponentially hard for classical computers and yet could be performed efficiently by a noisy intermediate-scale quantum device. A prime example of a distribution that is hard to sample is given by the output states of a linear interferometer traversed by Nidentical boson particles. Here, we propose a scheme to implement such a boson-sampling machine with ultracold atoms in a polarization-synthesized optical lattice. We experimentally demonstrate the basic building block of such a machine by revealing the Hong-Ou-Mandel interference of two bosonic atoms in a four-mode interferometer. To estimate the sampling rate for large N, we develop a theoretical model based on a master equation that accounts for particle losses, but does not include technical errors. Our results show that atomic samplers have the potential to achieve a quantum advantage over today’s best supercomputers with N40. DOI: 10.1103/PhysRevA.110.012615 I. INTRODUCTION The idea that quantum computers could efficiently solve problems that are believed to be intractable for classical computers is the main motivation for the development of quantum computing devices [1–3]. However, despite the impressive progress in increasing the number of qubits and extending their coherence time [4–16], building a fault-tolerant universal quantum computer is not yet within the reach of current quantum technology [17]. This fact has stimulated the development of alternative concepts of quantum computation that can be performed with noisy intermediate-scale quantum (NISQ) devices — machines that are far less demanding than a fault-tolerant quantum computer and yet can outperform the best available classical computers on specific tasks. *Contact author: [email protected] Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article’s title, journal citation, and DOI. Open access publication funded by Max Planck Society. Examples of such NISQ devices are quantum annealers [18], quantum simulators [19–27], quantum learning machines [28,29], digital-analog quantum machines [30], and quantum sampling machines [31]. A quantum sampling machine deals with the task of drawing from the probability distribution of the outcomes that are produced by measuring a quantum system in a highly entangled state. In essence, the idea is to use the randomness inherent to a measured quantum system to construct a hard- to-simulate sampling machine. Compared to other problems (e.g., decision problems), quantum sampling has the advantage that its computational complexity can be ascertained for many quantum distributions [32] by relying only on a few widely held assumptions (e.g., no collapse of the polynomial hierarchy). Knowing the computational complexity of the specific problem allows us to gain important insights into the conditions (e.g., size of the Hilbert space) and class of quantum states [33–36] required to achieve a quantum advantage over classical machines [37,38]. Quantum sampling also appeals for practical reasons because its computational hardness is generally robust to small experimental errors [39,40]. Such a natural tolerance to errors makes quantum sampling a particularly suitable task to be performed with NISQ devices. Based on these motivations, several proposals have been put 2469-9926/2024/110(1)/012615(16) 012615-1 Published by the American Physical Society CARSTEN ROBENS et al. PHYSICAL REVIEW A 110, 012615 (2024) forward, where one draws samples from the state generated by a quantum circuit such as a constant-depth quantum circuit [41–43], instantaneous quantum polynomial-time circuit [44,45], random quantum circuit [39,46–49], or linear quantum circuit of indistinguishable bosons [50], better known as a boson sampler. Bosonsampling[51] refers to the problem of sampling from the probability distribution of the outcomes generated by Nidentical, noninteracting bosons that have traveled through an M-mode interferometer, with the initial and final N-particle states being of the form of Fock states. The state of each particle evolves according to the same M×Munitary matrix U, mapping the initial into the final Mmodes of the linear interferometer. The probability of detecting a particular outcome comprising Nbosons is proportional to the absolute square of the permanent of a N×Nsubmatrix of U[52,53]. In spite of its compact analytical expression, the permanent (and likewise its absolute square) is very hard to compute, for it requires a time exponential in N[54]. In fact, even its approximation to a multiplicative factor has been shown [55] to fall into the #P-hard complexity class [56]. From a physics point of view, it is worth emphasizing that the hardness of this problem is due to the quantum statistics of indistinguishable bosons and not to interactions between particles [57,58]. A number of experiments have been reported demonstrating boson sampling in photonic quantum circuits [59–70], with the current record being N=20 photons in M=60 modes [71]. Because of losses, however, it is hard to reach in the near future a much higher number of photons in a deterministic manner. This limitation along with the development [72] of more efficient classical algorithms for simulating boson sampling have prompted the study of variants of the problem that better cope with losses, such as lossy boson sampling [73,74], scattershot boson sampling [74–77], and Gaussian boson sampling [74,78]. This latter in particular, which uses squeezed light instead of single photons, has demonstrated [79–82] a huge increase in the number of photons detected at the interferometer output, on the order of 100, leading to claims of a quantum advantage. The quantum advantage of Gaussian boson-sampling machines has been questioned, though, as it has been shown that classical sampling algorithms are able to efficiently draw samples from a sufficiently close distribution [83–86]. For random quantum circuits [48,49], likewise, effective representations of the qubits’ entangled state have been found [87,88]using tensor networks, which result in a tremendous speed-up of classical simulations, since only a tiny fraction of the Hilbert space is actually used when the gate fidelity is below a certain threshold. Such a race between quantum hardware and ever more efficient classical algorithms is indeed expected to continue in the coming years, promising new insights into what makes quantum systems advantageous from a computational complexity perspective. Remarkably, it was shown [36] based on fine-grained complexity arguments that a boson sampling quantum machine of the original type [50] with N=100 and M=500 achieves quantum advantage with respect to any (i.e., known and unknown) classical simulation algorithms. These numbers are large, yet not beyond the reach of scalable NISQ devices such as ultracold atoms in optical lattices. In this article, we propose to use ultracold atoms in state-dependent optical lattices as a scalable architecture for boson sampling with hundreds of bosons. We also report on the experimental realization of the basic building block of the proposed boson-sampling machine, demonstrating the Hong-Ou-Mandel interference between two atoms trapped in state-dependent optical lattices. In our scheme, atoms cooled into their motional ground state play the role of identical bosons, while the lattice site as well as two internal atomic states serve as the bosonic modes. Distant modes, associated with different lattice sites, are brought together by state-dependent shift operations, which are realized with polarization-synthesized optical lattices [89,90]. Modes that are spatially overlapped are coupled in pairs, by a combination of microwave and site-resolved optical pulses, realizing the analog of phase-programmable photonic quantum circuits [91,92]. It should be mentioned that based on a similar motivation to establish a quantum advantage, other NISQ proposals alternative to photonic boson samplers have been put forward in the past years relying on trapped ions [93–95], superconducting circuits [96], and neutral atoms with microwave-assisted tunneling [97]. Furthermore, after the submission of this article, the first demonstration of boson sampling using ultracold atoms has been presented [98], involving 180 atoms spread across 1000 sites in a tunnel-coupled optical lattice. This recent experiment beautifully demonstrates the potential of ultracold atoms to realize a large-scale boson-sampling device, once arbitrarily programmable quantum circuits can be created. Such arbitrary quantum circuits could be produced either using programmable tweezer arrays [99]orwithstatedependent potentials, as discussed in this article. II. BOSON SAMPLING WITH ATOMS IN OPTICAL LATTICES A boson-sampling quantum machine is in essence an M- port quantum circuit traversed simultaneously by Nidentical bosons that do not interact with each other. As there are no interactions between the particles, such a quantum circuit behaves as a linear interferometer, mapping each input mode into a superposition of the output modes, a† i→ M  j=1 Uji a† j.(1) Here, a† iis the operator creating a boson in the ith mode, and Uji is the matrix element of a unitary transformation U, which is randomly chosen from the uniform distribution (i.e., Haar measure) over all M×Munitaries. The randomness of Uensures that no particular feature can be exploited to efficiently simulate the boson sampler machine with a classical computer. By detecting the occupation of the output modes, the machine thus directly samples from the probability distribution P(n1,n2,...,nM)=|n1,n2,...,nM|U|ψ0|2. Here, ni denotes the number of bosons in the ith output mode, and |ψ0represents the initial state with Nidentical bosons, each occupying a particular input mode. According to bestknown algorithms [72], sampling from Pcannot be performed 012615-2 BOSON SAMPLING WITH ULTRACOLD ATOMS IN A … PHYSICAL REVIEW A 110, 012615 (2024) FIG. 1. Illustration of a quantum circuit based on ultracold atoms in state-dependent optical lattices. Each site accommodates two modes, |±, of the quantum circuit represented by two internal states of the atom. A representative initial state is shown, where every second mode of the circuit is occupied. State-dependent shift operations connect distant modes, while local operations couple the internal modes. Inset: Hong-Ou-Mandel interference of two indistinguishable atoms, where a combination of local phase-imprinting pulses and microwave pulses realize the equivalent of a generalized photonic beam splitter. efficiently with classical computers, as it is bound to computing the permanent of N×Nmatrices, which requires a computation time of order O(N22N)[100]. Importantly, to be hard to simulate by a classical computer, a boson sampler must have a number of modes much larger than that of particles, MN1[50]. The gold standard satisfying this condition is given by the scaling law M=N2 because it ensures that detecting two or more particles in any of the output modes has a small probability [101]. In fact, only when the output modes are singly occupied, i.e., for the so-called collision-free outcomes, does the conjectured hardness of boson sampling hold [50]. We therefore assume such a quadratic scaling in this paper. It should, however, be emphasized that this scaling has so far only been experimentally realized with a relatively small number of particles, N<10, by photonics devices [71]. In the remainder of this section, we develop a concept of how to implement such a boson-sampling quantum machine with ultracold atoms in state-dependent optical lattices. We start with the key idea of how to construct arbitrary quantum circuits, and then discuss initialization and detection. A. Arbitrary quantum circuits using polarization-synthesized optical lattices Figure 1illustrates how to “wire” an arbitrary quantum circuit using ultracold atoms in state-dependent optical lattices. The idea here is to use the lattice sites along with two internal states of the atom, |+ and |−, to represent the modes of the quantum circuit, so that M/2 lattice sites accommodate Mmodes. Modes associated with adjacent sites are connected in pairs by state-dependent shift operations. Such state-dependent shift operations can be performed using polarization-synthesized optical lattices [89]. This piece of technology relies on the synthesis of polarization states of light to create two movable, fully independent periodic potentials, V±(x)=V0 ±cos2{2π/λL[x−x±(t)]},(2) which selectively trap atoms in either the |+ or |− internal state. Here, V0 ±represents the trap depth and x±(t) the position of the respective periodic potentials, xis the coordinate along the lattice direction, and λLis the wavelength of the lattice laser. The underlying concept of state-dependent optical potentials is suited to atomic species such as Rb and Cs [102,103]. In this work, we will consider specifically the case of 133Cs, where the internal modes are the hyperfine states |+ = |F=4,mF=3and |− = |F=3,mF=3, and λL is set to the value of 870 nm, for which the trapping potential of right and left circularly polarized light selectively traps the two internal states. The lattice potentials must be chosen sufficiently deep, with V0 ±being on the order of a few hundred recoil energies, to prevent atoms from tunneling to the neighboring sites. In such a deep-lattice regime, one can shift the atoms to the adjacent sites in a state-dependent manner by simply varying the relative position, x+(t)−x−(t), as a function of time t.We have experimentally demonstrated [104] that repeated statedependent shift operations preserve the coherence between the two internal states. Furthermore, we have shown in a recent work [105] that shifting the atoms by one lattice site can be rapid, with the minimum duration being bounded by the trap period at around 10 µs. Crucially, a quantum circuit such as the one in Fig. 1, where the modes are locally coupled in alternating pairs, allows one to realize any arbitrary M×Munitary transformation Uof the input into the output modes [106,107]. For a generic matrix U, a minimum number M(M−1)/2 of local operations Tis required, arranged in a circuit of M-step depth [107]. Such an operation Tdefines the basic unit of the quantum circuit, coupling together the modes |± associated with a given lattice 012615-3 CARSTEN ROBENS et al. PHYSICAL REVIEW A 110, 012615 (2024) site, T=e−iφcos(θ/2) −sin(θ/2) e−iφsin(θ/2) cos(θ/2) ,(3) where φand θare parameters depending on the particular site and time step. A programmable quantum device of this kind is said to be completely controllable [108]. We propose to implement Tthrough composite pulses, where two types of elementary operations are stacked together: local phase imprints A(ϕ) and global Hadamard pulses H. In fact, for any T, one can find suitable angles θand φ yielding the following decomposition: T=e−iφ/2T=e−iφ/2H†A(θ)HA(φ),(4) where A(ϕ)=exp[−iσzϕ/2] imprints onto the two modes |± a relative phase depending on the lattice site, whereas H=exp(−iσxπ/4) acts on all sites identically, realizing the equivalent of a beam splitter (here, σirepresent the Pauli matrices). Note that the local common-mode phase shift by φ/2, which appears in Eq. (4), can be avoided by conveniently adapting the algorithm by Clements et al. [107]touseT instead of Tas the basic unit. The decomposition of Tin Eq. (4) reveals a direct analogy to phase-programmable photonic circuits [91,92]. Their structure reveals, however, an important difference: for ultracold atoms, a single spatial dimension suffices to wire the circuital modes, whereas at least two dimensions are necessary for photonic devices [70]. The advantage of ultracold atoms simply arises from the fact that massive particles can be held in a specific location by a trapping potential. The global Hadamard gates are readily implemented by means of π/2 microwave pulses, which act homogeneously on all lattice sites and require a time of order of 1µs. The local operator A(ϕ) can be realized by exploiting the differential Stark shift that is produced by an array of laser beams focused on the target lattice sites through a high-numerical-aperture objective lens [109–111]. Exploiting the vector polarizability of alkali atoms [102], one can imprint a purely differential phase shift ϕonto the atoms by means of a circularly polarized light field. For Cs atoms, this condition is fulfilled when the wavelength of the addressing light field is chosen at λA= 880 nm. Such local pulses also require that the addressing beam has a nonzero component along the quantization axis. This additional condition can be met by tilting the quantization axis with respect to the lattice direction (see Appendix A). The differential phase shift ϕis directly controlled by the product of the laser intensity and pulse duration. We estimate that the addressing pulses A(ϕ) can be realized in about 1 µs using approximately 10 µW of laser power per addressed lattice site. These pulses have a small impact on the coherence time of the atoms, because the probability that an atom scatters a photon off the addressing beam is approximately 4 ×10−5. It is worth noting that the composite pulse scheme proposed to implement Toffers an important advantage over other schemes that use local resonant pulses to couple the two hyperfine states, |±. The reason for this is the difference in sensitivity to the crosstalk caused by the light field at the sites adjacent to the target lattice site. Differential Stark shift pulses, as in the proposed scheme, depend on the intensity of the addressing laser beams in their Hamiltonian, while resonant pulses directly depend on the respective electric fields. This different sensitivity implies that for the same intensity Ileaking to the neighboring sites, crosstalk errors are smaller in the proposed scheme: the crosstalk infidelity is proportional to I2in the proposed scheme, in contrast to Iin the resonant pulse schemes. B. Initializing an array of identical atoms Atom sorting techniques have been demonstrated [90,112– 116] where movable optical potentials are used to deterministically fill a predefined array of optical traps with one atom each. Recently, it has become possible to achieve densely packed arrays with more than 1000 atoms [117,118]. Once loaded into the desired sites of an optical lattice, atoms can be cooled to their motional ground state using sideband cooling techniques, making them indistinguishable in their mechanical degrees of freedom. Ground-state probabilities above 90% have already been achieved for atoms trapped in optical tweezers [115,119–121], whereas higher values above 99% are expected [122] for more tightly confined atoms in a threedimensional optical lattice. C. Detection of individual atoms The final state is measured by recording a fluorescence image of the atoms [111,123]. Using a high-resolution objective lens, the positions of the individual atoms in the optical lattices can be reconstructed with a high fidelity, exceeding 99%. Standard fluorescence-imaging techniques, however, only give information about the occupation of modes belonging to distinct lattice sites. To also resolve the occupation of modes associated with the same site, a state-sensitive detection scheme resolving the two hyperfine states, |±, is needed. For this purpose, a long-distance state-dependent transport operation can be used to realize an optical Stern-Gerlach detection, mapping the two internal states to different lattice sites [124,125]. Alternatively, one can use a magnetic Stern- Gerlach detection scheme in a multilayer optical lattice [126]. A particle number resolving detection is more demanding. Standard fluorescence imaging is not suitable because of light-induced collisions, which only allow the parity of the occupation number to be measured [127]. One approach is to distribute the atoms to multiple sites prior to fluorescence imaging [128], similar to spatial multiplexing in photonic devices [63]. An improved version of this approach consists of using a pinning lattice to detect the atoms [129,130]. Alternatively, one can exploit the interaction blockade to induce occupation-dependent tunneling to distinct sites of an optical lattice [126]. III. SCALING LAW OF AN ATOM-BOSON-SAMPLING MACHINE To appreciate the quantum advantage of an atom boson sampler over classical machines, we study in this section the sampling rate Ras a function of the number of bosons. 012615-4 BOSON SAMPLING WITH ULTRACOLD ATOMS IN A … PHYSICAL REVIEW A 110, 012615 (2024) A. Ideal boson sampler In the ideal case of no atom losses, the sampling rate is simply given by the repetition rate Rrep at which Nbosons are made to interfere with each other in a quantum circuit of M modes. Three terms determines this rate, R−1 rep =tinit +texec +tdet,(5) where tinit is the time for preparing the initial state of Natoms, texec is the time for executing the quantum circuit, and tdet is the time for detecting the atoms in the Moutput modes. To estimate the execution time texec, we assume that local Stark shift pulses can be carried out in parallel by optically addressing all sites simultaneously [16,131]. The time for executing the quantum circuit is thus proportional to the total number of steps, which in turn is equal to the number of modes M(see Sec. II A). Considering that the number of modes is given by M=N2, as previously reasoned, we find that the execution time has a quadratic dependence on the number of bosons, texec =N2tstep, where tstep is the time to perform the single step. The initialization time tinit is proportional to Nfor linear atom sorting [112,113], and to log(N) for parallel atom sorting [90]. For simplicity, we assume that this time is fixed at 500 ms, since the initialization of 100 atoms can be efficiently performed in less than this time [27]. Likewise, we consider the detection time to be fixed, tdet =100 ms, since both positions and spin can be efficiently detected for all atoms in a single operation relying on fluorescence imaging [124,125]. Furthermore, if we postselect only those events with all atoms populating a different output mode (i.e., the so-called collision-free events), because these are the events hard to simulate with a classical machine, the sampling rate is reduced by a constant factor 1/ein the limiting case of large N[101], leading to Rideal ≈Rrep/e. Thus, we conclude that under ideal conditions, an atom boson sampler can draw events from the boson distribution efficiently, since its computation time 1/Rideal scales with N2 for sufficiently large N(i.e., polynomial time complexity). In contrast, classical computer simulations require an exponentially longer time to perform the same task, which scales with O(N22N)[72] (see Sec. II). B. NISQ boson sampler In a realistic scenario typical of NISQ devices, the sampling rate is significantly degraded by state preparation errors, atom losses while executing the quantum circuit, and detection inefficiency. Along the lines of Refs. [68,72], we estimate the sampling rate as RNISQ =(ηinitηdet)NPsurv Rideal,(6) where ηdet is the detection efficiency, ηinit the cooling efficiency into the motional ground state, and Psurv the probability that all Natoms survive. As reasoned in Sec. I, we only consider the case where no particle is lost. Equation (6) immediately reveals that the computation time 1/RNISQ scales exponentially with the number of particles. It is therefore important to carefully evaluate the expression in Eq. (6) to determine the conditions when an atom boson sampler offers a quantum advantage over classical computer simulations. As described in Sec. II, cooling and detection of ultracold atoms can be done efficiently, with reported values of ηinit and ηdet above 90% [115,119–121] and 99% [124], respectively. The survival probability Psurv in Eq. (6) depends on two main loss mechanisms, which we discuss below. The first mechanism responsible for the loss of atoms is collisions between one of the Ntrapped atoms and a particle from the background gas at room temperature, causing the atom involved in the collision to be ejected from the trap. For Natoms, the probability that no collision with the background gas occurs during a single step is given by the exponential formula PBG step =exp (−Ntstep/τBG ), where τBG is the background-gas-limited mean lifetime of a single atom. The second mechanism leading to the loss of atoms is given by inelastic collisions of atoms occupying the same lattice site. Inelastic collisions cause the atoms to change their hyperfine state [132–134], and to acquire kinetic energy, thus leaving the motional ground state where they are initially prepared. Such inelastic collisions typically result in the loss of atoms from the trap because of the large energy separation between hyperfine states (several MHz between adjacent mFstates, 9.2 GHz between different Fstates, expressed in frequency units). Three-body collisions are neglected because the probability of three (and more) particles occupying the same lattice site compared to that of pairs is negligible in the limit of a large number of modes (see Appendix B). To account for the two-atom lossy collisions, we introduce the survival probability of a pair of atoms located in the same lattice site, given by exp (−t/τTB), where τTB is the mean lifetime limited by two-body collisions. Note that for simplicity we use the same constant τTB without differentiating between the three possible spin configurations of the two bosons occupying the same site. To estimate the number of pairs of atoms that can collide on site, we make the conservative assumption that all states of Nbosons have equal probability of being occupied at every time step. This is a conservative assumption, which overestimates the probability of inelastic collisions at the initial steps since the atoms are first prepared in different sites. Based on these assumptions, the probability of finding ksites occupied by exactly a pair of atoms can be estimated as Pk=e−3/2(3/2)k/k! (see Appendix B). For example, P0is the probability of the collisionless subspace, where all atoms occupy distinct lattice sites. Thus, the survival probability per time step, limited by two-body lossy collisions, is obtained by the evaluating the following sum: PTB step = N/2  k=0 Pke−ktstep τTB ≈exp 3 2e−tstep τTB −1,(7) where the expression on the right-hand side holds in the limit of large N(see Appendix B). For weak two-body losses, tτTB, the survival probability PTB step decays as exp [−3tstep/(2τTB)], while in the limiting case of strong losses the survival probability approaches P0. Combining the two loss mechanisms, the survival probability per step is simply given by Pstep =PBG stepPTB step. Because the execution of the quantum circuit requires M=N2steps, the 012615-5 CARSTEN ROBENS et al. PHYSICAL REVIEW A 110, 012615 (2024) FIG. 2. Scaling of boson-sampling machines. Predicted sampling rate vs the number of bosons Nis shown for atomic (blue), photonic (purple), and classical (gray) boson-sampling machines. The atomic sampling is computed based on Eq. (6), where an extended model (see Appendix B)isusedforPstep to account for both particle pairs and triplets. Our atomic sampling model disregards decoherence by technical noise sources; see text. The photonic and classical curves correspond to Eqs. (C1)and(C2), respectively. Under state-of-the-art conditions, atomic NISQ devices have the potential to overtake classical algorithms at N≈37. Pioneering photonic experiments are marked with symbols [59], [60], and [61], while the best reported boson-sampling experiment is marked with [71]. Note that the photonic experimental points refer to implementations of the original boson-sampling problem, and thus do not include Gaussian boson-sampling experiments, for the reasons presented in Sec. I. Our proof-of-principle experiment, described in Sec. IV, is marked with . The numerical results obtained with the master equation approach (see Appendix D) are indicated with , with the vertical bars indicating the 1-σstatistical uncertainty. total survival probability of Natoms (where N1) is thus Psurv =(Pstep )M =exp −N3tstep/τBG +N2(3/2)e−tstep τTB −1.(8) A comparison of the two terms in Eq. (8) shows that under typical conditions tstep τTB τBG two-body collisions are the dominant loss mechanism for N<Nthreshold = 3τBG/(2τTB). As will be argued below, realistic experiments are expected to operate with a number of atoms below this threshold. To evaluate RNISQ in Eq. (6), we consider two different scenarios, which are based on conservative and state-of-the- art assumptions, respectively. In the conservative scenario, we assume a step duration tstep =170 μs and a mean lifetime limited by two-body collisions τTB =40 ms, while in the state-of-the-art scenario, we consider tstep =33 μs and τTB =400 ms. For the initialization and detection times, we assume tinit =500 ms and tdet =100 ms, with efficiencies of ηinit =0.90 and ηdet =0.99 for the conservative scenario, and ηinit =ηdet =0.99 for the state-of-the-art scenario. For the mean lifetime limited by background gas collisions, we take τBG =360 s in both scenarios. The threshold value Nthreshold is larger than 1000 atoms in both scenarios, implying that for a realistic number of atoms the dominant loss mechanism is inelastic two-body collisions rather than collisions with the background gas. In Fig. 2, we show the sampling rate RNISQ as a function of the number of particles N, computed for an atom boson sampler with conservative and state-of-the-art assumptions (blue curves). To identify the regime of potential quantum advantage, we present in the same figure the sampling rate Rclassical of best algorithms [72] simulating a boson sampler using a standard laptop and the Tianhe-2 supercomputer (gray curves). For the sake of comparison, we also report in the figure the sampling rate expected for NISQ photonic devices (purple curves) for a conservative and state-of-the-art scenario; see Appendix Cfor details. To validate our model of the sampling rate RNISQ in Eq. (6), we have carried out exact numerical simulations based on a master equation approach (Appendix D)forNup to 4. The result of the numerical simulations (blue squares in Fig. 2) shows a very good agreement with the curves from the model. In the scenario of N=50, which is relevant for quantum advantage, we find that the sampling rate of the fastest atomic sampler proposed in this work (tstep =33 μs) is dominated by initialization and detection times. We expect a different situation in tunnel-coupled optical lattices [98], where a tunneling event (i.e., the equivalent of a time step) takes about tstep ≈ 1 ms. For these samplers, the execution time texec =N2tstep is 012615-6 BOSON SAMPLING WITH ULTRACOLD ATOMS IN A … PHYSICAL REVIEW A 110, 012615 (2024) on the order of a few seconds for N=50 particles and will likely be the factor limiting the sampling rate. We should emphasize that our model takes into account interactions between atoms only through their dissipative effects, which are accounted for in Eq. (6) in terms of atom losses. The model does not consider interaction-induced phase shifts. Modeling coherent interactions between atoms requires a different approach [135], and goes beyond the scope of this work. We expect that the interaction-induced phase shifts will make this boson-sampling problem even harder to simulate on classical computers compared to its linear counterpart, as was originally proposed [55]. Finally, we would like to point out that, both in our theoretical model of Eq. (6) and in the numerical simulations, we have not considered technical errors affecting the operations during the quantum circuit. Future investigations on the scaling of atomic sampling devices will have to address not only atom losses, but also the loss of coherence. The specific technical errors will depend on the specific implementation, and a detailed analysis thereof goes beyond the scope of this work. We refer the reader to the Appendix of Ref. [136]for a discussion of the main technical decoherence mechanisms, and to Ref. [89] for a characterization of the noise sources affecting polarization-synthesized optical lattices. The present work rather focuses on quantifying the effect of fundamental errors that exist across all neutral atom platforms. IV. EXPERIMENTAL DEMONSTRATION OF THE HONG-OU-MANDEL INTERFERENCE We have performed a proof-of-principle experiment with two atoms in a four-mode interferometer, which demonstrates the Hong-Ou-Mandel effect with atoms, as schematically shown in the inset of Fig. 1. Such an experiment establishes the basic building block of the envisaged boson-sampling machine. The Hong-Ou-Mandel effect with atoms has been previously demonstrated experimentally using movable optical tweezers [137], an optical lattice superimposed to a box potential [138], and a free-fall atom interferometer [139]. Compared to these setups [140] and to related proposals based on microwave-induced tunneling [97], our setup is distinguished by the way modes are coupled, where the atoms are moved with state-dependent shift operations [89] instead of having them tunnel through an optical potential barrier. Our approach enables faster operations on the scale of a few microseconds instead of milliseconds. The setup used for our experimental demonstration is schematically depicted in Fig. 3(a). We start with a handful of Cs atoms, which are sparsely loaded in a one-dimensional polarization-synthesized optical lattice [89]. Using the atom sorting technique presented in Ref. [90], a pair of atoms is then selected and repositioned to a relative distance of 20 lattice sites with a success rate of about 99%, mainly limited by an incorrect detection of the initial distance between the two atoms [123]. To make the two atoms identical, we cool them to the ground state of the lattice site potential in which they are respectively trapped. For this purpose, we use resolved sideband cooling, where the sideband transitions are driven by FIG. 3. Experimental setup probing the Hong-Ou-Mandel interference with two atoms. (a) Atoms are trapped in a polarizationsynthesized optical lattice, formed by two optical standing waves of left (L) and right (R) circular polarization, which can be shifted by varying the optical phases φLand φR(adapted after Ref. [89]). Two Raman laser beams perform transverse sideband cooling. A spiral phase plate (SPP) generates a hollow-tube laser beam (intensity profile in the inset), enhancing the transverse confinement of the atoms. Cooling along the longitudinal and transverse directions is evidenced by the suppressed blue detuned sidebands in the (b) microwave and (c) Raman sideband spectra, respectively. microwave radiation [141] for the direction along the lattice axis and by two Raman lasers [119] for the transverse directions. The optical lattice provides a tight confinement (ν≈ 120 kHz sideband) along its longitudinal direction, while a hollow-tube potential collinear with the lattice axis also provides a tight confinement (ν⊥≈20 kHz sideband) in the transverse directions. These trap frequencies are much larger than the recoil frequency (≈2 kHz), thus ensuring that the Lamb-Dicke condition necessary for ground-state cooling is fulfilled. We alternate between microwave and Raman sideband cooling three times in order to cool the atoms in both the longitudinal and transverse directions. By allowing a slight ellipticity of the transverse potential, we lift the degeneracy of the transverse motional states, allowing Raman sideband cooling to be effective along both transverse directions. At the end of the cooling process, the atoms are polarized in state |+ = |F=4,mF=4with a probability of 99%. Note that in this section |+ refers to a different Zeeman state than the one considered in the rest of this work (cf. Sec. II A). With the mFstate chosen for the experimental demonstration, it must be taken into account that the state-dependent potentials depend on both left and right circular polarization components of the trapping light field [105]. Figures 3(b) and 3(c) report a typical microwave and Raman sideband spectrum recorded after the cooling procedure, demonstrating a pronounced suppression of the cooling (blue detuned) sideband with respect to the heating (red detuned) sideband. From the ratio of the sideband amplitudes [142], we derive a ground-state probability of ∼95% for the longitudinal direction and of ∼84% for each transverse direction. Thus, the overall probability of occupying the motional ground state can be estimated as P3D ≈95% ×84% × 84% ≈67(9)%. After sideband cooling, a magnetic field gradient along the lattice direction (11.6G/cm) is ramped up in 10 ms and 012615-7 CARSTEN ROBENS et al. PHYSICAL REVIEW A 110, 012615 (2024) maintained until detecting the atoms by fluorescence imaging. The magnetic field gradient induces a position-dependent Zeeman shift (≈1.2 kHz per lattice site), which is used to selectively transfer one of the two atoms to the |− state. We perform such a selective spin flip by addressing the target atom with a microwave narrow-bandwidth πpulse (Gaussian shape, 7-kHz rms width). Spin-flip errors are clearly visible in the final fluorescence image, allowing them to be removed by postselection. The atom thus selected is then adiabatically transported in 1 ms to the site of the second atom by shifting the V−(x) lattice potential. With the two atoms occupying the same site, we apply a fast microwave π/2 pulse (square shape, 4.8 μs duration). This pulse acts much like the beam splitter of a Hong-Ou-Mandel optical interferometer, erasing the whichway information of the two impinging particles. Last, we shift the V+(x) lattice potential to map the internal states, |+ and |−, to two different locations ten lattice sites apart, where the atoms are detected by position-resolved fluorescence imaging. Two identical atoms are expected to bunch together in the same lattice site with unit probability because of the Hong-Ou-Mandel interference (bosonic quantum statistics). In practice, however, the two atoms can differ from each other because of their motional states. For two atoms in orthogonal states (i.e., fully distinguishable particles), the outcomes resemble those obtained from the toss of two independent coins, yielding a bunching probability of 1/2 (classical statistics). For partially distinguishable atoms like ours, the probability to bunch is determined by the so-called quantum purity of the state, γ≈P2 3D, which represents the probability of the two atoms to be indistinguishable: Pbunch =γ+(1 −γ)/2. Thus, the Hong-Ou-Mandel interference is established if we can show that the bunching probability of the two atoms fulfills Pbunch >1/2. In the experiment, we distinguish three outcomes corresponding to the detection of zero, one, and two atoms in the final fluorescence image. Figure 4shows the experimentally recorded probability for each of them. When both atoms are positively detected, the atoms are found at different locations, ten sites apart (see fluorescence image in Fig. 4). Importantly, such an outcome can only occur when the two atoms have not bunched together. Its probability is thus directly related to Pbunch through the expression P2=S2(1 −Pbunch), where Sis the single-atom survival probability. From the measurement of P2=19(3)% and the independent characterization of the single-atom survival probability S=84(1)% (see Appendix E), we therefore obtain Pbunch =73(4)%, which exhibits a 5-σdeviation from the reference value 1/2. Such a value of Pbunch establishes that the Hong-Ou- Mandel interference of the two atoms occurs with a probability γ=2Pbunch −1=45(8)%, in good agreement with the value expected from the independent measurement of the ground-state fraction, γ≈P2 3D ≈45(12)%. We expect that γ can be significantly improved in the future with more efficient ground-state cooling of the atoms in a three-dimensional optical lattice. An analysis of all experimental outcomes, including those with zero and one atom detected, yields a value of Pbunch =73(6)% that is statistically consistent with the value we have derived from P2only (see Appendix E). In the future, it will be interesting to test not only the degree of indistinguishability between atoms, but also their FIG. 4. Detection of the Hong-Ou-Mandel interference. Right: measured probability for the detection of zero (P0), one (P1), or two atoms (P2). The dashed lines show the case of distinguishable particles as a reference (see Appendix E). The error bars represent the 68% Clopper-Pearson confidence intervals. Left: representative fluorescence images of the two atoms after the Hong-Ou-Mandel sequence, with the internal states |− and |+ mapped to the sites 0 and 10. When the atoms are bunched in the same site, inelastic lightinduced collisions result in either one or zero atoms being detected. Superresolution microscopy allows resolving the lattice sites despite the diffraction-limited optical resolution of approximately four sites [123]. degree of entanglement. For that, one could study crosscorrelations with a two-atom interferometer as presented in Refs. [143–146]. V. CONCLUSIONS In this work, we have presented a scheme for the realization of programmable NISQ circuits with neutral atoms in state-dependent optical lattices. Quantum circuits based on the proposed scheme can be easily reprogrammed and scaled up to hundreds of modes. Both repogrammability and scalability are key to realize large random unitaries—a prerequisite for any large-scale boson-sampling machine. Furthermore, we have experimentally demonstrated the basic building block of an atom boson-sampling machine by executing a quantum circuit with four modes and two indistinguishable atoms. We observed the atoms bunching in pairs, thus revealing their bosonic nature. The Hong-Ou-Mandel interference signal of the atom bunching is found to deviate from the outcome predicted for distinguishable (i.e., classical) particles by 5 σ. The degree of indistinguishability of the atoms is determined by the probability of occupying the motional ground state in the potential well of an optical lattice site. We independently measured the motional ground-state occupancy of the atoms and showed that it is in good agreement with the ground-state occupancy inferred from the observed bunching probability. We have discussed in detail how to wire quantum circuits using a one-dimensional state-dependent optical lattice. Our analysis of NISQ devices has shown that controlling more than M=500 lattice sites will be required to reach a quantum advantage over the best supercomputers. Controlling such a 012615-8 BOSON SAMPLING WITH ULTRACOLD ATOMS IN A … PHYSICAL REVIEW A 110, 012615 (2024) large number of lattice sites may become difficult to realize in a one-dimensional geometry. However, our scheme can be readily extended to two-dimensional state-dependent optical lattices [147], leading to a more compact and less resourceintensive platform. For future studies, it will be interesting to investigate the role of controlled coherent collisions among atoms [148], which can be exploited to imprint collisional phases onto the quantum state when two or more particles meet at the same site [149]. The inclusion of such nonlinearities is shown to augment the amount of correlations in the output distribution [135]. For this reason, there is a potential that simulating a nonlinear boson sampler with classical computers will be an even harder task than the original linear problem. Finally, we emphasize that beyond the boson-sampling application, the proposed scheme can be used to implement reprogrammable parametrized quantum circuits—a key component for quantum machine learning [28,29]. Note added. Recently, the first demonstration of an atomic boson sampler has been put forward [98], involving 180 atoms spread across 1000 optical tweezer sites. ACKNOWLEDGMENTS We acknowledge financial support from the NRW- Nachwuchsforschergruppe “Quantenkontrolle auf der Nanoskala,” the Deutsche Forschungsgemeinschaft SFB project OSCAR, the Basque Government with Ph.D. Grant No. PRE-2015-1-0394, the Junta de Andalucía (Grants No. P20-00617 and No. US-1380840), the Spanish Ministry of Science, Innovation, and Universities (Grants No. PID2019- 104002GB-C21 and No. PID2019-104002GB-C22), the National Natural Science Foundation of China (Grant No. 12075145), and Science and Technology Commission of Shanghai Municipality (Grant No. 2019SHZDZX01-ZX04). A.A. acknowledges support from the Alexander von Humboldt Foundation, I.A. from the European Union’s Research and Innovation Programm (Grant No. SuperQuLAN 899354), and C.R. from the Studienstiftung des deutschen Volkes (Grant No. 421987027). C. R. and I. A. contributed equally to this work. APPENDIX A: QUANTIZATION AXIS The propagation direction of the addressing beam must be perpendicular to the optical lattice itself in order to allow it to be tightly focused on the individual sites of the lattice itself. The only way to satisfy this geometric condition and the condition stated in Sec. II A that the quantization axis must have a nonzero component along the addressing beam is to have the quantization axis form an angle α= 0 with the direction of the optical lattice. However, tilting the quantization axis by αwith respect to the optical lattice laser beams causes a wobbling of the optical lattice potential depth, V0 ±, during the statedependent shift operations. Because of this wobbling, the lattice depth is reduced by a factor |cos(α)|during transport. The extent of this effect is very small for small angles. For example, for α=15 ◦the lattice depth is reduced by only ∼3%. This wobbling can be easily taken into account and compensated for in the design of transport operations by optimal control [105]. APPENDIX B: PAIR DISTRIBUTION AND EXTENDED MODEL In the limit of large Nand after averaging over random quantum circuits, the state of the Nbosons is described by a uniform statistical mixture ρu, where all possible configurations of the Nbosons over the Mmodes are equally weighted [101]. Using this result, we derive a general expression P(k2,k3) to account for the probability of finding exactly k2sites occupied by a pair and k3sites occupied by a triplet, whereas the other sites are singly occupied. To calculate P(k2,k3), we first determine the number of configurations containing k3sites occupied by a triplet of atoms. For that, we consider that there are M/2 k3possible combinations to arrange k3triplets in M/2 sites, where we assume for simplicity that the overall number of modes Mis even. Given the two spin states, for each site occupied by a triplet, we have 2 3=4 possible spin configurations, where the double brackets denote the multiset coefficient. Thus, the previous number of combinations must be multiplied by 4k3 to obtain the total number of configurations for the k3triplets. Next, we consider that there are M/2−k3 k2combinations to arrange k2pairs in the remaining M/2−k3 sites. This number must be multiplied by 3k2to account for the 2 2 =3 different spin configurations for each pair. Now, there are M/2−k2−k3 N−2k2−3k3 different combinations to place the remaining N−2k2−3k3 particles in the rest of the sites. For each singly occupied site, there are only two possible spin configurations. Finally, to obtain the probability P(k2,k3), all the configurations should be divided by the overall number of possible bosonic configurations, which is given by the multiset coefficient M N. Hence, the probability of having exactly k2sites occupied by pairs and k3sites occupied by triplets is given by P(k2,k3)=4k3M/2 k33k2M/2−k3 k22N−2k2−3k3 ×M/2−k2−k3 N−2k2−3k3M N.(B1) In the limit of large N, the expression in Eq. (B1) yields a vanishing probability to have k3>0 triplets, limN→∞ P(k2,k3>0) =0. Instead, when k3=0, Eq. (B1) converges to a Poisson distribution for the occurrence of k2pairs, lim N→∞ P(k2,0) =λk2 eλk2!,(B2) with average value λ=3/(2c). Here, the constant factor c denotes the ratio c=M/N2, which in the main text has simply been assumed equal to 1. Figure 5shows the distributions P(k2,0) (left panel) and P(0,k3) (right panel) for an increasing number of particles N=3,9, and 27, assuming c=1. The graphs show that the probability associated with the collision-free subspace, P(0,0), tends to the finite value exp[−3/(2c)]. We also notice that for a relatively small number of particles N10, the probability of finding a triplet, P(0,1), has a non-negligible value between 0.05 and 0.1. 012615-9 CARSTEN ROBENS et al. PHYSICAL REVIEW A 110, 012615 (2024) [148] C. Chin, R. Grimm, P. Julienne, and E. Tiesinga, Feshbach resonances in ultracold gases, Rev. Mod. Phys. 82, 1225 (2010). [149] O. Mandel, M. Greiner, A. Widera, T. Rom, T. Hänsch, and I. Bloch, Controlled collisions for multi-particle entanglement of optically trapped atoms, Nature (London) 425, 937 (2003). [150] N. Schlosser, G. Reymond, I. Protsenko, and P. Grangier, Subpoissonian loading of single atoms in a microscopic dipole trap, Nature (London) 411, 1024 (2001). 012615-16