Comment by DannyBee | Hacker News Reader

Comment by DannyBee | Hacker News Reader

Parent Full thread

The one part that sort of surprises me is he says "The second thing we are missing is that the Model has not in fact found a way of obtaining a program with g < m. (Moreover, Fable tells me this is impossible, but I do not follow the argument yet.)"

I'm not sure what argument fable gave him, but this part seems not horribly difficult to prove. I'm sure i'm missing something since i'm not that great at this kind of math.

The short reason is that each slice call can at most double the number of nonzero entries, but a transform that would enable g < m must turn a single nonzero entry into (2^m) nonzero entries in a single call.

Since the permutes can't generate non-zero entries (since they only move things around), you actually need exactly m slice calls in the initial 2-instruction model given (where you can only do slices and permutes) precisely because of the need to create 2^m non-zero entries where each individual slice op can only double the number (and permutes do nothing)

Astra actually comes up with a variant of this argument as well: https://gist.github.com/dberlin/e785c51aff0285c9c0a3ea0f24fa...

I think you have an also have not disproven the existence of a magical gadget of this general style. The programs mentioned in the paper have a very restrictive form, and I think you’re right that a program of that sort cannot propagate information through the array faster than the naive algorithm. But the actual average-case-ish gadget mentioned later is not of that form - it also has additions and maybe other things going on.

Interestingly, the operations discussed in this part of the note are, I think, pretty much exactly the operations needed to operate on classical representations of an m-qubit quantum state, implementing single-qubit unitary quantum gates on each qubit.

I suspect that, if you had asked me fifteen years ago if I thought you could do the same exact operations like this on each of n different states (on a classical computer) faster than n times however long it would take to do it once, I would have said “sure, why not?” It probably helps that I worked with people who really liked matrix multiplication and similar problems :)

For fun, I have ChatGPT Pro chewing on the following prompt:

Suppose I have a m-qubit quantum state. I can do an operation U = U_1 \otimes ... \otimes U_m, which is just a unitary operation on each individual register.

I can also simulate this on a classical computer. Start with the state, written out classically as a complex amplitude for each state in the computational basis (i.e. 2^m complex numbers). U acts on this state in a linear manner to produce a new state. What's the classical time complexity of this? (Assume a model of computation with exact complex addition, multiplication, conjugation, etc taking unit time, but don't cheat by encoding absurd things into complex numbers. Assume data movement is free.)

Now suppose I want to apply the same U to n separate input states. Can I do better than n times however long it takes to do the operation once?

I actually agree with what you wrote. I'm specifically referring to the very restricted instruction set and not the later one where it is allowed another type of operation. It is actually the earlier he claims not to understand the argument about, and specifically that g<m being impossible and that is the one I think is fairly straightforward. But you are also right that while what I said definitely rules out g<m, It does not rule out making it faster despite that and I would not be shocked if it was possible even without allowing for another kind of operation

ChatGPT Pro says that it can be done faster based on the earlier OpenAI DFT paper.

All of these algorithms are neat but utterly ridiculous :)

The answer I got back makes me suspicious that quite a few of the recent OpenAI improvements on problems that involve some sort of multiplication are are related to each other and may even be, in some sense, examples of the same insight.

Reply on news.ycombinator.com