Source-linked AI summary
Realization of a scalable Shor algorithm
Thomas Monz, Daniel Nigg, Esteban A. Martinez, Matthias F. Brandl, Philipp Schindler, Richard Rines, Shannon X. Wang, Isaac L. Chuang, Rainer Blatt
TL;DR
As register size grows, directly optimizing operations on the entire Hilbert space becomes impractical. The paper instead decomposes operations into optimized building blocks, uses spectroscopic decoupling and pulse-sequence engineering, and evaluates controlled multipliers and their components.
Problem
As the Hilbert space grows, directly optimizing unitary operations acting on the entire register is no longer possible, motivating decomposition into smaller-register building blocks.
Method
The approach decomposes modular arithmetic into pulse-optimized Fredkin and controlled-NOT building blocks, using spectator-qubit decoupling and in-sequence single-qubit detection with protected qubits.
Results
Modular multipliers modulo 15 achieved fidelities of {48(5), 40(5), 50(6), 46(5), 38(5)}%, consistent with the multiplied fidelities of their individual building blocks.
Takeaways & Limitations
The measured multiplier quality is consistent with the performance expected from composing the individual quantum-operation building blocks.
Abstract
from arXiv · showhide
Quantum computers are able to outperform classical algorithms. This was long recognized by the visionary Richard Feynman who pointed out in the 1980s that quantum mechanical problems were better solved with quantum machines. It was only in 1994 that Peter Shor came up with an algorithm that is able to calculate the prime factors of a large number vastly more efficiently than known possible with a classical computer. This paradigmatic algorithm stimulated the flourishing research in quantum information processing and the quest for an actual implementation of a quantum computer. Over the last fifteen years, using skillful optimizations, several instances of a Shor algorithm have been implemented on various platforms and clearly proved the feasibility of quantum factoring. For general scalability, though, a different approach has to be pursued. Here, we report the realization of a fully scalable Shor algorithm as proposed by Kitaev. For this, we demonstrate factoring the number fifteen by effectively employing and controlling seven qubits and four "cache-qubits", together with the implementation of generalized arithmetic operations, known as modular multipliers. The scalable algorithm has been realized with an ion-trap quantum computer exhibiting success probabilities in excess of 90%.
Pulse sequences
The experiment builds pulse sequences from collective rotations, single-qubit phase shifts, and Mølmer–Sørensen entangling interactions. These operations provide the local and entangling ingredients for universal quantum gates, including direct GHZ-state preparation.
- Collective operations address all ion-qubits on the S1/2(m = −1/2) ↔D5/2(m = −1/2) transition to realize unitary operations.
- The rotation angle is set by θ = Ωt/π, where Ω is the Rabi frequency and t is the laser pulse duration.
- A bit flip around σx is represented as R(1, 0), while focused-laser AC-Stark shifts implement single-qubit phase rotations.
- Combining arbitrary local operations with an entangling interaction yields a universal gate set capable of implementing any desired unitary operation.
- The maximally entangling MS(1/2) operation applied to |0 . . . 0⟩ directly creates an N-qubit GHZ state.
Single-qubit measurement
The measurement scheme protects all unmeasured qubits by encoding them in D5/2 states, allowing collective shelving light to project only a selected qubit.
- Electron-shelving ordinarily addresses and projects all qubits, but Kitaev’s implementation requires measuring only one qubit.
- A refocusing sequence, R2(0.5, 0)·Sz(1, i)·R2(0.5, 0), encodes all qubits except qubit i in two D5/2 manifolds.
- After this encoding, shelving light can illuminate the entire register while projecting only qubit i.
In-sequence detection and feed-forward
State-dependent photon scattering enables in-sequence discrimination and feed-forward operations. The D and S photon-count distributions are well separated during a 300 µs detection window.
- 99.8% confidence distinguishes state D from state S using a 4-count discriminator during the 300 µs detection window.
- State D produces 0.07 counts and state S produces 14.4 counts on average within the detection window.
- The discriminator’s boolean output drives state-dependent pulses and subsequent state-dependent operations.
- The corresponding Poisson photon-count distributions are well distinguishable.
Recooling and Qubit-reset
Photon scattering heats the ion string and can reduce the quality of later operations, so the experiment recools the ions without disturbing quantum information stored in D5/2.
- Photon scattering during detection heats the ion string and can lower the quality of subsequent quantum operations.
- Recooling is necessary after electron-shelving illumination but must preserve quantum information in the other qubits.
- Three-beam Raman cooling acts in the S1/2 ↔P1/2 manifold while hidden information remains stored in D5/2.
Pulse sequence optimisation
For larger Hilbert spaces, the required unitaries are decomposed into smaller building blocks so optimized pulse sequences remain usable. Here, decoupling enables optimization of a controlled swap in a 3-qubit rather than 5-qubit space.
- Pulse sequence optimisation: Large-register unitaries are decomposed into smaller building blocks to enable optimized pulse sequences for large-scale computation.Direct optimization over the entire register becomes impractical for sufficiently large Hilbert spaces.
- Pulse sequence optimisation: The approach reduces the optimization problem by isolating the qubits involved in the operation from spectator-qubit interactions.
- Pulse sequence optimisation: Decoupling qubits from interactions allows the controlled swap to be optimized in a 3-qubit Hilbert space instead of a 5-qubit space.
Controlled-SWAP
The controlled-SWAP, or Fredkin operation, is central to modular multiplication but requires a pulse sequence specialized to the three-qubit case. Decoupling spectator qubits removes the need to support arbitrary spectators.
- Controlled-SWAP: The controlled-SWAP operation, also called the Fredkin operation, plays a crucial role in modular multiplication.
- Controlled-SWAP: 18 pulses, including 4 MS interactions, implement the exact three-qubit controlled-SWAP sequence.
- Controlled-SWAP: The sequence works for three-qubit systems because spectator qubits would not experience the identity operation.
Four-Target Controlled-NOT
Four-target controlled-NOT operations conditionally apply NOT operations to four target qubits based on a control qubit. They are used in the modular multipliers for 7 mod 15 and 13 mod 15.
- Four-Target Controlled-NOT: The modular multipliers (7 mod 15) and (13 mod 15) require controlled-NOT operations acting on all computational-register qubits.
- Four-Target Controlled-NOT: The all-qubit controlled-NOT can be implemented with 2 MS operations plus local operations regardless of computational-register size.
- Four-Target Controlled-NOT: The four-target controlled-NOT conditionally applies NOT operations to qubits {2-5} depending on the state of qubit 1.
Two-Target Controlled-NOT
An analytic multi-target controlled-NOT solution exists with spectator qubits, but decoupling subsets before the operation facilitates pulse optimization and improves the resulting realization.
- Two-Target Controlled-NOT: An analytic solution realizes multi-target controlled-NOT operations in the presence of spectator qubits.
- Two-Target Controlled-NOT: The operation is required for the {2, 7, 8, 13}2 mod 15 multiplier.
- Two-Target Controlled-NOT: Decoupling subsets of qubits before the multi-target controlled-NOT facilitates optimization and improves realization performance.
Controlled Quantum Modular Multipliers
The experiment evaluates the building blocks and controlled modular multipliers using truth-table fidelities averaged over 200 repetitions. It reports fidelities for Fredkin operations, a 4-target CNOT, and modular multipliers modulo 15.
- Truth-table elements were obtained as averages over 200 repetitions, with fidelities reported as mean probabilities and standard deviations.
- Fredkin operations controlled by qubit 1 achieved fidelities of 76(4)%, 73(6)%, 72(4)%, and 68(7)% across four target configurations.
- The 4-target CNOT gate operated at a fidelity of 86(3)%.
- With control state |0⟩, the modular multipliers implement identity; with control state |1⟩, they multiply inputs by the specified values modulo 15.