Meeting notes 11 08 03

Lukas talking about MUSIQC. Start with a simple Bernstein-Vazirani algorithm, and then convert into a fault-tolerant computation. This involves classically changing the gates we apply depending on the measurement results.

Kamil: Looking at area laws, and reading this paper. Also, how can you can extract all the information from an oracle? One answer is here.

Kevin: Matrix sparsification is a very useful tool in computer science, and has some application to quantum information. In particular, it improves quant-ph/0109050 by reducing the number of elements in the POVMs. These results are described in 1107.0088.

Greg: Is there an 8-qubit distance-3 subsystem code with weight-2 generators? Some related exhaustive searches have been done by quant-ph/0508131.

Isaac: Still trying to kill D-Wave (why? see here). The original approach is running into difficulties, but perhaps there are efficient algorithms related to the AM protocol of quant-ph/0606140.

Rowan: Beware that "1" is not a sparse matrix, while 1*speye(N) is.

Melanie: Learning about Bessel functions and perturbation theory.

Tom: Using iterative methods to find the largest eigenvalue of some big sparse matrix, related to the k-extendable optimization problem.

Steve: How do agents update their beliefs by talking to each other and observing evidence? Can we model anti-induction? Can we convince anti-inductivists that induction is the way to go?

Johnny: Hamiltonian perturbation gadgets.

<math>\begin{align} \tilde H &= \sum_{i=1}^n \tilde H_i\\ \tilde H_i &= H_i + xV_i \\ H_i &= \sum_{j=1}^k \frac{\Delta}{2} (I-Z_{i,j})\\ V_i &= \frac{1}{2}\sum_{j=1}^k X_{i,j} \otimes (P_aP_b + P_cP_d)\\ H^{\rm eff} &= \sum_{i=1}^n P_0V_ix^{m+1}\sum' S_i^{k_1}V_iS_i^{k_2}V_i \ldots S_i^{k_m}V_iP_0 \\ &=-\frac{kx^2}{2\Delta} P_0 \otimes (I+P_aP_bP_cP_d)+E\\ \|E\| &\leq n\Delta\left(\frac{4x\|V_i\|}{\Delta}\right)^3 \end{align}</math>

It appears that k=1 is optimal, and varying x defines a tradeoff between effective Hamiltonian strength and error.

David: Looking at applying module theory to quantum factoring algorithms. Let R be a principle ideal domain and let M be a finitely generated torsion R-module. Then R decomposes as <math>\bigoplus_{i,j} \langle\langle v_{i,j} \rangle\rangle </math> for some <math>v_{i,j}\in M</math> with orders <math>p_i^{e_{i,j}}</math> for some primes <math>p_i</math>. Background on these topics is in this book. The goal is to generalize Shor's factoring algorithm.