Source-linked AI summary
Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, Jeremy L. O'Brien
TL;DR
The paper implements controlled quantum operations and a semi-classical Fourier transform in an optical circuit to study order finding. Its output shows a threefold contrast between observing 0 and 1 in the control register, with quantum interference determining that contrast.
Problem
The work addresses how quantum interference affects the Fourier-transform output used for order finding.
Method
The experiment uses an optical entangling gate to implement controlled operations and a semi-classical Fourier transform for order finding.
Results
The probability of observing 0 in the control register is three times that of observing 1 in the Fourier-transform output.
Takeaways & Limitations
Quantum interference produces the observable contrast between control-register outcomes in the Fourier-transform output.
Abstract
from arXiv · showhide
Quantum computational algorithms exploit quantum mechanics to solve problems exponentially faster than the best classical algorithms. Shor's quantum algorithm for fast number factoring is a key example and the prime motivator in the international effort to realise a quantum computer. However, due to the substantial resource requirement, to date, there have been only four small-scale demonstrations. Here we address this resource demand and demonstrate a scalable version of Shor's algorithm in which the n qubit control register is replaced by a single qubit that is recycled n times: the total number of qubits is one third of that required in the standard protocol. Encoding the work register in higher-dimensional states, we implement a two-photon compiled algorithm to factor N=21. The algorithmic output is distinguishable from noise, in contrast to previous demonstrations. These results point to larger-scale implementations of Shor's algorithm by harnessing scalable resource reductions applicable to all physical architectures.
Methods
The experiment implements a photon-based, qubit-recycled order-finding circuit using path and polarization encoding, with a work qutrit and postselected photonic gates. The circuit’s entangling operation is validated through a strong CHSH Bell-inequality violation.
- Optical circuit: The optical circuit uses calcite beam displacers to build stable Jamin–Lebedeff polarization interferometers, with beam splitters implementing the required PBS elements.The architecture provides parallel light paths for interferometric stability.
- State preparation: The circuit initializes the control and work registers through wave-plate settings implementing Hadamard and Identity operations within an eCNOT gate.Pre-entangled photons from the SPDC source are converted from polarization entanglement to path entanglement using PBSs and polarization flips.
- Register encoding: The control register is polarization encoded as a qubit, while the work register uses polarization and spatial modes to encode the |0⟩, |1⟩, and |2⟩ qutrit states.The |1⟩ work state initially has zero probability amplitude and is represented in the upper spatial mode.
- Entangling gate: The pCNOT gate is tuned with a half-wave plate at 62.5° and heralded by detecting one photon in the control modes and one in the work modes.Balancing loss is introduced in the W(2) mode, whose output shares a spatial mode with the pCNOT loss mode but has different polarization.
- Measurement and validation: 2.67 ± 0.01 CHSH value demonstrates entangling capability, violating the classical limit of 2 by 55 standard deviations.The control qubit is subsequently phase assigned and projected for semi-classical Fourier-transform order finding, while the work qutrit only heralds detection at the final stage.
Appendix A: Supplementary Information
The appendix details the compiled N = 21, x = 4 implementation, which replaces the standard five-qubit work register with a single qutrit and explains how Fourier-transform interference shapes the output probabilities.
- Compiling the algorithm: The compiled circuit implements f(x, a, N) = x^a (mod N) for N = 21 and x = 4 using controlled unitary operations with redundant elements omitted.The relevant unitaries and decompositions can be calculated explicitly for this specific factoring case.
- Compiling the algorithm: A single qutrit represents the active work-register states {1, 4, 16}, replacing the 5-qubit work register in the compiled N = 21 implementation.The qutrit uses photon path and polarisation degrees of freedom, with labels based on logarithms of the encoded values.
- Algorithm operation: The first control-qubit projection ideally yields equal probabilities for |0⟩ and |1⟩, corresponding to the least significant output digit.Selecting identity or bit-flip operations before polarisation post-selects the corresponding state component.
- Algorithm operation: The 0 control-register term has three times the probability of the 1 term because of constructive versus destructive Fourier-transform interference.The contrasted terms correspond to digits 00 and 10, and decoherence degrades this contrast.
- Algorithm operation: The Fourier transform produces equal probabilities for control-register values 0 and 1 in the second projection, corresponding to final digits 01 and 11.A phase adjustment undoes the phase flip introduced by the controlled-swap-equivalent operation.