- Feb 15 2018 quant-ph arXiv:1802.04926v1We introduce a three-player nonlocal game, with a finite number of classical questions and answers, such that the optimal success probability of $1$ in the game can only be achieved in the limit of strategies using arbitrarily high-dimensional entangled states. Precisely, there exists a constant $0 <c\leq 1$ such that to succeed with probability $1-\varepsilon$ in the game it is necessary to use an entangled state of at least $\Omega(\varepsilon^{-c})$ qubits, and it is sufficient to use a state of at most $O(\varepsilon^{-1})$ qubits. The game is based on the coherent state exchange game of Leung et al. (CJTCS 2013). In our game, the task of the quantum verifier is delegated to a third player by a classical referee. Our results complement those of Slofstra (arXiv:1703.08618) and Dykema et al. (arXiv:1709.05032), who obtained two-player games with similar (though quantitatively weaker) properties based on the representation theory of finitely presented groups and $C^*$-algebras respectively.
- Genuine high-dimensional entanglement, i.e. the property of having a high Schmidt number, constitutes a resource in quantum communication, overcoming limitations of low-dimensional systems. States with a positive partial transpose (PPT), on the other hand, are generally considered weakly entangled, as they can never be distilled into pure entangled states. This naturally raises the question, whether high Schmidt numbers are possible for PPT states. Volume estimates suggest that optimal, i.e. linear, scaling in local dimension should be possible, albeit without providing an insight into the possible slope. We provide the first explicit construction of a family of PPT states that achieves linear scaling in local dimension and we prove that random PPT states typically share this feature. Our construction also allows us to answer a recent question by Chen et al. on the existence of PPT states whose Schmidt number increases by an arbitrarily large amount upon partial transposition. Finally, we link the Schmidt number to entangled sub-block matrices of a quantum state. We use this connection to prove that quantum states invariant under partial transposition on the smaller of their two subsystems cannot have maximal Schmidt number. This generalizes a well-known result by Kraus et al. We also show that the Schmidt number of absolutely PPT states cannot be maximal, contributing to an open problem in entanglement theory.
- In this paper, we give quantum algorithms for two fundamental computation problems: solving polynomial systems and optimization over finite fields. The quantum algorithms can solve these problems with any given probability and have complexities polynomial in the size of the input and the condition number of certain polynomial system related to the problem. So, we achieved exponential speedup for these problems when their condition numbers are small. As special cases of the optimization problem, quantum algorithms are given for the polynomial systems with noise, the short integer solution problem, cryptanalysis for the lattice based NTRU cryptosystems. The main technical contribution of the paper is how to reduce polynomial system solving and optimization over finite fields into the determination of Boolean solutions of a polynomial system over C, under the condition that the number of variables and the total sparseness of the new system is well controlled.
- Feb 09 2018 quant-ph arXiv:1802.02648v1Multipartite entanglement has been widely regarded as key resources in distributed quantum computing, for instance, multi-party cryptography, measurement based quantum computing, quantum algorithms. It also plays a fundamental role in quantum phase transitions, even responsible for transport efficiency in biological systems. Certifying multipartite entanglement is generally a fundamental task. Since an $N$ qubit state is parameterized by $4^N-1$ real numbers, one is interested to design a measurement setup that reveals multipartite entanglement with as little effort as possible, at least without fully revealing the whole information of the state, the so called "tomography", which requires exponential energy. In this paper, we study this problem of certifying entanglement without tomography in the constrain that only single copy measurements can be applied. This task is formulate as a membership problem related to a dividing quantum state space, therefore, related to the geometric structure of state space. We show that universal entanglement detection among all states can never be accomplished without full state tomography. Moreover, we show that almost all multipartite correlation, include genuine entanglement detection, entanglement depth verification, requires full state tomography. However, universal entanglement detection among pure states can be much more efficient, even we only allow local measurements. Almost optimal local measurement scheme for detecting pure states entanglement is provided.
- Feb 08 2018 quant-ph arXiv:1802.02526v1It is possible for two parties, Alice and Bob, to establish a secure communication link by sharing an ensemble of entangled particles, and then using these particles to generate a secret key. One way to establish that the particles are indeed entangled is to verify that they violate a Bell inequality. However, it might be the case that Bob is not trustworthy and wishes Alice to believe that their communications are secure, when in fact they are not. He can do this by managing to have prior knowledge of Alice's measurement device settings and then modifying his own settings based upon this information. In this case it is possible for shared particle states that must satisfy a Bell inequality to appear to violate this inequality, which would also make the system appear secure. When Bob modifies his measurement settings, however, he produces false correlations. Here we demonstrate experimentally that Alice can detect these false correlations, and uncover Bob's trickery, by using loop-state-preparation-and-measurement (SPAM) tomography. More generally, we demonstrate that loop SPAM tomography can detect false correlations (correlated errors) in a two-qubit system without needing to know anything about the prepared states or the measurements, other than the dimensions of the operators that describe them.
- It is not known what the limitations are on using quantum computation to speed up classical computation. An example would be the power to speed up PSPACE-complete computations. It is also not known what the limitations are on the duration of time over which classical general relativity can describe the interior geometry of black holes. What is known is that these two questions are closely connected: the longer GR can describe black holes, the more limited are quantum computers. This conclusion, formulated as a theorem, is a result of unpublished work done by Scott Aaronson and myself which I explain here.
- Feb 01 2018 quant-ph arXiv:1801.10446v2We present self-testing protocols to certify the presence of tensor products of Pauli measurements on maximally entangled states of local dimension $2^n$ for $n\in\mathbb{N}$. This provides self-tests of sets of informationally complete measurements in arbitrarily high dimension. We then show that this can be used for the device-independent certification of the entanglement of all bipartite entangled states by exploiting a connection to measurement device-independent entanglement witnesses and quantum networks. This work extends a more compact parallel work on the same subject and provides all the required technical proofs.
- Feb 01 2018 quant-ph arXiv:1801.10444v1We present a method to certify the entanglement of all bipartite entangled quantum states in a device-independent way. This is achieved by placing the state in a quantum network and constructing a correlation inequality based on an entanglement witness for the state. Our method is device-independent, in the sense that entanglement can be certified from the observed statistics alone, under minimal assumptions on the underlying physics. Conceptually, our results borrow ideas from the field of self-testing to bring the recently introduced measurement-device-independent entanglement witnesses into the fully device-independent regime.
- We classify instances of quantum pseudo-telepathy in the graph isomorphism game, exploiting the recently discovered connection between quantum information and the theory of quantum automorphism groups. Specifically, we show that graphs quantum isomorphic to a given graph are in bijective correspondence with Morita equivalence classes of certain Frobenius algebras in the category of finite-dimensional representations of the quantum automorphism algebra of that graph. We show that such a Frobenius algebra may be constructed from a central type subgroup of the classical automorphism group, whose action on the graph has coisotropic vertex stabilisers. In particular, if the original graph has no quantum symmetries, quantum isomorphic graphs are classified by such subgroups. We show that all quantum isomorphic graph pairs corresponding to a well-known family of binary constraint systems arise from this group-theoretical construction. We use our classification to show that, of the small order vertex-transitive graphs with no quantum symmetry, none is quantum isomorphic to a non-isomorphic graph. We show that this is in fact asymptotically almost surely true of all graphs.
- In this note we discuss the geometry of matrix product states with periodic boundary conditions and provide three infinite sequences of examples where the quantum max-flow is strictly less than the quantum min-cut. In the first we fix the underlying graph to be a 4-cycle and verify a prediction of Hastings that inequality occurs for infinitely many bond dimensions. In the second we generalize this result to a 2d-cycle. In the third we show that the 2d-cycle with periodic boundary conditions gives inequality for all d when all bond dimensions equal two, namely a gap of at least 2^d-2 between the quantum max-flow and the quantum min-cut.

- Supported by Silverpond.