PDQP/qpoly=ALL (pp0901-0909)
          Scott Aaronson
We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.

Universal bound on the cardinality of local hidden variables in networks (pp0910-0926)
          Denis Rosset, Nicolas Gisin, and Elie Wolfe
We present an algebraic description of the sets of local correlations in arbitrary networks, when the parties have finite inputs and outputs. We consider networks generalizing the usual Bell scenarios by the presence of multiple uncorrelated sources. We prove a finite upper bound on the cardinality of the value sets of the local hidden variables. Consequently, we find that the sets of local correlations are connected, closed and semialgebraic, and bounded by tight polynomial Bell-like inequalities.

Limitations on transversal computation through quantum homomorphic encryption (pp0927-0948)
          Michael Newman and Yaoyun Shi
Transversality is a simple and effective method for implementing quantum computation fault-tolerantly. However, no quantum error-correcting code (QECC) can transversally implement a quantum universal gate set (Eastin and Knill, {\em Phys. Rev. Lett.}, 102, 110502). Since reversible classical computation is often a dominating part of useful quantum computation, whether or not it can be implemented transversally is an important open problem. We show that, other than a small set of non-additive codes that we cannot rule out, no binary QECC can transversally implement a classical reversible universal gate set.  In particular, no such QECC can implement the Toffoli gate transversally.}{We prove our result by constructing an information theoretically secure (but inefficient) quantum homomorphic encryption (ITS-QHE) scheme inspired by Ouyang {\em et al.} (arXiv:1508.00938).  Homomorphic encryption allows the implementation of certain functions directly on encrypted data, i.e. homomorphically.  Our scheme builds on almost any QECC, and implements that code's transversal gate set homomorphically.  We observe a restriction imposed by Nayak's bound  ({\em FOCS} 1999) on ITS-QHE, implying that any ITS quantum {\em fully} homomorphic scheme (ITS-QFHE) implementing the full set of classical reversible functions must be highly inefficient.  While our scheme incurs exponential overhead, any such QECC implementing Toffoli transversally would still violate this lower bound through our scheme.

Is error detection helpful on IBM 5Q chips? (pp0949-0964)
          Christophe Vuillot
This paper reports on experiments realized on several IBM~5Q chips which show evidence for the advantage of using error detection and fault-tolerant design of quantum circuits. We show an average improvement of the task of sampling from states that can be fault-tolerantly prepared in the $[[4,2,2]]$ code, when using a fault-tolerant technique well suited to the layout of the chip. By showing that fault-tolerant quantum computation is already within our reach, the author hopes to encourage this approach.

Quantum signaling to the past using P-CTCS (pp0965-0974)
          Soumik Ghosh, Arnab Adhikary, and Goutam Paul
Closed Timelike Curves (CTCs) are intriguing relativistic objects that allow for time travel to the past and can be used as computational resources. In Deutschian Closed Timelike Curves (D-CTCs), due to the monogamy of entanglement, non-local correlations between entangled states are destroyed. In contrast, for Postselected Closed Timelike Curves (P-CTCs), a second variant of CTCs, the non-local correlations are preserved. P-CTCs can be harnessed for the signaling of non-orthogonal states to the past without a disruption of causality. In this paper, we take up signaling to the past and show a method of sending four non-orthogonal states to the past using P-CTCs. After constructing our signaling protocol, we study the causality violations that our protocol results in and put forward two consistency relations to prevent them.

Weak measurement for improving the efficiency of remote state preparation in noisy (pp0975-0987)
          Ming-Ming Wang and Zhi-Guo Qu
Quantum communication provides a new way for transmitting highly sensitive information. But the existence of quantum noise inevitably affects the security and reliability of a quantum communication system. The technique of weak measurement and its reversal measurement (WMRM) has been proposed to suppress the effect of quantum noise, especially, the amplitude-damping noise. Taking a GHZ based remote state preparation (RSP) scheme as an example, we discuss the effect of WMRM for suppressing four types of quantum noise that usually encountered in real-world, i.e., not only the amplitude-damping noise, but also the bit-flip, phase-flip (phase-damping) and depolarizing noise. And we give a quantitative study on how much a quantum output state can be improved by WMRM in noisy environment. It is shown that the technique of WMRM has certain effect for improving the fidelity of the output state in the amplitude-damping noise, and only has little effect for suppressing the depolarizing noise, while has no effect for suppressing the bit-flip and phase-flip (phase-damping) noise. Our result is helpful for improving the efficiency of entanglement-based quantum communication systems in real implementation.