Quantum AI running self driving cars in the blockchain cloud, social VR controlled. Experience our agile experience powered with renewable big data. Gamifying the digital transformation of tomorrow!
so what learning were learnt for this lesson?
Google Quantum AI
181–190 of 210 posts
Re: Google Quantum AI
#182The fact this prize exists is admitting that no one has figured out a use for quantum computers. I have heard this mentioned several times in the last decade or so : "The only thing a quantum computer definitively does better than a classical computer is simulating a quantum computer." Whether this capability is useful is up in the air. Note that in practice, classical computers are going to be better at factoring nu…
Quantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions. The problem there is that decomposing real world problems into 128bit combinatorial selection is really hard.
>Quantum computers SHOULD destroy regular computers at knapsack style problems and other combinatorial explosions.
You can get a Turing award if you can show this, even theoretically.
Re: Google Quantum AI
#183Earlier quoted context omitted.
> 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…
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 a…
Well they are physically impractical now, but they might get practical in the future.
But no, I'm fairly sure that QC in general isn't known to be able to solve NP problems. And since Traveling Salesman is NP complete (iirc), I don't think there's a QC alg to solve traveling salesman in P (otherwise that would imply QC would solve all of NP in P, which I know isn't true). Where did you see indication otherwise?
FWIW, my favorite CS blogger is Scott Aaronson, and the subtitle of his blog has always been: "If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel." This reflects the very common misunderstanding of how QC works.
Re: Google Quantum AI
#184Earlier quoted context omitted.
That sounds… wrong. A simulation of a plane is a model, implemented by humans, of how physics works. A simulation of a quantum system is still a human implementation of mechanics. A quantum computer per my understanding should not be able to add anything to that. You’re not able to just say well this thingy has quantum mechanics and this is a quantum computer so it’s better able to do that. Quantum computers are abou…
No that’s not how it works, quantum mechanics cannot be simulated efficiently on a classical computer, the state space grows exponentially with the number of degrees of freedom, every degree has relative phases to every other degree even when only looking at pure states, that’s why even the largest super computers cannot simulate more than 50 quantum degrees of freedom currently (see quantum supremacy).
Simulation usually involves randomized and sampling algorithms, not a full state space exploration.
A good part of theoretical chemistry today relies on simulating quantum systems.
Re: Google Quantum AI
#185Earlier quoted context omitted.
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 a…
Well they are physically impractical now, but they might get practical in the future. But no, I'm fairly sure that QC in general isn't known to be able to solve NP problems. And since Traveling Salesman is NP complete (iirc), I don't think there's a QC alg to solve traveling salesman in P (otherwise that would imply QC would solve all of NP in P, which I know isn't true). Where did you see indication otherwise? FWIW,…
Hah ok point taken. Here’s the paper I found about traveling salesman - looks like a version of Grover’s algorithm so I think that means it provides a speed-up but not polynomial time? Paper is paywalled: https://link.springer.com/article/10.1134/S1063776123080095#....
Re: Google Quantum AI
#186Earlier quoted context omitted.
> so you waste less time testing bad samples. How is this not “wrong answers are not calculated”? You gave a lot more detail on the mechanics of how these probability amplitudes are canceling each other out but the answer seems the same? I don’t follow how this maps to helping simulate the quantum systems. Quantum computers are good at finding solutions to problems efficiently. But the quantum systems we are describi…
For simulation, it's not about the bad samples: the point is information about the distribution itself.
But simulating a process is not the same thing as efficiently routing space exploration. Quantum computing grants you the latter. Why does it impact the former?
Re: Google Quantum AI
#187Earlier quoted context omitted.
The origins of quantum computing give it a clear use: simulation of many-body systems. Number factorization and anything else in BQP is also an use for them.
Looking forward to when leetcode problems require BPQ complexity analysis
We might never retire but at least we’ll grind out leetcode in our 60’s while on adderall, ozempic, lions mane etc…and won’t feel a day over 55!
Re: Google Quantum AI
#188Earlier quoted context omitted.
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.
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.
What's stopping classical computers from doing this sampling?
If it's sampling, you don't have to deal with the exponential here.
Re: Google Quantum AI
#189The fact this prize exists is admitting that no one has figured out a use for quantum computers. I have heard this mentioned several times in the last decade or so : "The only thing a quantum computer definitively does better than a classical computer is simulating a quantum computer." Whether this capability is useful is up in the air. Note that in practice, classical computers are going to be better at factoring nu…
Ther are plenty of well documented uses for quantum computers, the hardware is just too nascent to fully accommodate them. The most powerful quantum computers today still only have just over 1,000 qbits.
I don't think this is totally accurate.
If you have significantly better quantum computers, you can solve realistic problems, yes.
But what's not being spelled out here is that as far as we know classical computers will still totally smoke them unless you allow a large probability of inaccurate results.
And if you are fine with inaccurate results, classical randomized algorithms make it a much more difficult deadline to beat.
Re: Google Quantum AI
#190Earlier quoted context omitted.
Yes, that was the point of the parent comment.
Thanks for reaffirming Poe's law. I was amused by how 'cell phone' was taken as a given, when talking about a CCD sensor.
No, it was not taken as a given, it was an example of a very common product that digital image sensors enabled. I could have chosen e.g. digital cinema cameras, but they would not nearly have the same profound effect as cell phone cameras have had on society.