Difference between revisions of "Meeting notes 11 05 12"
(created page) |
|||
| Line 1: | Line 1: | ||
| − | Aram | + | ;Aram |
| − | + | Consider a real-valued function on the boolean hypercube: | |
| − | <math>f:Z_2^n \rightarrow | + | <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. | ||
Latest revision as of 18:57, 12 May 2011
- 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.
