Monday, September 19, 2016

Brute forcing Crazy Game Puzzles

In the 1980s, as a kid I loved my Crazy Turtles Puzzle ("Das verr√ľckte Schildkr√∂tenspiel"). For a number of variations, see here or here.

I had completely forgotten about those, but a few days ago, I saw a self-made reincarnation when staying at a friends' house:



I tried a few minutes to solve it, unsuccessfully (in case it is not clear: you are supposed to arrange the nine tiles in a square such that they form color matching arrows wherever they meet).

So I took the picture above with the plan to either try a bit more at home or write a program to solve it. Yesterday, I had about an hour and did the latter. I am a bit proud of the implementation I came up with and in particular the fact that I essentially came up with a correct program: It came up with the unique solution the first time I executed it. So, here I share it:

#!/usr/bin/perl

# 1 rot 8
# 2 gelb 7
# 3 gruen 6
# 4 blau 5

@karten = (7151, 6754, 4382, 2835, 5216, 2615, 2348, 8253, 4786);

foreach $karte(0..8) {
  $farbe[$karte] = [split //,$karten[$karte]];
}
&ausprobieren(0);

sub ausprobieren {
  my $pos = shift;

  foreach my $karte(0..8) {
    next if $benutzt[$karte];
    $benutzt[$karte] = 1;
    foreach my $dreh(0..3) {
      if ($pos % 3) {
 # Nicht linke Spalte
 $suche = 9 - $farbe[$gelegt[$pos - 1]]->[(1 - $drehung[$gelegt[$pos - 1]]) % 4];
 next if $farbe[$karte]->[(3 - $dreh) % 4] != $suche;
      }
      if ($pos >= 3) {
 # Nicht oberste Zeile
 $suche = 9 - $farbe[$gelegt[$pos - 3]]->[(2 - $drehung[$gelegt[$pos - 3]]) % 4];
 next if $farbe[$karte]->[(4 - $dreh) % 4] != $suche;
      }

      $benutzt[$karte] = 1;
      $gelegt[$pos] = $karte;
      $drehung[$karte] = $dreh;
      #print @gelegt[0..$pos]," ",@drehung[0..$pos]," ", 9 - $farbe[$gelegt[$pos - 1]]->[(1 - $drehung[$gelegt[$pos - 1]]) % 4],"\n";
      
      if ($pos == 8) {
 print "Fertig!\n";
 for $l(0..8) {
   print "$gelegt[$l] $drehung[$gelegt[$l]]\n";
 }
      } else {
 &ausprobieren($pos + 1);
      }
    }
    $benutzt[$karte] = 0;
  }
}

Sorry for variable names in German, but the idea should be clear. Regarding the implementation: red, yellow, green and blue backs of arrows get numbers 1,2,3,4 respectively and pointy sides of arrows 8,7,6,5 (so matching combinations sum to 9).

It implements depth first tree search where tile positions (numbered 0 to 8) are tried left to write top to bottom. So tile $n$ shares a vertical edge with tile $n-1$ unless it's number is 0 mod 3 (leftist column) and it shares a horizontal edge with tile $n-3$ unless $n$ is less than 3, which means it is in the first row.

It tries rotating tiles by 0 to 3 times 90 degrees clock-wise, so finding which arrow to match with a neighboring tile can also be computed with mod 4 arithmetic.

Monday, June 20, 2016

Restoring deleted /etc from TimeMachine

Yesterday, I managed to empty the /etc directory on my macbook (don't ask how I did it. I was working on subsurface and had written a perl script to move system files around that had to be run with sudo. And I was still debugging...).

Anyway, once I realized what the problem was I did some googling but did not find the answer. So here, as a service to fellow humans googling for help is how to fix this.

The problem is that in /etc all kinds of system configuration files are stored and without it the system does not know anymore how to do a lot of things. For example it contains /etc/passwd which contains a list of all users, their home directories and similar things. Or /etc/shadow which contains (hashed) passwords or, and this was most relevant in my case, /etc/sudoers which contains a list of users who are allowed to run commands with sudo, i.e. execute commands with administrator privileges (in the GUI this shows as as a modal dialog asking you to type in your password to proceed).

In my case, all was gone. But, luckily enough, I had a time machine backup. So I could go 30 minutes back in time and restore the directory contents.

The problem was that after restoring it, it ended up as a symlink to /private/etc and user helling wasn't allowed to access its contents. And I could not sudo the access since the system could not determine I am allowed to sudo since it could not read /etc/sudoers.

I tried a couple of things including a reboot (as a last resort I figured I could always boot in target disk mode and somehow fix the directory) but it remained in /private/etc and I could not access it.

Finally I found the solution (so here it is): I could look at the folder in Finder (it had a red no entry sign on it meaning that I could not open it). But I could right click and select Information and there I could open the lock by tying in my password (no idea why that worked) and give myself read (and for that matter write) permissions and then everything was fine again.

Tuesday, May 24, 2016

Holographic operator ordering?

Believe it or not, at the end of this week I will speak at a workshop on algebraic and constructive quantum field theory. And (I don't know which of these two facts is more surprising) I will advocate holography.

More specifically, I will argue that it seems that holography can be a successful approach to formulate effective low energy theories (similar to other methods like perturbation theory of weakly coupled quasi particles or minimal models). And I will present this as a challenge to the community at the workshop to show that the correlators computed with holographic methods indeed encode a QFT (according to your favorite set of rules, e.g. Whiteman or Osterwalder-Schrader). My [kudos to an anonymous reader for pointing out a typo] guess would be that this has a non-zero chance of being a possible approach to the construction of (new) models in that sense or alternatively to show that the axioms are violated (which would be even more interesting for holography).

In any case, I am currently preparing my slides (I will not be able to post those as I have stolen far too many pictures from the interwebs including the holographic doctor from Star Trek Voyager) and came up with the following question:

In a QFT, the order of insertions in a correlator matters (unless we fix an ordering like time ordering). How is that represented on the bulk side?

Does anybody have any insight about this?

Thursday, April 21, 2016

The Quantum in Quantum Computing

I am sure, by now, all of you have seen Canada's prime minister  "explain" quantum computers at Perimeter. It's really great that politicians care about these things and he managed to say what is the standard explanation for the speed up of quantum computers compared to their classical cousins: It is because you can have superpositions of initial states and therefore "perform many operations in parallel".

Except of course, that this is bullshit. This is not the reason for the speed up, you can do the same with a classical computer, at least with a  probabilistic one: You can also as step one perform a random process (throw a coin, turn a Roulette wheel, whatever) to determine the initial state you start your computer with. Then looking at it from the outside, the state of the classical computer is mixed and the further time evolution also "does all the computations in parallel". That just follows from the formalism of (classical) statistical mechanics.

Of course, that does not help much since the outcome is likely also probabilistic. But it has the same parallelism. And as the state space of a qubit is all of a Bloch sphere, the state space of a classical bit (allowing mixed states) is also an interval allowing a continuum of intermediate states.

The difference between quantum and classical is elsewhere. And it has to do with non-commuting operators (as those are essential for quantum properties) and those allow for entanglement.

To be more specific, let us consider one of the most famous quantum algorithms, Grover's database lookup, There the problem (at least in its original form) is to figure out which of $N$ possible "boxes" contains the hidden coin. Classically, you cannot do better than opening one after the other (or possibly in a random pattern), which takes $O(N)$ steps (on average).

For the quantum version, you first have to say how to encode the problem. The lore is, that you start with an $N$-dimensional Hilbert space with a basis $|1\rangle\cdots|N\rangle$. The secret is that one of these basis vectors is picked. Let's call it $|\omega\rangle$ and it is given to you in terms of a projection operator $P=|\omega\rangle\langle\omega|$.

Furthermore, you have at your disposal a way to create the flat superposition $|s\rangle = \frac1{\sqrt N}\sum_{i=1}^N |i\rangle$ and a number operator $K$ that act like $K|k\rangle= k|k\rangle$, i.e. is diagonal in the above basis and is able to distinguish the basis elements in terms of its eigenvalues.

Then, what you are supposed to do is the following: You form two unitary operators $U_\omega = 1 - 2P$  (this multiplies $|\omega\rangle$ by -1 while being the identity on the orthogonal subspace, i.e. is a reflection on the plane orthogonal to $|\omega\rangle$) and $U_s = 2|s\rangle\langle s| - 1$ which reflects the vectors orthogonal to $|s\rangle$.

It is not hard to see that both $U_s$ and $U_\omega$ map the two dimensional place spanned by $|s\rangle$ and $|\omega\rangle$ into itself. They are both reflections and thus their product is a rotation by twice the angle between the two planes which is given in terms of the scalar product $\langle s|\omega\rangle =1/\sqrt{N}$ as $\phi =\sin^{-1}\langle s|\omega\rangle$.

But obviously, using a rotation by $\cos^{-1}\langle s|\omega\rangle$, one can rotate $|s\rangle$ onto $\omega$. So all we have to do is to apply the product $(U_sU\omega)^k$ where $k$ is the ratio between these two angles which is $O(\sqrt{N})$. (No need to worry that this is not an integer, the error is $O(1/N)$ and has no influence). Then you have turned your initial state $|s\rangle$ into $|omega\rangle$ and by measuring the observable $K$ above you know which box contained the coin.

Since this took only $O(\sqrt{N})$ steps this is a quadratic speed up compared to the classical case.

So how did we get this? As I said, it's not the superposition. Classically we could prepare the probabilistic state that opens each box with probability $1/N$. But we have to expect that we have to do that $O(N)$ times, so this is essential as fast as systematically opening one box after the other.

To have a better unified classical-quantum language, let us say that we have a state space spanned by $N$ pure states $1,\ldots,N$. What we can do in the quantum case is to turn an initial state which had probability $1/N$ to be in each of these pure states into one that is deterministically in the sought after state.

Classically, this is impossible since no time evolution can turn a mixed state into a pure state. One way to see this is that the entropy of the probabilistic state is $\log(N)$ while it is 0 for the sought after state. If you like classically, we only have the observables given by C*-algebra generated by $K$, i.e. we can only observe which box we are dealing with. Both $P$ and $U_\omega$ are also in this classical algebra (they are diagonal in the special basis) and the strict classical analogue would be that we are given a rank one projector in that algebra and we have to figure out which one.

But quantum mechanically, we have more, we also have $U_s$ which does not commute with $K$ and is thus not in the classical algebra. The trick really is that in this bigger quantum algebra generated by both $K$ and $U_s$, we can form a pure state that becomes the probabilistic state when restricted to the classical algebra. And as a pure state, we can come up with a time evolution that turns it into the pure state $|\omega\rangle$.

So, this is really where the non-commutativity and thus the quantumness comes in. And we shouldn't really expect Trudeau to be able to explain this in a two sentence statement.

PS: The actual speed up in the end comes of course from the fact that probabilities are amplitudes squared and the normalization in $|s\rangle$ is $1/\sqrt{N}$ which makes the angle to be rotated by proportional to $1/\sqrt{N}$.

One more resuscitation

This blog has been silent for almost two years for a number of reasons. First, I myself stopped reading blogs on a daily basis as in open Google Reader right after the arXiv an checking what's new. I had already stopped doing that due to time constraints before Reader was shut down by Google and I must say I don't miss anything. My focus shifted much more to Twitter and Facebook and from there, I am directed to the occasional blog post, but as I said, I don't check them systematically anymore. And I assume others do the same.

But from time to time I run into things that I would like to discuss on a blog. Where (as my old readers probably know) I am mainly interested in discussions. I don't write here to educate (others) but only myself. I write about something I found interesting and would like to have further input on.

Plus, this should be more permanent than a Facebook post (which is gone once scrolled out of the bottom of the screen) and more than the occasional 160 character remark on Twitter.

Assuming that others have adopted their reading habits in a similar way to the year 2016, I have set up If This Than That to announce new posts to FB and Twitter so others might have a chance to find them.

Friday, May 23, 2014

Conference Fees for Speakers

Listening to a podcast on open access I had an idea: Many conferences waive conference fees (which can be substantial) for invited speakers. But those are often enough the most senior people who would have the least difficulty in paying the fee from their budget or grant money. So wouldn't it be a good idea for conferences to offer to their invited speakers to instead waive the fee for a graduate student or junior post-doc of the speakers choice and make the speaker pay the fee from their grant (or reduce the fee by 50% for both)?

Discuss!

Wednesday, January 29, 2014

Questions to the inter webs: classical 't-Hooft-limit and path integral entanglement

Hey blog, long time no see!

I am coming back to you with a new format: Questions. Let me start with two questions I have been thinking about recently but that I don't know a good answer to.

't Hooft limit of classical field equations

The 't Hooft limit leads to important simplifications in perturbative QFT and is used for many discoveries around AdS/CFT, N=4 super YM, amplitudes etc etc. You can take it in its original form for SU(N) gauge theory where its inventor realized you can treat N as a parameter of the theory and when you do perturbation theory you can do so in terms of ribbon Feynman diagrams. Then a standard analysis in terms of Euler's polyhedron theorem (discrete version of the Gauss-Bonnet-theorem) shows that genus g diagrams come with a factor 1/N^g such that at leading order for large N only the planar diagrams survive.

The argument generalizes to all kinds of theories with matrix valued fields where the action can be written as a single trace. In a similar vain, it also has a version for non-commutative theories on the Moyal plane.

My question is now if there is a classical analogue of this simplification. Let's talk the classical equations of motion for SU(N) YM or any of the other theories, maybe something as simple as
d^2/dt^2 M = M^3 for NxN matrices M. Can we say anything about simplifications of taking the large N limit? Of course you can use tree level Feynman diagrams to solve those equations perturbatively (as for example I described here), but is there a non-perturbative version of "planar"?
Can I say anything about the structure of solutions to these equations that is approached for N->infinity?

Path Integral Entanglement

Entanglement is the distinguishing feature of quantum theory as compared to classical physics. It is closely tied to the non-comutativity of the observable algebra and is responsible for things like the violation of Bell's inequality.

On the other hand, we know that the path integral gives us an equivalent description of quantum physics, surprisingly in terms of configurations/paths of the classical variables (that we then have to take the weighted integral over) which are intrinsically commuting objects. 

Properties of non-commuting operators can appear in subtle ways, like the operator ordering ambiguity how to quantize the classical observable x^2p^2, should it be xp^2x or px^2p or for example (x^2p^2 + p^2x^2)/2? This is a true quantization ambiguity and the path integral has to know about it as well. It turns out, it does: When you show the equivalence of Schroedinger's equation and the path integral, you do that by considering infinitesimal paths and you have to evaluate potentials etc on some point of those paths to compute things like V(x) in the action. Turns out, the operator ambiguity is equivalent to choosing where to evaluate V(x), at the start of the path, the end, the middle or somewhere else.

So far so good. The question that I don't know the answer to is how the path integral encodes entanglement. For example can you discuss a version of Bell's inequality (or similar like GHZ) in the path integral language? Of course you would have to translate the spin operators to positions .