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}, d o t s, a_{n}$ [/tex] of residues mod [tex] $p$ [/tex] and suppose [tex] $n > l o g_{2} p$ [/tex], find two distinct subsets [tex] $S_{1}, S_{2} s u b s e t 1, 2, d o t s, n$ [/tex] so that [tex] $p r o d_{i i n S_{1}} a_{i} = p r o d_{i i n S_{2}} a_{j} r m m o d 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} $[/ t e x] i s [t e x]$ 2^n $[/ t e x] (b e c a u s e e a c h e l e m e n t e i t h e r i s o r i s n o t i n t h e s u b s e t, a n d “ i s ” a n d “ i s n o t ” i s b i n a r y, a n d s o w e h a v e a b i n a r y s t r i n g o f l e n g t h [t e x]$ n $[/ t e x] .) B u t [t e x] 2^{n} > p [/ t e x], s o w e a r e p u t t i n g m o r e o b j e c t s i n t o o u r “ h o l e s ” w h i c h r u n f r o m [t e x]$ 0 $[/ t e x] t o [t e x]$ 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 i n {m a t h b b Z}_{p}$ [/tex] find the smallest [tex] $s$ [/tex] such that [tex] $a^{s} = b r m m o d 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}, d o t s, a_{n}} (b_{1}, d o t s, b_{n}) = a_{1}^{b_{1}} a_{2}^{b_{2}} d o t s a_{n}^{b_{n}}$ [/tex], where [tex] $b_{i} i n {m a t h b b Z}_{2} [/ t e x] . T h e n a r e s u l t b y S c o t t A a r o n s o n s a y s t h a t u s i n g a q u a n t u m a l g o r i t h m r e q u i r e s [t e x]$ Omega((2^n)^{1/5}) $[/ t e x] q u e r i e s o f t h i s f u n c t i o n (l a t e r i m p r o v e d t o [t e x]$ Omega((2^n)^{1/3}) $[/ t e x] b y Y a o y u n S h i) t o s o l v e t h i s p r o b l e m . S o t h i s n a i v e a p p r o a c h t o a t t a c k i n g p r o b l e m s i n P P P f a i l s . A n i n t e r e s t i n g o p e n q u e s t i o n r e m a i n s, h o w e v e r, w h e t h e r t h e r e i s a m o r e s o p h i s t i c a t e d a p p r o a c h t o e f f i c i e n t l y s o l v i n g p r o b l e m s i n P P P u s i n g a q u a n t u m c o m p u t e r . I n t e r e s t i n g l y, t h e p r o b l e m S c o t t a n d Y a o y u n w o r k o n i s a l s o r e l a v e n t t o a p h y s i c i s t i n t h e l a b . T h e p r o b l e m t h e y c o n s i d e r i s c a l l e d t h e c o l l i s i o n p r o b l e m . S u p p o s e y o u h a v e a f u n c t i o n [t e x]$ f $[/ t e x] f r o m [t e x]$ {mathbb Z}_N $[/ t e x] t o [t e x]$ {mathbb Z}_N $[/ t e x] w h i c h i s p r o m i s e d t o b e e i t h e r 1 - t o - 1 o r 2 - t o - 1 a n d t h e p r o b l e m i s t o d i s t i n g u i s h b e t w e e n t h e s e t w o c a s e s . S c o t t a n d Y a o y u n^{'} s r e s u l t s a y s t h a t i f y o u d o t h i s y o u n e e d t o q u e r y t h i s f u n c t i o n [t e x]$ Omega((2^n)^{1/3}) $[/ t e x] t i m e s (a n d, i t t u r n s o u t t h a t t h e r e i s a q u a n t u m a l g o r i t h m w h i c h u s e s t h i s n u m b e r o f q u e r i e s) t o d i s t i n g u i s h b e t w e e n t h e s e t w o c a s e s . N o w h o w d o e s t h i s h a v e r e l e v a n c e t o a p h y s i c i s t ? S u p p o s e w e f o l l o w t h e s t a n d a r d q u e r y m e t h o d a n d q u e r y t h e f u n c t i o n t o p r o d u c e t h e s t a t e [t e x]$ N^{-1/2} sum_{x in {mathbb Z}_N} |x>|f(x)> $[/ t e x] . D i s c a r d i n g t h e s e c o n d r e g i s t e r p r o d u c e s a m i x e d s t a t e o f r a n k [t e x]$ N $[/ t e x] i f [t e x]$ f $[/ t e x] i s 1 - t o - 1 b u t o f r a n k [t e x]$ N/2 $[/ t e x] i f [t e x]$ f $[/ t e x] i s 2 - t o - 1. T h e e n t r o p y o f t h e s e s t a t e s i s t h u s e i t h e r [t e x]$ log_2 N $[/ t e x] o r [t e x]$ log_2 N-1 $[/ t e x] r e s p e c t i v a l l y . N o w s u p p o s e y o u a r e a p h y s i c i s t i n t h e l a b a n d y o u w a n t t o m e a s u r e t h e e n t r o p y o f a q u a n t u m s t a t e w h i c h y o u c a n p r e p a r e m u l t i p l e c o p i e s o f . Y o u m i g h t b e i n t e r e s t e d i n h o w m a n y c o p i e s y o u w i l l n e e d t o m e a s u r e t h i s e n t r o p y . S c o t t a n d Y a o y u n^{'} s r e s u l t t h e n i m p l y t h a t y o u w i l l n e e d t o p e r f o r m a n u m b e r o f e x p e r i m e n t s w h i c h i s a t l e a s t [t e x]$ Omega(d^{1/3}) $[/ t e x] s u c h e x p e r i m e n t s t o m e a s u r e t h e e n t r o p y, w h e r e [t e x]$ 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.

10 Replies to “Pigeons, Discrete Log, and Entropy”

aram harrow says:

May 31, 2005 at 2:43 pm

where did you come up with that problem? is it related to your recent HSP paper?
it seems like you would want to choose b_i from {-1, 0, 1} rather than from {0,1}. other than this wrinkle, it seems vaguely like simon’s algorithm.

Dave Bacon says:

May 31, 2005 at 2:50 pm

Which problem, the PPP problem? I took the example from Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. “The relative complexity of NP search problems.” Journal of Computer and System Sciences, 57:3-19, 1998.
What do you mean I want b_i to be from {-1,0,1}? In the above problem f will not be 2-to-1 on all inputs, but I think the Aaronson, Shi bound still applies.

Suz says:

May 31, 2005 at 4:34 pm

I don’t even know what that big symbol(capital pi?) represents. Is there an equation to relate how many years since graduating from Caltech with the knowledge you retain? (I guess other variables are your field of study, what you did afterward, etc.)
In any case, thanks for making me feel stupid, Baco.

Jeff Hodges says:

May 31, 2005 at 11:41 pm

Looks like its back to the biologists’ being the mad scientists of popular culture again. Physicists have had 50 years of nuclear technology to be smacked around with. Personally, I like going to parties, telling people I want to get my Ph.D. in physics and getting “That’s..uh.. cool. *blank stare*” instead of “Bomb builder! *throws drink in face*”.
Welcome to the terrordome, I guess.

Dave Bacon says:

May 31, 2005 at 5:01 pm

Capital pi represent product, like capital sigma represents sum.
You can always retaluate by writing a post on your blog about biology and then I will sit there like a slack jawed yokol (like Cletus, that is).

Suz says:

May 31, 2005 at 6:14 pm

Whenever I write about biology, my friends just get grossed out or make comparisons between my mouse-killing to that of genocidal maniacs.

aram says:

June 1, 2005 at 1:12 pm

yeah, i meant the first problem you wrote, from the paper you cited.
i want b_i in {-1,0,1} so that i can set b_i = -1 if i\in S_1, b_i = 1 if i\in S_2 and b_i=0 otherwise.
that way, you’re searching for a nonzero string b s.t.
prod_i a_i^{b_i} = 1 (mod p).
but it’s not like i can do anything useful with this formulation – it just seems more natural to me.
also, why do you say the Aaronson/Shi bound applies? do you mean it applies if you ignore the structure of this problem and just look at it as a blackbox on b?

Dave Bacon says:

June 1, 2005 at 2:24 pm

The Aaronson/Shi bound applies because one cannot gain distinguishability by making the 2-to-1 function 1-to-1 on some domain of the function.

Suz says:

June 1, 2005 at 3:00 pm

I can’t believe it took me this long to notice:
“so we are putting more objects into our â€œholesâ€”
you pervert.

divya says:

October 19, 2008 at 9:24 pm

hai every1,i m dng a project on the topic pigeonhole principle…i need the complete algorith/proof of this principle in a clear manner…..sme1 plz help me…

10 Replies to “Pigeons, Discrete Log, and Entropy”

Leave a Reply to divya Cancel reply