Gil, again I’m not following your reasoning here. From my layman perspective, it seems very natural that noise should scale up at least linearly* with the number of qbits for boson sampling, absent error correction, or for any quantum circuits, absent error correction.** But this is fully consistent with QC being physically possible, e.g. we could both have polynomial noise for boson sampling, absent error correction, and negligible noise for boson sampling, present error correction. So, what is your line of thought according to which the former is evidence against the latter?

* actually I would have expected superpolynomial

** in the same vein and reversed direction, I also don’t get what intuition about the physical world would plead for position b, i.e. noise should increase as 1/poly(n).

The relevant bits seem to be

We show an experimental demonstration of an actual memcomputing architecture that solves the NP-complete version of the subset sum problem in only one step and is composed of a number of memprocessors that scales linearly with the size of the problem. We have fabricated this architecture using standard microelectronic technology so that it can be easily realized in any laboratory setting. Although the particular machine presented here is eventually limited by noise—and will thus require error-correcting codes to scale to an arbitrary number of memprocessors—it represents the first proof of concept of a machine capable of working with the collective state of interacting memory cells, unlike the present-day single-state machines built using the von Neumann architecture.

from the abstract, and

We therefore conclude that our machine compresses data in an exponential way with constant capacity. At the output, we have an exponentially decreasing probability of finding one solution of the SSP when we implement the algorithm by brute force, that is, without any error-correcting coding. However, from the Shannon theorem, there exists a code that allows us to send the required information with bounded error. The question then is whether there is a polynomial code that accomplishes this task. We briefly discuss the question here heuristically. If our machine were Turing-like, then the polynomial code could exist only if N P = P. Instead, our machine is not Turing-like, and the channel can perform an exponential number of operations at the same time. Because this is similar to what quantum computing does when solving difficult problems such as factorization, and we know that for quantum computing polynomial correcting codes do exist (9), we expect that similar coding can be applied to our specific machine as well.

That sounds incredibly hand-waving to me: “quantum computing does something similar to what ours is doing, therefore ours is at least as good as that”, but it’d be nice if you could analyse that claim more robustly. At the very least, would a polynomial error codes existing allow solving NP-complete problems in polynomial time and resources, and is there reason to think polynomial error codes won’t exist.

]]>First, I would say that one can’t judge the value of an opinion *solely* by the amount of courage that’s required to hold it. I hope reasonable people can agree that, all else equal, it’s more valuable to speak a moral truth that no one in your social circle recognizes than one that everyone in your circle recognizes—but that *either* is more valuable than speaking a moral falsehood.

Second, what is or isn’t worth saying, and what does or doesn’t require courage to say, are extraordinarily context-dependent questions. I’ll admire you for talking about everything the US military has done wrong in rural Oklahoma, but in Berkeley, CA, I’ll probably only admire you for talking about what the US military has done *right*.

I think this phenomenon can fully explain how it’s possible that Turing could be hounded to death for being homosexual, while at the same time and in the same country, George Orwell could truthfully say that, in the social circles where *he* traveled, defending homosexuality was so passé that one obviously got no moral credit for doing it.

“Within the last few decades, in countries like Britain or the United States, the literary intelligentsia has grown large enough to constitute a world in itself. One important result of this is that the opinions which a writer feels frightened of expressing are not those which are disapproved of by society as a whole. To a great extent, what is still loosely thought of as heterodoxy has become orthodoxy. It is nonsense to pretend, for instance, that at this date there is something daring and original in proclaiming yourself an anarchist, an atheist, a pacifist, etc. The daring thing, or at any rate the unfashionable thing, is to believe in God or to approve of the capitalist system. In 1895, when Oscar Wilde was jailed, it must have needed very considerable moral courage to defend homosexuality. Today it would need no courage at all: today the equivalent action would be, perhaps, to defend antisemitism. But this example that I have chosen immediately reminds one of something else—namely, that one cannot judge the value of an opinion simply by the amount of courage that is required in holding it. There is still such a thing as truth and falsehood, it is possible to hold true beliefs for the wrong reasons, and—though there may be no advance in human intelligence—the prevailing ideas of one age are sometimes demonstrably less silly than those of another.”

Orwell, in 1949. So a few years before Turing was murdered for being homosexual.

http://georgeorwellnovels.com/essays/unfinished-essay-on-evelyn-waugh-1949/

]]>And if you wanted *classical* complexity theory rather than quantum, here are four books I recommend (the first is the most introductory, the third and fourth are the most modern in what they cover):

Sipser, Intro to the Theory of Computation

Papadimitriou, Computational Complexity

Arora and Barak, Computational Complexity: A Modern Approach

Mertens and Moore, The Nature of Computation

My (less obvious and more interesting, yet disputed) modeling draws from d) consequences (implicitly described) for general implementations of quantum circuits. (I think that they are kosher as well…)

Regarding the second question: for all we know, noisy quantum states describing implementations of universal noisy circuits with a small number n of qubits can be compared to implementations of noisy bosonsampling with a small number n of bosons. For the later model Kindler and I showed that the states can be approximated by low-degree polynomials and this is likely to apply also for the first model (for low entropy states.) For our result, all you need to assume is that the initial conditions are subject to Gaussian noise of some kind.

This gives a good theoretical reason that breakdown will occur for handful of qubits since we do not expect “bounded-depth machines” that practically compete well (or are even superior to) the full power of classical computers.

]]>@Scott I sort of try to learn complexity theory on my own on my spare time. So I followed your advice, and bought your book, QCSD. I read all of it cover to cover. Frankly speaking, I did not understand 95% of the materials, especially how easily you posed and solved the problems. I have not given up, and I will re-read the book again after I finish writing my PhD thesis (my major is engineering), somewhere in March 2016. I think I need more background materials. I searched my university library and found a book by Chuang et al. “Quantum computation and quantum information.“ Do you reccomend this book? Also what othe authors should I seek to cover enough starting materials to enrich my understanding of complexity theory?

Sorry I put this here where everyone is cheering the recent good work.

]]>> If this is what you mean

Yes

> There is a [somewhat disputed] modeling of noise (…) I expect it to escape any threshold theorem

Ok. Do you expect it (or a variation on it) to become kosher soon? (from the point of view of, say, most experts discussing this topic)

> there are good theoretical reasons for why implementation of quantum circuits will fail on a small number of qubits

Can you tell more? and, more specifically, do you have some intuition about what kind of hamiltonian or initial conditions could force this feature?

]]>