Meeting notes 11 09 27

From Quantum Computing Theory Group
Jump to: navigation, search

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 <math>G=UDU^\dagger</math>, 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 <math>\epsilon</math>? 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. <math>\mathbb{Z}_2\times \mathbb{Z}_2</math>. n is a positive integer. <math>G^n := G \times G \times \cdots \times G</math>

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

David: Looking at factoring in <math>Z[e^{2 pi i /n}]</math>; these are cyclotomic integers, and as an extension, have degree phi(n). <math>\prod_{1 \leq j \leq n - 1, gcd(j, n) = 1} (x-e^{2\pi ij/n})</math> 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?