5 ms·

I thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency.

I thought one of the main advantages of QC was that it could (theoretically) solve existing problems that have exponential time complexity with more efficiency. Isn’t the idea that it could make everything faster? Or did I fall for the marketing.

jncfhnb 2y ago
The basic idea is that for a certain class of problems, you can have the quantum computer skip certain incorrect paths on the calculation by having their probability amplitudes cancel each other out.
- eru 2y ago
  With emphasis very much on '_certain_ class of problems'. It's only a precious few problems quantum computers actually help with as far as we know, even theoretically.
edgyquant 2y ago
This is true in theory but don’t think it’s ever been proven in practice
- eru 2y ago
  Which theory are you talking about? See https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
HarHarVeryFunny 2y ago
It could make somethings faster, not everything, but so far the number of useful somethings that people have come up with is very small. A quantum computer is not a general purpose computer than can be programmed in the way we're used to - it's more like an analog computer that is configured rather than programmed. It's only useful if the problem you are trying to solve can be mapped into a configuration of the computer.
edanm 2y ago
> Isn’t the idea that it could make everything faster? If that is your understanding, then yes, you have unfortunately fallen for the very mistaken reporting on this. There are specific algorithms that Quantum Computing can solve faster than regular computers. Some of these algorithms are incredibly important, and a faster solution to them would cause serious changes to the world, namely Shor's algorithm, which would make factoring large numbers much faster. This would effectively break many/most encryption schemes in the world. So it's a big deal! Nevertheless, this isn't true in general - not every algorithm is known to have such a speedup. (I'm not an expert, I'm not sure if we know that there isn't a general speedup, or think there might be but haven't found it.)
- cwillu 2y ago
  Public key crypto is vulnerable to period finding, but symmetrical key cryptography is pretty safe from quantum computing advances.
  - immibis 2y ago
    Quadratic speedup, IIRC - a 128-bit key can be found by brute force in (roughly) 2^128 steps by a normal computer, or 2^64 steps by a quantum computer. This applies to all brute force algorithms, so just make your keys and hashes twice as long as you think they should be, and you're good.
  - edanm 2y ago
    This might be true (I'm not that up to date on whether there are symmetrical algorithms that negate the advantage of QC), but most of the internet / world commerce relies on public key crypto.
- jacobsimon 2y ago
  Huh yeah I guess I need to learn more. My layman’s assumption was that it would help with a lot of NP problems that involved recursion or backtracking algorithm would benefit from it. From some quick googling it seems like they have already designed QC algorithms for traveling salesman etc. Isn’t that sort of meaningful or am I missing something? I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.
cwillu 2y ago
If a problem can be reduced to efficiently sampling from the summation of an exponentially large number of FFT's, then a quantum computer will destroy a classical computer. If a task can't be efficiently reduced to such a problem, then a QC probably won't ever help at all; the square root time advantage from grover's algorithm is too easily overwhelmed by simple engineering factors.
- fooker 2y ago
  What's stopping classical computers from doing this sampling? If it's sampling, you don't have to deal with the exponential here.
  - cwillu 2y ago
    See https://www.scottaaronson.com/papers/optics.pdf https://www.scottaaronson.com/papers/optics.pdf “We give new evidence that quantum computers—moreover, rudimentary quantum computers built entirely out of linear-optical elements—cannot be efficiently simulated by classical comput- ers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum com- putation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.” Which is the basis for the experiment discussed here: https://scottaaronson.blog/?p=5122 https://scottaaronson.blog/?p=5122
eru 2y ago
You got a useful response already, so let me give you a good response: https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
- jacobsimon 2y ago
  LOL

jncfhnb 2y ago

The basic idea is that for a certain class of problems, you can have the quantum computer skip certain incorrect paths on the calculation by having their probability amplitudes cancel each other out.

eru 2y ago
With emphasis very much on '_certain_ class of problems'. It's only a precious few problems quantum computers actually help with as far as we know, even theoretically.

edgyquant 2y ago

This is true in theory but don’t think it’s ever been proven in practice

eru 2y ago
Which theory are you talking about? See https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3

HarHarVeryFunny 2y ago

It could make somethings faster, not everything, but so far the number of useful somethings that people have come up with is very small. A quantum computer is not a general purpose computer than can be programmed in the way we're used to - it's more like an analog computer that is configured rather than programmed. It's only useful if the problem you are trying to solve can be mapped into a configuration of the computer.

edanm 2y ago

> Isn’t the idea that it could make everything faster? If that is your understanding, then yes, you have unfortunately fallen for the very mistaken reporting on this. There are specific algorithms that Quantum Computing can solve faster than regular computers. Some of these algorithms are incredibly important, and a faster solution to them would cause serious changes to the world, namely Shor's algorithm, which would make factoring large numbers much faster. This would effectively break many/most encryption schemes in the world. So it's a big deal! Nevertheless, this isn't true in general - not every algorithm is known to have such a speedup. (I'm not an expert, I'm not sure if we know that there isn't a general speedup, or think there might be but haven't found it.)

cwillu 2y ago
Public key crypto is vulnerable to period finding, but symmetrical key cryptography is pretty safe from quantum computing advances.
- immibis 2y ago
  Quadratic speedup, IIRC - a 128-bit key can be found by brute force in (roughly) 2^128 steps by a normal computer, or 2^64 steps by a quantum computer. This applies to all brute force algorithms, so just make your keys and hashes twice as long as you think they should be, and you're good.
- edanm 2y ago
  This might be true (I'm not that up to date on whether there are symmetrical algorithms that negate the advantage of QC), but most of the internet / world commerce relies on public key crypto.
jacobsimon 2y ago
Huh yeah I guess I need to learn more. My layman’s assumption was that it would help with a lot of NP problems that involved recursion or backtracking algorithm would benefit from it. From some quick googling it seems like they have already designed QC algorithms for traveling salesman etc. Isn’t that sort of meaningful or am I missing something? I could totally see the argument that they are physically impractical and therefore not likely to be actually used vs parallelizing conventional computers.

cwillu 2y ago

If a problem can be reduced to efficiently sampling from the summation of an exponentially large number of FFT's, then a quantum computer will destroy a classical computer. If a task can't be efficiently reduced to such a problem, then a QC probably won't ever help at all; the square root time advantage from grover's algorithm is too easily overwhelmed by simple engineering factors.

fooker 2y ago
What's stopping classical computers from doing this sampling? If it's sampling, you don't have to deal with the exponential here.
- cwillu 2y ago
  See https://www.scottaaronson.com/papers/optics.pdf https://www.scottaaronson.com/papers/optics.pdf “We give new evidence that quantum computers—moreover, rudimentary quantum computers built entirely out of linear-optical elements—cannot be efficiently simulated by classical comput- ers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum com- putation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions.” Which is the basis for the experiment discussed here: https://scottaaronson.blog/?p=5122 https://scottaaronson.blog/?p=5122

eru 2y ago

You got a useful response already, so let me give you a good response: https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3

jacobsimon 2y ago
LOL