Ghost Paper Dance!

In a belated revival of the Ghost Pontiff’s “Happy Paper Dance” ritual, I’d like to talk about the recent paper The k-local Pauli Commuting Hamiltonians Problem is in P by my student Jijiang (Johnny) Yan and his former advisor, Dave Bacon. The abstract is:

Given a Hamiltonian that is a sum of commuting few-body terms, the commuting Hamiltonian problem is to determine if there exists a quantum state that is the simultaneous eigenstate of all of these terms that minimizes each term individually. This problem is known to be in the complexity class quantum Merlin-Arthur, but is widely thought to not be complete for this class. Here we show that a limited form of this problem when the individual terms are all made up of tensor products of Pauli matrices is efficiently solvable on a classical computer and thus in the complexity class P. The problem can be thought of as the classical XOR-SAT problem over a symplectic vector space. This class of problems includes instance Hamiltonians whose ground states possess topological entanglement, thus showing that such entanglement is not always a barrier for the more general problem.

This result follows a long string of papers that discuss the complexity of finding the ground state energy of k-local Hamiltonians, usually modified by various adjectives like “commuting” or “frustration-free” or “Pauli” or “in d dimensions.” Typically, these problems are shown to be somewhere between NP and QMA, and the subtle differences between these relate to issues such as topological order and the quantum PCP conjecture. In fact, one specific inspiration for this paper was 1102.0770, which showed that 3-qubit (or even 3-qutrit) commuting Hamiltonians could not have topologically-ordered ground states, while 4-qubit commuting Hamiltonians include the toric code, and 2-qubit non-commuting Hamiltonians include things that look like the toric code.
This paper shows that, in the case of commuting Pauli Hamiltonians, the difference between 3-local and 4-local is not important from a complexity point of view; indeed, it is possible to efficiently find the ground state of even $latex O(n)$-local Hamiltonians.
At first this is shocking, but to see why it’s reasonable to expect this result, consider classical (commuting, Pauli) Hamiltonians. Determining whether these terms has a simultaneous ground state is equivalent to solving a linear system of equations over $latex mathbb{F}_2$, which of course can be done in poly-time. This paper extends that to general Paulis, but the algorithm still involves solving linear systems of equations–this time over $latex mathbb{F}_4$. It is one of my favorite examples of the power and simplicity of the Pauli matrices, tied perhaps with the elegant Wehner-Winter uncertainty relations for anti-commuting observables.

|Democrat> + |Republican> / sqrt(2)?

It has long been known that party politics exhibits quantum effects. (An excerpt, that I’m sure is not retaliation for Sokal’s hoax, is “…we show evidence using the Smith et. al data that a tenet of a classical model that has animated work in the field appears violated in a form that gives way naturally to embrace of the superposition principle and then suggest that the classical formalisms and theories of preference separability might best be viewed as special cases of the quantum versions.”)
But what use is this theory, if we can’t apply it to any situations of practical relevance? Finally, the theory of quantum politics has found a way to explain current politics with A Quantum Theory of Mitt Romney, in an article that actually does a better job of explaining complementarity, uncertainty, etc. than do a lot of popular articles (quantum leap, not so much).
As an example of what this new theory explains, here is a Feynman diagram depicting a collision between a Romney and an anti-Romney that yields an electron and a $20 bill.

Debate!

Before I did math, I did debate.
And now I’ve found a way to reconcile the two! Gil Kalai is a great researcher in theoretical computer science who has written several articles that are skeptical of the possibility of quantum computers ever being built. I think his ideas are interesting, but wrong.
So we’ve agreed to debate on the neutral territory of Dick Lipton and Ken Regan’s blog, Godel’s Lost Letter.
The debate begins with Gil laying out his case for skepticism of quantum computing.
In a few days, I’ll post my reply there. Stay tuned…

Why boycott Elsevier?

Everyone has their own reasons for doing this. There is an interesting debate at Gower’s blog, including a response from an Elsevier employee. Some people dislike Elsevier’s high prices, their bundling practices, their fake medical journals, their parent company’s (now-former) involvement in the global arms trade, their lobbying for SOPA/PIPA/RWA, or other aspects of their business practice. Indeed, for those who want to reform Elsevier, this is one limitation of the boycott, in that it doesn’t clearly target a particular practice of the company that we want changed. On the other hand, others think Elsevier isn’t evil, but just has a communications problem.
In this post, I want to defend a more radical position, which is that we should try not to reform Elsevier or other publishers of academic journals, but to eliminate them. Until the debate over SOPA, I thought this position was too extreme. I thought we could tolerate a status quo in which journals are used for credentialing, and although it is a little unjust and absurd, the only real cost is bleeding the library budgets a little bit.
But the status quo isn’t stable. Open access and self-archiving are expanding. Soon, someone will successfully mirror JSTOR. Libraries are increasingly complaining about subscription costs.
In the long run, the future looks more like arxiv.org. Their front page boasts (as of this writing):

Open access to 731,335 e-prints in Physics, Mathematics, Computer Science, Quantitative Biology, Quantitative Finance and Statistics.

Just like the walled gardens of Compuserve and AOL would never grow into the Internet, no commercial publisher will ever be able to match the scope and ease of access of arxiv.org. Nor can they match the price. In 2010, there were about 70,000 new papers added to arxiv.org and there were 30 million articles downloaded, while their annual budget was $420,000. This comes to $6 per article uploaded (or 1.4 cents per download). Publishers talk about how much their business costs and how even “open access” isn’t free, but thanks to arxiv.org, we know how low the costs can go.
By contrast, if you want your article published open access with Springer, it costs $3000. This seems like something we might be able to protest, and convince them to change. We can’t. Elsevier’s outgoing CEO left with a golden parachute worth two million pounds. They’re not going to make that kind of money while running with the efficiency of arxiv.org. So while scientists and the public see the internet as a way of sharing knowledge and driving down costs, publishers like Elsevier see it as a threat. For them, $6/article is a nightmare scenario that has to be stopped.
Some of you might think I’m overreacting. After all, publishers have tolerated self-archiving, citeseer, arxiv.org, etc. so far. This is partly to avoid backlash, and partly because for historical reasons editors of journals like Science and Nature have personally supported the advance of science even over the profits of the companies they work for. But in the long run, we can’t both have everything available for free, and journals continuing to charge extortionate prices. I suspect that a conflict is inevitable, and when it happens, we’ll regret the fact that journals hold all of the copyrights. SOPA was the first sign that publishers are not on the side of advancing knowledge, and if a journal ever goes bankrupt and sells its portfolio of intellectual property, we’ll find out what they’re capable of when they no longer are run by people who place any value on science.
So what can we do about it? A boycott of Elsevier is a good first step. But really we need to change the system so that publishers no longer hold copyright. Their role (and rate of profits) would be like that of the local Kinko’s when they prepare course packs. This would also improve the academic societies, like ACM and APS, by removing the terrible incentive that their publishing gives them to support organizations like the AAP that in turn support SOPA. Instead, they could simply represent communities of scientists, like they were originally designed to do.
I’m not idealistic enough to imagine that arxiv.org is enough. The issue is not so much that it lacks refereeing (which could be remedied easily enough), but that it lacks scarcity. To see what I mean, imagine starting a free online-only virtual journal that simply selects papers from the arxiv. The entire journal archives could be a single html file of less than a megabyte. But without space constraints, it would need to credibly signal that papers accepted into it were high quality. This is nontrivial, and involves convincing authors, readers, referees and hiring committees, all more or less simultaneously. As a community, we need to figure out a way to do this, so that the internet can finally do what it was designed for, and disrupt scientific publishing.
Update: Via John Baez, I came across a proposal for replacing academic journals with overlay boards that seems promising.

referee Hall of Fame/Shame

At the Pontiff, we are big fans of Science 2.0 in all its forms. But even within the traditional journal system, there are ways to improve the peer review system. One tragedy of peer review is how little credit the referees get for doing good work, and how there’s nothing to trouble them if they don’t but their own guilty consciences and a bunch of emails from an editor.
One approach I recently came across is from an economics journal. They publish a list of their associate editors, together with average turnaround time for manuscripts.

Editorial Board Member Manuscripts
Name Affiliation Reviewed Avg Days
1 Bessembinder, Hank

University of Utah

8

14

2

DeAngelo, Harry

University of Southern California

4

18

3

Dittmar, Amy

University of Michigan

4

25

4

Duffie, Darrell

Stanford University

2

12

5

Fama, Eugene

University of Chicago

6

2

etc.

This is a nice start, but surely we could do more. When I teach, I get student evaluations. What if the authors of the papers I refereed also gave me 1-5 stars as a reviewer? Before you mention the obvious problem, the way to average the ratings would be by outcome: all the “reject outright” ratings are averaged together, all the “revise and resubmit” ratings are averaged together, etc., before these are all combined into a final score. That way, you couldn’t get high ratings just by always accepting everything.
Clearly this proposal still needs more work. Any ideas?

strike!

In a move that will undoubtedly bring the US Senate to its knees, the Quantum Pontiff is going dark from 8am to 8pm EST on Jan 18 to protest SOPA, PIPA, the Research Works Act and other proposed acts of censorship.
We suggest you use this time to contact your representatives, read a book (or 1201.3387), or go outside.

Could Elsevier shut down arxiv.org?


They haven’t yet, but they are supporting SOPA, a bill that attempts to roll back Web 2.0 by making it easy to shut down entire sites like wikipedia and craigslist if they contain any user-submitted infringing material. (Here is a hypothetical airline-oriented version of SOPA, with only a little hyperbole about planes in the air.)
I think that appealing to Elsevier’s love of open scientific discourse is misguided. Individual employees there might be civic-minded, but ultimately they have $10 billion worth of reasons not to let the internet drive the costs of scientific publishing down to zero. Fortunately, their business model relies on the help of governments and academics. We can do our part to stop them by not publishing in, or refereeing for, their journals (the link describes other unethical Elsevier practices). Of course, this is easy to say in physics, harder in computer science, and a lot harder in fields like medicine.
There is another concrete way to stand up for open access. The White House Office of Science and Technology Policy has requested comments on the question of public access to federally-funded scientific research. Comments should be from “non-Federal stakeholders, including the public, universities, nonprofit and for-profit publishers, libraries, federally funded and non-federally funded research scientists, and other organizations and institutions with a stake in long-term preservation and access to the results of federally funded research.” That’s us!
But don’t procrastinate. The deadline for comments is January 2.
Here is more information, with instructions on how to comment.
Here is also the official government Request For Information with more details.

QIP 2012 Day 4

Possible location of QIP 2014??

Aleksandrs Belovs
Span Programs for Functions with Constant-Sized 1-certificates, based on 1105.4024

Consider the problem of finding whether or not a triangle exists in a graph with n vertices. Naively using Grover’s algorithm requires time $latex n^{3/2}$. But a series of improvements have brought this down to $latex n^{10/7}$ (using Grover with better combinatorics) and $latex n^{13/10}$ (using element distinctness in a clever way). The current paper reduces this run time to $latex n^{35/27}$. That is, the exponent is improved from 1.3 to 1.296296296…
Before you roll your eyes and move to another tab, hear me out. The real improvement is in the technique, which is radically new, and has applications to many problems; not only triangle-finding.
The idea is to construct something called a learning graph. Each vertex is a subset of [n], and (directed) edges are weighted, and correspond to (sets of) queries. These are like randomized decision trees except they can have loops.
The complexity of the resulting algorithm (which we’ll describe below) is a little tricky to define. There is a “negative complexity” which is simply $latex sum_e w_e$. And a positive complexity which involves maximizing over all yes inputs $latex x$, and then minimizing over all flows of size 1 where the source is the empty set and the sinks are the 1-certificates for $latex x$.
Algorithms in this model correspond to flows of intensity one. The vertex corresponding to the empty set is the root, and 1-certificates (i.e. proofs that x is indeed a yes instance) are the sinks. The cost is $latex sum_e p_e^2/w_e$, where $latex p$ denotes the flow.
From a learning graph, there is a recipe to produce a span program, and in turn a quantum query algorithm, with the query complexity equal to the geometric mean of the negative and positive complexities of the learning graph.
As an example, consider the OR function. Here the learning graph is comprised entirely of a root and n leaves. Weight each edge by 1, so the negative complexity is n. If there are k solutions, then the resulting flows are 1/k on each edge, and so the positive complexity is 1/k. The algorithm’s complexity is $latex sqrt{n/k}$. Phew!
Less trivial is element distinctness:
Are there two indices $latex ineq j$ such that $latex x_i=x_j$?
Again the algorithm achieves the optimal complexity, which is $latex O(n^{2/3})$, matching Ambainis’s algorithm.
There are lots of new applications too, to improving the triangle runtime, but also getting a bunch of polynomial speedups for other problems that either are, or resemble, subgraph containment. For example, it improves some of the results from 1011.1443, and gets linear time algorithms to check whether a graph contains subgraphs from certain families, like lines, T-shaped things, and lines that go through stars.

Francois le Gall,
Improved output sensitive quantum algorithms for Boolean matrix multiplication

Boolean matrix multiplication means that the matrices are binary, + is replaced by OR, and * is replaced by AND. This arises in many cases, often related to graph theory, such as computing the transitive closure of a graph, triangle-detection, all-pairs shortest path, etc. Also it has application to recognizing context-free languages.
The naive algorithm is $latex O(n^3)$. Reducing to integer multiplication gives $latex O(n^{2.3ldots})$. Quantumly, we can use Grover to compute each entry, for a total runtime of $latex O(n^{2.5})$.
But suppose C has only one nonzero entry. Then we can do recursive Grover search and get time complexity $latex O(n^{1.5})$ [Buhramn Spalek ‘05].
If it has $latex l$ nonzero entries, we get $latex O(n^{1.5}) sqrt l$, neglecting polylogs.
The parameter l represents the sparsity of matrix “output sensitive algorithms”.
In this work, the runtime is improved to $latex O(n^{3/2} + nl^{3/4})$. There is also a more complicated result for query complexity. The techniques are adapted from papers of Williams & Williams, and Lingas. They also make use of a wide range of polynomial speedup tricks: Grover, approximate counting, triangle-detection, etc. The talk leaves the exciting impression that we not yet finished seeing improvements to these techniques.

Richard Cleve Discrete simulations of continuous-time query algorithms that are efficient with respect to queries, gates and space, joint work with Dominic Berry and Sevag Gharibian.

After he was introduced, Richard sheepishly admitted, “The title isn’t really that efficient with its use of space.”
Normally the oracle for a quantum query algorithm defines the oracle query by flipping the phase of certain bits. In the continuous-time setting, we can get other phases. So, for example, a ”half-query” would give $latex Q |x rangle = i^{x_j} | x rangle$, since i is a square root of minus one. In this model, we only charge 1/2 of a query for this oracle call. More generally, we can have arbitrary fractional queries. Then we can take a limit and get to continuous time to find $latex expbigl(i(H_U + H_Q)tbigr)$ where $latex H_U$ is the driving (gate) Hamiltonian and $latex H_Q$ is a query Hamiltonian.
It is essential to be able to translate from the continuous-time model back to the discrete-time model for algorithmic applications. (cf. The work on NAND trees.) Is there a systematic way to do this translation? Yes, CGMSY-M `09 (improved by LMRSS `11) showed that the query complexity can be directly translated with the same number of queries. But these constructions are not gate efficient. Can we improve the gate complexity of the translation?
We have to be careful because the gate complexity will depend on the complexity of the driving Hamiltonian, so we have to carefully define a notion of approximately implementable Hamiltonian. If we have an epsilon-approximate implementation, and a driving Hamiltonian H, then the number of gates is at least $latex G ge log (|H|)/epsilon$, where the norm is the operator norm of the Hamiltonian (but modulo some details about the global phase.)
Main results: We can translate from the continuous-time setting to the discrete-time setting by using:

$latex O(T log T / log log T)$ queries
$latex O(T G log^2 TG)$ gates
$latex O(log^2 TG)$ qubits of ancilla space

Miklos Santha, Hidden Symmetry Subgroup Problems, joint work with Thomas Decker, Gábor Ivanyos and Pawel Wocjan

First let’s observe an interesting connection. In the dihedral group $latex D_{2p}$ for a prime p, the two-element subgroups generated by reflections coincide with the symmetries of the level sets of quadratic polynomials over $latex mathbb{F}_p$.
Can we more generally study subgroups which are hidden by symmetries? This generalizes and connects many problems in quantum algorithms, e.g. the hidden subgroup problem (HSP) over non-abelian groups, non-linear hidden structures and hidden polynomial problems among others, as the above example demonstrates.
Recall that the HSP is defined as follows. There is a function (for which you have an oracle) which is constant and distinct on the cosets of a subgroup of some group G. You want to obtain a generating set for the subgroup.
The hidden symmetry subgroup problem (HSSP): the input is a group G, a group action $latex circ$ which acts on a set M, a closed set of subgroups $latex mathcal{H}$, and there is an oracle function $latex f:M to S$, such that (we’re promised) for some subgroup $latex H in mathcal{H}$, $latex f(x) = f(y) leftrightarrow H circ x = H circ y$ for $latex x,y in M$. You want to output this (unique) H.

Rahul Jain and Ashwin Nayak:
A quantum information cost trade-off for the Augmented Index

Consider a twist (due to Yao ‘82) on the usual communication complexity problem. Alice has x, Bob has y, and they both want to compute f(x,y). But this time, they don’t want to leak (to the other party) more information than is already expressed by the answer, e.g. the millionaire problem.
Start with the usual example: equality testing. There is a O(log n) one-way protocol with 1/poly(n) error, and reveals only O(1) bits about one input.
Today’s talk is about:
Augmented index: Alice has $latex x_1, ldots, x_n$. Bob has $latex k, x_1,ldots, x_{k-1}, b$.
They want to know whether $latex b=x_k$.
(This has many connections to other works in theoretical computer science, not all of which are obviously communication-related. See paper for detail.)
Main result: For any quantum protocol which computes the augmented index with probability $latex 1-epsilon$ on the uniform distribution, we must have either: 1) Alice reveals $latex Omega(n/t)$ bits of info about x, or 2) Bob reveals $latex Omega(1/t)$ about k, where t is the number of messages. This is true even when restricted to 0-inputs.
There is also an earlier classical result by the same authors: Alice reveals $latex Omega(n)$ or Bob reveals $latex Omega(1)$. If there are only two messages, then the lower bound for Bob is improved to $latex Omega(log n)$ (which is optimal), even when restricted to 0-inputs.
At this point, Ashwin, apparently reading the audience’s mind, puts up a slide that is not quite as pertinent as Josh Cadney’s opening question, but is still what we are all thinking:
“Why Augmented Index? Why privacy w.r.t. 0-inputs?”
Answer: Suppose we care about a streaming algorithm, which for quantum is relevant because we might only have O(1) qubits for the foreseeable future. There are exponential space improvements in this model, but let’s just say they don’t look like the sort of problems that Cisco was dying to implement on their routers. Augmented Index, by contrast, is much more natural. One semi-related version is Dyck(2), which is determining whether a sequence of (,),[,] is properly bracketed (this is a special case of recognizing context-free languages). Here we observe a big separation between one and two passes over the input (if the second pass goes in reverse order), and the lower bound on the (classical) one-pass complexity is based on (classical) lower bounds for the augmented index problem.
Having motivated the question, Ashwin is left with “-2 minutes” to finish his talk. Talk about a cliffhanger! Now he’s guaranteed to have the proof accepted to QIP 2013 (although he did give away the punchline by stating the theorem at the start of his talk). Moreover, the chair apparently has a sign for -2 minutes left, since he didn’t say anything, he just held up a sign. I guess staying on time is not a strong point in our community. 🙂
Ashwin is now ruining his cliffhanger, giving an intuitive and cute overview of the proof! He claims that this part of the talk is “in reverse.”

Sevag GharibianHardness of approximation for quantum problems, joint work with Julia Kempe

Finding the ground state energy of a local Hamiltonian is QMA-complete, and this is harder than NP, because, um, there’s quantum in there too, and well, it seems harder? Sev wants to say something more concrete here. We’ve given up on solving local Hamiltonian exactly in general, because we’ve already given up on solving NP on a quantum computer (mostly). But surely there are good approximation algorithms for these things. Right? Well, today, we’ll talk about hardness of approximation, thus casting complexity-theoretic cold water on seemingly less ambitious goals.
All we know about approximating the local Hamiltonian problem:

  • PTAS on planar graphs
  • $latex 1/d^{k-1}$-approximation algorithm for dense graphs with k-local Hamiltonians.

This talk takes a step away from QMA, and considers instead the complexity class cq-$latex Sigma_2$, which is the set of problems that can be expresses as “there exists x, such that for all $latex |psirangle$, a poly-time verifier V accepts $latex (x, |psirangle)$.
Their main result is to show that the following problem is complete for cq-$latex Sigma_2$, and the hardness part holds even if we demand only approximate solutions.
The quantum succinct set cover problem: Given a set of 5-local Hamiltonians acting on n qubits, and a parameter $latex alpha>0$, and the promise that
$latex sum_{iin S} H_i succeq alpha I$,
find the smallest subset $latex S’subseteq S$ such that
$latex sum_{iin S’} H_i succeq alpha I$.
The diagonal case was shown to be hard to approximate by Chris Umans in 1999.
For the technical details, there are lots of nice tools, and you’ll just have to look at the paper (when it comes out…).

Jérémie Roland,Quantum rejection sampling, joint work with Maris Ozols and Martin Roetteler

Let’s first review classical rejection sampling, which is a tool that you can use to sample from arbitrary probability distributions. It has numerous applications: Metropolis sampling, Monte Carlo algorithms, optimization algorithms (e.g. simulated annealing) and many others. In the quantum case, we wish to replace probabilities by amplitudes.
Consider two probability distributions P and S. Suppose we can sample from P repeatedly, but we wish to sample from S. Define $latex Pr[{rm accept} k] = gamma s_k/p_k$ and continue to sample until you accept. Here we will choose the parameter $latex gamma$ in a way to try to minimize the expected amount of sampling from P that we need to do. The best way to do it is to choose $latex gamma = min_k p_k/s_k$. Then the expected number of samples from P to get a sample from S is $latex 1/gamma$.
Now for the quantum case. We are given access to a black box which prepares a state $latex |pi^xirangle = sum_k pi_k |xi_krangle |krangle$ where the $latex pi_k$ are known amplitudes. We want to prepare the state $latex |sigma^xirangle = sum_k sigma_k |xi_krangle |krangle$ in terms of some new amplitudes. What is the randomized query complexity of this?
Instead of computing a function, which is the normal thing that we use oracles for, we wish to generate a quantum state. There is an oracle, which is a unitary that hides the label $latex xi$ in a non-explicit way. The action of the oracle is $latex O_xi |0rangle = sum_k pi_k |xi_krangle |krangle$.
Let’s define quantum state preparations:
We have a set of quantum states $latex Psi = {psi_xi}$
set of oracles $latex O = { O_xi }$
Goal: generate $latex psi_xi$ given black box access to $latex O_xi$
What’s the minimum number of calls to the oracle to get the correct state (up to a coherent error with amplitude $latex sqrt{epsilon}$)?
We introduce a coherent coin.
$latex O_xi |0rangle to sum_k pi_k |xi_krangle |krangle (sqrt{ pi – alpha})|0rangle + alpha|1rangle)$
This rotated ancilla is like a classical coin, but now we have a superposition. If we measure the ancilla then we accept if we get one.
Using amplitude amplification, we can get a speedup over the naive accept probability.
We can also optimize over the rotation angle to get the optimum. This can be done efficiently since it’s an SDP. They can prove that this is an optimal algorithm. [photo 70]
Now for the applications. Linear systems of equations: the HHL algorithm basically just does phase estimation followed by quantum rejection sampling. [photo 71] The quantum Metropolis algorithm is a way to prepare a Gibbs state of H at inverse temperature beta.
Direct mapping of Metropolis MRRTT algorithm OK for diagonal Hamiltonians, but if Hamiltonian is not diagonal we want to avoid the work of diagonalizing it.
One of the reasons that the Q. Metropolis algorithm was difficult was that the “reject” moves required that you go back to a state that you just measured. You can avoid having to deal with this difficulty if you use quantum rejection sampling. One can amplify the accepted moves and therefore avoid having to revert moves at all!
Boolean hidden shift. f(x+s) = f(x) find s in Z_2^n. If the function is a delta function, then you can basically only do Grover. You can do bent functions (those with flat Fourier spectrum) with only 1 query [Roetteler 10]. These are the extreme cases, but what happens when we interpolate between them? We can use quantum rejection sampling to analyze this problem.
Other applications: Amplify QMA witnesses [MW05, NWZ09], prepare ground states of PEPS parent Hamiltonians on a quantum computer [STV11]. [photo 76]

Rolando Somma, Spectral Gap Amplification, joint work with Sergio Boixo

Preparation of eigenstates is a central problem and fast quantum methods for computing expectation values of observables leads to speedups for many problems. Let’s begin by considering adiabatic state transformations. The run time is governed by the spectral gap of the interpolating Hamiltonian. The generic cost C(T) of a quantum algorithm that prepares the eigenstate depends on the inverse power of the spectral gap.
given H with eigenstate psi and gap Delta, can we construct an H with same eigenstate psi but a larger gap? (without cheating by multiplying by some constant?) We want to consider that the Hamiltonian is a sum of terms which are, say, local. We have a black box which on input k, s evolves according to $latex e^{-i s H_k}$. How many times do we need to use this box? We require that the cost of evolving with H’ is the same.
They achieved a quadratic gap amplification for the following case: if H is frustration free, then the new gap is $latex Omega(sqrt{Delta/L})$ where L is the number of terms in the Hamiltonian. In particular, when the spectral gap is very small in terms of L this gives an improvement. It turns out this amplification is optimal.
Question: What prevents you from iterating amplification process?
Ans. The new Hamiltonian isn’t FF, so you can only do the amplification once.
S. Flammia: Optimality of results?
Ans. There may be better constructions with respect to the scaling in L.

Rajat Mittal, Quantum query complexity for state conversion, joint work with Troy Lee, Ben Reichardt, Robert Spalek and Mario Szegedy

We live in a quantum world, so why are we always trying to solve classical tasks, like computing f(x), for x specified by an oracle? How about trying to prepare $latex |psi(x)rangle$ given x specified by an oracle? Or even more generally, converting $latex |psi_1(x)rangle$ into $latex |psi_2(x)rangle$? To make things simple, let’s focus on creating $latex |psi(x)rangle$, although the results apply to more general state conversion problems as well. The difficulty of doing this is defined entirely by the Gram matrix $latex G_{x,y} = langle psi(x)|psi(y)rangle$.
Previous work on adversary bounds gave a tight characterization of quantum query complexity for boolean functions. The present work extends the result to general functions, and indeed to state conversion.
$latex gamma_2(G-J|Delta)$
Ok, what is this thing $latex gamma_2(M|Delta)$?
Without the $latex Delta$, we define $gamma_2(M)$ to be the minimum over factorizations $latex {u_x}$, $latex {v_y}$ (meaning that $latex M_{x,y} = langle u_x, v_yrangle$ of $latex max |u_x|,|v_y|$
w.r.t. $latex Delta$; it’s similar, but with $latex M_{x,y} = langle u_x, v_yrangle N_{x,y}$.
e.g. $latex gamma_2(M|J) = gamma_2(M)$ and $latex gamma_2(M|M)=1$.
This gives some nice corollaries, e.g. that function composition does what you’d expect to query complexity.

Fernando Brandao, Random quantum circuits are unitary polynomial designs, joint work with Aram Harrow and Michal Horodecki

Previously blogged here.
Questions:
Patrick Hayden: To fool a circuit takes more time than the circuit does. Can you introduce some kind of restriction to make it go in a more favorable direction?
Aram: We could try to fool quantum Turing machines, but I don’t think our techniques say much that’d be helpful there.
Renato: Could you replace a random circuit by a random Hamiltonian?
Ans. Interesting question. Hayden et al do something like that. More interesting is to…

BUSINESS MEETING

The headline stat: 42 papers were accepted out of 198 submitted, meaning a 21% acceptance rate. (Louis also said the “real” rate was 29%.)
There were 485 reviews, of which 104 are from 72 external reviewers.
There were 198 = 144 (early) + 54 (late) poster submissions.
Of the 42 talks, there were 4 plenary, 9 long, 27 regular and 2 merged.
The budget breakdown is: rental+technical 55k, food+drinks 90k, personnel 30k, student support 10k for a of total 185k.
There were 259 participants of which 113 students.
Thus conference fees were 105k and there was 85k from sponsors. This leaves a surplus of 5k, presumably to cover damages during the rump session.
For the locals, the conference booklet explains how to get to the rump session. You take the metro, and as Louis said, “you will visit a lot of stations.” Note that this post will go online after the rump session.
Also, where is QIP 2013???
BEIJING! (specifically, Tsinghua University)
Local organizers are: Andy Yao (general chair), Amy Wang (organizing chair), Giulio Chiribella, Luming Duan, Kihwan Kim, Jian Li, Yaoyun Shi, Shengyu Zhang.
There is a new CQI at Tsinghua. You can guess what it stands for. Note that few permutations of those three letters remain.
Tentative dates are: Jan 21-25 or Jan 28-Feb 1, 2013.
A truly open question is: where will QIP 2014 be?
Two tentative proposals on the table are IBM Yorktown Heights and Barcelona.
But volunteers are still welcome! If you want the experience of hosting QIP, send an email to Louis Salvail soon.
Possible locations include a science museum, a university campus and… La Pedrera? Seriously? (See picture at the top of the post.)
Then there was general discussion about QIP.
Suggestions include

  • not posting the long versions (at least without the authors confirming)
  • Renaming QIP Workshop -> QIP Conference.
  • Getting rid of the 3-page submissions? Here was the heated discussion. There always has to be a heated discussion about something.
  • Dec vs Jan? The audience seemed to overwhelmingly prefer January (among those who cared). And yet here they are, all here in December!