Factoring an integer with three oscillators and a qubit

Abstract

A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computations manipulating bits. It allows for a device-independent development of algorithmic primitives. Here we argue that an alternative approach centered on the physical setup can yield great benefits. As an example, we consider hybrid qubit-oscillator systems with linear optics operations augmented by certain qubit-controlled Gaussian unitaries. The continuous variable Fourier transform and certain arithmetic operations have native realizations in such systems. We put this to algorithmic use and give a polynomial-time quantum factoring algorithm which uses only one qubit and three oscillators, independent of the number being factored. The number of qubits needed for Shor’s factoring algorithm scales with the size of the integer to be factored. Here, the authors propose an alternative approach that would require only three harmonic oscillators and a qubit, regardless of the size of the integer, but incurring in an extensive energy cost.