Source-linked AI summary
Experimental demonstration of Shor's algorithm with quantum entanglement
B. P. Lanyon, T. J. Weinhold, N. K. Langford, M. Barbieri, D. F. V. James*, A. Gilchrist, A. G. White
TL;DR
Shor’s factoring algorithm requires quantum order-finding, but full-scale realization remains challenging because it demands substantial resources and coherent entanglement. This paper implements a compiled order-finding routine photonicly, verifies entangled states and circuit processes, and finds near-ideal algorithm outputs despite lower circuit-level performance. The results demonstrate core processes needed for larger implementations while showing why algorithm and circuit performance require separate characterization.
Problem
Full realization of Shor’s factoring algorithm remains a major quantum-computation challenge because factoring underpins modern cryptographic protocols and requires substantial resources.
Method
The authors implement a compiled version of Shor’s algorithm with photonic quantum-logic gates, measurement-induced nonlinearity, and quantum state and process tomography.
Results
The experiments implement every stage of a small-scale order-finding algorithm, obtain near-ideal algorithm performance, and verify entangled register states with tomography.
Takeaways & Limitations
Algorithm success rates can substantially exceed circuit-level indicators, so quantum algorithms require characterization of both their outputs and underlying circuit performance.
Takeaways & Limitations
The compiled experiments are not scalable, and directly encoding the order-4 circuit is infeasible with current photon rates and nondeterministic gates.
Abstract
from arXiv · showhide
Shor's powerful quantum algorithm for factoring represents a major challenge in quantum computation and its full realization will have a large impact on modern cryptography. Here we implement a compiled version of Shor's algorithm in a photonic system using single photons and employing the non-linearity induced by measurement. For the first time we demonstrate the core processes, coherent control, and resultant entangled states that are required in a full-scale implementation of Shor's algorithm. Demonstration of these processes is a necessary step on the path towards a full implementation of Shor's algorithm and scalable quantum computing. Our results highlight that the performance of a quantum algorithm is not the same as performance of the underlying quantum circuit, and stress the importance of developing techniques for characterising quantum algorithms.