Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
From MaRDI portal
Publication:5212793
DOI10.1145/3313276.3316404zbMath1434.68179arXiv1906.08890OpenAlexW3101424970MaRDI QIDQ5212793
Adam Bene Watts, Avishay Tal, Robin Kothari, Luke Schaeffer
Publication date: 30 January 2020
Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1906.08890
Quantum algorithms and complexity in the theory of computing (68Q12) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Trading locality for time: certifiable randomness from low-depth circuits, 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time, A generalisation of the phase kick-back, Power of uninitialized qubits in shallow quantum circuits, Unnamed Item, Sampling Lower Bounds: Boolean Average-Case and Permutations, Quantum advantage through the magic pentagram problem
