3 ms·
"progress after 21 will be much quicker" Can you provide a quick verification for that?
by oh_my_goodness 1y ago
"progress after 21 will be much quicker"
Can you provide a quick verification for that?
- wongarsu 1y agoThe article lists three reasons why 21 is so much harder than 15. Mostly that with 15 most of the required conditional multiplications are multiplications by 1 and the remaining multiplication can be done with cheap shifts because it's a multiplication by a power of 2 modulo 15 (which is one less than a power of two). But 22 and 24 are in the same boat as 21 here. All three of them require computing only factors that are not one, all three are not one less than a factor of 2. You need slightly more multiplications (and thus more gates) as the numbers get larger, but that only grows linearly. Maybe the conditional multiplications required get slightly more expensive to implement, but I wouldn't expect a 100x cost blowup from that. Error correction is still an issue, potentially making a linear complexity increase quadratic, but qubit counts in quantum computers also increase at an exponential rate
- oh_my_goodness 1y ago23 and 29 are prime.
- wongarsu 1y agoThat's what I get for not enough coffee. Same holds for 22 and 24 though
- oh_my_goodness 1y ago24 has 3 as a factor. 3 is one less than a power of 2.
- freehorse 1y agoWell n=21 too but the solution for n=15 used that 15 is one less than a power of 2, not its divisors, because we are living in modulo n.
- oh_my_goodness 1y agoThanks. I don't understand quantum computing at all.
- Dylan16807 1y agoThat's a bit off, but more importantly using information about the answer to make the circuit cheaper is cheating.