Hmm, I guess not, actually. If that were the case, UHU* + VKV* would be diagonal, with eigenvalues lambda_i + mu_i, if lambda_i are the eigenvalues of H and mu_i are the eigenvalues of K. So the rhs above should be diagonal with e^{i(lambda_i + mu_i)} entries on the diagonal.
-
-
Replying to @3blue1brown
That's right. When H and K don't share a common basis there's no obvious reason to expect there to be any relationship between the spectrum of exp(iH) exp(iK) and H and K. Thompson tells you there's a really strong relationship.
1 reply 1 retweet 3 likes -
Replying to @michael_nielsen
Interesting. Is there a short answer to what U and V are in this case?
1 reply 1 retweet 2 likes -
Replying to @3blue1brown
Not as far as I know. In fact, I'm not even certain there's a constructive proof known - unless the situation has changed, Thompson's result depends on the proof of Horn's Conjecture by Allen Knutson, Terry Tao, and Alexander Klyachko, and I've never mastered that.
2 replies 1 retweet 2 likes -
Replying to @michael_nielsen
Whoa! Now I feel downright sheepish about my initial take. I'll have to think more on this... It feels like U and V have to bear some relation to the relevant diagonalizing, but maybe that's just me being grounded too stubbornly in certain intuitions.
1 reply 1 retweet 2 likes -
Replying to @3blue1brown
Some relationship, yes. But a priori, to me, it seems very complicated to say what exactly.
1 reply 1 retweet 1 like -
Replying to @michael_nielsen @3blue1brown
Hmm. Actually, upon reflection I like your response: I'll bet there is a reasonably simple proof of Thompson's theorem possible. But so far as I know the best way known today is still through the proof of Horn's conjecture, and that is somewhat hairy.
1 reply 1 retweet 1 like -
Replying to @michael_nielsen
Well, in either case, it seems worth meditating on for a bit. Is there a nice use for this result in QM/QC?
1 reply 1 retweet 3 likes -
Replying to @3blue1brown
With some collaborators I used it to figure out the optimal approach to synthesizing certain quantum gates: https://arxiv.org/pdf/quant-ph/0307190.pdf … I suspect something in this vein must be useful for proving more powerful results in quantum computational complexity.
1 reply 1 retweet 4 likes -
Replying to @michael_nielsen @3blue1brown
In general, a huge problem in computational complexity (classical and quantum) is that there's no powerful notion known of "accumulated progress", of what it means to get closer to a target operation.
1 reply 1 retweet 4 likes
Thompson's theorem tells us that in fact the spectrum does behave in a well-behaved way, and so does give a useful measure of progress. Unf. there's good reasons to think it's not powerful enough to prove the kinds of things
-
-
Replying to @michael_nielsen @3blue1brown
you'd really like (e.g., superlinear lower bounds for 3SAT).
1 reply 1 retweet 3 likes -
Replying to @michael_nielsen @3blue1brown
(Terribly embarrassing: AFAIK, the best circuit lower bounds for 3SAT are _linear_. I.e., we can't even prove it takes n log n gates. Basically, we know that you need to examine the input, and not much else...)
0 replies 1 retweet 4 likes
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.