We try to minimize the number of qubits needed to factor an integer of n bits using Shor's algorithm on a quantum computer. We introduce a circuit which uses 2n+3 qubits and O(n^3 lg(n)) elementary quantum gates in a depth of O(n^3) to implement the factorization algorithm. The circuit is computable in polynomial time on a classical computer and is completely general as it does not rely on any property of the number to be factored. Keywords: Factorization, quantum circuits, modular arithmetics
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
> Is there some minimum number of qubits at which some minimum viable quantum-supreme task can theoretically be achieved?
That is a very broad range of possibilities, so allow me to narrow it to cryptography. I am by no means an expert on this, but I spent the weekend reading about quantum motivations to change the cryptographic algorithms society uses and as at as I can tell, nobody knows what the hard lower bound is for breaking hardness assumptions in classical cryptography. The best guess is that it is many orders of magnitude higher than what current machines can do.
We are so far from machines capable of this that it is unclear that a machine capable of it will be…
Read the full comment
made in our lifetimes, despite optimism/fear/hope, depending on who you are, to the contrary.
> What would be required to factor a 1024 bit integer key?
I assume you mean a 1024-bit RSA key (if you mean a 1024-bit ECC key, I want to know what curve). You can crack 1024-bit RSA with 2051 logical qubits according to:
https://arxiv.org/abs/quant-ph/0205095
In order for it to actually work, it is believed that you will need between 1000 to 10000 physical qubits for every logical qubit, so it could take up to 20 million qubits.
Coincidentally, the following paper claims that cracking a 2048-bit RSA key can be done in 8 hours with 20 million physical qubits:
https://arxiv.org/abs/1905.09749
That sounds like it should not make sense given the previous upper estimate of 20 million physical qubits for a 1024-bit RSA key. As far as I can tell, there are different ways of implementing Shor’s algorithm and some ways use more qubits and some ways use less. The biggest factor in the number of physical qubits used is the error correction. If you can do better error correction, you can use fewer physical qubits.
From [1]:
> We implemented the algorithm on IBM quantum processors using only 5 qubits
Last December, a team based out of Harvard demonstrated the ability to scale up to 48 logical qubits: https://arxiv.org/abs/2312.03982
It has been shown that, to factor an integer with n bits, Shor's algorithm requires ~2n logical qubits: https://arxiv.org/pdf/quant-ph/0205095.pdf
> and how many are needed
According to this paper, one can use 2n+3 qubits to factor an integer with n bits:
https://arxiv.org/abs/quant-ph/0205095
Those would be perfect qubits, if you use noisy qubits you'd need many more (maybe a factor of 1000x more), since quantum error correction imposes a lot of overhead.
According to this paper:
https://arxiv.org/abs/quant-ph/0205095
You can implement Shor's algorithm to factor an N-bit number with just 2n+3 qubits. So the 20 qubit processor would be able to factor any 8 bit number (not necessarily faster than a classical computer could, or even a human could, mind you).
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.