urgoroger

What I was trying to communicate was that the Turing machine believed to represent the limits of what is physically possible. So then you have

turing machines >= brain (since a brain is physical) and brain >= turing machine (by simulation argument)

The conclusion is the brain and Turing machine can do the same thing (brain = turing machine).

In accordance with the Church-Turing thesis, the Turing machine stands to be capable of doing anything that should be called computation. It follows that if the brain is capable of simulating of a Turing machine (this is called a universal Turing machine, by the way), then it too can do any computation. So then the class of things that both can do are the same, and so it is reasonable to call them the same thing, in some sense.

I think the commentor's point is that measurement (which is a key component of quantum computation) is not a unitary operation.

It might be easier to view entropy of a state as sort of the probability that that state would occur after randomly arranging all of its parts (usually particles). In fact this is pretty close to the actual definition.

Here's an example: Suppose you had a container and you put some marbles at the bottom such that there are reasonably large gaps between the marbles. Now if you close and then shake the container hard (this is the 'random arrangement' process), then it is with high probability when you open the container that the marbles will be arranged reasonably spread out across the bottom. In this sense, when the marbles are spread kind of far apart in the container, it is in a state of high entropy (probability).

There is also the chance that when you open the container the marbles form a perfect straight line at the bottom. However, this is much more unlikely, so that you would consider this a low entropy state.

Now, consider the universe in place of the container, and subatomic particles as the marbles. Randomly configuring all of these particles, it would be really hard to end up with a stars, galaxies, humans. These are like straight lines in the marble example. It is much more likely you just get a soup of somewhat uniformally distributed particles (as in the marbles just being sort of randomly spread out from each other). This is what you describe as "a perfectly uniformly distributed of zero temperature mass (or maybe absoute zero, not sure) of grey energy is the perfect order". It wouldn't really be 'perfect' in some senses of the word though, which may be your cause of confusion. It would be more like if you took a snapshot of the static on an old TV.

Yes, this is pretty much the basis to quantum key distribution protocols, and probably one of the first studied uses of quantum information in general. Consider BB84 (http://www.cse.wustl.edu/~jain/cse571-07/ftp/quantum/, https://en.wikipedia.org/wiki/BB84, apparently the first quantum cryptography protocol), which would allow the transmission of a one time pad with an any eavesdropper being unnoticed with provably exponentially decreasing probability in terms of key length. The one time pad can then be used to securely transmit data.

Thus it is possible to transmit arbitrary (classical) data with exponentially decreasing probability that we do not detect an eavesdropper. Alice and Bob can communicate with each other knowing that there is provably pretty much no chance that anyone else knows what they said to each other.

I want to add that quantum FFT performs the transform on the amplitudes in the n-qubit state. Thus its output is an n-qubit state with the amplitudes matching the fourier tranforms. We cannot actually directly extract the amplitudes of the resulting state (which is the actual transformed values) from the system, since a measurement collapses the state of the system.

While some people have figured out how to used the result of the quantum FFT to do useful things (e.g. Shor's algorithm), it does not actually provide us with the transformed values in the traditional sense as the classical algorithm does.

I think you have the right idea but the wrong terminology. A n qubit system requires amplitudes (probabilities) for all 2^n possible basis states. For example, the representation we can give to a 2-qubit system is just a probability (technically an amplitude) associated with each of states 00, 01, 10, and 11. It's not really fancy or hard to see how this increases exponentially.

Here's an example with classical randomness (and has a close quantum analogue). If you have two closed boxes with coins in them and shake both around so that the coins flip around in the in such a way that they land 50/50 on each side, you could represent that state of the system as [1/4, 1/4, 1/4, 1/4], that is, each possible state of the system of two coins (heads head, heads tail, tail head, and tail tail), has 1/4 chance of being observed when you open the boxes.

Note that entanglement refers to the idea that two bits can be correlated. That is, the state of one is correlated with the state of another in some sense. In the example I just gave, the coins are not entangled, since the observation of one of the coins does not affect the probability of what the other coin could be. In mathematics we say this is possible if the state of the 2-coin system [1/4 1/4 1/4 1/4] can be written as a tensor product of the constituent 1-coin systems [1/2 1/2] and [1/2 1/2], which it can (entanglement refers to a state where this factorization isn't possible).

That said, we can achieve entanglement with the coins too, by somehow getting a state vector like [1/2 0 0 1/2] (50% chance that both coins are heads and 50% chance both are tails), which cannot be written as a tensor product of two 1-coin states. Moreover, if you open one box and see its a heads coin, you know the other box must also have a head coin. That's what is meant by 'correlation'. To product such a state of the coin boxes, I guess you would need a third party or something to put the two coins in the boxes and delivering them to you.

My conclusion is, entanglement doesn't have to do too much with the exponential size of representation n-qubit states, and I hope I gave a good example of what entanglement kind of really means. While (randomized) classical analogues to quantum effects are not really perfect, I think they demonstrate these effects more understandably.

That's correct. Given a polynomial time approximate algorithm for Ek-SAT (note, by approximate algorithm I mean along the lines of the formal definition of approximate algorithm, that the solution given by the algorithm falls in some fraction of the real answer for all instances, see https://en.wikipedia.org/wiki/Hardness_of_approximation), you would show P=NP.

My first concerns, namely the usage of analog methods to solve NP-complete problems, lies along the same lines as this post: https://www.scottaaronson.com/blog/?p=2212

Moreover, from what I can see, and as you mention as your original concern, the extent of proof for the 'exponential-speedup' claim exists in the form of some benchmarks, hardly a proof that their method actually works on all instances, which would be needed to show that it is a approximation algorithm as commonly defined.

The purpose of my post was to highlight that for some problems (for example, TSP), even a really crappy approximation algorithm would imply P=NP. As highlighted by the authors of this paper, MAX-EkSAT is in a similar situation, though judging by https://www.cse.buffalo.edu/~hungngo/classes/2006/594/notes/..., unlike TSP, approximation to SOME ratio is possible, though there exists aratio >1 which cannot be beat unless P=NP.

I was simply trying to address the statement: "So it appears that they're finding approximate solutions, so already it's rather less significant than the title suggests. ", since an actual approximation algorithm for some ratio really WOULD be significant (showing P=NP).

While I agree with you, you should note that even approximation within any degree of error is NP-complete for a large class of NP-complete problems (e.g. TSP, and the problem MAX-EkSAT used in the paper).

That is, a polynomial algorithm for the approximate problem would be just as significant as one for the exact version.

Don't worry! I study quantum computation, and I didn't notice that the |> was supposed to be a D to form the word LIQUID!

Could be wrong too, ML is not my field.

Basically, a generator neural network has two things which affect its output: an input and some parameters (weights).

Let's use the setting of the task for denoising images. They use a network who's output is to is the denoised image, and compare it to the noisy image to get a score for how good the denoised output was.

Now the strange thing is, for the input of the network, they just use random garbage. The only thing they move around to try get a good denoising score are the parameters of the network (not the input).

They find that by only adjusting the parameters, even with fixed random crap inputs, if they find the parameter setting which minimizes the noise, they actually still get great looking results.

This suggests that the networks they tested this method with (other researchers work who do well on this task) are based much more in the inherent structure of the network, rather than the model refinement from training on thousands of images, since even given random crap, they generates good results, as long as the parameters are tuned well to the noisy image.

x is actually the generated image they are testing against x0. A lower E(x; x0) means an image which fits well towards the objective based on the original image (depends on the task). The paper gives some examples. For example, for the task of image denoising, E(x; x0) is just the squared distance of the generated (denoised candidate) image x to the pixels to the original image x0. Obviously you would want this to be low in the generated version since it should still look close to x0.

R(x) is a regularization term to avoid overfitting. For example, in the denoising example, it could be a measure of the variation in color of x. Clearly, just taking x = x0, the squared error (E(x; x0)) is 0, but it will have high R(x) because of all the noise. That's why they try to minimize both quantities combined, so we get min_x E(x; x0) + R(x), to get close to the objective but also not overfit.

https://en.wikipedia.org/wiki/Regularization_(mathematics)

This is correct, and I think it's mentioned in the article. I think this is probably what most people would think of too rather than the heap based solution. Using the heap solution also requires you to know how to use a heap in whatever language your interviewing in, or you could implement one (which would probably a lot more effort), so I prefer this one.

EDIT: Ah, I didn't read your comment carefully enough. I thought you were referring to a divide and conquer approach when you meant 'like merge sort', where you the list of lists in half for each recursion, the recombine the sorted halves using a standard merge sort list merge.

What you describe is basically the same as the solution given by the author. However, you don't give a way to find the minimum pointer, in the case of the author, a heap is used. Using a more naive data structure/algorithm (e.g. just finding the min over all pointers every time) will probably give worse asymptotic complexity than using a heap to maintain the least element

There are a two cases: BQP contains something BPP doesn't: Then the thesis is false as long as we can realize a quantum computer, as then there exists something which can be solved in polynomial time (with bounded error) on a machine in the universe which cannot be done on a classic Turing machine as efficiently.

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.

While 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/) "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.