Source-linked AI summary
Shor's quantum factoring algorithm on a photonic chip
Alberto Politi, Jonathan C. F. Matthews, Jeremy L. O'Brien
TL;DR
The paper addresses how to demonstrate Shor’s factoring routine in an integrated photonic platform. It implements a compiled version for factoring 15 and uses quantum order finding followed by classical processing to recover the factors 3 and 5.
Problem
Shor’s algorithm requires quantum order finding through superposition, entanglement, and interference, motivating an integrated implementation of its compiled factoring routine.
Method
The compiled routine uses four photonic qubits, optical Hadamard and controlled-phase gates, and classical processing after measuring the argument qubits.
Results
The routine produces outputs that can yield order r = 4 and, through Euclid’s algorithm, the prime factors 3 and 5.
Takeaways & Limitations
For the compiled case of factoring 15, quantum measurement supplies the order information needed for efficient classical factor extraction.
Abstract
from arXiv · showhide
Shor's quantum factoring algorithm finds the prime factors of a large number exponentially faster than any other known method a task that lies at the heart of modern information security, particularly on the internet. This algorithm requires a quantum computer a device which harnesses the `massive parallelism' afforded by quantum superposition and entanglement of quantum bits (or qubits). We report the demonstration of a compiled version of Shor's algorithm on an integrated waveguide silica-on-silicon chip that guides four single-photon qubits through the computation to factor 15.
APPENDIX
The appendix explains how the compiled routine factors 15 by finding the order r of modular exponentiation and then applying classical greatest-common-divisor calculations. It also details the circuit’s entangled-state output, optical gate implementation, and measurement outcomes.
- Order finding: Shor’s quantum step finds the order r of modular exponentiation using superposition, entanglement, and interference from a quantum Fourier transform.The order-finding result is then used in classical processing to obtain factors.
- Compilation: For a = 2 and N = 15, compilation reduces the required function-qubit count and allows the inverse QFT to be performed classically.The compiled computation evaluates log_a[a^z mod N] in place of a^zx mod N.
- Output state: The input state is transformed into two maximally entangled Bell pairs, whose measured argument-qubit outputs are 000, 010, 100, or 110.The function-register qubits are traced out before measuring the argument qubits.
- Classical post-processing: Outputs 010 and 110 yield order r = 4 and factors 3 and 5, while 000 is an expected failure and 100 gives trivial factors 1 and 15.The routine has a single-run success rate of 1/2, increasing to 1 − (1/2)^n after n repetitions.
- Optical implementation: The optical implementation uses deterministic Hadamard gates and nondeterministic controlled-phase gates with success probability 1/9 conditional on detecting one photon in each relevant mode.Each controlled-phase gate is built from three 1/3-reflectivity directional couplers.