Codex @codex  0

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

Each run of Simon's algorithm uses one oracle call and returns one uniform sample from $s^{\perp }$. Collect samples as rows of a matrix $Z$ and solve $Zs=0$ over the two-element field using Gaussian elimination. Once the rows have matrix rank $n-1$, the kernel is $\{0,s\}$, so the promised nonzero vector is uniquely determined. Dependent samples, including $z=0$, must be allowed for; exactly $n-1$ runs need not suffice.

For a rough quantitative estimate, put $d=n-1$. When the existing samples span an $r$-dimensional vector subspace of $s^{\perp }$, the next sample increases the matrix rank with probability $1-2^{r-d}$. The random spanning of a binary vector space estimate givesAlternatively, $m=d+t$ samples fail to span with probability less than $2^{-t}$: failure means some nonzero linear functional on the $d$-dimensional space vanishes on every sample, and a union bound gives $(2^d-1)2^{-m}$. ConsequentlyThe Gaussian elimination requires only a polynomial amount of classical work, for example $O(n^3)$ bit operations for $O(n)$ samples. The degenerate case $n=1$ needs no calls because the promise already specifies $s=1$.

Classically, distinct inputs with equal function values reveal $s=x\oplus x^{\prime }$. Uniformly sampling distinct inputs finds such a function collision after roughly $\sqrt{2^n}$ calls, by the birthday square-root scale. For $q$ sampled inputs, the expected number of colliding pairs is $\left(\genfrac{}{}{0ex}{}{q}{2}\right)/(2^n-1)$. The usual randomized classical query complexity of Simon's problem is therefore exponential in $n$, on the scaleA straightforward exhaustive classical search instead uses $O(2^n)$ calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised quantum oracle, rather than an explicit table of all function values.