Quantum algorithms for linear systems of equations

Aram Harrow — arXiv:0811.3171

The article of the day: Mathematicians create algorithm so complex no computer can use it… yet! and if you wanna laugh, read the comments!

Goal: solving sparse linear system of equations Ax=b
Tools: Hamiltonian simulation, phase estimation and amplification.

It is really interesting to see how the condition number κ of A is the important parameter in the analysis of the running time of the algorithm. κ exhibits the same behavior as in the classical case: it can sometimes be improved; in other cases κ can be big but it does not make the algorithm less stable.

The running time of their algorithm is Õ(κT + log(N) κ2 s2 / ε) (where T is the time to encode b into a quantum state, s is the sparseness of A and ε the precision desired.

Open question: can we reduce the dependency in κ in order √κ? (which is a proven lower-bound)

“We can do some George Bush thing: we decide what we want κ to be.”


Random quantum satisfiability: statistical mechanics of disordered quantum optimization

Sergey Bravyi, Cristopher Moore, Alexander Russell, Christopher Laumann, Andreas Läuchli, Roderich Moessner, Antonello Scardicchio, and Shivaji Sondhi — arXiv:0903.1904 and arXiv:0907.1297

That's a talk about random 3-SAT, but considering the average complexity (which instances are hard?) The classical theory (supposedly) well-known. What about the quantum case? Quantum k-SAT:
The clause density is defined by α = N / M.

It does not look surprising, but there are phase transitions. (at least for 2-QSAT at α = 1/2)
In the satisfying phase, there is an other phase in which satisfying states can we written as a linear combination of some "satisfying product states". (I'm wondering how big is that phase) Anyway, they are able to derived a (supposedly) necessary and sufficient condition.

Ok, so for k=2 SAT=PROD-SAT.
For k=3, PROD-SAT for α ≤ 0.92 and UNSAT for α ≥ 3.52. (and it is not clear what happens in between)

A quantum Lovász Local Lemma

Julia Kempe — arXiv:0911.1696

Still about k-SAT when we consider weakly dependent clauses (a variable appears in a few new number of clauses)

LLL (Lovász Local Lemma) Pr[B_i] ≤ p, B_i,…,B_m are independent (of all but d) then e p (d + 1) ≤ 1 => Pr[no event B_i occur] > 0. Corollary: A k-SAT formula where each variable appears in at most 2^k/(ek) clauses, it is always satisfiable.

An now, the quantum case (k-QSAT) Weak dependency: each qubit appearz in at most 2^k / (ek) projector when H is satisfiable.

QLLL: Define R(X) = dim X / dim V for X in V. R(X_i) ≥ 1-p, X_1,…,X_m in V are independent (of all but d), e p (d+1) ≤ 1 => dim( intersec X_i) > 0

R(X) behaves a lot like a probability distribution. Corollary: k-QSAT with weakly independent clauses is satisfiable.  Applying QLLL to random k-QSAT helps reducing the gap between the satisfiable and the unsatisfiable phases. And by a big factor. Previously, the gap was between α=1 and α=2^k. Now it is between 2^k/k^2 and 2^k. Wow! (up to some constants, of course)

Whereas the satisfiable states for α≤1 where product states (remember the previous talk?), satisfiable states between 1 and 2^k/k^2 are believed to be always entangled.

(Is anyone counting how many times Julia says "OK?" ?)


(Vincent Nesme came to me yesterday to tell me that the only reason he writes localisability with the British spelling is his pedantry!)


Business meeting

Talks acceptance ratio: 22%

Poster: 5 rejected: 2 out of scope, 1 not enough info, 2 for correctness reason. See Dave Bacon's blog post.

QIP 2011 will be held in Singapore. (so: scuba-diving, enjoying beaches, eating amazing fruits and see food — something tells me that it will be a lot cheaper than Zürich) Tutorial session: 8-9 jan. 2011
Conference: 10-14 jan. 2011

2 and 1/2 proposals for QIP 2012: Montréal and Santa Barbara (and Jerusalem but it can also work for 2013)
Santa Barbara won. (and that was quite a surprise) but the final decision will be taken by the steering committee.

(It  was the least organized vote ever. But somehow democratic. Somehow)