Quantum computers can solve certain problems more efficiently than any possible conventional computer. Small quantum algorithms have been demonstrated on multiple quantum computing platforms, many specifically tailored in hardware to implement a particular algorithm or execute a limited number of computational paths [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] . Here, we demonstrate a five-qubit trappedion quantum computer that can be programmed in software to implement arbitrary quantum algorithms by executing any sequence of universal quantum logic gates. We compile algorithms into a fully-connected set of gate operations that are native to the hardware and have a mean fidelity of 98 %. Reconfiguring these gate sequences provides the flexibility to implement a variety of algorithms without altering the hardware. As examples, we implement the Deutsch-Jozsa (DJ) [11] and Bernstein-Vazirani (BV) [12] algorithms with average success rates of 95 % and 90 %, respectively. We also perform a coherent quantum Fourier transform (QFT) [13, 14] on five trappedion qubits for phase estimation and period finding with average fidelities of 62 % and 84 %, respectively. This small quantum computer can be scaled to larger numbers of qubits within a single register, and can be further expanded by connecting several such modules through ion shuttling [15] or photonic quantum channels [16] . Implementing a scalable programmable quantum computing architecture requires high fidelity initialization and detection at the individual qubit level and pristine control of interactions between qubits. While most physical platforms have nearest-neighbor interactions only, a multi-qubit trapped-ion system features an intrinsic longrange interaction that is optically gated and connects any pair of qubits [17, 18] . Unlike solid-state implementations [19, 20] , the quantum circuitry is determined by external fields, and hence can be programmed and reconfigured without altering the structure of the qubits themselves. By optically resolving individual ions, we implement single-qubit rotations and arbitrary two-qubit gates by directly addressing pairs of ions without additional overhead such as moving information through local couplings [19, 21] or hiding qubit populations in additional auxiliary states [10] . Such native gates can then be used to construct modular logic gates that can be called in reconfigurable algorithm sequences. We observe A linear chain of trapped ion qubits along the Z-axis is shown at the center of the figure. An imaging objective collects ion fluorescence along the Y-axis and maps each ion onto a multichannel photo-multiplier tube (PMT) for measurement of individual qubits. Counterpropagating Raman beams along the X-axis perform qubit operations. A diffractive beam splitter creates an array of static Raman beams that are individually switched using a multi-channel acousto-optic modulator (AOM) to perform qubit-selective gates. By modulating appropriate addressing beams, any single-qubit rotation or twoqubit Ising (XX) gate can be realized. For the two-qubit gates between qubits i and j, we can continuously tune the nonlinear gate angle χij. This represents a system of qubits with fully connected and reconfigurable spin-spin Ising interactions (inset). a mean fidelity of 98% in these native operations without the use of spin echo or dynamical decoupling techniques [10, 22, 23] . This bottom-up approach can be adapted for arXiv:1603.04512v3 [quant-ph] 3 Aug 2016 2 large scale computation using micro-fabricated ion traps with integrated optics [25] and high optical access, and we expect gate fidelities can exceed 99.9 % with straightforward improvements on the classical control [23, 24] . The programmable and reconfigurable nature of the ion trap quantum computer is illustrated by a hierarchy of operations from software to hardware, shown in figure 1a. At the top is a high-level user interface that specifies the desired algorithm, represented by a standard family of modular universal logic gates such as Hadamard (H), controlled-NOT (CNOT), and controlled-phase (CP) gates [14] . Next, a quantum compiler translates the universal gates into gates native to the hardware, which in our case are two-qubit Ising (XX) gates [18] and single-qubit rotation (R) gates [14] . Finally, these native gates are decomposed into laser pulses that are pre-calculated to effect the desired qubit operation through the Coulomb-coupled motion while disentangling the motion at the end of the gates [26] . At the hardware level, the processor consists of trapped 171 Yb + atomic ion qubits with information stored in the hyperfine "clock" states |0 ≡ |F = 0; m F = 0 and |1 ≡ |F = 1; m F = 0 of the 2 S 1/2 electronic ground level with a qubit frequency splitting of ν 0 = 12.642821 GHz [27] . Here, F and m F denote the quantum numbers associated with the total atomic angular momentum and its projection along the quantization axis defined by an applied magnetic field of 5.2 G. We measure a qubit coherence time in excess of 0.5 s, and with magnetic shielding we expect this to improve to be longer than 1000 s [28] . We confine the ions in a linear radio frequency (rf) Paul trap, with radial and axial trap frequencies ν x = 3.07 MHz and ν z = 0.27 MHz, respectively. The ions are laser-cooled to near their motional ground state and form a linear crystal with a spacing of ∼ 5µm for n = 5 ions. A computation is performed by first initializing all qubits to state |0 through optical pumping [27]. This is followed by quantum gates, implemented by a series of coherent rotations using stimulated Raman transitions driven by a 355nm mode-locked laser, where the beat-note between two counterpropagating Raman beams drives qubit and motional transitions [29] . To achieve individual addressing, we split one of the Raman beams into a static array of beams, each of which is directed through an individual channel of a multi-channel acousto-optic modulator (AOM) and focused onto its respective ion, as shown in figure 1b. Finally, the qubit register is measured with high fidelity (see methods) by driving the 2 S 1/2 → 2 P 1/2 cycling transition near 369 nm and simultaneously collecting the resulting state-dependent fluorescence from each ion using high-resolution optics and a multi-channel photo-multiplier tube (PMT). The lowest level of qubit control consists of native single-and two-qubit operations. We perform singlequbit rotations R φ (θ) by tuning the Raman beat-note to qubit resonance ν 0 . Here, the rotation angle θ and axis φ are determined by the duration and phase offset of the beat-note, which is programmed through rf signals on appropriate AOM channels. Two-qubit XXgates are performed by invoking an effective spin-spin Ising interaction between qubits mediated by the collective modes of motion of the chain [18] . Here, we apply Raman beat-notes tuned close to ν 0 ± ν x that coherently couple the spins to all modes of motion. A pulse shaping technique [26] disentangles the motion at the end of the gate, resulting in a two-qubit entangling rotation of any amount XX(χ i,j ). Here, the geometric phase χ i,j originates from the integrated Ising interaction [18, 26] , the sign α i,j = ±1 of which arises from the Coulomb interaction between qubits i and j (Fig. 1b inset) . We pre-calculate and optimize XX-gate pulse shapes off-line for all {i, j} to achieve high fidelity while keeping the gates relatively fast (see methods). We use these native R and XX-gates to construct standard logic gates, which can be called by a quantum algorithm. For instance, we implement the single-qubit Hadamard gate as H = R x (−π)R y (π/2) and the Zrotation as R z (θ) = R y (−π/2)R x (θ)R y (π/2). Two-qubit logic gates such as CP and CNOT are compiled to account for the signs of the CP rotation angle β and the Ising interaction α i,j , making them independent of {i, j} and therefore modular (Fig. 2) . At the highest level we program arbitrary sequences of such logic gates as required to implement any quantum algorithm. We first implement the Deutsch-Jozsa algorithm [11] , which determines whether a given function (the "oracle") is constant or balanced. A function that has an n-bit input and a 1-bit output (f : {0, 1, 2, ..., 2 n − 1} → {0, 1}) is balanced when exactly half of the inputs result in the output 0 and the other half in the output 1, while a constant function assumes a single value irrespective of the input. In our setup we program 7 out of the 70 possible oracles of three-qubit balanced functions by using seven different sequences of CNOT gates between each of the three qubits in the control register x = {X 1 X 2 X 3 } and the function register X 4 (Fig. 3a) . We program the two constant functions by setting X 4 to either 0 or 1. Executing the algorithm starts with preparing the control register in the superposition state |x = 1 √ 8 7 k=0 |k , followed by the function evaluation oracle. A CNOT is then performed between the function register X 4 and the ancilla qubit X 5 (initially set to 1 √ 2 (|0 −|1 )). All qubits are then rotated and measured (except for the ancilla) as shown in figure 3a . Finally, a measurement of x (conditioned upon X 4 = 1, occurring with 50% probability) determines if the function is constant or balanced. Measurement of the output x = {111} indicates a constant function, while any other value indicates a balanced function (see supplementary materials). The average success probability is 0.967(2) for constant and 0.932(3) for balanced functions (Fig. 3b) . The Bernstein-Vazirani algorithm is a variant of the DJ algorithm where the oracle function is an inner product of two n-bit strings: f c (x) = c · x. Here, the aim is to determine the vector c = {c 1 c 2 ...c n } in a single trial [12] . We program all 16 instances of the four-bit oracle that evaluate the function f c (x)⊕X 5 . This is achieved by applying a particular pattern of CNOT gates, determined by c, between x = {X 1 X 2 X 3 X 4 } and X 5 = 1 √ 2 (|0 − |1 ) (Fig 3c) . For example, if c = {0101} then CNOT gates are applied between X 2 , X 5 and X 4 , X 5 . We start with a superposition state |x = 1 √ 16 15 k=0 |k , followed by the oracle. Finally, applying a global R y (π/2) rotation produces the output statec, which is the inverse of c. In the experiment, a single-shot measurement of the correct outcomec is obtained with a probability of 0.903(2) (Fig  3d) , averaged over all possible oracle states. Exponential speed-up of many quantum algorithms arises from the fact that parallel function evaluation is C k |k . The shaded gray region contains a sequence of modular gates for implementing the QFT, which is then followed by a measurement of the register. (b) Quantum period finding. Input states are prepared using single-qubit rotations to modulate the 32 state amplitudes with periods 1, 3, 4, 8, 16, and 32 (see methods). The squared statistical overlap (SSO) [5] signifies the fidelity of the protocol where the error is a statistical estimate over 8,000 experimental repetitions. (c) Quantum phase estimation using five measurement qubits. The plot shows populations in the output state that estimates the given phase modulation φ of the input state amplitudes {C k }. We observe the correct value of the phase in each case with a probability > 0.6. The experiment is repeated 8,000 times for each value of φ. performed on a superposition of all classical input states of an n-bit string. These evaulation paths are then interfered using a quantum Fourier transform (QFT) to produce the desired solution [14] . One such example is the order-finding protocol in Shor's quantum factorization algorithm [13] . Another application is solving the eigenvalue problem A|φ = e iφ |φ , where the phase φ can be estimated to n-bit precision using an n-bit QFT [14] . These algorithms have been implemented in experiments using a semi-classical version of the QFT that consists of single-qubit rotations based on classical feed-forward and qubit recycling which reduces the required register size [5, 10, 30] . The coherent QFT, on the other hand, is reversible and can be concatenated within an algorithm sequence. Here, we construct a coherent QFT on five qubits using all 10 modular CP gates and involving a total of 80 singleand two-qubit native gates. This circuit fully exploits the high connectivity of a trapped ion system and illustrates how it can be scaled to larger modules (Fig. 4a) . We apply the QFT in a period-finding protocol where we first prepare an input superposition state 31 k=0 C k |k such that the coefficients {C k } exhibit a periodic amplitude or phase modulation (see methods), which is followed by the QFT operation. The modulation periodicity then appears in the output state populations (Fig.4.b) . We further examine the performance of the QFT in a phase estimation protocol where the eigenvalue φ is estimated to 5-bit precision. In this case the input state is prepared in the form which exhibits a φ-dependent phase modulation C k = 1 √ 32 e −ikφ . We apply the QFT on this state to estimate φ by mapping its value onto populations of the output state, as shown in figure 4c. This is repeated for several cases where φ is incremented in steps of 2π/64 over the range 0 to 2π. Values of φ that are integer multiples of 2π/32 result in the output state |32φ/2π . This is achieved with an average fidelity of 0.619(5). For non-5 integer values, the population is distributed between the nearest 5-bit approximate states [14] . In our experiments, each algorithm fidelity is limited mainly by the native gate errors (< 2%), which propagate into the standard logic gate errors (< 5%) (see supplementary materials). These errors are dominated by Raman beam imperfections and therefore can be reduced by mitigating Raman beam intensity noise [23] and individual addressing crosstalk (see methods). Systematic shifts in the axes of the gate-rotations accumulate due to unequal Stark shifts across the qubits, which result in algorithmic errors that depend upon the circuit structure. This type of error can be easily eliminated by feeding forward known shifts to the rf of individual qubit control beams. The algorithms presented here illustrate the computational flexibility provided by the ion trap quantum architecture. Within a single module, this system can be scaled to dozens of qubits by linearly increasing the number of rf controls, AOM-and PMT-channels at the hardware level. In software, the number of XX-and R-gate calibrations required to compile any logic gate scale as O(n 2 ). As more ions are added to the chain, the axial confinement must be weakened to maintain a linear crystal. This will slow down the XX-gate duration roughly as n 1.7 , but the crosstalk is not expected to get worse (see methods). Finally, implementing this architecture on multi-zone ion traps such as surface traps will provide further control over the connectivity of qubits though shuttling [15] for scalable computation. This will also enable selective measurement of qubits that can be fedforward classically to perform conditional operations in the module [5] as required in fault-tolerant computing.
REF A netlist consists of a list of connections in a circuit and a list of the gates they are connected to.
Demonstration of a small programmable quantum computer with atomic qubits
Nature 536, 63-66 (2016)
Medicine Computer Science Physics