Researcher show that n-bit integers can be factorized by independently running a quantum circuit
with orders of magnitude fewer qubits many times. It then use polynomial-time classical post-processing. The correctness of the algorithm relies on a number-theoretic heuristic assumption reminiscent of those used in subexponential classical factorization algorithms. It is currently not clear if the algorithm can lead to improved physical implementations in practice.
Shor’s celebrated algorithm allows to factorize n-bit integers using a quantum circuit of
size O(n^2). For factoring to be feasible in practice, however, it is desirable to reduce this number further. Indeed, all else being equal, the fewer quantum gates there are in a circuit, the likelier it is that it can be implemented without noise and decoherence destroying the quantum effects.
The new algorithm can be thought of as a multidimensional analogue of Shor’s algorithm. At the core
of the algorithm is a quantum procedure.
Without full fault tolerance in quantum computers we will never practically get past 100 qubits but full fault tolerance will eventually open up the possibility of billions of qubits and beyond. In a Wright Brothers Kittyhawk moment for Quantum Computing, a fully fault-tolerant algorithm was executed on real qubits. They were only three qubits but this was never done on real qubits before.
If the new decryptian algorithm is verified and we get fault tolerant qubits at scale, then all current internet and financial encryptian would be broken. There quantum computing resistant math for encoding that would not be vulnerable to quantum computers, but they will likely take a decade or more to implement. It will still take many years for fault tolerant quantum qubits to scale.
Brian Wang is a Futurist Thought Leader and a popular Science blogger with 1 million readers per month. His blog Nextbigfuture.com is ranked #1 Science News Blog. It covers many disruptive technology and trends including Space, Robotics, Artificial Intelligence, Medicine, Anti-aging Biotechnology, and Nanotechnology.
Known for identifying cutting edge technologies, he is currently a Co-Founder of a startup and fundraiser for high potential early-stage companies. He is the Head of Research for Allocations for deep technology investments and an Angel Investor at Space Angels.
A frequent speaker at corporations, he has been a TEDx speaker, a Singularity University speaker and guest at numerous interviews for radio and podcasts. He is open to public speaking and advising engagements.
The new algorithm by Oded Regev requires fewer quantum gates, but more qubits. There’s no free lunch.
There are already a range of “quantum safe” crypto systems that are resistant to factoring attacks: https://research.ibm.com/blog/nist-quantum-safe-protocols
“Decryptian”? I think you meant “decryption”. And “encryption”.
Your spell checker isn’t picking that up?
Anyway: Trust in nothing but one time pads. They’re the only genuinely secure encryption scheme. And event that is vulnerable to rubber hose cryptanalysis.
Just make sure the pads are only used ONE TIME.
“By reusing one-time pads, Russian agents accidentally leaked enough information for eavesdroppers in Blighty to figure out the encrypted missives’ plaintext. Two separate messages encrypted reusing the same key from a pad could be compared to ascertain the differences between their unencrypted forms, and from there eggheads could, using stats and knowledge of the language, work out the original words.”
See:
https://www.theregister.com/2018/07/19/russia_one_time_pads_error_british/
One-time pads are fine if you can meet in person to exchange pads. For anything that’s all remote, they’re worthless.