Difference between revisions of "Meeting notes 11 09 27"

From Quantum Computing Theory Group
Jump to: navigation, search
(started notes)
 
Line 11: Line 11:
 
Tom: Writing up report related to k-extendable states.  Next, analyzing the [http://en.wikipedia.org/wiki/Power_iteration power method] (an algorithm for estimating the top eigenvalue of a matrix).
 
Tom: Writing up report related to k-extendable states.  Next, analyzing the [http://en.wikipedia.org/wiki/Power_iteration 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 = U D U^\dagger</math>, e.g. with a QR decomposition.
+
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 [http://en.wikipedia.org/wiki/Exact_cover Exact Cover], up to n around 45.
 
Rowan: Planted solution for [http://en.wikipedia.org/wiki/Exact_cover Exact Cover], up to n around 45.
Line 25: Line 25:
 
<math>G^n := G \times G \times \cdots \times G</math>
 
<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>.  How quickly does the cardinality of
+
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?
 
<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>.
 
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 [http://mathworld.wolfram.com/CyclotomicInteger.html cyclotomic integers], and as an extension, have degree phi(n).  <math>\prod_{j=1}^{n-1} (x-e^{2\pi ij/n})</math> is called the n<sup>th</sup> 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?

Revision as of 01:04, 28 September 2011

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_{j=1}^{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?