Background

The story

So I was reading this lecture note about secretary problems, and I was trying to prove Theorem 24.3 myself. I also obtained an sum representing the probability which is different from the one in the lecture note. However I had some difficulty proving that the two sums are equilvalent (if not given this problem). After a day of suffering, using the summation by parts technique, I found that the sum was in fact a high-order sum of the harmonic series, and that this sum has a pretty simple representation.

Introduction

Let's start with the SAT problem: suppose we are given a boolean SAT formula with \(n\) variables and \(poly(n)\) clauses, and we want to know whether there exists a satisfiying assignment. This problem is known to be NP-complete, thus is generally believed to be hard to solve on a classical computer. The exponential time hypothesis states that satisfiability of SAT cannot be solved in \(2^{o(n)}\) time. However, with Grover's algorithm on a quantum computer, one can determine the existence of satisfying assignment, or even find one, within time \(O\left(2^{\frac n2}\right)\)! In fact, for any search problem with \(N\) candidates and \(M\) solutions, Grover's algorithm can find one solution with \(O\left(\sqrt{\frac NM}\right)\) operations, while a classical algorithm usually takes \(O(\frac NM)\) operations.

Recall the definition of algebraic numbers: \(x\) is an algebraic number iff it is a root of some non-zero polynomial with rational coefficients.

Definition of Algebraic Numbers

Let \(x\in\mathbb C\) be a complex number. We call it an algebraic number iff \(\exists n>0\), \(\exists a_0,\cdots,a_n\in\mathbb Q, a_n\ne0\), s.t. \(\sum_{i=0}^na_nx^n=0\).

Algebraic number is algebraically closed

The algebraic numbers have an intriguing property: it is algebraically closed. That is, the sum, difference, product and quotient of two algebraic numbers is again algebraic. Moreover, the roots of a non-zero polynomial whose coefficients are algebraic numbers is again algebraic.

The idea of the proof is from ¹, page 429-431.

Definition

Spectral Expander

Let \(G\) be an \(n\)-vertex \(d\)-regular undirected graph. Let \(A\) be its random walk matrix, i.e. \(a_{i,j}=\frac 1d |E(i,j)|\). One can see that the largest eigenvalue of \(A\) is \(1\). We define \(\lambda(G)\) as the second-largest eigenvalue of \(H\). If \(\lambda(G)\le\lambda\) for some \(\lambda<1\), then we say \(G\) is an \((n,d,\lambda)\)-spectral-expander.

Edge Expander

Let \(G=(V,E)\) be an \(n\)-vertex \(d\)-regular undirected graph. We call it an \((n,d,\rho)\)-edge-expander iff \[ \forall S\subset V, |S|\le\frac n2\implies E(S,\bar S)\ge\rho d|S| \]

Edge Expansion Implies Spectral Expansion

In fact, we can show that the two expanders are somewhat "equivalent", i.e. spectral expansion implies edge expansion and vice versa. Here we focus on the hard direction: edge expansion implies spectral expansion.

Theorem

An \((n,d,\rho)\)-edge-expander is an \((n,d,1-\frac{\rho^2}2)\)-spectral-expander.

h1 Heading 8-)

h2 Heading

h3 Heading

h4 Heading

h5 Heading

h6 Heading