Pigeons, Discrete Log, and Entropy

The pigeon hole principle states that if you put m pigeons into n<m holes, then there are at least two pigeons in one hole. Consider, for example, the following problem
Given a list [tex]$a_1,dots,a_n$[/tex] of residues mod [tex]$p$[/tex] and suppose [tex]$n>log_2 p$[/tex], find two distinct subsets [tex]$S_1,S_2 subset {1,2,dots,n}$[/tex] so that [tex]$prod_{i in S_1} a_i =prod_{i in S_2}a_j~{rm mod}~p$[/tex].
Here we have said “find”, but how do we even know that two subsets which solve this problem exist? The pigeon hole principle! The number of possible subsets of [tex] {1,2,dots,n}$[/tex] is [tex]$2^n$[/tex] (because each element either is or is not in the subset, and “is” and “is not” is binary, and so we have a binary string of length [tex]$n$[/tex].) But [tex]2^n>p[/tex], so we are putting more objects into our “holes” which run from [tex]$0$[/tex] to [tex]$p-1$[/tex]. Thus by the pigeon hole principle there must be two distinct subsets (two pigeons) whose product is the same.
In computational complexity the above problem belongs to a class of search problems called PPP, which, according to the complexity zoo, stands for “Polynomial Pigeonhole Principle.” These are problems where we are searching for a solution to an instance of a problem, this solution can be verified to be a solution in polynomial time, and the existence of a solution is guaranteed by a pigeon hole argument. The second of these should be familiar from the class NP, and the first of these is what you’re doing when you go beyond decision problems and actually want to find a solution.
PPP is interesting for various reasons, but one of the reasons I know of it is because it is at least as hard as the discrete log problem. In the discrete log problem is given two elements [tex]$a,b in {mathbb Z}_p$[/tex] find the smallest [tex]$s$[/tex] such that [tex]$a^s=b~{rm mod}~p$[/tex]. One of the neat things about a quantum computer is that it can efficiently solve the discrete log problem, whereas there is no known efficient classical algorithm.
So what do we know about the power of quantum computers to solve problems in PPP? Well we know a little. We know that a naive approach to solving these problems will fail. Suppose that we try to solve the above PPP problem by querying the function [tex]$f_{a_1,dots,a_n}(b_1,dots,b_n)=a_1^{b_1} a_2^{b_2} dots a_n^{b_n}$[/tex], where [tex]$b_i in {mathbb Z}_2[/tex]. Then a result by Scott Aaronson says that using a quantum algorithm requires [tex]$Omega((2^n)^{1/5})$[/tex] queries of this function (later improved to [tex]$Omega((2^n)^{1/3})$[/tex] by Yaoyun Shi) to solve this problem. So this naive approach to attacking problems in PPP fails. An interesting open question remains, however, whether there is a more sophisticated approach to efficiently solving problems in PPP using a quantum computer.
Interestingly, the problem Scott and Yaoyun work on is also relavent to a physicist in the lab. The problem they consider is called the collision problem. Suppose you have a function [tex]$f$[/tex] from [tex]${mathbb Z}_N$[/tex] to [tex]${mathbb Z}_N$[/tex] which is promised to be either 1-to-1 or 2-to-1 and the problem is to distinguish between these two cases. Scott and Yaoyun’s result says that if you do this you need to query this function [tex]$Omega((2^n)^{1/3})$[/tex] times (and, it turns out that there is a quantum algorithm which uses this number of queries) to distinguish between these two cases. Now how does this have relevance to a physicist? Suppose we follow the standard query method and query the function to produce the state [tex]$N^{-1/2} sum_{x in {mathbb Z}_N} |x>|f(x)>$[/tex]. Discarding the second register produces a mixed state of rank [tex]$N$[/tex] if [tex]$f$[/tex] is 1-to-1 but of rank [tex]$N/2$[/tex] if [tex]$f$[/tex] is 2-to-1. The entropy of these states is thus either [tex]$log_2 N$[/tex] or [tex]$log_2 N-1$[/tex] respectivally. Now suppose you are a physicist in the lab and you want to measure the entropy of a quantum state which you can prepare multiple copies of. You might be interested in how many copies you will need to measure this entropy. Scott and Yaoyun’s result then imply that you will need to perform a number of experiments which is at least [tex]$Omega(d^{1/3})$[/tex] such experiments to measure the entropy, where [tex]$d$[/tex] is the dimension of your quantum states. This is bad news if you really want to measure the entropy of a many-qubit system! In a related manner one can think of the period finding function of Shor’s algorithm as a method for determining the entropy for special class of states which have a particular promise (that they are periodic).
Discrete log is a pigeon problem, naive quantum algorithms for pigeon problems fail, and pigeon problems put limits on how efficiently we can measure the entropy of a system. It’s topics like these, which spread from computer science all the way to relevance for a experimental physics, which make me happy to be working in quantum information science.