4 ms·

Putting aside speed, what is possible in quantum computing that's not possible in classical computing?

xapata 10y ago
Some problems can be solved immediately, in a single clock cycle, that are intractable for a traditional CPU. For example, cracking RSA encryption.
- ctz 10y ago
  This is not even remotely close to being true. Shor's algorithm runs in polynomial time.
- jMyles 10y ago
  > single clock cycle What does this even mean in this context? My understanding (which is limited!) is that there are some apparently NP-complete problems that are P for a quantum process. Now, it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers. Or it may be that quantum computers can really solve some NP-complete problems in P time. Either way though, it isn't a consequence of CPU-cycles per se, but the underlying mathematical distinction (ie, what a silicon vs quantum computer does, not what it can do in a "cycle").
  - Ar-Curunir 10y ago
    If quantum computers could solve NP-complete problems efficiently, the entire community would astounded. As it stands, quantum computers can solve some problems faster than classical computers currently can; factorisation, discrete log and other problems with a particular kind of repeated structure are some such problems. However, we do not know for certain that these problems are not efficiently solvable using classical computers (I'd bet that factorisation will be put in P within my lifetime). A big goal of the QC community is to demonstrate quantum supremacy: to unconditionally show that quantum computers can solve a problem with fewer resources than classical computers. We've made progress on this (check out Scott Aaronson's blog for more info), but still haven't achieved it. Lastly, a small nitpick. "P time" is not a meaningful phrase; P is a complexity class consisting of problems solvable efficiently (i.e., in polynomial time) on classical computers. The class of efficiently solvable problems on quantum computers is BQP: Bounded-error Quantum Polynomial-time, which means that BQP is the class of problems that are efficiently solved by a quantum computer, but only with some probability bounded away from 1/2. This means the QC can return incorrect answers, but there are techniques to reduce the error probability to extremely small values. The classical analogue of this class is BPP, which is Bounded-error probabilistic poly-time. There's a conjecture that BPP=P, and if we have any sort of crypto then the conjecture is true.
  - pwdisswordfish 10y ago
    Limited indeed. If nothing else, I'd suggest reading <http://www.scottaaronson.com/democritus/> http://www.scottaaronson.com/democritus/>. In short: > there are some apparently NP-complete problems that are P for a quantum process The definition of P refers to deterministic machines; no quantum. 'P for a quantum process' is a meaningless phrase. Problems solvable in polynomial time by quantum computers are contained in the classes EQP (if the answers are to be always correct) and BQP (if the answers are to be correct with a probability which may be made as high as desired). > it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers. 'NP-complete' is not an exact synonym of informal concepts like 'hard' or 'intractable'. It has a precise definition: NP-complete problems are those for which are simultaneously NP (the solution can be verified in polynomial time) and NP-hard (every instance of any NP problem can be reduced in polynomial time to it). There are problems that have been proved NP-complete. For others there are no known polynomial time algorithms, but they are suspected not to be NP-complete either. If P = NP, the notion of NP-completeness becomes trivial and equivalent to simply being in P. There's no way a problem now known to be NP-complete will later be shown not to be. > Or it may be that quantum computers can really solve some NP-complete problems in P time. This has not been proved false, but generally considered unlikely. (Also, 'some NP-complete problems' would imply 'all of them', by the definition of NP-completeness.)
    - jMyles 10y ago
      Awesome - you have upgraded me today.
mathgenius 10y ago
Apart from speed the only other thing is memory. And yes, for example simulating a quantum system takes exponentially much classical memory (just to store the state of the system). This is one of the proposed killer apps for quantum computing.
- deleted 10y ago
  [deleted]
ivan_ah 10y ago
It's not a question of possibility, but rather speedup. The three "flagship" algos are for unstructured search[1] (not clear if really useful), factoring[2] (useful to crack public key crypto), and more recently there is a result that shows that random instances of general linear problems can be solved faster[3]. Another class of algorithms use quantum computers as simulators (e.g. for chemical simulations). You can also encode certain optimization problems as "constraints" in a quantum system and hope that quantum dynamics will find good solutions to the optim. problem faster. [1] https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm [3] https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_s...
- mathgenius 10y ago
  > It's not a question of possibility Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.
  - Ar-Curunir 10y ago
    That's just a matter of speed no? It's not an impossibility result like Turing's; classical computers can compute whatever quantum computers can. That's the Church-Turing hypothesis.
    - moefh 10y ago
      It's just a matter of speed, but there's no need to invoke the Church-Turing hypothesis. One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly). [1] http://epubs.siam.org/doi/abs/10.1137/S0097539796300921 http://epubs.siam.org/doi/abs/10.1137/S0097539796300921
      - 10y ago
sbov 10y ago
I am not involved in quantum computing at all, and only have read a few articles, but my understanding is: Calling it a speed up is kinda correct but seems slightly wrong to me. It is a completely different computing model which tends to use different algorithms that make solutions to certain problems feasible on a quantum computer that aren't on an equally powered classical computer. That is why it's so powerful, but at the same time, classical computing could stay "faster" than quantum computing for a long time, or even forever.
- Terr_ 10y ago
  IANAPhysicist, but the analogy I use for my relatives is that electronic->quantum is similar to the jump from clock-work->electronic. Most concepts carry over, but some just don't make sense anymore, and a lot of effort must be invested into fundamentally new click-clack (or zip-zap) arrangements to get things done. A large part of the "intelligence" in the final system is actually latent in its structure.
- yarou 10y ago
  The way I understand it, quantum speedup simply means that the set of candidate solutions for a problem contained in BQP are more accurate over time.

Some problems can be solved immediately, in a single clock cycle, that are intractable for a traditional CPU. For example, cracking RSA encryption.

ctz 10y ago
This is not even remotely close to being true. Shor's algorithm runs in polynomial time.
jMyles 10y ago
> single clock cycle What does this even mean in this context? My understanding (which is limited!) is that there are some apparently NP-complete problems that are P for a quantum process. Now, it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers. Or it may be that quantum computers can really solve some NP-complete problems in P time. Either way though, it isn't a consequence of CPU-cycles per se, but the underlying mathematical distinction (ie, what a silicon vs quantum computer does, not what it can do in a "cycle").
- Ar-Curunir 10y ago
  If quantum computers could solve NP-complete problems efficiently, the entire community would astounded. As it stands, quantum computers can solve some problems faster than classical computers currently can; factorisation, discrete log and other problems with a particular kind of repeated structure are some such problems. However, we do not know for certain that these problems are not efficiently solvable using classical computers (I'd bet that factorisation will be put in P within my lifetime). A big goal of the QC community is to demonstrate quantum supremacy: to unconditionally show that quantum computers can solve a problem with fewer resources than classical computers. We've made progress on this (check out Scott Aaronson's blog for more info), but still haven't achieved it. Lastly, a small nitpick. "P time" is not a meaningful phrase; P is a complexity class consisting of problems solvable efficiently (i.e., in polynomial time) on classical computers. The class of efficiently solvable problems on quantum computers is BQP: Bounded-error Quantum Polynomial-time, which means that BQP is the class of problems that are efficiently solved by a quantum computer, but only with some probability bounded away from 1/2. This means the QC can return incorrect answers, but there are techniques to reduce the error probability to extremely small values. The classical analogue of this class is BPP, which is Bounded-error probabilistic poly-time. There's a conjecture that BPP=P, and if we have any sort of crypto then the conjecture is true.
- pwdisswordfish 10y ago
  Limited indeed. If nothing else, I'd suggest reading <http://www.scottaaronson.com/democritus/> http://www.scottaaronson.com/democritus/>. In short: > there are some apparently NP-complete problems that are P for a quantum process The definition of P refers to deterministic machines; no quantum. 'P for a quantum process' is a meaningless phrase. Problems solvable in polynomial time by quantum computers are contained in the classes EQP (if the answers are to be always correct) and BQP (if the answers are to be correct with a probability which may be made as high as desired). > it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers. 'NP-complete' is not an exact synonym of informal concepts like 'hard' or 'intractable'. It has a precise definition: NP-complete problems are those for which are simultaneously NP (the solution can be verified in polynomial time) and NP-hard (every instance of any NP problem can be reduced in polynomial time to it). There are problems that have been proved NP-complete. For others there are no known polynomial time algorithms, but they are suspected not to be NP-complete either. If P = NP, the notion of NP-completeness becomes trivial and equivalent to simply being in P. There's no way a problem now known to be NP-complete will later be shown not to be. > Or it may be that quantum computers can really solve some NP-complete problems in P time. This has not been proved false, but generally considered unlikely. (Also, 'some NP-complete problems' would imply 'all of them', by the definition of NP-completeness.)
  - jMyles 10y ago
    Awesome - you have upgraded me today.

mathgenius 10y ago

Apart from speed the only other thing is memory. And yes, for example simulating a quantum system takes exponentially much classical memory (just to store the state of the system). This is one of the proposed killer apps for quantum computing.

deleted 10y ago
[deleted]

ivan_ah 10y ago

It's not a question of possibility, but rather speedup. The three "flagship" algos are for unstructured search[1] (not clear if really useful), factoring[2] (useful to crack public key crypto), and more recently there is a result that shows that random instances of general linear problems can be solved faster[3]. Another class of algorithms use quantum computers as simulators (e.g. for chemical simulations). You can also encode certain optimization problems as "constraints" in a quantum system and hope that quantum dynamics will find good solutions to the optim. problem faster. [1] https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm [2] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm [3] https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_s...

mathgenius 10y ago
> It's not a question of possibility Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.
- Ar-Curunir 10y ago
  That's just a matter of speed no? It's not an impossibility result like Turing's; classical computers can compute whatever quantum computers can. That's the Church-Turing hypothesis.
  - moefh 10y ago
    It's just a matter of speed, but there's no need to invoke the Church-Turing hypothesis. One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly). [1] http://epubs.siam.org/doi/abs/10.1137/S0097539796300921 http://epubs.siam.org/doi/abs/10.1137/S0097539796300921
    - 10y ago

sbov 10y ago

I am not involved in quantum computing at all, and only have read a few articles, but my understanding is: Calling it a speed up is kinda correct but seems slightly wrong to me. It is a completely different computing model which tends to use different algorithms that make solutions to certain problems feasible on a quantum computer that aren't on an equally powered classical computer. That is why it's so powerful, but at the same time, classical computing could stay "faster" than quantum computing for a long time, or even forever.

Terr_ 10y ago
IANAPhysicist, but the analogy I use for my relatives is that electronic->quantum is similar to the jump from clock-work->electronic. Most concepts carry over, but some just don't make sense anymore, and a lot of effort must be invested into fundamentally new click-clack (or zip-zap) arrangements to get things done. A large part of the "intelligence" in the final system is actually latent in its structure.
yarou 10y ago
The way I understand it, quantum speedup simply means that the set of candidate solutions for a problem contained in BQP are more accurate over time.