Puzzles: Languages and locks

I recently heard a fun puzzle. Puzzle: How many languages are needed so that we can have that for any two people in a group of 70 each one knows a language that the other does not.






Solution: Basically we need to assign to each person a unique subset of languages. If there are K languages number of such such subsets will be maximum if each person knows K/2 languages. So, we will need the number of languages K to be such that

\[ \left( \begin{matrix} K\\K/2  \end{matrix} \right) \ge 70 \]

Another, variant of this puzzle is regarding bank locks. Puzzle: Suppose, you have \(n\) people working at a bank and you want that at least \(m\) should be present to be able to open a lock. How many locks do you need, and how many keys are needed for each lock.




Solution: For each subset of \(m-1\) people there should be a lock that they cannot open so  we need

\[ \left( \begin{matrix} n\\m-1  \end{matrix} \right) \]

locks. Also, for any lock we cannot find m people that together cannot open it. So each lock should have \(n-(m-1)\) keys.

Trace and transpose trick: Computing derivatives

I am not sure why but none of the college courses on linear algebra or calculus ever introduced me to working with derivatives of functions of matrices and vectors. This comes up on a daily basis in optimization and is a lot cleaner than dealing with summations. Here is a trick that comes in very handy when taking derivatives of a functions that maps vectors or matrices to scalars. Basically, one can replace a scalar results of matrix vector products by its transpose and in some cases by their trace (and then use the cyclic property of  trace to rewrite expressions) in which the desired terms appear at the end and are correctly transposed.

Simplest case: Linear function takes a vector to a scalar.
\[f : \mathbb{R}^n \rightarrow \mathbb{R}\]
\[ \mathrm{d} \left(c^Tx \right) = c^T \mathrm{d}x\]

Next level: Function takes a vector to a scalar using a quadratic form. We will use the transpose trick here:
\[f : \mathbb{R}^n \rightarrow \mathbb{R}\]
\[ \mathrm{d} \left(x^TAx \right) = (\mathrm{d}x)^TAx + x^TA(\mathrm{d}x) \]

The first term on the RHS is a scalar so we can take its transpose and get

\[ \mathrm{d} \left(x^TAx \right) = x^TA^T(\mathrm{d}x) + x^TA(\mathrm{d}x)  = (x^TA^T + x^TA) \mathrm{d}x\]

Next level: Function takes a matrix to a scalar. We will use the trace trick here: 

\[f : \mathbb{R}^{nxn} \rightarrow \mathbb{R}\]
\[ \mathrm{d} \left(a^TXb \right) = a^T (\mathrm{d}X)b \]
Now since the RHS is a scalar we can think of it as a trace and rotate the terms to get:
\[ \mathrm{d} \left(a^TXb \right) = \mathrm{Tr}(ba^T \mathrm{d}X) \].
Now, we will use the symbol (:) that rewrites the matrix as a concatenation of its vectors and rewrite the above as:
\[ \mathrm{d} \left(a^TXb \right) = (ab^T): (\mathrm{d}X): \].
Giving us \( \frac{\mathrm{d} \left(a^TXb \right)}{\mathrm{d}X} = ab^T \).

Lets use this machinery to attempt something more complicated and find \( \frac{\mathrm{d}(a^TX^TCXb)}{\mathrm{d}X} \)

\[ \mathrm{d} (a^TX^TCXb)  = a^T(\mathrm{d}X^T)CXb + a^TX^TC(\mathrm{d}X)b \]

\[ = b^TX^TC^T(dX)a + a^TX^TC(dX)b \]

\[ = \mathrm{Tr}( b^TX^TC^T(\mathrm{d}X)a + a^TX^TC(\mathrm{d}X)b ) \]

\[ = \mathrm{Tr}( ab^TX^TC^T(\mathrm{d}X) + ba^TX^TC(\mathrm{d}X)) \]

\[ = (CXba^T+C^TXab^T): (\mathrm{d}X): \]

\[ \Rightarrow \mathrm{d}(a^TX^TCXb)/\mathrm{d}X = (CXba^T+C^TXab^T) \]

Bell states to test nature's inherent uncertainity

This post is to succinctly describe the key ideas that are presented by Prof. Vazirani in his QMQC course on EdX (I saw this when it was originally offered on coursera) related to Bell's idea to show that quantum randomness is (or is not) inherent in nature.

So, as usual, we have two players Alice and Bob who can initially agree on a strategy and are then separated by a huge distance over which we will assume that they cannot communicate. Now, the game is that both Alice and Bob receive a binary input and produce a binary input. They win when they generate different inputs only when both their inputs are 1, otherwise they should produce the same output. Classically, we can see that the best that Alice and Bob can do is win with a probability of 0.75.

However, if they can share an entangled Bell state then they can achieve a better probability of success. An entangled state of two particles is one which cannot be expressed as a product of the states of the two particles. So, as an example,

\[ \lvert \Psi \rangle = \frac{1}{\sqrt{2}} \left(   \lvert 00 \rangle +  \lvert 11 \rangle \right) \]

is an entangled state. It is instructive to see that this state cannot be written as a tensor product of the individual states of the two particles. Now, the next fun thing to note is that the representation of this state when written in any other orthonormal basis \(u, u^{\perp} \) does not change (again, expand out the tensor products to see this). So, our state above can be expressed as


\[ \lvert \Psi \rangle = \frac{1}{\sqrt{2}} \left(   \lvert uu \rangle +  \lvert u^{\perp}u^{\perp} \rangle \right) \]

Now, let Alice and Bob share the entangled state with one particle each before separation and are then taken to two corners of the universe. They can choose their basis (x for Alice and y for Bob) as shown in the figure below and announce their result depending on whether they see the particle oriented along their basis vector or orthogonal to it. In, all cases except when \(x=y=1\) their basis vectors are oriented at an angle of \( \frac{\pi}{8} \), and only when \(x=y=1\) there basis vectors are orientated at an angle of \( \frac{3\pi}{8} \). In both cases the probability of winning is \( \cos^2\frac{\pi}{8} \approx 0.85 \), much better than can be obtained classically.

A nice article discussing the questions still surrounding the experimental results with Bell's states appeared here recently.