4 ms·

> 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 tha

by 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.

by jMyles 10y ago

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.