Meeting notes 11 05 12

Aram

Consider a real-valued function on the boolean hypercube: <math>f:Z_2^n \rightarrow \mathbb{R}</math>.

This has the Fourier transform: <math>\hat{f}(s) = {1 \over 2^n} \sum_{x \in Z_2^n} (-1)^{x \cdot s} f(x)</math>

Consider two types of noise

• Flip each bit with probability p. Define g(x) to be the average of f(y) where y is chosen by flipping each bit of x with i.i.d. probability p.
• Flip a subset of k random bits. Define h(x) to be the average of f(y) where y is chosen by flipping a random subset of k bits in x.

The first type of noise affects the Fourier basis by <math>\hat g(s) = (1-2p)^{|s|} \hat f(s)</math>.

The second type of noise affects the Fourier basis by <math>\hat h(s) = K_k^n(|s|) \hat f(s)</math>, where <math>K_k^n</math> is a Krawtchouk polynomial, described in more detail at http://mathworld.wolfram.com/KrawtchoukPolynomial.html .

Dave

Describing Scott's latest quantum money proposal.

Fix a subspace <math>S\subset \mathbb{Z}^n_2</math>.

Choose two polynomials of degree <math>\geq 3</math>, f and g such that f(x)=0 if <math>x\in S</math>, and <math>g(x)=0</math> if <math>x\in S^\perp</math>.

The money state is <math>\frac{1}{\sqrt{|S|}} \sum_{x\in S}|x\rangle</math>. This has the property that Hadamarding will give an identical state with S replaced by <math>S^\perp</math>.

S is kept secret, while f and g are included with the banknote, along with their digital signatures.

To break, it suffices to find two distinct nonzero strings y,z in S.

Greg

had some awesome pictures of tensors. See https://github.com/gcross/Nutcracker for details.