Physics is informational

• No, this blog is not dead.
• You can follow my (hum) thoughts (hum...) on CS and quantum on twitter here @loickq
• If you think that a "theory overflow" website should open on the same principles than MathOverflow and StackOverflow, I strongly advise you to commit to this project.

First of all, you can now watch the talks, all the links are on the QIP'10 programme webpage.

Second of all, Pablo Arrighi is giving the talk Unitarity + causality => localizability one more time here at QuPa. I did not understand anything the first time. I'm hapy to have a second chance.

Unitarity plus causality implies localizability

Pablo Arrighi, Universiy of Grenoble

« I already explained this a couple of times. So I redo… »

We are considering only finite dimensional Hilbert spaces because « we cannot say much on circuit representation on unitaries in infinite dimensional Hilbert spaces » (huh???) and we consider only discrete time evolution.

Consider a graph. Each vertex is a Hilbert space. The "global" HS is the tensor product of all of them. U: unitary operator between time t and t+1. There is an edge between a vertex v and all of his neighbors if the states in the Hilbert space of v depends on U and the states in the HS of its neighbors. (Is that understandable?) — That's causality.

I'm almost lost again. He tries to decompose U into small "local" unitaries. To do that, he double his graph with ancillas.

Basically, the result is that time t, the evolution of the state in the HS of a node does depend only of states of his neighbors (and their neighbors, and their neighbors, etc. but not too many of them) — That's localizability.

If the graph is regular grid and the size of all the Hilbert spaces are the same, this thing is a cellular automata ; and QCA are universal.

(It's all I got, and and it can be quite wrong. Hey people, it's not because something is on the Internet that it's right, does it?)

New evidence that quantum mechanics is hard to simulate on classical computers

Scott Aaronson

“Experiments can prove whatever you like, so who cares?”

Quantum simulation is not in BPP unless factorization is. “I think that factoring is not in P, I would not bet my life on that as would bet that P ≠ NP”

« "foo-bar is true => PH collapse at a finite level" is almost as insane as "foo-bar is true => P = NP" »

Suppose the output distribution of an linear-optics circuit can be approximately efficiently sampled classically, then a BPP^NP machine can additively approximate the permanent of X, where the entries of X are i.i.d. N(01) Gaussians. (Permanent is #P-complete, Gaussian permanent is also conjectured to be #P-complete)

"I heard that there is some kind of Fourier transform defined on the real… In computer science, it is on the Boolean hypercube!"

Fourier Fishing: We are given oracle access to n Boolean functions f₁,…, f_n, which are chosen uniformly and independently at random. The task is to output n strings,
z₁,...,z_n ∈ {0,1}ⁿ, at least 75% of which satisfy |f_i(zi)|≥1 and at least 25% grater or equal than 2.

Fourier Fishing is in BQP but not in PH. (it is not a decision problem)

Fourier Checking is in BQP but there are evidences that it is not in PH. (by supposing the "Generalized Linial-Nisan Conjecure")

Quantum sampling is hard. (if it is in BPP, PH collapses at the third level)

PostBQP = PostIQP = PP

For a computer scientist point of view, Bosons are associated with Permanent, and Fermions with determinant.

Let's do linear optics for dummies (=computer scientists) and try to make it computer scientist by citing simulations of bosonic polynomial circuits by Seth LLoyd and the (wonderful) paper that is [KLM01].

And now, he's speaking too fast because he doesn't have enough time. (Gaussian, permanent, simulation, 30 squeezed states)

Prize problems:

• 200$ — Solve the generalized Linial-Nisan Conjecure
• 140 CHF — Solve the Permanent of Gaussian state conjecture (Hummm. What is that?)
• Big prize  — Does linear optics contradict the generalized Church-Türing thesis?

Quantum algorithms for linear systems of equations

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) κ² s² / ε) (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

• N qubits
• Π(m) = proj(Φ_m) (rank = 1 => it excludes a one-dimensional subspace)
• H = Σ Π(m)
• SAT if the ground-state is 0.

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

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.

Business meeting

Quantum coin flipping

André Chailloux — arXiv:0904.1511

André talks about the divorce of Alice and Bob: they're divorcing and they need to flip a coin to know who's gonna keep the car.

There are two versions:

• Weak coin flipping: one side of the coin is labeled "Alice wins" and the other one "Bob wins".
• Strong coin flipping. A&B now really hate each other and they want to be sure that the other "player" has not put a bomb in the car.

State of the art:

• Weak: optimal biais = ε [Mochon07]
• Strong:lower-bound = 1/√2 [Kitaev] (again, it uses SDP, that is really the mathematical tool of the year!) and upper-bound by 1/√2 [ChaillouxKerenidis09] (this talk)

Highly entangled states with almost no secrecy

Improved extractors against bounded quantum storage

Improving the security of quantum protocols via open-and-commit

Unconditional security from noisy quantum storage

Unitary plus causality implies localisability

I got a complaint yesterday from Iordanis Kerenidis: I forgot to tell the Internet that he actually made people laugh during his (fabulous) talk about the power of unique quantum witness.

RT @qudit How many computer scientists does it take to connect a laptop to a projector? Latest count, 7. #qip

Span Programs and quantum algorithms

Ben Reichardt

Ben spoke about span programs (which is something totally new for me) and how they relate to the general adversary method for quantum query algorithms. He also gave the recipe for finding optimal quantum query algorithms (for Boolean functions).

Conjecture : when the adversary bound and the general adversary bound are equal, there is an optimal span program.
Partial answer: span programs are (almost) equivalent to quantum query algorithms for Boolean functions (up to a log/(log log) factor hat may even not be needed)
Open question: what is the lower of element distinctness (in the quantum case)?
Open question: how to extend the span programs framework beyond Boolean functions ?
Open question: what is the relation between time complexity and span programs?

Non-commutative compressed sensing: theory and applications for quantum tomography

David Gross, Yi-Kai Liu, Steve Flammia, Steven Becker, Jens Eisert and Vincent Nesme — arXiv:0909.3304, arXiv:0910.1879 and arXiv:10012738

«I will cite a Nobel Laureate: "Yes, we can!” »

Using matrix completion (reconstruct low rank matrix from a few randomly chosen matrix elements [Tao09]) the authors are able to prove
Theorem: Knowing rd log d randomly chosen Pauli expecation values, one can recover any rank-r density matrix.

He started by quoting a Nobel laureate, but he used results from Fields medalists and “The Chairman” aka Andreas Winter.

An efficient algorithm for finding Matrix Product ground states

Norbert Schuch, J. Ignacio Cirac, Dorit Aharonov, Itai Arad, and Sandy Irani — arXiv:0910.5055 and arXiv:0910.4264

Not attending to.

The query complexity of Hamiltonian simulation and unitary implementation

Dominic W. Berry and Andrew M. Childs — arXiv:0910.4157

Goal: simulation of a NxN Hamiltonian using a black box that outputs matrix elements.

For the first time since the beginning of QIP I’m feeling lost. The simulation is a quantum walk of O(√N) steps (grover-like search. Is that related to [ManiezNayakRolandSantha07]?) and in order to perform one step you need to call the oracle (how many times per step?) I have the feeling that this talk was design for people who already knew this kind of stuff and wanted to know the new refinements in that domain.

Simulating quantum computers with probabilistic methods

Maarten Van den Nest — arXiv:0911.1624

I just saw the ugliest picture of the conference…

New bridges between Computer Science and Quantum Computation

Invited perspective talk: Umesh Vazirani

It’s a talk on relationship between theoretic computer science, quantum computer science and quantum physics.
« Computer scientists spend their lives trying to avoid to use continuous variables »
Old question still not answered: How powerful is BQP? Scott Aaronson’s conjecture: Fourier checking is in BQP, but not in PH. (see Scott’s blog post to understand the relation between theoretical CS and quantum CS)
QIP = IP = PSPACE (solved in the framework of SDP. Hey that’s from classical CS too! More on that later)
Now the other side: classical problems solved with quantum technics.
Lattice based cryptography: Post quantum crypto: classical crytpo systems that are resistant to quantum attacks.
Is there a quantum PCP theorem?
D-wave bashing, but most importantly he’s explaining the work of Broadbent, Fitzsimons and Kashefi on blind computing: can we check if a computer is an actual quantum computer without opening it?

The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems

Daniel Gottesman and Sandy Irani — arXiv:0905.2419

QMA_{EXP} is QMA but with exponential size witnesses and checking circuits.
Theorem: 2-LOCAL-HAMILTONIANS in 1D is QMA_{EXP}-complete when the Hamiltonians involve translation-invariant nearest-neighbor interactions.

On the power of a unique quantum witness

Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang — arXiv:0906.4425

Why are NP-complete problems hard? Because they are too many witnesses? No. (Valiant-Vazirani work on Unique-SAT: if there is an efficient algorithm for unique-SAT, then there is an efficient algorithm for SAT)
Why are QMA-complete problems hard? FewQMA is not harder than Unique-QMA. Next goal: proving the QMA is no harder than Unique-QMA.

A full characterization of quantum advice

Scott Aaronson and Andrew Drucker

Motivating question: How much useful computational work can you “store” in a quantum state for later retrieval? Result: BQP/qpoly = YQP/poly
Trusted quantum advice is equivalent in power to trusted classical advice combined with untrusted quantum advice. (“Quantum states never need to be trusted”)

You can find an other version of Scott’s slides on his webpage.

Last slide of Scott. “Please, if you can explain what squeezed states, parametric down-conversion and homodyne measurements mean to a computer scientist, please talk to me”. I never wrote parametric down-conversion in my papers…