Tangram puzzles and the cost of calculating entanglement

I haven’t got many memories of my time as a kid. They mostly survive through exhilarating accounts narrated by my parents to other relatives and friends over and over again… but I do not remember living most of them (not sure why). Yet one of the distinctive memories I have is that of me sitting in the one and only barber shop in my home village, sometime during my primary school years, and discovering a great way of killing time during the long waits: Tangram. Yes, Tangram, the traditional dissection puzzle invented ages ago in China and imported in the western world during the 19th century, a sample of which eventually ended up in that barber shop.

Tangram set (source: Wikipedia)

I clearly remember myself playing with the seven wooden pieces, and the cheer of satisfaction when I finally figured out a way to reassemble them into the designed large square. More recently, with the advent of smartphones, plenty of Tangram puzzle apps became available for download, all based on the same principle: reassembling a number of small polygonal pieces in a puzzle, to reconstruct a target, more complex shape. Sometimes, there is only one way to achieve the goal, given the set pieces; some other times, there are multiple solutions to a puzzle.

Today I am going to discuss a variation of the Tangram puzzles, with an important twist: price. Imagine that each of the set pieces, to be used for assembling the final target shape, comes at a cost (that we will indicate with the currency symbol ¥). For any given target shape, the goal of the game is then to find the solution which minimizes the overall cost. This may not be necessarily the one with the least amount of used pieces, but must be the solution (or solutions) involving the overall cheapest possible combination of the pieces, in order to reconstruct the target.

For example, imagine we are allowed the following set with associated prices: squares with side lengths of 1 unit (available for free, 0¥), right-angled triangles with two side lengths of 1 unit (priced at 1¥), and right-angled triangles with two side lengths of 2 units (priced at 2¥). See below, a picture is worth a million words.

Notice that, counterintuitively, one may combine two small triangles (totalling 2¥) to form a unit square (which by itself costs 0¥): this is a bit like mixing two contrasting flavours which eventually annihilate each other. For the goals of the game, this simple observation implies that putting two triangles in place of a whole unit square (whenever the latter is available) generally leads to overpriced strategies, hence to non-optimal solutions.

Then, let’s try to analyze different solutions for the following target shape: a trapezium. We depict the target and a few solutions below, together with their price. One can easily convince oneself that, given an unlimited number of set pieces as in the collection above, the best possible combinations to achieve the target require a total spend of  2¥. Other solutions, even with less pieces, are more expensive.

Consider now the situation in which one restricts the available set pieces. Say we are only allowed to use at most one 0¥ unit square, two 1¥ smaller triangles, and three 2¥ bigger triangles. It is a nice exercise for the reader to figure out all the possible solutions in this case (some are shown below). Interestingly, it turns out all of them carry the same total price (6¥) in this case, whatever the arrangement. They are all equivalently optimal.

One may wonder whether this is a coincidence, or a more general consequence of the fact that, in particular, we limited our set to only one free piece. One may then go and investigate more complex shapes, and the answer to the latter question is probably not so important for the art of Tangram puzzles per se. However, the answer to a closely related question turns out to be crucial for the quantification of entanglement in multipartite quantum systems.

We have talked about entanglement in previous posts, and we will likely talk about it again. It is one of the most puzzling yet fundamental characteristics of quantum mechanics, which enables the implementation of disruptive technologies, and manifests as a strong form of correlations among different parts of a composite quantum system. Determining precisely how strong is a very difficult problem in general. We have to adopt a measure to gauge the extent to which a group of many quantum particles are entangled. This is akin to the currency we adopted to gauge the value of Tangram shapes, only that the entanglement currency is usually expressed in ebits rather than ¥.  In general, a system of many quantum particles can be prepared in infinitely many different states: a state is a collection of information about the system, which allows to predict with what probabilities we can obtain an outcome rather than another when measuring properties of the system with an apparatus. If this information is complete, we say the system is in a pure state. If instead the information is incomplete (i.e., we have some ignorance about possible measurement results, due to the effect of noise or due to a lack of control over the system itself), then we say that the system is in a mixed state.

Pure states are akin to our Tangram set pieces, while a mixed state is like our Tangram target shape. Some pure states come at no cost, meaning that they have no entanglement (they are called separable states, as the properties of the various subsystems are independent from each other), much like the little red squares in our Tangram set. A mixed state can be prepared by combining various pure states, and there are many different (infinitely many!) combinations of pure states which allow us to construct a given mixed state. It can happen that mixing two or more pure entangled states one obtains overall a separable mixed state (analogously to the case of combining two 1¥ triangles to obtain the 0¥ square): in this case, such a preparation is certainly not the most efficient, as one could have obtained the same result by using only pure separable states, without the use of any entanglement whatsoever, that is, without paying any price.

Like in our variation of the Tangram game, we can in fact assign an overall cost to each different preparation of a target mixed state from ensembles of pure states. The costs are now measured in ebits. Given an entanglement measure (in particular, technically speaking, some polynomial function of the state elements), it is relatively easy to evaluate it for pure states, so that we can assign prices to all the pure states in our quantum Tangram set a priori. The hard question now becomes the following: given a target mixed state, what is the preparation using pure states which carries the minimum overall cost in ebits? Such a minimum cost will be assigned as the entanglement value of the target mixed state. As you can see, the question is exactly like the one we asked in the Tangram puzzle game. In quantum mechanics and convex analysis, this is known as the convex roof problem. Such a problem can be solved exactly in few cases where the target mixed state has some particular symmetries, or has a small dimension, but it is a nightmare to deal with it in general.

In a recent article, my student Bartosz and I found a particularly interesting way to solve the convex roof problem for the quantification of entanglement in systems of many quantum particles, under two specific conditions: 1) we specialized to mixed states which have rank equal to 2 (stretching our analogy, we could say target Tangram shapes which are two-dimensional polygons, rather than more complicated three-dimensional figures); 2) we focused on the case where, among all possible pure states in our available set, there is only one which is separable (i.e. with 0 ebits, like the restriction to only one free square in the second Tangram example above). We call this second crucial condition one root, which is a shorthand for “one root to rule them all” (we even write this in the actual paper! Yes, we are such nerds). Then, some cool things happen. First of all, we can represent our set of states on a sphere.

On this sphere, pure states (our set pieces) span the surface, while mixed states are in the interior. For instance, the point indicated by ρ is a particular mixed state, like the trapezium target shape in our earlier examples. In this depiction of our quantum Tangram version of the convex roof problem, finding a preparation for the mixed state ρ amounts to finding a set of points on the surface (pure states), such that their barycenter (aka their weighted average) coincides with the point ρ. For instance, the target state ρ can be prepared by mixing the pure states Φ₀ and Φ₁ with suitable weights, or alternatively the pure states ψ₀ and ψ₁ with other suitable weights. But the crux of the problem remains: which ones of all these possible preparations of the mixed state ρ are the cheapest in units of entanglement? You will have noticed that the sphere is coloured: the colours actually reflect the entanglement value of all the pure states on the surface, ranging from 0 (red) to some maximal value (blue). As per the one root requirement, there is only one pure state with exactly zero entanglement, and is denoted by a z. The state diametrically opposite to it on the sphere, labelled z’, is in turn the most entangled one.

Well, we are now ready to give the solution to the main problem: under the conditions stated above, the convex roof problem becomes completely trivial! More precisely, any possible preparation of ρ carries the same overall entanglement value, even if the individual pure states involved in each preparation may have varying levels of entanglement. This is a bit like the second example with the trapezium in our Tangram analogy, with the important difference that in the present case we have a theorem proving that all solutions are equivalent when the one root condition is in force. The theorem follows from nothing more than elementary Euclidean geometry, and builds on a classical result due to Apollonius of Perga (circa 200 BC). Such a finding implies that entanglement can be quantified easily in mixed states of many particles compliant with the one root constraint, and is exactly specified in geometric terms by the distance between the plane containing the given mixed state ρ and the separable state z embodying the one root (i.e., in the picture, the length of the segment connecting z to the centre ρ_c of the shaded plane containing ρ). This is particularly remarkable and leads to novel formulas for various classes of states whose entanglement determination had remained unsolved so far, yet what we are mostly pleased about is the fact that our study unveils a new link between classical geometry and quantum information theory, leading to mathematically elegant and physically insightful results.

More details are available in the (pretty technical) research paper (free preprint available here), and in a more accessible coverage of our result which appeared in the Phys.Org website.

Finally, I am personally quite excited to realize that, somehow unconsciously, my longstanding passion for Tangram has finally proven useful to illustrate some of the complicate problems that I like to face at work nowadays. Coming to think about it, it would not be a bad idea at all to implement a suitable variant of Tangram, which might provide new solutions for the convex roof entanglement problem in more general cases, where even a brute-force computer optimization becomes unfeasible. There is a bunch of interesting activities coming from various groups and aimed at coding “games for quantum research”, i.e. exploiting the human abilities in devising solutions to complex optimization problems of current relevance, under the masquerade of playing simple and addictive games. Foldit was a breakthrough in this respect in the field of biochemistry. For recent worthy developments in quantum theory through games, keep an eye on ScienceAtHome and the QuantumGameJam.

But this can perhaps be the subject of another post. For now, let me be excused, as I have a particularly challenging non-quantum Tangram to solve on my phone!  🙂

 

Advertisement