Quantum A.I. Publications
research.google.com
research.google.com
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.
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
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 Don't forget to read it with a thick Brooklyn (long island) accent.
A good place to start might be this paper by Mermin, which defines classical computing bits (Cbits) in a specific mathematical framework and then expands that definition to define Qbits and their states: https://arxiv.org/pdf/quant-ph/0207118.pdf
[1]: https://www.edx.org/course/quantum-mechanics-quantum-computa...
Maybe the notes of his course at Berkeley can be used to supplement the videos? http://people.eecs.berkeley.edu/~vazirani/f16quantum.html
https://www.amazon.com/Quantum-Physics-Dummies-Steven-Holzne...
Secondly, even when people are wrong here they don’t seem any more intransigent or arrogant on average. The point is I would assume they are acting in good faith, however I can’t be sure because you criticize people without specific citations. You use citations in your papers I assume?
Let me change course and try and make this as productive as possible by looking at your comments in the most positive light. You are eminent in the field and somehow found yourself reading terribly uninformed assertively stated comments.
What a lost opportunity to correct and inform. What you could say in only a matter of minutes, could seem invaluable to those passionately interested in the subject. I’m sure it would be appreciated, raise the quality of discourse, and may help spread a more informed and accurate lay perspective of the field.
What would Susskind do? If he were here reading comments on a black hole article (for a reason I can’t imagine)? I don’t know him personally but whenever I listen to him lecture I’m always impressed by how willing he seems to share his genius with people interested in learning.
HN readers aren't sheep. We're more than capable of skimming past light-on-fact comment to get to the good ones.
> Often, the article is so wrong it actually presents the story backward-reversing cause and effect. I call these the “wet streets cause rain” stories.
[0]: https://web.archive.org/web/20141025035056/http://www.thegre...
Let’s add cryptography and quantum complexity theory while we’re at it :)
I'm sure we can all do with a bit of education here.
Edit: This seems to be an unpopular comment already, so let me sidestep potential criticism with the following clarification: I work in cryptography, both professionally and academically, and I make every attempt to help improve understanding of that discipline here on HN. My comment here is directed at the current top comment in the thread. An open rant about some group’s poor understanding of a highly technical area to that group does not improve their understanding, and it will just isolate everyone who reads the comment who doesn’t have a firm grasp of the field (which by the nature of the rant will imply most people reading it).
The feeling of exasperation is valid, but share it with colleagues, or augment it with some attempt at guidance. Otherwise, what are you ranting about except to yell at something that isn’t going to change, while everyone must sit around and be witness to your condescension?
for example:
field: physics
specialty: quantum optics, spectroscopy
level: researcher, PhDBut there is -- though not always -- more of a culture of anonymity here.
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".
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.
More over, as a scientist, I don't think highly trained scientists are "higher" than highly trained engineers. They're different and not well-ordered. So your "maxes out at" verbage is not agreeable to me.
I apologize with no reservations. I try to read precisely before responding, but clearly did not take care to do so in this case.
Ironically after reading/thinking more, we may actually have similar perspectives on the subject. I’m curious what you mean by “not well-ordered”? However if you do you feel like replying, no problem, I would understand that.
In any case, take care. Sorry for the misunderstanding.
Just that researchers aren't better/smarter/etc. than engineers and vice versa. They are different jobs, both essential in their own way, both difficult in their own way.
> Sorry for the misunderstanding.
No worries! :)
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.
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.
"So the bottom line is that, for "generic" or "unstructured" search problems, quantum computers can give some speedup over classical computers -- specifically, a quadratic speedup -- but nothing like the exponential speedup of Shor's factoring algorithm."
"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."
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 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.
A “non-recursive function” would be more powerful than that; or, conversely, it would be a function which cannot be computed using a Turing machine. Alternatively, these are also know as super-recursive functions [2].
[1] https://en.wikipedia.org/wiki/Computable_function [2] https://en.wikipedia.org/wiki/Super-recursive_algorithm
> A probabilistic TM can efficiently[1] simulate any realistic model of computation.
Taken from [0].
Note that this statement is actually false if two things are true: (a) BPP ≠ BQP (this is unknown, at the moment; we don't even know if BPP ≠ P, but it's not difficult to show that P ⊆ BPP ⊆ BQP) and (b) that BQP is physically realizable (e.g. we can actually make physical quantum computers)---both statements are, overall, what Google is claiming.
Why? Because (b) would mean that there is a realistic model of computation which models BQP and (a) would mean that there is at least one problem in BQP which is not polynomially reducible to a problem in BPP; therefore it follows that a probabilistic TM (which models BPP, by definition) cannot efficiently simulate the particular model of computation given by a model of BQP (i.e. a quantum computer).
On the other hand, if we find that BPP = BQP (which is widely believed to not be true) then we're back to square one and the strong Church-Turing thesis would still hold.
---
[0] https://en.wikipedia.org/wiki/Church–Turing_thesis#Variation...
[1] "Efficiently" here means that any model is polynomial-time reducible to a standard model of probabilistic computing.
Additionally, the "probabilistic" aspect comes from the "fact" (i.e. observation) that we can make "good" random number generators in real life (say, by measuring background radiation), but it's unclear if there exist pseudo RNGs that are "good enough," algorithmically, to derandomize BPP. That is, such that BPP = P (the claim of "good enough" PRNGs is stronger than BPP = P, in fact, see https://mathoverflow.net/questions/2272/pseudorandom-generat...).
That is, we do not know if P ≠ BPP.
BQP is a subset of BPP (equal or ~~strict~~): Then the state of the thesis is unknown. There is still some chance that is is false, either by a superpolyomial speedup somewhere higher up the hierarchy (not too sure about this one, my complexity theory is not sharp enough to rule out that this is impossible given BQP is a subset of BPP), or that there exists another realizable model of computation other than quantum computing that beats the randomized turing machine.
EDIT: It appears that BPP (trivially) a subset of BQP, so that the strict inclusion of BQP in BPP is impossible, though BQP = BPP is possible.
(Except Penrose, perhaps.)
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
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!
Correct me if I'm wrong, but wouldn't a system that computes a non-recursive function be some sort of box where, given the same inputs, you invariably obtain the same outputs; however there is no way of finding any mathematical or algorithmic expression that could, in any finite amount of time, predict the same result? To find yourself in that situation, you need a physical process that is intrinsically non-computable; being unable to compute the sum of computable processes is not enough.
edit: I guess not, since all you need is access to the real numbers which is a strict superset of computable numbers, but this doesn't seem like an "interesting" violation of the SCT.
Math is FULL of functions that can be described -- have properties X and Y, which are useful to prove theorems -- which nobody has thought about how to compute.
(Obviously, there are the ones related to incomputibility like the Godel function, but there are others too... I'd appreciate help from others here :) )
And it might not even be useful or interesting (for the purposes of mathematics) to compute them. Not all math is constructive.
Likewise you can describe physical processes without computing them.
That said, you're right, if all that is required is real numbers, then hypothetically an analog computer is all that would be required. But in a truly quantum world where SCT holds, an "analog" computer is only a computable approximation.
(Full disclosure: I guess....)
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.
If it matters at all, I've just finished a PhD in quantum computing.
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.
I think that if quantum computers become mainstream enough we'll find ways to use them for more general-purpose stuff.
WTF, has Google gone completely insane? This is so wrong from every angle...
---
[1] https://en.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93...
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)
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.
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.