Physics is informational

Posting a question on Mathoverflow is bad for academic productivity.

I just spent the last hour hitting F5.

By the way, if "Association Schemes" rings a bell, you might be acknowledged in a paper.

2 comments

Old and new

A few weeks ago I needed the state $| \psi \rangle = \sum_{i \in \mathbb Z^*_N} |i\rangle$ where $\mathbb Z^*_N$ is the group of integers modulo N with multiplication.

I first thought it would be hard to build it. Then I came with this algoritm:

(it succeeds with probability at least 4/15)

I find that delightful. Step 2 is performing Euclid’s Algorithm on a quantum superposition: the oldest algorithm on the most cutting-edge device. I loved it. It made my day.

(I guess this was already known, but it’s fun)

3 comments

3 little things

3 comments

My most personnal blog post

This was recorded during the Monumenta 2010 « Personne » exhibition in Paris. Turn the volume up.

one comment

A bit more on QIP

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?)

one comment

Please Sokal come back!

OVARIUS® is a 4-dimensional creation emanating from research into Kinetic Energy. This leads naturally to say that Energy is Information on the Move, helping to explain the Human Being as a fractal of the Universe

The information in wine is essential for the evolution of Man. OVARIUS® is created as an Enlighter of Wine Energy, giving Man conscience elevation through the 4th dimension that is movement.

Ovarius is a wine carafe.

OVARIUS® est une création quadridimensionnelle émanant de recherches en Energie Cinétique. Cela conduit naturellement à dire que l’Energie Cinétique est de l’Information en Mouvement et permet d’affirmer que chaque Etre est une fractale de l’Univers.

Les informations contenues dans le vin sont un essentiel à l’évolution de l’Homme. OVARIUS® est créé comme Révélateur de l’Energie du Vin, offrant à l’Etre l’élévation de conscience par la 4e dimension qui est le Mouvement.

Ovarius est une carafe à vin.

2 comments

QIP '10 Liveblogging - Day 4.5

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 efficiently sampled classically, then P#P = BPPNP and hence PH collapses at the 3d level.

Suppose the output distribution of an linear-optics circuit can be approximately efficiently sampled classically, then a BPPNP 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 f1,…, fn, which are chosen uniformly and independently at random. The task is to output n strings,
z1,...,zn ∈ {0,1}n, at least 75% of which satisfy |fi(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:


Anthony, you're famous! One of your comments on my own blog has been ask to Scott: "Why are hardcore computer scientists interested with continuous variables?" Scott answer: "I don't know what is 'continuous variables, squeezing and homodyne measurement"

11 comments

QIP '10 Liveblogging - Day 4

So Loïck wants me (Fred Grosshans) to live-blog this morning session. Any mistake are therefore mine and not his ! This morning is mainly about trying to get beyond quantum mechanics and/or understanding why quantum mechanics is the way it is. In other words, why is so difficult to get PR-boxes.

Information causality

Marcin Pawłowski arXiv:0905.2292

Marcin speaks about those people that are so angry not to get a PR-box. I think you can count me among them ! To understand why the world makes us so unhappy, he introduce a new principle (information causality), which has been a “small step for mankind, but a big step for his PhD thesis”. He has a good explanation what principles should be, in decreasing order of importance :

As far as I understood, information causality is a quantitative statement saying there is no more information in a message than the sender initially put into it. It is now well known that prefect PR-boxes (with CHSH=4) make any distributed computation task trivial. in other words, with a single bit of classical communication and shared nonlocal randomness (from perfect PR-boxes), Alice and Bob could compute any distributed function f(x,y), where x and y are bit-strings. A single bit could get information from many bits. Information causality, if it is true, prevents this by saying that m bits can only carry m bits of information.

Information causality is true in every theory allowing to introduce a reasonable mutual information, i.e. one which obeys the following axioms:

Furthermore, it allows them to recover Tsirelson/Cirel’son/Цирельсон ’s bound (CHSH≤2√2) with only information theoretic axioms and no (direct) reference to quantum mechanics!



Local quantum measurement and relativity imply quantum correlations

Salman Beigi, Sergio Boixo, Matthew Elliot, and Stephanie Wehner arXiv:0910.3952

Here, the question is whether a theory can be locally quantum and violate the Tsirelson bound. After some math involving POVM, the naswer is no. In other words, if you manage to violate the Tsirelson's inequality in a Bell-like set-up, you have also proven that quantum mechanics is wrong locally.

According to Antonio Acín in rump session, this result do not extend to 3-party.

All reversible dynamics in maximally non-local theories are trivial

David Gross, Markus Mueller, Roger Colbeck, and Oscar Dahlsten arXiv:0910.1840 , accepted yesterday in PRL.

This talk brings us to (N,M,K)-boxworld. In Boxworld, states are described by nonlocal hidden variables, where N parties can choose between M measurement devices which give K outcomes. Standard PR-boxes exist in (2,2,2)-boxworld. The question is basically what kind of reversible computing is possible in boxworld. The symmetry of boxworld, where the equivalent of Bloch's sphere are pointy polytopes strongly reduce the number of possible reversible transformations to basically trivial transformations.

In particular, you cannot reversibly create PR-box from product states, even if the theory allows for their existence.

Measurements incompatible in quantum theory cannot be measured jointly in any other no-signaling theory

Michael M. Wolf, David Perez-Garcia, and Carlos Fernandez

The title says everything I was able to catch from Michael's talk. Except that some dual semi-definite programs where involved during the proof.

Laying the quantum and classical embedding problems

Toby Cubitt, Jens Eisert, and Michael Wolf

The problem here is basically finding a master equation compatible with a CP-map description of a channel. The classical version of this problem (finding a Markov equation explaning a stochastic transformation) is as old as the Hindenburg disaster (1937) and had not been solved.

Using Linblad generators, matrix logarithms, 1-in-3SAT problem, integer semi-definite programming, Toby shows that the quantum and the classical problems are NP-hard. Solving the problem is equivalent to solving P=NP. But there is a (known) algorithm which is efficient for fixed dimension.

It somehow means that physics extraction from experimental data is NP-complete !

Quantum interactive proofs with short messages

Salman Beigi, Peter W. Shor, and John Watrous

Since QIP=IP=PSPACE, quantum proofs seem to bring no advantages over classical proofs and QIP = QIP(3). This talk is about the power of QIP(1) = QMA, QIP(2), QIP[log,poly]…

Theorem: QIP[log,poly] = QMA.
Theorem: QIP_log = BQP
Theorem: QAM[poly,log] = BQP

Open problem: what is the power of QIP[poly,log]

one comment

QIP '10 Liveblogging - Day 3

Quantum algorithms for linear systems of equations

Aram HarrowarXiv: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 KempearXiv: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)

one comment

QIP '10 Liveblogging - Rump Session

There was no internet connection in the rump-seesion room. But I’m better than that: here is my (slightly delayed) live blogging on the rump session. No edit made, no censorship. Only beer and wine.

Rump-Session Prologue Louis Salvail (5)
25 papers submitted, 26 accepted and 1 withdrawal.
Gilles Brassard was BOOded because he didn’t understand the rule of the game.
 
Quantum communicating arbitrarily fast, far and reliably Austin Fowler (5)
Ooops, I think I missed it!
 
Unified framework for classical blah blah blah by Tonio Acin
Tony tries to speak the fastest he can and it is fast. “we try relaxation of some quantum conditions” Hey Tony, relax your own condition!
- Chairman: is there any question?
- People: Are there open questions?
 
The dependence of the ferromagnetic ordering in the degenerated electron system from the dimension Fedor Orlenko, George Zegrya and Elena Orlenko (4)
Canceled
 
Free probability techniques in quantum information theory Benoit Collins and Ion Nechita (7)
He’s speaking about random channels and non-additivity of the output entropy. And my beer starts to be too warm… Oh no, it’s empty.
 
Announcement of TQC 2010 Viv Kendon and Wim van Dam (2)
It will be held 13-15 April 2010 in Leeds, UK. Younger conference than QIP but with proceedings.
 
The Video Abstracts at Quantiki Daniel Burgarth (4)
Papers used to be less formal than nowadays: make informal video abstract of your paper, go to quantiki and publish your video!
 
Fixed-gap universal adiabatic quantum computation Ari Mizel (8)
1½ joke is supposed to be included in this talk.
PRA 63, 040302 (2001) should have had more impact, but it was published the same year than Britney Spear’s Baby One More Time…
Use ground state quantum computation with gate teleportation. Simulate a faulty quantum computation with error probability p. The gap that results is function of that probability.
 
Monotone ‘metric’ in the channel space: resource conversion approach Keiji Matsumoto (5)
Hum…
 
Entanglement-assisted communication of classical and quantum information Min-Hsiu Hsieh and Mark Wilde (8)
Denise successfully negotiated the opening of the Kitchen during the talks… Yey!
André and I unashamedly stole a bottle of red wine. I have to admit that makes me proud.
And it’s snowing outside.
 
Multiplayer XOR games with clique-wise entanglement Jop Briet (5)
That was too interesting to be blogged. Sorry folks.
 
Trade-off capacities of the quantum Hadamard channels Kamil Bradler, Patrick Hayden, Dave Touchette and Mark Wilde (8)
In real life, one has to consider Hadamard channels (the ones that break entanglement) because super-duper-activation (whatever that is) is totally unrealistic…
 
Bounds for quantum oblivious transfer reductions Severin Winkler and Jürg Wullschleger (4)
I’m trying to listen but André is bugging me… It was about OT and bit commitment and there is no paper on the arXiv yet.
 
Teleportation: The Movie Clare Horsman (6)
@qudit talk is in fact named “Graphical QM” and its about categorical quantum mechanics.  We have a movie with colorful triangles, lines, and XKCD people. (The Man With The Hat) and we are supposed to believed that this was teleportation… Anyway, after the 2^3th time, it was hilarious…
Gilles Brassard: “I invented teleportation, and after watching your movie 8 times, I still don’t understand what your movie was about.”
Clare: “Please, read the paper, it’s on the arXiv”
 
QMA with unique witnesses: an impossibility result? Andris Ambainis (8)
Remember the open question at the end of Iordanis’ talk about the relationship between FewQMA and UniqueQMA? Andris has hints it will not be answered the way Iordanis wants. (hence the quantum case will be different from the classical one)
 
ICITS 2011 Serge Fehr (2)
Will take place in Amsterdam on May, 21-24. It’s about crypto and information theory security. Classical and Quantum.
 
Generating random stabilizer states: a theorem in search of an application Scott Aaronson and David Chen (8)
Generating random generators takes O(n^4) times. More clever approche by Gottesman O(n^3). Scott and David’s result: O(Mn) times where Mn is the multiplication matrix time. The proof maps any stabilizer states into a tensor product of ‘atomic’ stabilizer states.
Open problem: is that useful? Can we do better?
 
Nigel & Mary - A love story Katherine Brown, Clare Horsman, Viv Kendon and Bill Munro (5)
How to make cluster states sexy. In the slide, Nigel is looking under the dress of Mary. Is that sexy? “Odd women are difficult to deal with” The slide about “fault-tolerant” pictures Nigel & Mary arguing.
The talk was sexy, but I don’t know what it was about…
 
Announcement of Quantum Communication Workshop 2010, UNIK, Kjeller, Norway Sara Felloni (2)
Sarah is not here since she “met some guy somewhere” (Renato Renner)
 
The Impotence of Nonlinearity: Why closed timelike curves and nonlinear quantum mechanics don’t improve quantum state discrimination, and haven’t been shown to dramatically speed up computation, if computation is defined in a natural, adversarial way Charles Bennett, Debbie Leung, Graeme Smith and John Smolin (8)
I see a pumpkin butt on the screen.
This talk is about time travel, and more precisely about Scott’s talk last year at QIP, where he proved that BQP_CTC = BPP_CTC = PSPACE and how we can use CTC to distinguish non-orthogonal states.
Charlies’s point: these consequences are illusional.
“Time travel can make you impotent”
Question: “Is it the first time that a penis appears on a slide at QIP”?
 
Advertisement for poster 56 of Thursday January 21 Marco Piani, William Matthews and John Watrous (3).
Canceled
 
Bounds on the probability of transformation between multipartite pure states Wei Cui, Wolfram Helwig and Hoi-Kwong Lo (7)
It’s time to go to eat. No meat any more: I have to eat carrots.
 
You’re Telling Me The Uncertainty Principle Is Wrong? Joseph Renes, Roger Colbeck, Mario Berta, Matthias Christandl and Renato Renner (7)
It’s a 3-person dialog. And it is funny.
 
Learning quantum states coherently (and adaptive quantum compression) Robin Blume-Kohout and Sarah Croke (4)
“Now, it is the drunk part of the rump-session” That is not totally false.
“On this photo you can see koalas on a stick”.  I can assure you that this was not, and in any way, related to the talk.
“Here are some sheep”
“That’s me fishing” (still not related)
“That’s a quantum robot” (still not related even if there is the word quantum in it)
 
Quantum Money Andrew Lutomirski and et al. (7)
-        The bank can print it
-        Anyone can verify it
-        No one can copy it
“Scott published a way to do that. We broke it. Life goes on.”
 
The Next Quantum Frontier Todd Brun (5)
“Does forgetting your umbrella makes it more likely to rain?”
New fields in quantum computation:
  1. choose a topic that has never jhad the word “auntum”
  2. ex: animal husbandry
  3. insert quantum in it.
  4. Ex: quantum animal husbandry
  5. Apply for funding!
Quantum mechanics rules! Thanks you all. And good night!

2 comments

QIP '10 Liveblogging - Day 2

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:

State of the art:

The proof is a classical reduction to any optimal weak coin flipping protocol. The main trick is to create an unbiaised but unbalanced weak coin flipping.

« Bob does not touch Alice's private parts when he performs his operations » André is the only one that did not get his own joke!

I already seen this talk many times, but now comes the brand-new-QIP2010 part: the Kitaev's lower bound and the Mochon's paper condensed in 30 minutes.

You write the primal SDP, the dual, the right quantity, and it just “magically” appears. That does not really convince Dorit. (but SDP are black magic!)

The idea in Mochon's paper is to find in one block a protocol for weak coin flipping and dual feasible points that prove an upper bound on the optimal cheating probability. How do we find good ones? By making little drawings called Point Games. By making more and more complicated point games, one can achieve an ε biais point game.

I'm wondering more and more if one cannot use Learning technics in order to find useful point games. (ie, we can actually make real-life quantum protocols from them)(or maybe we can also just give a point game board to a monkey and wait long enough)

André's girlfriend just connect on skype! Everybody saw it. And now she's saying something in polish… (I offer some chocolate to anyone who tells me what she said…)

(As a Ph.D. student, I wonder what do we get from our adviser. André uses the same font that his adviser on his slides — courier new — and that is not a good idea)


Highly entangled states with almost no secrecy

Matthias Christandl, Norbert Schuch, and Andreas WinterarXiv:0910.4151

There are way too many "entanglement cost", "entanglement of formation", "bound entanglement", "squashed entanglement" for me. Unable to liveblog this talk.


Improved extractors against bounded quantum storage

Anindya De and Thomas VidickarXiv:0911.4680

Using a public source (long almost-random classical string) and a seed (a short one) shared between Alice & Bob, how much randomness can they extract? In this model, the adversary has a bounded memory (he cannot store all the public source). The goal is to be protected against quantum adversaries.

Their extractor is based on Trevisan's extractor and not on 2 universal hashing.

Thomas is underlining the role that the conditional min-entropy plays. My problem: this quantity is ill-defined for continuous variables!

(There will be a workshop on Cryptography from storage imperfection in march in Caltech)


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

Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner — arXiv:0902.3918

They are able to transform a large class of cryptographic protocols into more secure protocols (weaker assumptions on the power of the cheater) by performing so commit phase in the middle. The number of round is linear in the number of rounds of the initial protocols. In particular for protocols in the bounded storage model, protocols are also secure against cheater that have only a small quantum computer.

Unconditional security from noisy quantum storage

Robert Koenig, Stephanie Wehner, and Juerg WullschlegerarXiv:0906.1030  also arXiv:0911.2302

Yet another talk in which the Graal is two-party secure computation. The noisy storage model
* The adversary is computationally powerful
* Unlimited classical storage
* Actions are instantaneous
* Noisy storage

If the information sent to the memory (quantum channel) at a rate above the classical capacity of the channel, they are able to derive bound on the security of the protocols (bit commitment and oblivious transfer). They are even better than the one derived in the quantum bounded storage model! The protocols are composed by a weak string erasure (the quantum part) and classical post-processing.

Open question: by using the quantum capacity of channel, can we get a bound for other channels? (against individual attacks, at least)
Open question: what are the real limits on security?

(I always loved Stephanie's talks. They are accessible, she speaks quite slowly, her slides are helpful…)


Unitary plus causality implies localisability

Pablo Arrighi, Vincent Nesme, and Reinhard Werner

There is a trap: this talk is about quantum cellular automata! So there are actually people who study quantum cellular automata…

I. do. not. understand. (but I think, the words quantum cellular automata activated a switch in my head, and I suddenly remembered when I was little and my lecturer was trying to teach me cellular automata.)

(I was wondering why Vincent wrote localisability and not localizability. It's not because he is a snob. He speaks with a light British accent)

6 comments

QIP '10 Liveblogging - Day 1.5

Due to power outage, no liveblogging this afternoon. Sorry folks.

By the way, I like the comment “one author added” in the updated version of this paper

one comment

QIP '10 Liveblogging - Day 1

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…

3 comments

QIP '10 Liveblogging - Day 0.5

QIP = PSPACE

Rahul Jain, Zhengfeng Jin Sarvagya Upadhyay, John Watrous — arXiv:0907.4737

Known facts:

Need to show that QMAM ⊆ PSPACE. The key is to write the verifier’s Maximum Acceptance Probability (MAP) as a SDP and find feasible points. Pick some point of the primal. If they are not, they are (up to a projection) dual feasible points. Then use the MWU in order to improve the solution of the dual. Try log(size of the problem) times.

(and I did not get how to have a good solution of the primal from them) (strong duality?)

QIP = IP : Quantum Interactive Proofs are not more powerful than classical interactive proofs.

Random numbers certified by Bell’s theorem

Antonio Acín, Antoine Boyer and Stefano PironioarXiv:0911.3427

How can you trust your random number generators? Seriously: you have to be paranoid about your RNG. Do it yourself! You just need a device that violates Bell inequalities and extract the quantum randomness in it.

Protocol: you have two devices: you feed them with N join random bits and you compute the estimator of the violation of Bell inequalities with their outputs.

Result: A bound on the output entropy as a function of the violation of Bell inequalities: H ≥ N x f(I-ε) with probability 1-δ. where I is the estimator of the violation, ε and δ are small compared to N and f is a function.

Assumptions

The output string is not necessary uniform. You need to do randomness extraction to actually have useful randomness.

Adiabatic gate teleportation

Dave Bacon and Steve Flammia — arXiv:0905.0901 and arXiv:0912.2098

Steve is laughing at computer scientists that don’t like integrals.

Adiabatic teleportation: you make teleportion in an adiabatic way…

Adiabatic gate teleportation: you start with a qubit |ψ > and at the end of the teleportation you get U|ψ>

For a 1 qubit gate, you just need to perform a rotation on one qubit of your EPR pair before the usual teleportation. For 2 qubit gates, it is more complicated, you need to use a gadget and make 2 teleportations.

6 comments

QIP '10 Liveblogging - Day 0

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…

8 comments

QIP '10 Online resources

Does anyone have other resources?

2 comments

The Day Before QIP

Ski

no comment

Les miracles n'existent pas

- Youhou, j’ai ouvert un blog !
- Mais euh, pour quoi faire ?
- On va commencer par livebloguer QIP 2010, la grand’messe annuelle des informaticiens quanticiens.
- Et t’appelles ça un blog ? On voit bien que presque rien n’est fini, que ta police est moche,…
- N’empêche : j’ai un blog.

Si vous rencontrez un problème vraiment rédhibitoire, envoyez-moi un email ou laissez-un commentaire là-dessous, je ferai en sorte de corriger le plus vite possible.

2 comments