Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no ω(1)-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the 2→4 norm of a matrix, and the set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state. In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Watrous and Aaronson et al. These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz.

VL - 366 UR - https://arxiv.org/abs/1612.09306 CP - 2 U5 - https://doi.org/10.1007/s00220-019-03382-y ER - TY - Generic T1 - Sequential measurements, disturbance and property testing T2 - Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) Y1 - 2017 A1 - Aram W. Harrow A1 - Cedric Yen-Yu Lin A1 - Ashley Montanaro AB -We describe two procedures which, given access to one copy of a quantum state and a sequence of two-outcome measurements, can distinguish between the case that at least one of the measurements accepts the state with high probability, and the case that all of the measurements have low probability of acceptance. The measurements cannot simply be tried in sequence, because early measurements may disturb the state being tested. One procedure is based on a variant of Marriott-Watrous amplification. The other procedure is based on the use of a test for this disturbance, which is applied with low probability. We find a number of applications. First, quantum query complexity separations in the property testing model for testing isomorphism of functions under group actions. We give quantum algorithms for testing isomorphism, linear isomorphism and affine isomorphism of boolean functions which use exponentially fewer queries than is possible classically, and a quantum algorithm for testing graph isomorphism which uses polynomially fewer queries than the best algorithm known. Second, testing properties of quantum states and operations. We show that any finite property of quantum states can be tested using a number of copies of the state which is logarithmic in the size of the property, and give a test for genuine multipartite entanglement of states of n qubits that uses O(n) copies of the state. Third, correcting an error in a result of Aaronson on de-Merlinizing quantum protocols. This result claimed that, in any one-way quantum communication protocol where two parties are assisted by an all-powerful but untrusted third party, the third party can be removed with only a modest increase in the communication cost. We give a corrected proof of a key technical lemma required for Aaronson's result.

JA - Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) U4 - 1598-1611 UR - http://epubs.siam.org/doi/10.1137/1.9781611974782.105 U5 - 10.1137/1.9781611974782.105 ER - TY - JOUR T1 - Entanglement can completely defeat quantum noise JF - Physical Review Letters Y1 - 2011 A1 - Jianxin Chen A1 - Toby S. Cubitt A1 - Aram W. Harrow A1 - Graeme Smith AB - We describe two quantum channels that individually cannot send any information, even classical, without some chance of decoding error. But together a single use of each channel can send quantum information perfectly reliably. This proves that the zero-error classical capacity exhibits superactivation, the extreme form of the superadditivity phenomenon in which entangled inputs allow communication over zero capacity channels. But our result is stronger still, as it even allows zero-error quantum communication when the two channels are combined. Thus our result shows a new remarkable way in which entanglement across two systems can be used to resist noise, in this case perfectly. We also show a new form of superactivation by entanglement shared between sender and receiver. VL - 107 UR - http://arxiv.org/abs/1109.0540v1 CP - 25 J1 - Phys. Rev. Lett. U5 - 10.1103/PhysRevLett.107.250504 ER - TY - JOUR T1 - Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel JF - IEEE Transactions on Information Theory Y1 - 2011 A1 - Toby S. Cubitt A1 - Jianxin Chen A1 - Aram W. Harrow AB - The zero-error classical capacity of a quantum channel is the asymptotic rate at which it can be used to send classical bits perfectly, so that they can be decoded with zero probability of error. We show that there exist pairs of quantum channels, neither of which individually have any zero-error capacity whatsoever (even if arbitrarily many uses of the channels are available), but such that access to even a single copy of both channels allows classical information to be sent perfectly reliably. In other words, we prove that the zero-error classical capacity can be superactivated. This result is the first example of superactivation of a classical capacity of a quantum channel. VL - 57 U4 - 8114 - 8126 UR - http://arxiv.org/abs/0906.2547v3 CP - 12 J1 - IEEE Trans. Inform. Theory U5 - 10.1109/TIT.2011.2169109 ER - TY - JOUR T1 - Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem Y1 - 2006 A1 - Andrew M. Childs A1 - Aram W. Harrow A1 - Pawel Wocjan AB - Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call weak Schur sampling) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem. UR - http://arxiv.org/abs/quant-ph/0609110v1 J1 - Proc. 24th Symposium on Theoretical Aspects of Computer Science (STACS 2007) U5 - 10.1007/978-3-540-70918-3_51 ER -