13 ms·

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it

by tim-- 9y ago

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database?

empath75 9y ago
https://www.nature.com/articles/npjqi201523 https://www.nature.com/articles/npjqi201523 Here are a bunch of potential applications.
NhanH 9y ago
Quantum annealing can be used for optimization of functions. Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. But in general, quantum computer is not strictly a superset of improvement over Turing machine. It’s just different. And while it might reduces your database query time, unless you are already working at that abstraction it might probably be invisible changes for you.
- TrinaryWorksToo 9y ago
  From what I gathered, it's similar to how a CPU and GPU compare: different complexity classes, different problems it's efficient on.
  - asddkk 9y ago
    The CPU-GPU analogy is very good for all sorts of reasons. For some things there's no speedup, for some important things there's a huge speedup, for other things there's some significant speedup, but not game-changing. I tend to think of applications where you might want to brute-force search or simulate over some large set as being where quantum computing will be most significant, but I say that very vaguely and timidly. This gives a number of applications and algorithms; I found some of the references in it really interesting to read: http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/
- bsder 9y ago
  > Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. I thought it was still an open question as to whether a quantum computer would actually be able to solve this class of problems or not. In addition, quantum computers have a great deal of noise--so quantum error correction seems to be a thing.
  - yorwba 9y ago
    Quantum computing is certainly able to solve integer factorization and related problems (like breaking RSA encryption), just not for practical problem sizes yet. You are probably thinking about NP-hard problems, which may or may not be solvable faster than on classical computers.
  - jcoffland 9y ago
    Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit quantum computer to factor a 128 bit number and thereby break something like 128 bit RSA encryption. No one yet has, or is publicly admitting to having, a reliable 128 qubit device. In some cases, error correction can be achieved simply by running the algorithm a few times.
    - Beltiras 9y ago
      Error correction is immaterial for the factoring case. You multiply the factors and if you do not get the original number you know you have to run it again.
      - jcoffland 9y ago
        In Schor's algorithm, the quantum computer finds the period p of B mod N were N is the number you are trying to factor and B is a random number less than N. The quantum computer may find p with imperfect accuracy. Running the algorithm repeatedly can improve the accuracy of p. You can also try other numbers close to p. Both are examples of error correcting a quantum algorithm.
Nelgraf 9y ago
Someone linked this video the other day: https://vimeo.com/180284417 https://vimeo.com/180284417 I really enjoyed it for layman's perspective while still exposing technical depth. I hadn't thought about how one of the big challenges of quantum computing is figuring out how to morph your traditional parallel algorithm into a quantum algorithm (with all the weirdness that entails)
himom 9y ago
There is no added Turing power to QC over CC. Turing complete is Turing complete. Think of QC as a coprocessor for certain classes of algorithms like prime factorization.
- lisper 9y ago
  With exponential speedup. That's the big deal.
  - visarga 9y ago
    We don't know how to extract these benefits yet for real problems.
sytelus 9y ago
Here's my rather crude understanding of what QC can do (please feel free to comment if this is correct): Let's say you have a problem that requires examining 2^N different possibilities. So the brute force solution would have O(2^N) runtime. QC can potentially help to solve this problem in O(2^(sqrt(N))) time instead. This can make a world of difference. For example, if N=1024 and examining each possibility took 1 nanosecond, it would still exceed the time far far more than age of universe. With QC with 1024 qubits, it would take 1 microsecond to solve it.
- mercutio2 9y ago
  Utterly unimportant to your point, but 2^32 nanoseconds is not a microsecond...
- Sniffnoy 9y ago
  I'm afraid you're a bit off. A quantum computer can search N possibilities (such as when, say, looking up data in a database, though I doubt you'd go to the trouble of using a QC for that) in time O(sqrt(N)). So for 2^N things, that's 2^(N/2), not 2^(sqrt(N)). Obviously still a big improvement.
  - ryacko 9y ago
    But wouldn't it have to be stored as qubits? A database in qubits would be expensive.
    - Sniffnoy 9y ago
      Well, yes, that's one reason why you wouldn't actually use a QC for that...
Mizza 9y ago
Your bank could give you a quantum keyfob. All of your encrypted transactions are now entangled, so you know that nobody has spied on them: the act of observation modifies the result.
- Sniffnoy 9y ago
  It sounds like you're describing quantum cryptography, which doesn't require a quantum computer and in fact already exists commerically.
  - comstock 9y ago
    To be honest it sounds like they’re describing the plot of the next mission impossible film rather than anything that exists in our reality.
gaze 9y ago
We don't know. If someone manages to find an algorithm to do such things, it'll be helpful for that. It's as if we're rediscovering the computer itself from the beginning and we're still not sure what it's good for, but the things we've managed to find algorithms for it appears to be really really good at. Basically, don't worry too much about it, unless you wish to hunt for such algorithms yourself. The one thing it's definitely promising for is simulating quantum mechanics... something classical computers are very bad at, and has serious practical use. For this, they will always be very useful.
- akavel 9y ago
  Also, apart from inventing/discovering new algorithms, there's another part in inventing how to use them to help in particular "real-world" (or "non-quantum programmer world") problems. So, maybe one of the known algorithms could actually somehow help with "training a RNN", but probably nobody invented a way to rephrase ("refactor") the "training a RNN" problem in a way which could get boosted by one of the known quantum algos (the set of which can be looked at as "the quantum API") yet. Now that I think of it, the few most well known algorithms (like the Shor's one) are probably so because "real world" use cases were found for them, which are understandable to non-quantum engineers (i.e. "factorization of primes"), as opposed to "transforming a hamiltonian foobzdringle into a hilbertian mesoism in laplacian meta-subordinates" :P
frik 9y ago
Can the idea of quantum computing be simplified/abstracted to say instead of doing binary (0 1) calculations, it do does calculation on arbitrary base? E.g. base 16 (hex) or base 1024? If this is true, it would be easier to code, and compilers could spit out very efficient machine code.
- soberhoff 9y ago
  What? How does a compiler care about the base of your machine code?
- Sniffnoy 9y ago
  Yes, base has nothing to do with anything, talking about "qubits" is just a convention since computation is usually thought of in terms of bits. The fundamental idea of a quantum computer though has nothing to do with binary in particular. Same as for classical computers. It's not clear to me why you claim this would be related to efficient machine code, though.
  - frik 9y ago
    Current "digital" microchips use electric "on" (1) and "off" (0) and base 2 (also called binary) mathematics is used. Someone explained me quantum mechanics that it supports more states, not just on (1) and off (0), that it can have dozens or hundreds of states. Is this correct / state-of-the-art understanding? I imagine how cool it would be to have more states, not just 0 and 1. A computer running on more states could encode machine code in fewer instructions, so it could calculate more with the same frequency. So why downvote me? Either explain me where I got something wrong, or skip it in case you know less than me.
    - Sniffnoy 9y ago
      > Someone explained me quantum mechanics that it supports more states, not just on (1) and off (0), that it can have dozens or hundreds of states. Is this correct / state-of-the-art understanding? No, that's not really correct. Being able to put states in superposition is very different from having more classical states. > I imagine how cool it would be to have more states, not just 0 and 1. A computer running on more states could encode machine code in fewer instructions, so it could calculate more with the same frequency. That doesn't really make any sense. A cycle is still a cycle. How many instructions you can encode with a given length doesn't tell you anything about how fast they execute. Even going with an extremely charitable reading, I don't think there's any way anything that you're talking about could lead to anything better than a constant-factor speedup (and not a large one). The point of quantum computing isn't to get mere constant-factor speedups. Such a thing would be insignificant in comparison to what quantum computers can actually do.
IncRnd 9y ago
This should answer your question. http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/ However, quantum computing will likely do nothing for you as a person other than make your life more difficult due to complexity changes for solving non-pqc algorithms.
PeachPlum 9y ago
Decreasing lead time in manufacturing has dramatically changed the world during your lifetime. There are lots of unsolved problems in computational logistics that look like tsp. We have whole conferences on heuristics to shorten their runtimes. e.g. [1] And there are more. Hundreds of PhDs will be working today on just that topic. [1] http://iwi.econ.uni-hamburg.de/iccl/front.html http://iwi.econ.uni-hamburg.de/iccl/front.html
jcoffland 9y ago
The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travelling-sales-man-with-quantum-computers https://cstheory.stackexchange.com/questions/31084/travellin...
- xxs 9y ago
  Indeed, I have never heard how (any) NP-complete stuff would be solved by quantum computers. It was very surprising to see it as top comment.
  - deleted 9y ago
    [deleted]
- visarga 9y ago
  > The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?
  - CJefferson 9y ago
    It's unclear a quantum computer can find you an approximate solution any faster either.
  - monob 9y ago
    Do you have a paper on approximating NP complete problems and the bounds on the error in the solution?
  - jcoffland 9y ago
    That has nothing to do with quantum vs. classical.
    - visarga 9y ago
kybernetikos 9y ago
http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/ Of particular note, there are significant speed ups for optimization and constraint satisfaction, cryptanalysis, machine learning and indeed 'looking up data in a database' (grover search).
crobin 9y ago
I would expect, as the technology matures and the transistors needed become smaller, to see Quantum computers instead become quantum chips that you would install as a PCI-Express card just like a GPU and would assist a normal CPU into solving some of the problems that quantum computing is better at.
adrianN 9y ago
To me the most exciting prospect is exponentially faster simulation of quantum systems. Computational chemistry really sucks because either you rely on heuristics or you can't simulate systems with more that a handful of atoms. If we had big quantum computers we might make real inroads into understanding protein folding and could figure out how to make artificial proteins to use for all kinds of applications. Proteins are Nature's nano-robots. Full Drexler nanotechnology awaits.
skate22 9y ago
So the NSA can break RSA in the USA. sorry, got carried away there for a second..
snarfy 9y ago
I liked this explanation using playing cards - https://www.youtube.com/watch?v=1X4OZYVwyO8&t=4m38s https://www.youtube.com/watch?v=1X4OZYVwyO8&t=4m38s
jamesrcole 9y ago
The work on quantum computing is basic research. You can't expect to be able to predict the actual real-world impact of basic research while it's still being developed. Quantum mechanics is a good example. It's had massive, real-world impact, but nobody could have predicted that. The details need to be fleshed out, and people then need to explore things with it, play around, do further research on top of it.
naasking 9y ago
> The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database? "Quantum computers can search arbitrarily large databases by a single query" [1]. That's Grover's algorithm from 1997, one of the pinnacle results that got people excited about quantum computing. If you haven't come across it before, then you must not have read too much about quantum computing! [1] https://arxiv.org/pdf/quant-ph/9706005.pdf https://arxiv.org/pdf/quant-ph/9706005.pdf

by tim-- 9y ago

empath75 9y ago

https://www.nature.com/articles/npjqi201523 https://www.nature.com/articles/npjqi201523 Here are a bunch of potential applications.

NhanH 9y ago

Quantum annealing can be used for optimization of functions. Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. But in general, quantum computer is not strictly a superset of improvement over Turing machine. It’s just different. And while it might reduces your database query time, unless you are already working at that abstraction it might probably be invisible changes for you.

TrinaryWorksToo 9y ago
From what I gathered, it's similar to how a CPU and GPU compare: different complexity classes, different problems it's efficient on.
- asddkk 9y ago
  The CPU-GPU analogy is very good for all sorts of reasons. For some things there's no speedup, for some important things there's a huge speedup, for other things there's some significant speedup, but not game-changing. I tend to think of applications where you might want to brute-force search or simulate over some large set as being where quantum computing will be most significant, but I say that very vaguely and timidly. This gives a number of applications and algorithms; I found some of the references in it really interesting to read: http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/
bsder 9y ago
> Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. I thought it was still an open question as to whether a quantum computer would actually be able to solve this class of problems or not. In addition, quantum computers have a great deal of noise--so quantum error correction seems to be a thing.
- yorwba 9y ago
  Quantum computing is certainly able to solve integer factorization and related problems (like breaking RSA encryption), just not for practical problem sizes yet. You are probably thinking about NP-hard problems, which may or may not be solvable faster than on classical computers.
- jcoffland 9y ago
  Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit quantum computer to factor a 128 bit number and thereby break something like 128 bit RSA encryption. No one yet has, or is publicly admitting to having, a reliable 128 qubit device. In some cases, error correction can be achieved simply by running the algorithm a few times.
  - Beltiras 9y ago
    Error correction is immaterial for the factoring case. You multiply the factors and if you do not get the original number you know you have to run it again.
    - jcoffland 9y ago
      In Schor's algorithm, the quantum computer finds the period p of B mod N were N is the number you are trying to factor and B is a random number less than N. The quantum computer may find p with imperfect accuracy. Running the algorithm repeatedly can improve the accuracy of p. You can also try other numbers close to p. Both are examples of error correcting a quantum algorithm.

Nelgraf 9y ago

Someone linked this video the other day: https://vimeo.com/180284417 https://vimeo.com/180284417 I really enjoyed it for layman's perspective while still exposing technical depth. I hadn't thought about how one of the big challenges of quantum computing is figuring out how to morph your traditional parallel algorithm into a quantum algorithm (with all the weirdness that entails)

himom 9y ago

There is no added Turing power to QC over CC. Turing complete is Turing complete. Think of QC as a coprocessor for certain classes of algorithms like prime factorization.

lisper 9y ago
With exponential speedup. That's the big deal.
- visarga 9y ago
  We don't know how to extract these benefits yet for real problems.

sytelus 9y ago

Here's my rather crude understanding of what QC can do (please feel free to comment if this is correct): Let's say you have a problem that requires examining 2^N different possibilities. So the brute force solution would have O(2^N) runtime. QC can potentially help to solve this problem in O(2^(sqrt(N))) time instead. This can make a world of difference. For example, if N=1024 and examining each possibility took 1 nanosecond, it would still exceed the time far far more than age of universe. With QC with 1024 qubits, it would take 1 microsecond to solve it.

mercutio2 9y ago
Utterly unimportant to your point, but 2^32 nanoseconds is not a microsecond...
Sniffnoy 9y ago
I'm afraid you're a bit off. A quantum computer can search N possibilities (such as when, say, looking up data in a database, though I doubt you'd go to the trouble of using a QC for that) in time O(sqrt(N)). So for 2^N things, that's 2^(N/2), not 2^(sqrt(N)). Obviously still a big improvement.
- ryacko 9y ago
  But wouldn't it have to be stored as qubits? A database in qubits would be expensive.
  - Sniffnoy 9y ago
    Well, yes, that's one reason why you wouldn't actually use a QC for that...

Mizza 9y ago

Your bank could give you a quantum keyfob. All of your encrypted transactions are now entangled, so you know that nobody has spied on them: the act of observation modifies the result.

Sniffnoy 9y ago
It sounds like you're describing quantum cryptography, which doesn't require a quantum computer and in fact already exists commerically.
- comstock 9y ago
  To be honest it sounds like they’re describing the plot of the next mission impossible film rather than anything that exists in our reality.

gaze 9y ago

We don't know. If someone manages to find an algorithm to do such things, it'll be helpful for that. It's as if we're rediscovering the computer itself from the beginning and we're still not sure what it's good for, but the things we've managed to find algorithms for it appears to be really really good at. Basically, don't worry too much about it, unless you wish to hunt for such algorithms yourself. The one thing it's definitely promising for is simulating quantum mechanics... something classical computers are very bad at, and has serious practical use. For this, they will always be very useful.

akavel 9y ago
Also, apart from inventing/discovering new algorithms, there's another part in inventing how to use them to help in particular "real-world" (or "non-quantum programmer world") problems. So, maybe one of the known algorithms could actually somehow help with "training a RNN", but probably nobody invented a way to rephrase ("refactor") the "training a RNN" problem in a way which could get boosted by one of the known quantum algos (the set of which can be looked at as "the quantum API") yet. Now that I think of it, the few most well known algorithms (like the Shor's one) are probably so because "real world" use cases were found for them, which are understandable to non-quantum engineers (i.e. "factorization of primes"), as opposed to "transforming a hamiltonian foobzdringle into a hilbertian mesoism in laplacian meta-subordinates" :P

frik 9y ago

Can the idea of quantum computing be simplified/abstracted to say instead of doing binary (0 1) calculations, it do does calculation on arbitrary base? E.g. base 16 (hex) or base 1024? If this is true, it would be easier to code, and compilers could spit out very efficient machine code.

soberhoff 9y ago
What? How does a compiler care about the base of your machine code?
Sniffnoy 9y ago
Yes, base has nothing to do with anything, talking about "qubits" is just a convention since computation is usually thought of in terms of bits. The fundamental idea of a quantum computer though has nothing to do with binary in particular. Same as for classical computers. It's not clear to me why you claim this would be related to efficient machine code, though.
- frik 9y ago
  Current "digital" microchips use electric "on" (1) and "off" (0) and base 2 (also called binary) mathematics is used. Someone explained me quantum mechanics that it supports more states, not just on (1) and off (0), that it can have dozens or hundreds of states. Is this correct / state-of-the-art understanding? I imagine how cool it would be to have more states, not just 0 and 1. A computer running on more states could encode machine code in fewer instructions, so it could calculate more with the same frequency. So why downvote me? Either explain me where I got something wrong, or skip it in case you know less than me.
  - Sniffnoy 9y ago
    > Someone explained me quantum mechanics that it supports more states, not just on (1) and off (0), that it can have dozens or hundreds of states. Is this correct / state-of-the-art understanding? No, that's not really correct. Being able to put states in superposition is very different from having more classical states. > I imagine how cool it would be to have more states, not just 0 and 1. A computer running on more states could encode machine code in fewer instructions, so it could calculate more with the same frequency. That doesn't really make any sense. A cycle is still a cycle. How many instructions you can encode with a given length doesn't tell you anything about how fast they execute. Even going with an extremely charitable reading, I don't think there's any way anything that you're talking about could lead to anything better than a constant-factor speedup (and not a large one). The point of quantum computing isn't to get mere constant-factor speedups. Such a thing would be insignificant in comparison to what quantum computers can actually do.

IncRnd 9y ago

This should answer your question. http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/ However, quantum computing will likely do nothing for you as a person other than make your life more difficult due to complexity changes for solving non-pqc algorithms.

PeachPlum 9y ago

Decreasing lead time in manufacturing has dramatically changed the world during your lifetime. There are lots of unsolved problems in computational logistics that look like tsp. We have whole conferences on heuristics to shorten their runtimes. e.g. [1] And there are more. Hundreds of PhDs will be working today on just that topic. [1] http://iwi.econ.uni-hamburg.de/iccl/front.html http://iwi.econ.uni-hamburg.de/iccl/front.html

jcoffland 9y ago

The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travelling-sales-man-with-quantum-computers https://cstheory.stackexchange.com/questions/31084/travellin...

xxs 9y ago
Indeed, I have never heard how (any) NP-complete stuff would be solved by quantum computers. It was very surprising to see it as top comment.
- deleted 9y ago
  [deleted]
visarga 9y ago
> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?
- CJefferson 9y ago
  It's unclear a quantum computer can find you an approximate solution any faster either.
- monob 9y ago
  Do you have a paper on approximating NP complete problems and the bounds on the error in the solution?
- jcoffland 9y ago
  That has nothing to do with quantum vs. classical.
  - visarga 9y ago

kybernetikos 9y ago

http://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/ Of particular note, there are significant speed ups for optimization and constraint satisfaction, cryptanalysis, machine learning and indeed 'looking up data in a database' (grover search).

crobin 9y ago

I would expect, as the technology matures and the transistors needed become smaller, to see Quantum computers instead become quantum chips that you would install as a PCI-Express card just like a GPU and would assist a normal CPU into solving some of the problems that quantum computing is better at.

adrianN 9y ago

To me the most exciting prospect is exponentially faster simulation of quantum systems. Computational chemistry really sucks because either you rely on heuristics or you can't simulate systems with more that a handful of atoms. If we had big quantum computers we might make real inroads into understanding protein folding and could figure out how to make artificial proteins to use for all kinds of applications. Proteins are Nature's nano-robots. Full Drexler nanotechnology awaits.

skate22 9y ago

So the NSA can break RSA in the USA. sorry, got carried away there for a second..

snarfy 9y ago

I liked this explanation using playing cards - https://www.youtube.com/watch?v=1X4OZYVwyO8&t=4m38s https://www.youtube.com/watch?v=1X4OZYVwyO8&t=4m38s

jamesrcole 9y ago

The work on quantum computing is basic research. You can't expect to be able to predict the actual real-world impact of basic research while it's still being developed. Quantum mechanics is a good example. It's had massive, real-world impact, but nobody could have predicted that. The details need to be fleshed out, and people then need to explore things with it, play around, do further research on top of it.

naasking 9y ago

> The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database? "Quantum computers can search arbitrarily large databases by a single query" [1]. That's Grover's algorithm from 1997, one of the pinnacle results that got people excited about quantum computing. If you haven't come across it before, then you must not have read too much about quantum computing! [1] https://arxiv.org/pdf/quant-ph/9706005.pdf https://arxiv.org/pdf/quant-ph/9706005.pdf