3 ms·

Does quantum speed even matter? I would have thought a wide enough array of qubits could functionally do "anything" in one shot

by Havoc 11mo ago

tsimionescu 11mo ago
They most certainly can't, not even close to it. They can do a very limited subset of problems, and not at all in one shot - just far far far less shots than a classical computer. But even if you reduce and O(e^n) problem to an O(n) or O(n²) problem, that's not instantaneous, and the speed with which you perform these n or n² operations still matters.
Strilanc 11mo ago
Yes, speed matters. No, quantum computers can't do everything instantly even with unbounded qubits. A well studied example is that it's impossible to parallelize the steps in Grover's algorithm. To find a preimage amongst N possibilities, with only black box access, you need Ω(sqrt(N)) sequential steps on the quantum computer [1]. Another well known case is that there's no known way to execute a fault tolerant quantum circuit faster than its reaction depth (other than finding a rewrite that reduces the depth, such as replacing a ripple carry adder with a carry lookahead adder) [2]. There's no known way to make the reaction depth small in general. Another example is GCD (greatest common divisor). It's conjectured to be an inherently sequential problem (no polylog depth classical circuit) and there's no known quantum circuit for GCD with lower depth than the classical circuits. [1]: https://arxiv.org/abs/quant-ph/9711070 https://arxiv.org/abs/quant-ph/9711070 [2]: https://arxiv.org/abs/1210.4626 https://arxiv.org/abs/1210.4626
tbrownaw 11mo ago
There is a complexity class called BQP, which is more or less the things that quantum computers are good at. This includes P which is more or less the things they normal computers are good at. Things that quantum computers are better at would more or less be one minus the other. One interesting point is that BQP probably doesn't include all of the rather famous NP class.
moffkalast 11mo ago
Everything is possible when a quantum scientist needs to apply for another grant. Less so after the project is already signed.

Does quantum speed even matter? I would have thought a wide enough array of qubits could functionally do "anything" in one shot

by Havoc 11mo ago

Does quantum speed even matter? I would have thought a wide enough array of qubits could functionally do "anything" in one shot

tsimionescu 11mo ago

They most certainly can't, not even close to it. They can do a very limited subset of problems, and not at all in one shot - just far far far less shots than a classical computer. But even if you reduce and O(e^n) problem to an O(n) or O(n²) problem, that's not instantaneous, and the speed with which you perform these n or n² operations still matters.

Strilanc 11mo ago

Yes, speed matters. No, quantum computers can't do everything instantly even with unbounded qubits. A well studied example is that it's impossible to parallelize the steps in Grover's algorithm. To find a preimage amongst N possibilities, with only black box access, you need Ω(sqrt(N)) sequential steps on the quantum computer [1]. Another well known case is that there's no known way to execute a fault tolerant quantum circuit faster than its reaction depth (other than finding a rewrite that reduces the depth, such as replacing a ripple carry adder with a carry lookahead adder) [2]. There's no known way to make the reaction depth small in general. Another example is GCD (greatest common divisor). It's conjectured to be an inherently sequential problem (no polylog depth classical circuit) and there's no known quantum circuit for GCD with lower depth than the classical circuits. [1]: https://arxiv.org/abs/quant-ph/9711070 https://arxiv.org/abs/quant-ph/9711070 [2]: https://arxiv.org/abs/1210.4626 https://arxiv.org/abs/1210.4626

tbrownaw 11mo ago

There is a complexity class called BQP, which is more or less the things that quantum computers are good at. This includes P which is more or less the things they normal computers are good at. Things that quantum computers are better at would more or less be one minus the other. One interesting point is that BQP probably doesn't include all of the rather famous NP class.

moffkalast 11mo ago

Everything is possible when a quantum scientist needs to apply for another grant. Less so after the project is already signed.