8 ms·
Quantum A.I. Publications
- SomeStupidPoint 9y agoWhy is this being upvoted? It's literally just 20 random quantum computing papers with an unrelated heading and a Google banner, because they got flagged with a tag somewhere.
- mdturnerphys 9y agoThe papers aren't random--the names in blue are Google researchers.
- m3kw9 9y agoI would rather them just stick with Arxiv and then when they have something actually working practically, then post how it actually works. Sort of how Apple does it in their machine learning journal.
- dreamcompiler 9y ago"Soon we hope to falsify the strong Church-Turing thesis: we will perform computations which current computers cannot replicate." Yeah, no. This is a ridiculous statement and it is embarrassing to hear it from Google. Quantum computers are not hyper-Turing machines, and there is no reason to suspect they ever will be.
- sobellian 9y agoI too was skeptical. Is there any computation that a quantum computer can perform which cannot be simulated by a classical computer with an RNG?
- petters 9y agoNo, just that some problems are believed to require superpolynomial slowdown.
- sobellian 9y agoCorrect me if I'm wrong but isn't BQP ?= BPP considered a separate problem from the strong church turing thesis?
- petters 9y agoIt is certainly a separate problem. Just as the original comment says: I don't think anyone seriously argues that quantum computers will violate the CT thesis. (Except Penrose, perhaps.)
- deleted 9y ago[deleted]
- chubot 9y agoI think it has to be. The former problem is about computational complexity; the latter is about computability. I don't know much about this topic -- I skimmed through Scott Aaronson's "Quantum Computing and Democritus", and got lost by the last third. As far as I remember, it was all about computational complexity. I don't recall anything about computability, but correct me if I'm wrong. I just had to look up the strong Church-Turing Thesis: The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics. https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis I don't have much justification, but I believe it's false. There is a lot more to the universe than computers. Computers cannot simulate even elementary physical systems accurately. Doesn't it take supercomputers to even accurately simulate even a few atoms? I think the biggest cultural "lie" in the last couple decades is "the Matrix". Since that movie, educated people including software engineers take for granted the fact that the universe can be simulated by computers. They write silly papers like "we are almost certainly living in a simulation". Granted, that argument is sound if you believe it's even possible to simulate the universe with a computer. But I actually take that as further evidence that it's NOT possible to simulate the universe with a computer. Anyway, I haven't thought about these things in a long time, but I would say that just because something is impossible on a Turing machine doesn't mean it's impossible in the universe!
- adamnemecek 9y agoWhy not?
- urgoroger 9y agoWhile it is true that compatibility should remain intact, this comment seems to misunderstand what the STRONG Church-Turing thesis purports (EDIT: at least the one Google is probably referring to). I'm not sure if it's completely agreed upon, but the strong Church-Turing thesis that I am familiar with is: "Every realistic model of computation is polynomial time reducible to probabilistic Turing machines" (https://arbital.com/p/strong_Church_Turing_thesis/ https://arbital.com/p/strong_Church_Turing_thesis/) "A probabilistic Turing machine can efficiently simulate any realistic model of computation" (An Introduction to Quantum Computing, Phillip Kaye, Raymond Laflamme, Michele Mosca) In other words, the efficiency of every realized model of computation needs to be similar to that of a Turing machine for the thesis to hold. As soon as machines capable of quantum computation are realized, the thesis is broken, as they give superpolynomial speedup over classical Turing machines (assuming things like integer factorization are not in P). EDIT: I guess it should be noted that there are probably other 'strong Church-Turing theses' hanging around, but I'm fairly certain the folks at Google are referring to this one, which I too am most familiar with. If OP is referring to one which does not require similar efficiency, then the quotation does seem kind of ridiculous. I also agree that the part of the quote that says "current computers cannot replicate" needs to be interpreted with some notion of efficiency as well.
- Udik 9y agoAccording to Wikipedia: "the [Church-Turing] thesis has several possible meanings: 1) The universe is equivalent to a Turing machine; thus, computing non-recursive functions is physically impossible. This has been termed the Strong Church–Turing thesis, or Church–Turing–Deutsch principle, and is a foundation of digital physics."
- Aardwolf 9y agoWhat is meant by "non-recursive functions" here? From my knowledge a non-recursive function would be easier than a recursive one, since a non-recursive one will not call itself while a recursive one can. But the quoted phrase seems to imply it must be something more difficult instead... Problem is, wikipedia's page https://en.wikipedia.org/wiki/Non-recursive_function https://en.wikipedia.org/wiki/Non-recursive_function does not define it either, it just redirects you to the recursion page (though not recursively, so wikipedia did not go for the joke) which does not define it either.
- mtgx 9y agoWhenever I hear that "quantum computers will forever be specialized processors" I think that at how we must've thought about the very first computers, which were only really good at doing math calculations. Even GPUs have gotten way more general-purpose than what we thought they could achieve even 2 decades ago. I think that if quantum computers become mainstream enough we'll find ways to use them for more general-purpose stuff.
- mathgenius 9y agoQuantum computers (assuming we can build one) can access computational resources far beyond what classical computers can do: imagine a classical computer so big and hot that it collapses down into a black-hole. Or it takes so long to run the computation (eg. a classical computer the size of the solar system) that heat-death of the entire universe comes first. These are the physical limitations of classical computation, and a quantum computer will (if we can build one) surpass this.
- klmr 9y ago> These are the physical limitations of classical computation Classical computation (i.e. the Turing machine) is a mathematical model, and isn’t bound by the physical limitations you imagine. In particular, a Turing machine (which, after all, requires an infinite tape) is already not physically possible.
- mathgenius 9y agoFrom the OP: "computations which current computers cannot replicate." I was just explaining a bit more why this is so. If it matters at all, I've just finished a PhD in quantum computing.
- h2j24 9y agoI don't think that's really true. The difference between a quantum computer and a classical computer is that a classical computer can represent N states given N bits, whereas a quantum computer can represent 2^N states given N q-bits. However, this has a major caveat: you can never know the state of the system. You only get to measure one value at a time and you can never re-create or copy a previously obtained state. Still, some clever people have figured out how to exploit this to achieve polynomial speedup on problems where certain properties of the problem are exploited to get around the limitation of measurement in a quantum system.
- digitalshankar 9y agoI rather use Firefox Quantum than Google Quantum AI, yeah I know it's unrelated and hence the article too.
- deepnotderp 9y ago"Soon we hope to falsify the strong Church-Turing thesis: we will perform computations which current computers cannot replicate. " WTF, has Google gone completely insane? This is so wrong from every angle...
- LolWolf 9y agoSee the above thread given in [0]. It sounds weird, but they are talking about the strong CT thesis (e.g. that all realizable models are polynomial-time-reducible to BPP), not just the usual one (that no realizable model can solve halting-hard problems). --- [0] https://news.ycombinator.com/item?id=15785215 https://news.ycombinator.com/item?id=15785215
- jooke 9y agoThis is still a theoretical problem, not one solvable by building a faster computer
- LolWolf 9y agoYou're right that part of the problem is, indeed, theoretical (it remains to be shown that BPP ≠ BQP, even if it is widely believed to be true), but part of the problem is also physical (we need to build a model of BQP---i.e. a quantum computer---to show that there is a physically realizable model of it).
- klmr 9y agoAs alluded to above, “Strong CT” confusingly refers to several very similar, yet different, concepts. I think this is throwing people off. Quantum computers will almost certainly not disprove the CTD principle [1], which is also known as “Strong CT”. [1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93...
- hackernewsacct 9y agoHow does one get hired to be a researcher at google? What job title or level would this be? How does being a researcher differ from being a regular SDE? What background are they looking for here? Do these people write code on a daily basis?
- blauditore 9y agoDoes anyone know a good resource about quantum computing for quantum physics beginners? I've tried to understand the concepts from Wikipedia, but it's a bit too abstract and I keep on getting lost down the rabbit hole reading up about the QP terms being used. All I understand so far is that apparently, thanks to many independently controllable quantum states, some NP problems can be solved in polynomial time. If I'm not mistaken, this would require infinitely many possible different quantum states, but I've never seen this stated (or contradicted) explicitly anywhere.
- nlperguiy 9y agoI'm not sure if materials on edx are still available but Quantum Mechanics and Quantum Computing [1] course there was mindblowing. I was surprised how the ideas and maths were simple enough. [1]: https://www.edx.org/course/quantum-mechanics-quantum-computation-uc-berkeleyx-cs-191x https://www.edx.org/course/quantum-mechanics-quantum-computa...
- flor1s 9y agoAt least the videos can be found on YouTube: https://www.youtube.com/watch?v=bT5rFIZZeKI&list=PL2jykFOD1AWap0r8WOuZ-08BFgMyx-5RT https://www.youtube.com/watch?v=bT5rFIZZeKI&list=PL2jykFOD1A... Maybe the notes of his course at Berkeley can be used to supplement the videos? http://people.eecs.berkeley.edu/~vazirani/f16quantum.html http://people.eecs.berkeley.edu/~vazirani/f16quantum.html
- mathgenius 9y agoNice book, explaining QC at a high-school level: Terrance Rudolph "Q is for quantum". Here is a very modern approach, that is also understandable without much mathematics: "Bob Coecke: From quantum processes to cognition via pictures" https://www.youtube.com/watch?v=h84CtK33Q8s https://www.youtube.com/watch?v=h84CtK33Q8s Do you already understand the basics? Feynman is nice aswell, I like how he rambles. Try diving in here and backtracking as needed: http://www.feynmanlectures.caltech.edu/III_05.html http://www.feynmanlectures.caltech.edu/III_05.html Don't forget to read it with a thick Brooklyn (long island) accent.
- 9y ago
- yters 9y agoIf we get a useful quantum computer, what then? How will machine learning improve? As far as I know, QM speeds up integer factorization, but I don't see how this transfers to machine learning.
- mathgenius 9y agohttp://math.nist.gov/quantum/zoo/ http://math.nist.gov/quantum/zoo/
- mtgx 9y agoQuantum computers are good/super-efficient at optimization problems. That means they can optimize a solution for something with less data. Right now our AI is only good at solving problems for which we have millions and millions of data points. But we don't have that much data for every problem in the world. Quantum computers could potentially help us create an AI that can work with fewer data points.
- h2j24 9y agoNot an expert, but I believe most of the benefits will come from quantum annealing, which is capable of escaping local minima in optimization problems.
- yters 9y agoSimulated annealing is only guaranteed to find the global minimum as time approaches infinity. Does quantum annealing have a better guarantee?
- mtgx 9y agoIs this some pre-launch marketing for Google? I wonder if they're still able to meet their promise that they'll announce a 50-qubit quantum supremacy computer by 2017. Because the year is ending very soon. Was it delayed, or did IBM crash their party when they announced that even 56-qubits are not enough for quantum supremacy? (not sure if IBM's test was enough to prove that, though)
- pwdisswordfish2 9y agoRANT: As a researcher in quantum optics and spectroscopy, holy shit am I tired of reading through these comment threads where it's clear that nobody understands the topic, yet people still make assertive nicely-sounding statements that are bound to get up-voted by other people who also don't understand the topic. ~ugh~
- agumonkey 9y agoOh well, how timely, I was talking about quantum optics yesterday, and now Im curious about textbooks references, any suggestions ? Even fundamentals and not up to date QC research.
- infinity0 9y agoCan you be more specific and educate us?
- d--b 9y agoYes, please. It doesn't look like on this particular thread, there are many comments that are completely off. Also, CS people are probably just as good talking about the CS aspect of quantum computing as quantum physicists are regarding the quantum aspect of it. no?
- throwawayjava 9y ago> Also, CS people are probably just as good talking about the CS aspect of quantum computing as quantum physicists are regarding the quantum aspect of it. no? No, but that seems like an unfair comparison. Quantum physicists are by definition highly trained scientists; CS people range from teenagers hacking on word-press, to well-trained engineers without much science background, to highly-trained scientists. Or put another way, that depends on what you mean by "CS People".
- WhitneyLand 9y agoThe top end of your range of computer science people is maxed out at, engineers without much science background? The name Turing ring a bell? Just opinion, I consider him one of the greatest minds of his century. He worked on a lot of things but some would say he fits pretty well in cs. And there are more like him who just didn’t happen to become famous to the general public. I could give a dozen more examples of people’s contributions, profound insights, fundamentally important basic research results, that might make you extend, at least the top of your range a bit.