The NSF just announced that our own Scott Aaronson has been named a co-recipient of this year’s prestigious Alan T. Waterman award! The award is granted to outstanding researchers under the age of 35 across any field of science or engineering which is supported by the NSF.
Not only is this great news for Scott, but a rising tide lifts all boats: the entire field of quantum computing benefits when our talented researchers get recognition for their achievements.
Congratulations to The Optimizer on this richly deserved award.
Randomized Governance
What if instead of electing our representatives in government, we simply chose them at random?
A new Rasmussen poll asked 1,000 likely voters exactly this question. Turns out, 43% thought that a random choice of people from the phonebook would do a better job than the current legislators, a plurality. Of course, these people were themselves chosen randomly from a phonebook, so I’m not sure they are entirely unbiased. 🙂
But why stop at the legislators? Why not just write random legislation using context-free grammars? We already have software that can automatically write scientific papers, so it doesn’t seem like a stretch. I guess that a lot of this random legislation would be better than SOPA.
A Federal Mandate for Open Science
Witness the birth of the Federal Research Public Access Act:
“The Federal Research Public Access Act will encourage broader collaboration among scholars in the scientific community by permitting widespread dissemination of research findings. Promoting greater collaboration will inevitably lead to more innovative research outcomes and more effective solutions in the fields of biomedicine, energy, education, quantum information theory and health care.”
[Correction: it didn’t really mention quantum information theory—SF.]
You can read the full text of FRPAA here.
The bill states that any federal agency which budgets more than $100 million per year for funding external research must make that research available in a public online repository for free download now later than 6 months after the research has been published in a peer-reviewed journal.
This looks to me like a big step in the right direction for open science. Of course, it’s still just a bill, and needs to successfully navigate the Straights of the Republican-controlled House, through the Labyrinth of Committees and the Forest of Filibuster, and run the Gauntlet of Presidential Vetos. How can you help it survive this harrowing journey? Write your senators and your congresscritter today, and tell them that you support FRPAA and open science!
Hat tip to Robin Blume-Kohout.
Aram's rebuttal
Part one of Aram’s rebuttal is now up at Gödels Lost Letter. Go there and check it out!
The cost of knowledge
Tim Gowers has put up a new pledge website against Elsevier.
For many years, academics have protested against the business practices of Elsevier. If you would like to declare publicly that you will not support any Elsevier journal unless they radically change how they operate, then you can do so by filling in your details in the box below.
Why should we boycott Elsevier? We’ve blogged before about Elsevier and highlighted their support of SOPA. They’ve also supported and lobbied for PIPA and the Research Works Act. As Aram commented on Lance Fortnow’s blog, support for one or more of these is a very direct assertion that you oppose open research and the advancement of knowledge in favor of keeping it behind paywalls and protecting profits. That alone is reason enough, but if you want a few more reasons, go read Tim Gowers’ discussion of their heinous practice of “bundling” a few high-quality journals together with a bunch of low quality journals and forcing libraries to buy the whole package at exorbitant prices.
While you may disagree with choosing such a specific target as Elsevier when many of the problems are endemic to scientific publishing, this is as good a place as any to start, and it can serve as a wake up call to other publishers like Springer that also bundle or to other publishers that supported SOPA et al.
If you are interested in supporting the boycott, then we’ve helpfully compiled a list of every Elsevier journal in computer science, physics and mathematics to help you stick to your pledge. Fortunately in our field there are many strong alternatives, so we don’t have to put our academic careers at risk by publishing in inferior journals while adhering to the boycott.
Correcting Untruths
We here at the Quantum Pontiff value truth in all its forms: theorems, lemmas, statistical inference, and hard experimental data, to name just a few. So I feel compelled to highlight the following.
In his column on the New York Times website, Author S. Brisbane states,
I’m looking for reader input on whether and when New York Times news reporters should challenge “facts” that are asserted by newsmakers they write about. …
[An] example: on the campaign trail, Mitt Romney often says President Obama has made speeches “apologizing for America,” a phrase to which Paul Krugman objected…
As an Op-Ed columnist, Mr. Krugman clearly has the freedom to call out what he thinks is a lie. My question for readers is: should news reporters do the same?
What are we teaching journalism students that would lead them to ask this question in ernest? After double checking my calendar to make sure it wasn’t April 1st, I continued reading:
If [reporters should call out lies], then perhaps the next time Mr. Romney says the president has a habit of apologizing for his country, the reporter should insert a paragraph saying, more or less:
“The president has never used the word ‘apologize’ in a speech about U.S. policy or history. Any assertion that he has apologized for U.S. actions rests on a misleading interpretation of the president’s words.”
I’m not sure which is worse… that Mr. Brisbane feels he, a professional journalist, needs to ask his readers for their opinion on how to be a journalist, or that he doesn’t know the answer to this question which looks (to any scientist at least) to be completely obvious.
“Everyone is entitled to his own opinion, but not his own facts,” as a fellow once said. If you don’t know the answer to your question, Mr. Brisbane, then you are a stenographer, not a journalist, and you need to ask yourself why you would bother giving column inches in your newspaper to misinformation and distortions without bothering to correct them. Some things are true; you are not “biasing” anything by printing true statements.
More cracks in the theory of relativity?
When the OPERA collaboration announced their result that they had observed neutrinos traveling faster than the speed of light, it rocked the entire physics community. However, despite the high statistical certainty of the claim, any sober physicist knew that the possibility of systematic errors means that we must patiently wait for additional independent experiments. Einstein’s theory hasn’t been overthrown yet!
Or has it?
Enter the good folks at Conservapedia, a “conservative, family-friendly Wiki encyclopedia.” They have helpfully compiled a list of 39 counterexamples to relativity, and noted that “any one of them shows that the theory of relativity is incorrect.” In fact, relativity “is heavily promoted by liberals who like its encouragement of relativism and its tendency to mislead people in how they view the world.” That is already damning evidence, but you really must look at the list.
A few of them actually have some partial grounding in reality. For example,
6. Spiral galaxies confound relativity, and unseen “dark matter” has been invented to try to retrofit observations to the theory.
Most of them, however, are either factually challenged or irrelevant:
14. The action-at-a-distance by Jesus, described in John 4:46-54, Matthew 15:28, and Matthew 27:51.
18. The inability of the theory of relativity to lead to other insights, contrary to every extant verified theory of physics.
Why are these scientists at OPERA wasting tax payer’s money on their silly experiments when they can just check this list? And to Bill O’Reilly and Rush Limbaugh: please post your predictions for the LHC to the arXiv soon, before all the data gets analyzed.
Update from Aram: Ironically, conservativepedians don’t like Einstein’s relativity because of its occasional use as a rhetorical flourish in support of cultural relativism. (I agree that using it in this manner constitutes bad writing, and a terribly mixed metaphor.) But by denouncing relativity as a liberal conspiracy along with evolution and global warming, they’ve demonstrated their own form of intellectual relativism: the idea that there is no objective truth, but that we are all entitled to believe whatever facts about the world we prefer. At the risk of improving the credibility of Conservapedia, I made this point on their talk page. Let’s see how long it lasts.
Now that's what I call self correcting
Apparently this is the year for breakthroughs in self-correcting computer hardware. After hearing about Jeongwan Haah’s new self-correcting topological quantum memory at QIP, I just learned, via BBC news, about a new type of (classical) self correcting circuit: one which heals itself when one of the wires cracks! The full paper can be found here, and it is mostly quite readable. The basic idea is to start with a standard classical wire made of (for example) gold. The researchers sprinkled the wire with tiny capsules filled with a metal alloy (Ga-In) which is liquid at room temperature and has high conductivity. Then they bent the circuit board until it cracked, breaking the wire, and hence the circuit. Within milliseconds, the capsules also broke, the cracks filled with the liquid metal, and conductivity was restored. Self correcting, indeed!
One thing I didn’t understand is how the liquid metal stays in the cracks. I guess that at the scale they are working at, the surface tension alone is sufficient to keep the liquid metal in place?
QIP 2012 Day 5
The quantum pontiff brains have reached saturation.
Eric Chitambar, Wei Cui and Hoi-Kwong Lo:
Increasing Entanglement by Separable Operations and New Monotones for W-type Entanglement
These results demonstrate a large quantitative gap between LOCC and SEP for a particular task called random EPR distillation. Therefore, SEP may not always be a good approximation for LOCC. They also demonstrate entanglement monotones that can increase under SEP, the first known examples with analytic functions. They also show that LOCC is not a closed set of operations, so optimal LOCC protocols may not exist.
Recall how LOCC works: Alice and Bob share a bipartite pure state 
So now we know that SEP and LOCC are not equal, but how non-equal are they? That is, can we quantify the gap between the two classes? There is some previous work, such as Bennett et al., who showed that the mutual information for state discrimination had a gap of at least 
SEP is precisely the class of operations that cannot create entanglement out of nothing, but if we seed things with a little bit of entanglement, can we use SEP to increase the entanglement? We need to define some LOCC monotone to make this a meaning statement.
Surprisingly, yes! There are entanglement transforms that work in SEP but not LOCC, and therefore entanglement monotones (but artificial ones) that can increase under SEP but not LOCC. To give some intuition, though, here is a non-artificial task.
Random-party distillation of W-class states:
An N-partite W-class state looks (up to local unitary rotation) like
It’s a good class of states to study because they are only parameterized by N real numbers (as opposed to 2N), it is easy to characterize how the states transform under local measurements, and it is closed under SLOCC. See this paper by Kintas and Turgut for a review of the properties of W-class states.
Here is a nice example, due to Fortescue and Lo. Start with a tripartite W state, and have each party perform the measurement 
This can be generalized by using local filtering to first (probabilistically) map a W-class state to one with 
The fact that they establish an entanglement monotone means they get an awesome corollary. There is a parameter 
LOCC is not closed!
Here is a great open question (not in the talk): Find a similar monotone that describes data hiding, for example to improve the analysis of these states.
For the multipartite setting, there are a few more ideas. There is a single-copy “combing transformation” (analogous to the one of Yang & Eisert), which transforms all the entanglement to bipartite entanglement shared with Alice. Again SEP is better than LOCC, in ways that can be quantified.
Some open problems:
- What about the case of
W-states? They have some partial results, but it still remains open.
- Can the gap between SEP and LOCC be increased arbitrarily?
- Can one apply these ideas to other entanglement classes?
- Do there exist similar phenomena in bipartite systems?
- How much entanglement is required to implement SEP operations?
Rodrigo Gallego, Lars Erik Würflinger, Antonio Acín and Miguel Navascués:
Quantum correlations require multipartite information principles
(merged with)
An operational framework for nonlocality
Normally, we define “3-partite entanglement” to mean states that are not separable with respect to any bipartition; equivalently, they cannot be created by LOCC even if two parties get together. But this definition can be dangerous when we are considering nonlocality, as we will see below.
Nonlocality is a resource for device-independent information protocols. Define a local joint probability distribution to be one which satisfies 
Nonlocality is often described in terms of boxes that mimic measurements on entangled states. But entanglement can also be manipulated, e.g. by LOCC. What is the analogue for boxes? Are their variants of entanglement swapping, distillation, dilution, etc? In most cases, when we make the boxes stronger, the dynamics get weaker, often becoming trivial.
They define a new class or operations called WPICC, which stands for something about rewirings and pre- and post-processing (note that non-local boxes can be rewired in ways that depend on their outputs, so their causal structure can be tricky). WPICC are the operations which map local joint probability distributions to local joint probability distributions, and shouldn’t be able to create nonlocal correlations; indeed, we can use them to define nonlocal correlations, just as entanglement is defined as the set of states that can’t be created by LOCC.
However, with these operations, operations on two parties can create tripartite nonlocality, so this approach to defining nonlocality doesn’t work.
Instead, define a box to be tripartite nonlocal if it doesn’t have a TOBL (time-ordered bilocal) structure, meaning a Markov-like condition that’s described in the paper.
Moral of the story? If you want a sensible definition of tripartite correlations, then beware of operational definitions analogous to LOCC, and focus on mathematical ones, analogous to SEP.
Martin Schwarz, Kristan Temme, Frank Verstraete, Toby Cubitt and David Perez-Garcia:
Preparing projected entangled pair states on a quantum computer
There are lots of families of states which seem useful for giving short classical descriptions of highly entangled quantum states. For example, matrix product states are provably useful for describing the ground states of gapped one-dimensional quantum systems. More generally there are other classes of tensor network states, but their utility is less well understood. A prominent family of states for trying to describe ground states of 2d quantum systems is projected entangled pair states (PEPS). These are just tensor network states with a 2d grid topology. The intuition is that the structure of correlations in the PEPS should mimic the correlation in the ground state of a gapped system in 2d, so they might be a good ansatz class for variational methods.
If you could prepare an arbitrary PEPS, what might you be able to do with that? Schuch et al. proved that an oracle that could prepare an arbitrary PEPS would allow you to solve a PP complete problem. We really can’t hope to do this efficiently, so it begs the question: what class of PEPS can we prepare in BQP? That’s the central question that this talk addresses.
We need a few technical notions from the theory of PEPS. If we satisfy a technical condition called injectivity, then we can define (via a natural construction) a Hamiltonian called the parent Hamiltonian for which the frustration-free ground state is uniquely given by the PEPS. This injectivity condition is actually generic, and many natural families of states satisfy it, so intuitively it seems to be a reasonable restriction. (It should be said, however, that there are also many natural states which don’t satisfy injectivity, for example GHZ states.)
The algorithm is to start from a collection of entangled pairs and gradually “grow” a PEPS by growing the parent Hamiltonian term-by-term. If we add a term to the Hamiltonian, then we can try to project back to the ground space. This will be probabilistic and will require some work to get right. Then we can add a new term, etc. The final state is guaranteed to be the PEPS by the uniqueness of the ground state of an injective parent Hamiltonian.
In order to get the projection onto the new ground state after adding a new term to the Hamiltonian, we can use phase estimation. If you get the right measurement outcome (you successfully project onto the zero-energy ground space), then great! Just keep going. But if not, then you can undo the measurement with the QMA amplification protocol of Marriott and Watrous.
The bound on the run time is governed by a polynomial in the condition number of the PEPS projectors and the spectral gap of the sequence of parent Hamiltonians, as well as the number of vertices and edges in the PEPS graph.
This can also be generalized to PEPS which are so-called G-injective. This condition allows the method to be generalized to PEPS which have topological order, where the PEPS parent Hamiltonian has a degenerate ground space.
Good question by Rolando Somma: What happens if the ground state is stoquastic? Can you get any improvements?
Esther Hänggi and Marco Tomamichel:
The Link between Uncertainty Relations and Non-Locality
The main result: Nonlocality, which means achieving Bell value 
implies an uncertainty relation, namely, the incompatible bases used in the Bell experiment have overlap at most 
This is a sort of converse to a result of Oppenheim and Wehner.
This has some practical implications: the maximum basis overlap is important for things like QKD and the security of noisy storage, and this result implies that it can be tested robustly by observing a Bell inequality violation.
The kind of uncertainty relation we are interested in is of the form 
Actually, we need a variant to handle the case that both bases contain a “failure” outcome. This work replaces the maximum overlap 
This parameter 
Salman Beigi and Amin Gohari:
Information Causality is a Special Point in the Dual of the Gray-Wyner Region
What is information causality? Essentially the idea that the bound on random access coding should apply to general physical theories in a nonlocal setting. More precisely, Alice has independent bits 
![b in [n]](https://s0.wp.com/latex.php?latex=b+in+%5Bn%5D&bg=ffffff&fg=000&s=0&c=20201002)
If you look at the details, the key ingredients are the consistency of mutual information (that is, it accurately represents correlations), data processing and the chain rule. These all apply to quantum states as well (hence the quantum random access bound).
Overview of the talk
- connection to Gray-Wyner problem
- generalizing information causality
- connecting to communication complexity.
The Gray-Wyner region is defined as the set of rates 
Thm: For any physical theory satisfying the above “key ingredients” plus AMI (accessibility of mutual information, to be defined later), the point
AMI basically means that the mutual information satisfies something like HSW. There is an issue here, which the authors are looking into, with whether the Holevo information or the accessible information is the right quantity to use.
This theorem means that the information causality argument can be generalized: using the same assumptions, we also obtain all of the inequalities that are known to apply to the Gray-Wyner region. Hence the reference in the title to the dual of the Gray-Wyner region; the dual consists of all linear inequalities that are satisfied by the entire Gray-Wyner region.
This improves our understanding of these bounds. It also gives some new lower bounds on the communication cost of simulating nonlocal correlations.
Marcus P. Da Silva, Steven T. Flammia, Olivier Landon-Cardinal, Yi-Kai Liu and David Poulin:
Practical characterization of quantum devices without tomography
Current experimental efforts at creating highly entangled quantum states of many-body systems and implementing unitary quantum gates quickly run into serious problems when they try to scale up their efforts. The dimensionality of the Hilbert space is a serious curse if your goal is to characterize your device using full tomography. For example, the 8-qubit experiment that was done by Häffner et al. in 2005 took a tremendous number of measurements and many many hours of classical post-processing.
But what if you could avoid doing tomography and still get a good characterization of your device? Perhaps you are only interested in one number, say, the fidelity. Can you directly compute the fidelity without going through tomography?
Yes! And you can do it much more efficiently if you are trying to produce a pure quantum state or a unitary quantum gate.
We’ll focus on the case where the target state is a pure state for simplicity. But everything carries over directly to the case of unitary quantum gates with only minor modifications.
The fidelity between your target state 
If you expand the expression for F in everybody’s favorite basis, the Pauli basis, then you get
There are a couple of caveats. Sampling from the relevance distribution can in general be a hard problem for your classical computer (though you only have to sample a constant number of times). And the number of repeated measurements that you need to estimate the expectation value might have to scale with the dimension of the Hilbert space.
But there is some good news too. We get a lower bound on tomography which is 
Robin Blume-Kohout:
Paranoid tomography: Confidence regions for quantum hardware
(merged with)
Matthias Christandl and Renato Renner:
Reliable Quantum State Tomography
We consider the setting of a source of quantum states and some measurements, followed by the reconstruction of the quantum state or process. How can we get useful and reliable error bars on the reconstruction?
One problem that you might have when doing a naive linear inversion of a state estimate is that you could have negative eigenvalues on the estimate, which is non-physical. How might you deal with these? One way to do that is to use maximum likelihood estimation (MLE). How might you get an error bar? You could use “bootstrapping”, which is to resample data from the initial estimate to try to estimate the variance. But this can be unreliable: you can even construct counterexamples where it fails miserably! Is there a better way? You could try Bayesian update, where you begin with a prior on state space and then computer a posterior and an error bar. Now everything that you report will depend on the prior, which might be undesirable in e.g. a cryptographic setting. So we need a reliable way to report error bars.
There are some existing methods for producing error bars (e.g. compressed sensing, MPS tomography, and others), but here we are interested in systematically finding the optimal confidence region for an estimate, one that is adapted to the data itself. It is beyond the scope of this work currently to consider also the notion of efficiency; this is an open question.
The main result: They derive region estimators such that the true state is contained in the region with high probability (over the data), and where the size of the region is, in a certain sense, minimal.
Question: how do these relate to the classical statistical notions of confidence region and Baysian credible interval? Tell us in the comments!
The authors use two different techniques to achieve these results. RBK’s results use a likelihood ratio function in the setting of iid measurements. The region is the set of states for which the likelihood function is larger than some threshold
Here Matthias wants to give a new proof that was custom-made for QIP! It uses likelihood ratio regions for general measurements in a new way that all three authors came up with together. We can credit QIP with the result because the program committee forced Matthias+Renato to merge their talk with Robin Blume-Kohout’s. But the two papers had different assumptions, different techniques and different results! After discussing how to combine their proofs for pedagogical reasons (there wasn’t time to present both, and it also wouldn’t be so illuminating), they realized that they could use Matthias + Renato’s assumptions (which are more general) and Robin’s method (which is simpler) to get a result that is (more or less) stronger than either previous result.
Sandu Popescu:
The smallest possible thermal machines and the foundations of thermodynamics
Are there quantum effects in biology?
Biological systems are open, driven systems far from equilibrium.
Sandu: “In fact, I hope it is a long time before I myself reach equilibrium.”
This talk is somewhat classical, but it does talk about the physics of information, at small scales.
He talks about very small refrigerators/heat engines. It turns out there is no (necessary) tradeoff between size and efficiency; one can get Carnot efficiency with a three-level (qutrit) refrigerator, which is simultaneously optimal for both size and efficiency.
It was a great talk, but your humble bloggers had mostly reached their ground state by this point in the conference… see the photo at the top of the post.
QIP 2012 Day 3
PSPACE is a black hole gobbling up the other complexity classes.
And you thought the LHC was dangerous!
Troy Lee and Jérémie Roland:
A strong direct product theorem for quantum query complexity
Suppose you want to solve k independent instances of a problem with k-fold as many resources. For example, say you want to juggle 4 balls with two hands vs 2 balls with one hand.
A Strong Direct Product Theorem (SDPT) says (roughly) the following:
If we require r resources to solve one instance of a problem with success probability p, then using fewer than kr resources to solve k instances cannot succeed with probability greater than pk.
Intuitively, it ought to hold in many situations, but has been proven to hold only in a few. Some applications of SDPT:
- Making a hard function really hard, e.g. Yao’s XOR lemma
- Amplify soundness of a protocol, e.g. Raz
Here they study Quantum Query Complexity, which uses a black box oracle that can be queried in superposition, as a proxy for quantum time complexity. It behaves so well that it scarcely deserves to be called a computational model.
The big picture is that they use adversary methods and the state generation formalism due to Ambainis. The method defines a type of potential function and then bounds the rate of change from one query to the next. In the additive setting, they bound the difference, and in the multiplicative setting, they bound the ratio. The state generation method has the advantage that it allows the separation of lower bounds into two parts: the bound on the zero-error state generation and the minimization of this bound over the valid final Gram matrices of a successful protocol.
It is known that the multiplicative adversary method characterizes bounded-error quantum query complexity since the multiplicative adversary is at least as large as the additive one. One of the achievements of this paper is that they show that the multiplicative adversary method still works when the convergence ratio is strictly bounded away from one. This immediately implies a SDPT by the results of Spalek `08, but they reprove the SDPT from scratch so that they can get a better optimization of the parameters.
Conclusion and open problems: For Boolean functions, they show an XOR lemma. Does SDPT hold for all state generation problems? Is the multiplicative adversary method also tight in the case of large error?
André Chailloux and Or Sattath:
The Complexity of the Separable Hamiltonian Problem
First recall that QMA is the quantum analog of NP: it’s the set of problems which can be verified efficiently on a quantum computer when given a quantum proof (i.e. a quantum state for a witness). For QMA wth 2 provers, denoted QMA(2), there are two unentangled states which are given as proofs. It’s similar to interrogation of suspects: Author can play the two Merlins against each other and it is probably a much stronger class. (Each Merlin still sends poly(n) qubits, so QMA(2) is at least as strong as QMA, but is probably stronger.) Pure n-representability is known to be in QMA(2) but not known to be in QMA. It’s known that QMA(k) = QMA(2) for all k>2. We know only that QMA(2) 
The main result of this paper is to find a complete problem for QMA(2). The separable local Hamiltonian problem is actually in QMA, but the separable sparse Hamiltonian problem is QMA(2) complete.
The problem: given a Hamiltonian 
Separable Local Hamiltonian: Given a local Hamiltonian H find a separable (say across an n by n qubit cut) 
This sure doesn’t look like it’s in QMA!
If the prover sends
Instead, the prover sends
Separable Sparse Hamiltonian: A totally different story! Now it’s QMA(2) complete. (The first known such problem.) Immediately we see that the qubit structure doesn’t exist, so we can’t rely on the strategy of looking at marginals. Clearly the problem is in QMA(2). To show completeness, we adapt Kitaev’s Hamiltonian for encoding a circuit (his so-called clock construction.) One challenge is that if the QMA(2) verifier makes an entangled measurement, then the history state will be entangled, which is not of the form we want. We want to simulate a computation in which the input is entangled, but we don’t care about the later steps; however, we are given the ability to minimize the energy of the sparse Hamiltonian for separable states, period.
The trick is that 1001.0017 shows that QMA(2) = QMA(2)-SEP, which is defined to be the class where the verifier is restricted to making separable (i.e. non-entangling measurements, at least for the yes outcome). This measurement requires a controlled-SWAP on the two proofs, which interestingly, is sparse, but not local. You might think you can build this out of a bunch of small controlled-SWAPs, but this would produce entanglement at intermediate steps. SWAP has a complicated relationship with entanglement. It doesn’t entangle product states, but only if it’s applied to the entire state; applying it to subsystems can create entanglement.
Many of the same open questions remain, about the status of QMA vs QMA(2) (although there is evidence from the case of log-size proofs to suggest that they are different), and about whether pure N-representability is also QMA(2) complete.
Yaoyun Shi and Xiaodi Wu:
Epsilon-net method for optimizations over separable states
The QMA(2) session continues! Once upon a time, I (Aram) thought QMA(2) was the kind of thing that complexity theorists make up to have more things to talk about, but I’ve since made a total U-turn. The problem, especially it’s log-size-witness variant, is equivalent to a ridiculously large number of problems, like separability testing, mean-field Hamiltonians, computing minimum output Rényi entropies of channels, finding the largest singular value of tensors, estimating the 
This talk changes this, with a pair of elementary approximation algorithms, one of which matches the performance of a weaker variant of 1010.1750 (details below).
To understand the basic problem, we don’t need to think about provers or circuits. The problem is as follows: Given a Hermitian matrix H on 
It is known that performing this optimization up to 1/poly(d) accuracy is NP-hard. (This result is originally due to Gurvits, although that’s not so widely known, since most people only noticed the part of his paper which talks about the hardness of testing membership in 
This talk gives two algorithms for approximating OptSep.
One works well when H is nearly product; in particular, when H can be decomposed as 
The second algorithm does eigenspace enumeration directly on H, and achieves additive error 
Abel Molina and John Watrous:
Hedging bets with correlated quantum strategies
Alice and Bob are at it again, playing a nonlocal game. Here is the framework: Alice prepares a question and sends it to Bob, Bob responds by sending an answer to Alice. Based on Bob’s answer, as well as whatever memory she has of her own question, Alice decides whether Bob has passed or failed a test.
Alice’s actions are specified by a density operator and a two outcome POVM. We assume that Bob knows a complete description of Alice. Then the games that they consider here can be formulated as a semidefinite program to determine Bob’s optimal success probability for passing the test.
Let’s consider parallel repetition: Alice performs two tests independently, but Bob can correlate his strategy in an arbitrary way. Suppose that Bob’s optimal probability to pass a single instantiation of a given test is p, and Alice independently runs the test twice. There are several natural questions: What is the optimal probability for Bob to pass both or at least one test? To pass k out of n independent tests? If Bob uses an independent strategy, you can just calculate the success probability of that. Can he do better by correlating his strategies?
If Alice’s test is classical, then Bob gains no advantage. In the quantum setting, Bob’s optimal probability to pass both tests is again p2, so he gains no advantage by correlating the tests. Both facts can be proven using SDP duality.
It would be natural to conjecture that it is also optimal for Bob to play independently if he only cares about passing at least one test. But this turns out to be false. They have a simple counterexample to this natural conjecture, and they compute Bob’s optimal strategy for a simple nonlocal game. The strategy is a form of hedging.
This work is in a different setting than other results with non-classical correlations of measurement outcomes. It might give insight into possible attacks in cryptography, where breaking the system only once is all you need: you don’t try independent attacks, instead you entangle a joint attack! It also gives reduced errors in quantum interactive proof protocols. So far, they have proved some partial results along these lines.
Comment by Richard Cleve: There is a classical strategy for hedging in the CHSH game which can perfectly win 1 out of 2 parallel games.
Jop Briet and Thomas Vidick:
Explicit lower and upper bounds on the entangled value of multiplayer XOR games
Bell’s theorem says that the set of correlations ![P[ab|xy]](https://s0.wp.com/latex.php?latex=P%5Bab%7Cxy%5D&bg=ffffff&fg=000&s=0&c=20201002)
![P[aoplus b | xy]](https://s0.wp.com/latex.php?latex=P%5Baoplus+b+%7C+xy%5D&bg=ffffff&fg=000&s=0&c=20201002)
For bipartite entanglement, we understand the situation pretty well now, but what about multipartite? (Another motivation is that quantifying multipartite entanglement is tough because it’s not clear what the goals are: this gives a nice clear way of keeping score.)
For a desired bias ratio R (meaning the entangled value is R times the unentangled value).
upper bound ( game)
| lower bound (Best possible) | |
| min questions | 
|  .
|
| min local dimensions | 
| |
Here’s the outline of the proof.
- For any matrix (of appropriate size) we construct a 3-player XOR game.
- Relate R to spectral properties of matrix.
- Existence of a good matrix that gives a large separation
And the details.
1. Given R, choose n such that 
Give each player n qubits.
The game is to choose Paulis P,Q,R with probability 
2. The entangled bias is at least the largest eigenvalue of 
The classical bias is the 2-2-2 norm, = 
3. Choose
Some open questions: They leave open a gap of size R2 in the number of questions needed for an R-sized bias ratio. It would be nice to get a tight analysis. Another open question is to derandomize their construction.
Gus Gutoski and Xiaodi Wu:
Parallel approximation of min-max problems
with applications to classical and quantum zero-sum games
Everyone knows that QIP=PSPACE. But did you also know that SQG=QRG(2)=PSPACE? (Short quantum games, and two-turn quantum refereed games, of course.) All of these follow from using the multiplicative weights update method to solve large SDPs in parallel. (Here is a review of the multiplicative weights update method that doesn’t discuss quantum applications, and here is a review that does).
This work concerns 2-turn quantum refereed games. Some motivation comes from complexity theory. We can consider interactive proof systems with two competing provers, one trying to prove Yes and the other trying to prove No.
The key result is that SQG is contained in PSPACE thus unifying and simplifying previous results about various games and interactive proofs being equivalent to PSPACE.
Additionally, they showed that public coin RG is not equal to RG unless PSPACE = EXP. Thus, the case of two competing provers is different from the case of a single untrusted prover (the usual IP situation) in which the messages to the prover can be replaced by public coins.
The key technical result is a way to parallelize an SDP related to whether certain quantum states exist. SDPs in general cannot be parallelized unless NC=P, but this result is possible because it deals with normalized quantum states going through trace-preserving quantum channels, and so the multiplicative weights update method (MWUM) can give a good approximation. Indeed MWUM has previously been used to quickly find solutions to classical zero-sum games (and convex programs in general), so it is natural to examine it for quantum zero-sum games. And even though there may be many rounds of interactions, these can be modeled by a series of linear and semidefinite constraints, applied to the density matrices appearing at various intermediate steps. This “transcript representation” was originally invented by Kitaev (whose ghostly presence looms large over this entire conference) in his work on coin flipping.
They also discussed penalization and rounding theorems and space efficiency.
The best part was a nice artistic depiction of PSPACE as a black hole gobbling up the other complexity classes, as shown at the top of the page!