Hacker News
new
|
past
|
comments
|
ask
|
show
|
jobs
|
submit
login
djha-skin
3 days ago
|
parent
|
context
|
favorite
| on:
Why haven't quantum computers factored 21 yet?
Does this essentially mean that the Big-O "circuitry requirements" of factoring integers using Schorr's is super polynomial?
cvoss
2 days ago
[–]
The article explains the gate cost mostly comes from O(n) multiply-under-mod ops on O(n)-bit numbers. Each op could be naively spelled out as O(n^2) gates. So the whole thing looks cubic to me at worst.
reply
Guidelines
|
FAQ
|
Lists
|
API
|
Security
|
Legal
|
Apply to YC
|
Contact
Search:
