Search

We establish a connection between continuous-variable quantum computing and high-dimensional integration by showing that the outcome probabilities of continuous-variable instantaneous quantum polynomial (CV-IQP) circuits are given by integrals of oscillating functions in large dimensions. We prove two results related to the classical hardness of evaluating these integrals: (i) we show that there exist circuits such that these integrals are approximations of a weighted sum of #P-hard problems and (ii) we prove that calculating these integrals is as hard as calculating integrals of arbitrary bounded functions. We then leverage these results to show that, given a plausible conjecture about the hardness of computing the integrals, approximate sampling from CV-IQP circuits cannot be done in polynomial time on a classical computer unless the polynomial hierarchy collapses to the third level. Our results hold even in the presence of finite squeezing and limited measurement precision, without an explicit need for fault-tolerance., Comment: 11 pages, 3 Figures

We show how weak non-linearities can be used in a device-independent quantum key distribution (QKD) protocol using generalized two-mode Schr��dinger cat states. The QKD protocol is therefore shown to be secure against collective attacks and for some coherent attacks. We derive analytical formulas for the optimal values of the Bell parameter, the quantum bit error rate, and the device-independent secret key rate in the noiseless lossy bosonic channel. Additionally, we give the filters and measurements which achieve these optimal values. We find that over any distance in this channel the quantum bit error rate is identically zero, in principle, and the states in the protocol are always able to violate a Bell inequality. The protocol is found to be superior in some regimes to a device-independent QKD protocol based on polarization entangled states in a depolarizing channel. Finally, we propose an implementation for the optimal filters and measurements., Comments welcome

In general relativity, closed timelike curves can break causality with remarkable and unsettling consequences. At the classical level, they induce causal paradoxes disturbing enough to motivate conjectures that explicitly prevent their existence. At the quantum level, resolving such paradoxes induce radical benefits - from cloning unknown quantum states to solving problems intractable to quantum computers. Instinctively, one expects these benefits to vanish if causality is respected. Here we show that in harnessing entanglement, we can efficiently solve NP-complete problems and clone arbitrary quantum states - even when all time-travelling systems are completely isolated from the past. Thus, the many defining benefits of closed timelike curves can still be harnessed, even when causality is preserved. Our results unveil the subtle interplay between entanglement and general relativity, and significantly improve the potential of probing the radical effects that may exist at the interface between relativity and quantum theory., Comment: 6 pages, 5 figures. Comments most welcome

In 1972, P.W.Anderson suggested that `More is Different', meaning that complex physical systems may exhibit behavior that cannot be understood only in terms of the laws governing their microscopic constituents. We strengthen this claim by proving that many macroscopic observable properties of a simple class of physical systems (the infinite periodic Ising lattice) cannot in general be derived from a microscopic description. This provides evidence that emergent behavior occurs in such systems, and indicates that even if a `theory of everything' governing all microscopic interactions were discovered, the understanding of macroscopic order is likely to require additional insights., 7 pages, 5 figures