Quantum supremacy and high-dimensional integration
arXiv:1712.07288
Abstract
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.
arXiv comment11 pages, 3 Figures
Cited by in corpus (4)
- Strawberry Fields: A Software Platform for Photonic Quantum Computing
- Quantum Embedding Search for Quantum Machine Learning
- Characterizing the performance of continuous-variable Gaussian quantum gates
- Generalized binomial state: Nonclassical features observed through various witnesses and a measure of nonclassicality