Pretending to factor large numbers on a quantum computer

Abstract

Shor's algorithm for factoring in polynomial time on a quantum computer\cite{Shor} gives an enormous advantage over all known classical factoring algorithm. We demonstrate how to factor products of large prime numbers using a compiled version of Shor's quantum factoring algorithm. Our technique can factor all products of $p,q$ such that $p,q$ are unequal primes greater than two, runs in constant time, and requires only two coherent qubits. This illustrates that the correct measure of difficulty when implementing Shor's algorithm is not the size of number factored, but the length of the period found.

15 pages including 3 figures and supplementary material

References in corpus (5)

• Shor's quantum factoring algorithm on a photonic chip
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Computing prime factors with a Josephson phase qubit quantum processor
• Demonstration of Shor's quantum factoring algorithm using photonic qubits

Cited by in corpus (30)

• Quantum algorithms: an overview
• Scalable Quantum Simulation of Molecular Energies
• Defining and detecting quantum speedup
• Realization of a scalable Shor algorithm
• On the permutationally invariant part of a density matrix and nonseparability of N-qubit states
• Prime factorization using quantum annealing and computational algebraic geometry
• An Experimental Study of Shor's Factoring Algorithm on IBM Q
• Benchmarking quantum computers
• Quantum-enhanced magnetometry by phase estimation algorithms with a single artificial atom
• Large-Scale Simulation of Shor's Quantum Factoring Algorithm
• Exact search algorithm to factorize large biprimes and a triprime on IBM quantum computer
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Controlling NMR spin systems for quantum computation
• Implementations of more general solid-state (SWAP)${}^{1/m}$ and controlled-(swap)${}^{1/m}$ gates
• Factoring Safe Semiprimes with a Single Quantum Query
• The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
• Odd orders in Shor's factoring algorithm
• Shor's Factoring Algorithm and Modular Exponentiation Operators
• Realization of Shor's Algorithm at Room Temperature
• Logarithmic-Depth Quantum Circuits for Hamming Weight Projections
• Single-Layer Digitized-Counterdiabatic Quantum Optimization for $p$-spin Models
• Quantum-accelerated algorithms for generating random primitive polynomials over finite fields
• Blindly Factorizing 21 Quantumly
• Synthesizing Quantum Circuits for Simple Periodic Functions
• Simplified Factoring Algorithms for Validating Small-Scale Quantum Information Processing Technologies
• Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring
• Practical implementation of Toffoli-based qubit rotation
• Quantum Computation
• Quantum Fourier Transform in Oscillating Modes