Comment by krastanov | Hacker News Reader

Comment by krastanov | Hacker News Reader

Parent Full thread

There is a serious misconception in your claim. Yes, analog computers, whether quantum or classical solve even NP-complete problems in polynomial time. No, they can not be constructed in the real world because analog computing does not permit error correction, and in the real world you have to deal with noise. Only very small analog computers (nothing scalable, nothing solving general problems) can be constructed before noise becomes an issue.

Three good references:

Book on quantum and classical computing: Aaronson's "Quantum Computing since Democritus" for gentle-for-newbies but rigorous discussion

Very old paper on classical computing (analog vs digital): Von Neumann's "Probabilistic logics and the synthesis of reliable organisms from unreliable components" (pretty advanced)

Newish (old for the field) paper on quantum computing: Calderbank's "Good Quantum Error-Correcting Codes Exist"

Edit and addition: I work at Yale's Quantum Institute and we are some of the biggest proponents of "continuous variable" quantum computing. We use the continuous variables to encode a discrete "qudit" (with a "d") representation for the information, for all the reasons mentioned above (noise and error correction).

I love Aaronson's book but it's not "gentle-for-newbies". Not because it's not gentle! It just explicitly skips over a lot of the material. You're expected to already know about quantum computing since he doesn't feel he can add to existing authors on the subject. Instead, it's really a survey of quantum complexity theory, with some sampling of background material where the author felt he had something new to say.

What's a good book for Quantum Computing? When I took Aaronson's class last semester I got so wrecked by everything, and it just felt like everything was so conflicting from many different resources

I learned from a coursera course some number of years ago. It was actually quite good. (This should also give you the correct impression that I am not an expert here and you should take my suggestions with a grain of salt.) I think it was this one: https://www.edx.org/course/quantum-mechanics-quantum-computa... (Taught by Aaronson's advisor.)

To add to the answer already given, keep in mind that it depends on what you want to learn.

Theory from the point of view of physics (as in, less focus on algorithms, but some focus on building hardware): see Preskill's notes or Chuang&Nielsen's book.

I would suggest quickly skimming them once before trying to read them cover to cover.

And some lighter online introductions might help as a first step.

You definitely will need very good knowledge of college level linear algebra (linear operators, basis, diagonalization, eigenvalues).

Unfortunately I have nothing yet to add to your discussion with parent, but I was wondering if the two of you might peek at the following paper, and let me know if and where it fits into the picture:

[1] Jose Luis Rosales, Vicente Martin, "Quantum Simulation of the Factorization Problem", 9 Nov 2016. (https://arxiv.org/abs/1601.04896)

Disclaimer: I only skimmed the article.

This is pretty cool, but I think the main point of the article is to show an amazing link between number theory and the theory of quantum mechanics, not to suggest a practical quantum algorithm. Although, for certain hardware implementations what they are suggesting might be easier than Shor's algorithm, just because of technical reasons.

Either way, this is not "continuous variable" or "analog" in the sense discussed above. If you are interested about the distinction, you can also check out Adiabatic Quantum Computing, which also seems continuous on first sight, but it is equivalent to the typical model of quantum circuits (the trick being the existence of a "gap" between the ground state which we are adiabatically evolving and all the other states of the system).

I threw a bunch of terminology without defining them, but I would have to leave googling those to you. I would be happy to attempt to answer questions though.

They aren’t misconceptions, I’m questioning some currently held assumptions. You are still talking about electric right? Why are assuming I’m unaware of your claims? I’m aware of e.g. error corection problems but I would definitely not say it’s impossible.

Photonic systems have plenty of error correcting schemes.

Does not matter whether it is electric or photonic (and many systems are in between). Scalable error correction (i.e. the error approaches zero in the limit of a large system) is possible only with digital systems, whether classical or quantum.

There are things we can do to suppress errors and make a slightly bigger analog computer (classical or quantum) but there is no way to make an analog system scalable (i.e. not just lower errors to some floor, rather completely eliminate errors).

The book cited in my previous comment explains the details in a fairly understandable fashion, but it takes up a whole chapter. The gist of it is, you need some minimal "logic distance" between your data "levels" in order to be able to distinguish them and correct deviations. This requires digitization.

If somebody finds a way to error-correct analog representations they will have a way to solve NP-complete problems for instance. The Nobel price will be the least of their recognitions.

Have you ever heard the expression if an expert tells you something can be done, s/he's prolly right. If s/he tells you it can't be done it's not quite certain.

Im not convinced that our understanding is quite there to say it can or can't be done.

Certainly, this is a good point. However would you use that expression if what I said was "you can not make a perpetual motion machine"? Or if I had said "NP probably does not equal P"?

A scalable analog computer goes against some "first principles", not mere technicalities. If you want to claim that it is feasible to build it, you need a way to address those first principles.

For instance, the existence of scalable analog computers implies that we can solve NP-complete problems easily. This is a claim as crazy as "perpetual motion machines". It would be great if either of those claims actually become feasible, but there is a gigantic wall of "first principles" that have to be addressed - mere optimism is not enough.

This is what I want to stress - do not trust people when they rely on technicalities to shoot down your argument, but if they are pointing out fundamental laws of nature as impediments, maybe it would be interesting for everybody if we try to learn and discuss those fundamental laws.

Re: P != NP, I would say that question assumes a certain architecture, so while it might hold for Turing machines, the real question is is a HyperTuring/Turing machine really all there is? I assume you are familiar with Real Computation? https://en.wikipedia.org/wiki/Real_computation I did note the "if real computation were physically realizable" clause, however, I'm not going to be placing bets.

> A scalable analog computer goes against some "first principles", not mere technicalities. If you want to claim that it is feasible to build it, you need a way to address those first principles.

I find your argument to rely on classical logical reasoning as opposed to constructive (intuitionistic) logical reasoning. There is quite a lot of excluded middle in all of these questions that you aren't accounting for. "First principles" are nice and all but, my fundamental problem right now is that I'm having a hard time verifying the "first principles" for myself.

> but if they are pointing out fundamental laws of nature as impediments, maybe it would be interesting for everybody if we try to learn and discuss those fundamental laws.

You are assuming that I'm not aware of those principles. I'm not saying I have solutions, I just don't feel like anyone's given it a proper shake quite yet.

>Re: P != NP, I would say that question assumes a certain architecture, so while it might hold for Turing machines, the real question is is a HyperTuring/Turing machine really all there is?

No, P and NP are defined by an architecture, there's nothing to assume about it. E.g., P is defined as "problems solvable in polynomial time on a deterministic Turing machine".

I think that you misunderstood what I meant by assumed. If I replaced it with implies would that clear the confusion?

If your only response to a reasoned argument is a dubious aphorism, you’ve already lost the discussion. You are literally just arguing from disbelief.

I don’t agree that certain things are necessarily impossible. I don’t have a proof yet. Wait ten years.

Reply on news.ycombinator.com