Meeting notes 11 09 27

Quantum retreat? Paul will send a doodle poll.

Second QIP poster deadline is Nov 1.

Save scirate?

Group meeting: Use a twitter account and/or this UNM code.

Aram: Went to Hannover and Dagstuhl. Also went to ORAQL meeting, where the goal is to estimate how much time a quantum computer will take to solve various computational problems. Eventually there will be code that evaluates a given architecture/algorithm/FTQC-strategy combination.

Tom: Writing up report related to k-extendable states. Next, analyzing the power method (an algorithm for estimating the top eigenvalue of a matrix).

Kamil: Tried to solve HSP. Coding for the Oracle Set Identification Problem. To make a random unitary, let G be a random complex Gaussian, and diagonalize $G=UDU^\dagger$, e.g. with a QR decomposition.

Rowan: Planted solution for Exact Cover, up to n around 45.

Isaac: Looking at sublinear-time algorithms to test expansion. But at what $\epsilon$? Goal is to analyze Quantum Monte Carlo (note: is a classical algorithm; name predates invention of quantum computers).

Paul: ORAQL, and working on weakening his 2-D quantum adder paper with Krysta.

Melanie: Working on simulating welded cone trees. Hitting time seems linear, up to tree size ~30.

Steve: Drove to Seattle. Math time! G is a finite non-cyclic abelian group (e.g. $\mathbb{Z}_2\times \mathbb{Z}_2$. n is a positive integer. $G^n := G \times G \times \cdots \times G$

Sample non-identity elements $x_1,\ldots,x_m$ at random from $G^n$. Let How quickly does the cardinality of $\bigcup_{i=1}^m \langle x_i \rangle$ grow? And in particular, how large does m have to be before we are likely to cover all of $G^n$.

David: Looking at factoring in $Z[e^{2 pi i /n}]$; these are cyclotomic integers, and as an extension, have degree phi(n). $\prod_{1 \leq j \leq n - 1, gcd(j, n) = 1} (x-e^{2\pi ij/n})$ is called the nth cyclotomic polynomial, and has integer coefficients.

For factoring, would like the field norm to be a Euclidean norm, which is mostly not the case. There are 30 values of n for which the cyclotomic integers are a Euclidean domain (using ad hoc arguments), and so at most 30 in which factoring works well.

Uselessness: does it depend on the distribution over oracles, beyond their support?