Factoring an integer with three oscillators and a qubit
2024/12/17 by Lukas Brenner, Brenner, Lukas, Libor Caha +5 · 6 voices · 4 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications
paper · pdf · doi:10.1038/s41467-025-67694-5
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.
Cited by
Discussions
- New research: RSA-2048 encryption keys can be broken with single qubit and 3 oscillators. The catch? You’ll need about 10 followed by 45 million zeros joules of energy—roughly comparable to several me [bsky, 62 points, 2 comments]
- The "hide the exponential" game Scott Aaronson has complained about for decades is alive and well: arxiv.org/abs/2412.13164 Yes, Shor's algorithm with 3 registers only needs very basic operations. N [bsky, 50 points, 2 comments]
- Have to admit that this is very cool. arxiv.org/abs/2412.13164 It's time to dump your quantum stocks and buy shares in companies that make mattresses or any other kinds of springs or pendulums! Harmo [bsky, 28 points, 1 comments]
- Congrats to Brenner, Caha, Coiteux-Roy and Koenig for this fantastic result! (4/4) arxiv.org/abs/2412.13164 [bsky, 16 points, 0 comments]
- New SSL/TLS finding just dropped: RSA-2048 encryption keys can be broken with single qubit and 3 oscillators. If a threat actor is able to harness the power of several medium-sized stars they may be a [bsky, 2 points, 0 comments]
- [2412.13164] Factoring an integer with three oscillators and a qubit arxiv.org/abs/2412.13164 [bsky, 0 points, 0 comments]
Related