9:009:50 
PLENARY
[48] Mohammad Bavarian, Thomas Vidick and Henry Yuen. Anchoring games for parallel repetition. (Slides)
Two major open problems regarding the parallel repetition of multiplayer games are whether an analogue of Raz's parallelrepetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on these problems: we introduce a class of games we call "anchored", and then prove exponentialdecay parallel repetition theorems for anchored games in the multiplayer and entangled player settings. We then introduce a simple transformation on games called "anchoring", inspired in part by the FeigeKilian transformation [SICOMP '00], and show that this transformation turns any (multiplayer) game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness amplification technique for general games with multiple players or with quantum players. Our anchoring transformation allows us to circumvent the need to employ the correlated sampling technique, and thus provide a way to avoid the primary obstruction to proving hardness amplification results for general games beyond the classical twoplayer setting.
http://arxiv.org/abs/1509.07466




PARALLEL SESSION A 


10:0010:35 
[61] Mark Braverman, Ankit Garg, Young Kun Ko, Jieming Mao and Dave Touchette. Nearoptimal bounds on boundedround quantum communication complexity of disjointness. (Slides)
We prove a near optimal roundcommunication tradeoff for the twoparty quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of tilde{Omega}(n/r + r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r^2 + r) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2^{O(QIC(f))}, where QIC(f) is the priorfree quantum information complexity of f (with error 1/3).
http://eccc.hpi web.de/report/2015/081/



10:3511:00 
BREAK 


11:0011:35 
[33] David Sutter, Volkher Scholz, Andreas Winter and Renato Renner. Approximate degradable quantum channels. (Slides)
Degradable quantum channels are an important class of completely positive tracepreserving maps. Among other properties, they offer a singleletter formula for the quantum and the private classical capacity and are characterized by the fact that the complementary channel can be obtained from the channel by applying a degrading map. In this work we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite $\varepsilon \geq 0$. That is, there exists a degrading map which upon composition with the channel is $\varepsilon$ close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such $\varepsilon$ can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication.
http://arxiv.org/abs/1412.0980



11:4012:15 
[14] Andris Ambainis, Aleksandrs Belovs, Oded Regev and Ronald de Wolf. Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing. (Slides)
In the kjunta testing problem, a tester has to efficiently decide whether a given function f:{0,1}^n → {0,1} is a kjunta (i.e., depends on at most k of its input bits) or is εfar from any kjunta. Our main result is a quantum algorithm for this problem with query complexity O(sqrt{k/ε}) and time complexity O(n*sqrt{k/ε}). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic (4th power) improvement over the query complexity of the best classical algorithm. (The 4th power quantum advantage is a bit unusual  most of quantum algorithms are either exponentially better than classical or at most quadratically better.) To show that our algorithm can be implemented timeefficiently, we give a nearlinear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the SchurWeyl transform. We also prove a lower bound of O(k^{1/3}) queries for junta testing (for constant ε).
http://arxiv.org/abs/1507.03126




PARALLEL SESSION B 


10:0010:35 
[160] Anna Komar, Olivier Landon Cardinal and Kristan Temme. An Energy Barrier is Necessary for the Thermal Stability of Stabilizer Quantum Memories. (Slides)
We prove a lower bound to the spectral gap of the Davies generator for general N  qubit commuting Pauli Hamiltonians and for quantum doubles based on an Abelian group. We derive rigorous thermalization time bounds, also called mixing time bounds, for the Davies generators of these Hamiltonians. Davies generators are given in the form of a Lindblad equation and are known to converge to the Gibbs distribution of the particular Hamiltonian for which they are derived. The bound on the spectral gap essentially depends on a single number E referred to as the generalized energy barrier. When any local defect can be grown into a logical operator and in turn any product operator can be decomposed into a product of the clusters of such incomplete logical operators, then E corresponds to the largest energy barrier of the canonical logical operators. The main conclusion that can be drawn from our result is, that the presence of an energy barrier for the logical operators is in fact, although not sufficient, a necessary condition for a thermally stable quantum memory when we assume the full Davies dynamics as noise model. This rules out the possibility of entropic protection for this broad group of models.
http://arxiv.org/abs/1412.2858 http://arxiv.org/abs/1601.01324



10:3511:00 
BREAK 


11:0011:35 
[174] Vadym Kliuchnikov, Alex Bocharov, Martin Roetteler and Jon Yard. A framework for qubit unitary synthesis. (Slides)
We present an algorithm for efficient approximation of unitaries using gate sets based on totally definite quaternion algebras. It approximates unitaries within precision ε using circuits of length O(log(1/ε)) which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously known algorithms for Clifford+T [arXiv:1212.6253], Vbasis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552] and runs on average in time polynomial in log(1/ε) (conditional on a numbertheoretic conjecture). Our algorithm is the first algorithm with described properties that works for a wide range of gate sets.
http://arxiv.org/abs/1504.04350 http://arxiv.org/abs/1510.03888



11:4012:15 
[30] Michael Bremner, Ashley Montanaro and Daniel Shepherd. Averagecase complexity versus approximate simulation of commuting quantum computations. (Slides)
We use the class of commuting quantum computations known as IQP (Instantaneous Quantum Polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible averagecase hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random lowdegree polynomials. We observe that both conjectures can be shown to be valid in the setting of worstcase complexity. We arrive at these conjectures by deriving spinbased generalisations of the Boson Sampling problem that avoid the socalled permanent anticoncentration conjecture.
http://arxiv.org/abs/1504.07999



12:1513:40 
LUNCH 


13:4014:30 
PLENARY [186] Lior Eldar and Aram Harrow. Local Hamiltonians with no lowenergy trivial states. (Slides) 



PARALLEL SESSION A 


14:3515:10 
[34] Aleksander Kubica, Beni Yoshida and Fernando Pastawski. Unfolding the color code
The topological color code and the toric code are two leading candidates for realizing faulttolerant quantum computation. Here we show that the color code on a ddimensional closed manifold is equivalent to multiple decoupled copies of the ddimensional toric code up to local unitary transformations and adding or removing ancilla qubits. Our result not only generalizes the proven equivalence for d=2, but also provides an explicit recipe of how to decouple independent components of the color code, highlighting the importance of colorability in the construction of the code. Moreover, for the ddimensional color code with d+1 boundaries of d+1 distinct colors, we find that the code is equivalent to multiple copies of the ddimensional toric code which are attached along a (d1)dimensional boundary. In particular, for d=2, we show that the (triangular) color code with boundaries is equivalent to the (folded) toric code with boundaries. We also find that the ddimensional toric code admits logical nonPauli gates from the dth level of the Clifford hierarchy, and thus saturates the bound by Bravyi and Koenig. In particular, we show that the dqubit controlZ logical gate can be faulttolerantly implemented on the stack of d copies of the toric code by a local unitary transformation.
http://arxiv.org/abs/1503.02065



15:1015:35 
BREAK 


15:3516:10 
[89] Fernando Brandao and Aram Harrow. Estimating operator norms using covering nets with applications to quantum information theory. (Slides)
We present several polynomial and quasipolynomialtime approximation schemes for a large class of generalized operator norms. Special cases include the 2> q norm of matrices for q>2, the support function of the set of separable quantum states, finding the least noisy output of entanglement breaking quantum channels, and approximating the injective tensor norm for a map between two Banach spaces whose factorization norm through ell_1^n is bounded. These reproduce and in some cases improve upon the performance of previous algorithms by BrandaoChristandlYard and followup work, which were based on the SumofSquares hierarchy and whose analysis used techniques from quantum information such as the monogamy principle of entanglement. Our algorithms, by contrast, are based on brute force enumeration over carefully chosen covering nets. These have the advantage of using less memory, having much simpler proofs and giving new geometric insights into the problem. Netbased algorithms for similar problems were also presented by ShiWu and BarakKelnerSteurer, but in each case with a runtime that is exponential in the rank of some matrix. We achieve polynomial or quasipolynomial runtimes by using the much smaller nets that exist in ell_1 spaces. This principle has been used in learning theory, where it is known as Maurey's empirical method.
http://arxiv.org/abs/1509.05065



16:1516:50 
[9] Mario Berta, Joseph M. Renes, Marco Tomamichel, Mark Wilde and Andreas Winter. Strong Converse and Finite Resource Tradeoffs for Quantum Channels. (Slides)




PARALLEL SESSION B 


14:3515:10 
[135] Rotem ArnonFriedman, Christopher Portmann and Volkher Scholz. Quantumproof multisource randomness extractors in the Markov model
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multisource extractors one can easily see that high conditional minentropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multisource extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multisource extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown.
http://arxiv.org/abs/1510.06743



15:1015:35 
BREAK 


15:3516:10 
[113] Ning Bao, Sepehr Nezami, Hirosi Ooguri, Bogdan Stoica, James Sully and Michael Walter. The holographic entropy cone. (Slides)
In this work, we study the entropies of holographic quantum systems (that is, states of strongly coupled quantum field theories that admit a dual gravitational description). We show that, surprisingly, the study of holographic entropies can be reduced to combinatorics: an entropy inequality is valid for holographic systems if and only if it holds for the mincuts in an arbitrary graph. We discuss several consequences, one of which is a purely combinatorial proof technique that allows us to obtain an infinite family of new holographic entropy inequalities, generalizing the previously known ones. By systematically studying the holographic entropy cone, which parametrizes the region of allowed entropies, we also obtain new insights into the relationship between entropies in holographic systems and other quantum mechanical systems.
http://arxiv.org/abs/1505.07839



16:1516:50 
[153] Michael Beverland, Gorjan Alagic, Jeongwan Haah, Gretchen Campbell, Ana Maria Rey and Alexey Gorshkov. Implementing a quantum algorithm for spectrum estimation with alkaline earth atoms. (Slides)
In this work, we describe an experimentally feasible smallscale physical device, which uses n copies of an unknown quantum state to estimate the state's spectrum. The wellknown efficient quantum algorithm for this task utilizes the quantum Schur transform. Implementing such an algorithm in the usual way would require a scalable, universal circuitmodel quantum computer. Our protocol, on the other hand, involves Ramsey spectroscopy of fermionic alkalineearth atoms in a squarewell trap, and should be experimentally realizable with current technology. Much like the analogous quantum algorithm, our protocol effectively implements a measurement in the Schur basis. The Schur transform maps the computational basis of n qudits to the Schur basis, which consists of matrix entries of irreducible representations of S_n \times SU(d). The aforementioned efficient quantum algorithm (polynomial in n and d) for implementing the Schur transform was first given by Bacon, Chuang and Harrow, along with a number of applications. Among these are optimal spectrum estimation, universal entanglement concentration, encoding into decoherencefree subsystems, optimal hypothesis testing and quantum and classical communication without shared reference frames. We show that our physical system is wellsuited for spectrum estimation; adapting it to the other applications is an open problem.



16:5017:50 
Poster Session 3 


17:5518:45 
QIP 2016 Business Meeting II


