This makes me goggle at the possibility of what an AI with access to a quantum computer could do. There are already programs out there for generating and testing hypotheses, but obviously they take ages to work through the solution space. With a quantum computer, all we would have to do is feed it data about the universe and it would almost instantly spit out hypotheses ranked in order of probability, with suggested tests for sorting through them. This is terribly exciting!
With a quantum computer, all we would have to do is feed it data about the universe and it would almost instantly spit out hypotheses ranked in order of probability, with suggested tests for sorting through them.
Calculating consistent probabilities is in general NP-hard) (if one has probabilities that are all 0 or 1 then it easily mimics SAT, and one can without too much effort extend this to a proof for the general case). It is unknown at present if quantum computers provide any sort of speed-up for NP hard problems in the general case, and the suspicion by most in the field seems to be that the answer is “no” or at least that it doesn’t provide enough speed up to matter that much unless in fact P=NP outright (essentially, assuming that P!=NP, it is likely that BQP does not contain NP). So you probably can’t do this. That said, the bounds of what quantum computers can do efficiently are not well-understood and even drastic improvements in constants could be bad. Running a poorly understood AI on a quantum computer or having access to a quantum computer would thus be a really bad idea.
Indeed. A quantum computer can’t brute force NP-hard problems in polynomial time simply by being a quantum computer. It is indeed faster than a classical computer, but it’s still not fast enough. A quantum computer can brute force a problem in the square root of the time it takes a classical computer to do so, but the square root of an exponential function is still exponential. If the classical computer brute forces a problem of size n in 2^n time, then the quantum computer takes (sqrt(2))^n time.
This makes me goggle at the possibility of what an AI with access to a quantum computer could do. There are already programs out there for generating and testing hypotheses, but obviously they take ages to work through the solution space. With a quantum computer, all we would have to do is feed it data about the universe and it would almost instantly spit out hypotheses ranked in order of probability, with suggested tests for sorting through them. This is terribly exciting!
Calculating consistent probabilities is in general NP-hard) (if one has probabilities that are all 0 or 1 then it easily mimics SAT, and one can without too much effort extend this to a proof for the general case). It is unknown at present if quantum computers provide any sort of speed-up for NP hard problems in the general case, and the suspicion by most in the field seems to be that the answer is “no” or at least that it doesn’t provide enough speed up to matter that much unless in fact P=NP outright (essentially, assuming that P!=NP, it is likely that BQP does not contain NP). So you probably can’t do this. That said, the bounds of what quantum computers can do efficiently are not well-understood and even drastic improvements in constants could be bad. Running a poorly understood AI on a quantum computer or having access to a quantum computer would thus be a really bad idea.
Indeed. A quantum computer can’t brute force NP-hard problems in polynomial time simply by being a quantum computer. It is indeed faster than a classical computer, but it’s still not fast enough. A quantum computer can brute force a problem in the square root of the time it takes a classical computer to do so, but the square root of an exponential function is still exponential. If the classical computer brute forces a problem of size n in 2^n time, then the quantum computer takes (sqrt(2))^n time.