Implementation of the Semiclassical Quantum Fourier Transform in a Scalable System

See allHide authors and affiliations

Science  13 May 2005:
Vol. 308, Issue 5724, pp. 997-1000
DOI: 10.1126/science.1110335


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 Embedded Image (k is an integer ranging from 0 to N–1) according to Embedded Image1 The action on an arbitrary superposition of states may be written as Embedded Image2 where the complex amplitudes yj are the discrete Fourier transform (15) of the complex amplitudes xk. For three qubits, switching to binary notation, where k1, k2, and k3 are the most to least significant bits, respectively, in the label for the state Embedded Image, the transform can be written as (4) Embedded Image3 where [0.q1 q2...qn] denotes the binary fraction q1/2 + q2/4 +...+ qn/2n. When written in this form, it can be seen that the QFT is the application to each qubit of a Hadamard transformation [Embedded Image and Embedded Image] and a 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.

Fig. 1.

Circuits for the quantum Fourier transform (QFT) of three qubits. (A) The QFT as composed of Hadamard transforms and two-qubit conditional phase gates (4). The gate-labeling scheme denotes the axis about which the conditional rotation takes place and, below the axis label, the angle of that rotation. The Embedded Image and Embedded Image are the input and output states, respectively, of qubit i. The most significant qubit corresponds to i = 1. This circuit produces the QFT in reverse bit order, so in practice, the qubits are simply read out in reverse order (4). (B) The semiclassical (or “measured”) QFT (5). The double lines denote classical information. This circuit can be implemented by means of a single classically controlled quantum operation on each qubit. The protocol is preceded by state preparation (Table 1) of the quantum state to be transformed.

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 Embedded Image4 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 9Be+: the state Embedded Image, labeled Embedded Image, and the state Embedded Image, labeled Embedded Image. These states are separated in frequency by 1.28 GHz. Rotations Embedded Image5 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 σy are the usual Pauli spin operators. The beryllium ions are confined in a linear radio-frequency Paul trap (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 Embedded Image state fluoresces, whereas an ion in the Embedded Image 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.

Fig. 2.

Circuit for the QFT and locations of the ions in the multizone trap during protocol execution. (A) The semiclassical QFT (5) as implemented in this Report. The double lines denote classical information. The closed circles on control lines denote rotation conditional on “1”; the open circles denote rotation conditional on “0.” The initial conditional rotation of qubit 1 ensures that it is in the nonfluorescing state when the second ion is measured [the second ion is measured in the presence of the first ion, which contributes negligibly to the fluorescence signal during the second measurement (25); refer to “Second qubit measurement” in (B)]. This circuit, up to some irrelevant phases, can be obtained from that in Fig. 1B through conjugation of rotations and reordering of some operations. (B) The locations of the ions in the multizone trap structure during the QFT protocol as a function of time. Separation of ions and refocusing operations are performed in zone 6, and all other qubit operations are performed in zone 5.

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 Embedded Image in binary notation and ordered lexicographically. The periodicity is derived from the recurrence of the quantum amplitudes in a superposition of these eight states.

Table 1.

Periodic states prepared to test the semiclassical QFT protocol. Numbers in parentheses indicate experimental uncertainty.

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 Embedded Image. The period 2 state was generated from Embedded Image 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, Embedded Image.

The most obvious (approximate) period 3 state in this eight-state space is Embedded Image (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 Embedded Image to this superposition also results in an approximate period 3 state, Embedded Image. We used a cyclic permutation of Embedded Image; in particular, adding 3 (mod 8) to each state produces Embedded Image. This state is the tensor prdouct of Embedded Image (ions 1 and 3) with Embedded Image (ion 2). Starting from Embedded Image, 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 Embedded Image (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.

Fig. 3.

Results of the semiclassical QFT. Measured probability of each output state occurring after the application of the protocol is shown along with the expected transform output. Each plot contains data from 5000 experiments. The SSO γ is a measure of transform accuracy. Uncertainties quoted for the SSO are statistical and do not include systematic errors. (A) to (E) are the QFTs for Embedded Image, and Embedded Image, respectively.

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 Embedded Image, where mj and ej are the measured and expected output-state probabilities of state Embedded Image, 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 Embedded Image (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 Embedded Image and state Embedded Image (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.

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(θ,φ + φR)], we can create the state Embedded Image6 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.

Fig. 4.

Semiclassical QFT of nominal period 3 state as a function of preparation phase φR (Eq. 6). (A) The measured probabilities are plotted as a function of the output state and the phase of the state preparation after application of the QFT protocol. The QFT at each phase is based on 2000 experiments. (B) The expected probability plotted in the same manner. (C) The SSO γ as a function of preparation phase. Error bars represent 1σ statistical uncertainties only.

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.

References and Notes

View Abstract

Stay Connected to Science

Navigate This Article