-
Thanks, this is what i thought. It depends whether "better at" is referring to efficiency or universality. That seems to keep getting confused in discussions I see on Twitter.
@seanmcarroll@no_scooters
It's not really universality, so much as what notion of efficiency you mean. For asymptotic complexity, ignoring polylogarithmic overheads (for error-correction & differences in implementation difficult), QCs will always be at least as efficient, & sometimes far more so.
-
-
"asymptotic complexity" is the spherical cow of computer science
-
Yeah. But often it's what you want. Shor's algorithm (& others) justify a very, very large overhead in the difficulty in implementing a single gate.
- 2 more replies
New conversation -
-
-
Of course, those overheads are a big thing to ignore! But sometimes it makes a lot of sense. (I've actually forgotten the overhead required for fault-tolerance, it's so long since I worked on this stuff. I think it's polylogarithmic. "Small" in some sense. "Huge" in another)
-
I'm an engineer. Constant factors matter, and scaling limits _only_ matter up to the extent of the largest-imaginable system.
End of conversation
New conversation -
-
-
ah interesting, so in principle if we could get transistor (qbit) density high enough we could use quantum computers in lieu of classical ones? i suspect the instruction sets might be a bit different but still.
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.