Quantum conditional query complexity (pp0541-0566)
          Imdad S.B. Sardharwalla, Sergii Strelchuk, and Richard Jozsa
We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain highly efficient quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an $n$-input $m$-output boolean function is balanced or $\epsilon$-far from balanced; and (c) give an algorithm, requiring $\tilde{O}(n/\epsilon)$ queries, for testing whether an $n$-dimensional quantum state is maximally mixed or not.

Can small quantum systems learn (pp0567-0594)
          Nathan Wiebe and Christopher Grandade
We examine the question of whether quantum mechanics places limitations on the ability of small quantum devices to learn.  We specifically examine the question in the context of Bayesian inference, wherein the prior and posterior distributions are encoded in the quantum state vector.  We conclude based on lower bounds from Grover's search that an efficient blackbox method for updating the distribution is impossible.  We then address this by providing a new adaptive form of approximate quantum Bayesian inference that is polynomially faster than its classical anolog and tractable if the quantum system is augmented with classical memory or if the low--order moments of the distribution are protected through redundant preparation.  This work suggests that there may be a connection between fault tolerance and the capacity of a quantum system to learn from its surroundings.

Randomness in nonlocal games between mistrustful players (pp0595-0610)
          Carl A. Miller and Yaoyun Shi
If two quantum players at a nonlocal game $G$ achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player.  This is the basis for device-independent quantum cryptography.  In this paper we address a related question: does a superclassical score at $G$ guarantee that one player has created randomness from the perspective of the other player?  We show that for complete-support games, the answer is yes: even if the second player is given the first player's input at the conclusion of the game, he cannot perfectly recover her output.  Thus some amount of \textit{local} randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.

Super-additivity and entanglement assistance in quantum reading (pp0611-0622)
          Cosmo Lupo and Stefano Pirandola
Quantum information theory determines the maximum rates at which information can be transmitted through physical systems described by quantum mechanics. Here we consider the communication protocol known as quantum reading. Quantum reading is a protocol for retrieving the information stored in a digital memory by using a quantum probe, e.g., shining quantum states of light to read an optical memory. In a variety of situations using a quantum probe enhances the performance of the reading protocol in terms of fidelity, data density and energy efficiency. Here we review and characterize the quantum reading capacity of a memory model, defined as the maximum rate of reliable reading. We show that, like other quantities in quantum information theory, the quantum reading capacity is super-additive. Moreover, we determine conditions under which the use of an entangled ancilla improves the performance of quantum reading.

Improved Hamiltonian simulation via a truncated Taylor series and corrections (pp0623-0635)
          Leonardo Novo and Dominic Berry
We describe an improved version of the quantum algorithm for Hamiltonian simulation based on the implementation of a truncated Taylor series of the evolution operator. The idea is to add an extra step to the previously known algorithm which implements an operator that corrects the weightings of the Taylor series.This way, the desired accuracy is achieved with an  improvement in the overall complexity of the algorithm. This quantum simulation method is applicable to a wide range of Hamiltonians of interest, including to quantum chemistry problems.

The complexity of antiferromagnetic interactions and 2D lattices (pp0636-0672)
          Stephen Piddock and Ashley Montanaro
Estimation of the minimum eigenvalue of a quantum Hamiltonian can be formalised as the Local Hamiltonian problem. We study the natural special case of the Local Hamiltonian problem where the same 2-local interaction, with differing weights, is applied across each pair of qubits. First we consider antiferromagnetic/ferromagnetic interactions, where the weights of the terms in the Hamiltonian are restricted to all be of the same sign. We show that for symmetric 2-local interactions with no 1-local part, the problem is either QMA-complete or in StoqMA. In particular the antiferromagnetic Heisenberg and antiferromagnetic XY interactions are shown to be QMA-complete. We also prove StoqMA-completeness of the antiferromagnetic transverse field Ising model. Second, we study the Local Hamiltonian problem under the restriction that the interaction terms can only be chosen to lie on a particular graph. We prove that nearly all of the QMA-complete 2-local interactions remain QMA-complete when restricted to a 2D square lattice. Finally we consider both restrictions at the same time and discover that, with the exception of the antiferromagnetic Heisenberg interaction, all of the interactions which are QMA-complete with positive coefficients remain QMA-complete when restricted to a 2D triangular lattice.