## Abstract

We report the implementation of the semiclassical quantum Fourier transform in a system of three beryllium ion qubits (two-level quantum systems) confined in a segmented multizone trap. The quantum Fourier transform is the crucial final step in Shor's algorithm, and it acts on a register of qubits to determine the periodicity of the quantum state's amplitudes. Because only probability amplitudes are required for this task, a more efficient semiclassical version can be used, for which only single-qubit operations conditioned on measurement outcomes are required. We apply the transform to several input states of different periodicities; the results enable the location of peaks corresponding to the original periods. This demonstration incorporates the key elements of a scalable ion-trap architecture, suggesting the future capability of applying the quantum Fourier transform to a large number of qubits as required for a useful quantum factoring algorithm.

Among quantum algorithms discovered up to this time, Shor's method for factoring large composite numbers (*1*) is arguably the most prominent application of large-scale quantum information processing, given that efficient factoring would render current cryptographic techniques based on large composite-number keys vulnerable to attack. The key component of this algorithm is an order-finding subroutine that requires application of the quantum discrete Fourier transform (QFT) to determine the period of a set of quantum amplitudes (*1**-**4*). The QFT is also an essential part of quantum algorithms for phase estimation and the discrete logarithm (*4*). In fact, the polynomial-time QFT is responsible for most of the known instances of exponential speedup over classical algorithms.

Relative phase information of the output state from the QFT is not required when applied in any of the algorithms mentioned above; only the measured probability amplitudes of each state are used. This allows the replacement of the fully coherent QFT with the semiclassical (or “measured”) QFT (*5*), in which each qubit is measured in turn, and prescribed controlled-phase rotations on the other qubits are conditioned on the classical measurement outcomes. This eliminates the need for entangling gates in the QFT protocol, which considerably relaxes the required control of motional states for the trapped-ion implementation. In addition, the semiclassical version is quadratically more efficient in the number of quantum gates when compared with the fully coherent version (*6*), a benefit in any physical implementation of quantum computing. The coherent QFT has been implemented in nuclear magnetic resonance systems (*7**-**11*) but has not been demonstrated in a scalable system (*12*). Here, we describe an implementation of the measured QFT in an architecture that can be scaled (*13**,* *14*).

The QFT is a basis transformation in an *N*-state space that transforms the state (*k* is an integer ranging from 0 to *N*–1) according to 1 The action on an arbitrary superposition of states may be written as 2 where the complex amplitudes *y _{j}* are the discrete Fourier transform (

*15*) of the complex amplitudes

*x*. For three qubits, switching to binary notation, where

_{k}*k*

_{1},

*k*

_{2}, and

*k*

_{3}are the most to least significant bits, respectively, in the label for the state , the transform can be written as (

*4*) 3 where [0.

*q*

_{1}

*q*

_{2}...

*q*] denotes the binary fraction

_{n}*q*

_{1}/2 +

*q*

_{2}/4 +...+

*q*. When written in this form, it can be seen that the QFT is the application to each qubit of a Hadamard transformation [ and ] and a

_{n}/2^{n}*z*rotation conditioned on each of the less significant qubits, with a phase of decreasing binary significance due to each subsequent qubit, all followed by a bit-order reversal (

*4*). The three-qubit quantum circuit, without the bit-order reversal, is shown in Fig. 1A. The simplified circuit for the measured QFT is shown in Fig. 1B.

In the experiment, *z* rotations are transformed into *x* rotations, which are more straightforward to implement in our system, and rotations are redistributed to accommodate required spin-echo refocusing pulses (π rotations) which reduce dephasing due to fluctuating magnetic fields (*16**-**18*), but this does not change the basic protocol. Because of the substitution of π/2 rotations for Hadamard operations and our choice of conditional-rotation direction, the coherent QFT corresponding to our measured QFT is described by 4 The sign differences from Eq. 3 are unimportant, because only the probability amplitudes of the output state are measured; the relative phases of the output-basis states are arbitrary. We have applied this three-qubit QFT to input states of several different periodicities.

The qubits comprise two states of the ground-state hyperfine manifold of ^{9}Be^{+}: the state , labeled , and the state , labeled . These states are separated in frequency by 1.28 GHz. Rotations 5 are performed by means of two-photon stimulated-Raman transitions (*19**,* *20*). Here, θ is the rotation angle, φ is the angle of the rotation axis from the *x* axis in the *xy* plane of the Bloch sphere (*17*), *I* is the identity operator, and σ* _{x}* and σ

*are the usual Pauli spin operators. The beryllium ions are confined in a linear radio-frequency Paul trap (*

_{y}*21*), similar to that described in (

*18*). This trap contains six zones, and the ions can be moved between these zones, together or separately, by means of synchronized variation of the potentials applied to the trap's control electrodes. State determination is made by projection of the qubit state with the use of resonance fluorescence (

*19*) (an ion in the state fluoresces, whereas an ion in the state does not). Measurement results were recorded, and laser pulses were applied by means of classical logic to implement conditional operations. The QFT protocol proceeded as depicted in Fig. 2A, with ions located in the multizone trap as shown in Fig. 2B.

Five different states were prepared to test the QFT protocol (Table 1). These states have periods of 1, 2, 4, 8, and approximately 3. The three-qubit state space consists of eight states, labeled in binary notation and ordered lexicographically. The periodicity is derived from the recurrence of the quantum amplitudes in a superposition of these eight states.

Periodicity | State (normalization omitted) | Preparation fidelity |
---|---|---|

1 | |ψ_{1}〉 = |000〉 + |001〉 + |010〉 +...+ |111〉 | 0.98(1) |

2 | |ψ_{2}〉 = |001〉 + |011〉 + |101〉 + |111〉 | 0.98(1) |

∼3 | |ψ_{3}〉 = |001〉 + |011〉 + |100〉 + |110〉 | 0.90(2) |

4 | |ψ_{4}〉 = |011〉 + |111〉 | 0.98(1) |

8 | |ψ_{8}〉 = |111〉 | >0.99(1) |

The period 1 state was generated by applying the rotation *R*(π/2,–π/2) to all three ions in the initial state . The period 2 state was generated from by physically separating ion 3 from ions 1 and 2, applying a rotation *R*(π/2,–π/2) to ions 1 and 2, and then bringing all three ions back together. Similarly, the period 4 state was created by applying the rotation *R*(π/2,–π/2) to only the first ion after separating it from ions 2 and 3. The period 8 state was simply the state of the ions after initialization, .

The most obvious (approximate) period 3 state in this eight-state space is (here and in the following, we omit normalization factors). Because this state's periodicity is not commensurate with the state space, the addition of the next (in a sequence of three) basis state to this superposition also results in an approximate period 3 state, . We used a cyclic permutation of ; in particular, adding 3 (mod 8) to each state produces . This state is the tensor prdouct of (ions 1 and 3) with (ion 2). Starting from , this state can be prepared by entangling the outer two ions (ions 1 and 3) with a geometric phase gate embedded between two rotations—*R*(π/2,π/4) and *R*(3π/2,π/4)— applied to all three ions (*21**,* *22*). This was followed by a rotation *R*(π/2,–π/2) to all three ions. This state was produced with a fidelity of approximately 0.90 (resulting from the reduced fidelity inherent in multi-qubit entangling operations compared with single-qubit rotations).

Each experiment began with Doppler cooling and Raman-sideband cooling to bring the ions to the ground state of all three axial vibrational modes of the trapping potential and optical pumping to prepare the three ions in the internal state (*13**,* *23*). The aforementioned input states were then prepared as described above. For each input state, several thousand implementations of the QFT were performed, each involving: (i) rotation of ion 1, (ii) measurement of ion 1, (iii) rotation of ion 2 conditional on the measurement of ion 1, (iv) measurement of ion 2, (v) rotation of ion 3 conditional on the first two measurements, and (vi) measurement of ion 3. Each experiment required approximately 4 ms after initial cooling, optical pumping, and state preparation.

The measured output-state probabilities after application of the QFT algorithm are shown in Fig. 3 along with the theoretically expected probabilities for the five different input states. The data generally agree with the theoretical predictions, although the deviations from the predicted values are larger than can be explained statistically and are due to systematic errors in the experiment. These systematic errors are associated with the state preparation (not associated with the QFT protocol) as well as with the separate detections and conditional rotations of the three ions (intrinsic to the QFT protocol). The first, second, and third ions were measured approximately 1.2 ms, 2.4 ms, and 3.5 ms after the beginning of the algorithm. Dephasing due to slow local magnetic-field fluctuations, though mitigated by the refocusing (spin-echo) operations, grows as a function of time during each experiment; the chance that an error occurs because of dephasing grows from approximately 5% for the first ion to approximately 13% for the third ion.

Even with these systematic errors, the results compare well with theory, as can be shown by examining the squared statistical overlap (SSO) [derived from the statistical overlap of (*24*)] of each set of data with the associated predictions. Here, we define the SSO as , where *m _{j}* and

*e*are the measured and expected output-state probabilities of state , respectively. This is an effective measure of fidelity without regard for relative output phases. The lowest measured SSO for the five prepared states is 0.87, suggesting that peaks can be reliably located to determine periodicities as required for Shor's factorization algorithm. To verify the reliability of the protocol for this task, one should compare the experimental and theoretical values of the measurement probabilities of the output states where peaks are located. For the period 2 state, the measured probability for the output state (the measurement outcome sufficient to determine the periodicity as 2), was 0.538, an 8% difference from the expected value of 0.5. For the period 3 state, the sum of the measured probabilities for output state and state (the states corresponding to the most correct periodicity) was 0.301, a 29% difference from the expected value of 0.426. Notably, the preparation fidelity of this state was not as high as for the others.

_{j}One other set of input states was created to demonstrate that the semiclassical QFT protocol is sensitive to relative input phases. All the states of Table 1 had amplitudes (of the basis states in the superpositions) with the same phase. We also prepared a period 3 state with a relative phase between some states in the superposition. By incrementing the phase of the three uniform rotations used in the creation of the period 3 state with respect to the operations in the QFT protocol by a phase φ* _{R}* [that is,

*R*(θ,φ) →

*R*(θ,φ + φ

*)], we can create the state 6 The relative phase between pairs of basis states in this superposition leads to a Fourier transform that depends on φ*

_{R}*. The measured probabilities of the eight output states are plotted in Fig. 4A along with the theoretical values in Fig. 4B. The level of agreement can be seen in Fig. 4C, a plot of the SSO as a function of preparation phase.*

_{R}These results demonstrate that for small state-spaces, the QFT can be performed semiclassically with a signal-to-noise level sufficient for period-finding in quantum algorithms by means of a system of trapped-ion qubits. Even with input state infidelities as large as 0.10, as in the period 3 state created here, the measured QFT had substantial SSO with the theoretical prediction for the correct input state. Furthermore, the effect of the incommensurability of state periodicity with state space is diminished as the size of the state space increases. Peaks due to similar incommensurate periodicities will be easier to locate in larger state spaces (compared to the case of a period 3 state in an eight-state space). Extension of the technique described here to larger quantum registers (*13**,* *14*) is a function only of trap-array size and involves a linear overhead in ion separation and movement. The main source of intrinsic error in our implementation was qubit dephasing resulting from magnetic-field fluctuations. Use of first-order magnetic field–independent qubit transitions (*13*) can mitigate this problem and lead to a high-fidelity method for implementation of the QFT, a necessary step toward large number–factorization applications of quantum computing.