Fourier 1-norm and quantum speed-up
arXiv:1612.08070 · doi:10.1007/s11128-019-2208-7
Abstract
Understanding quantum speed-up over classical computing is fundamental for the development of efficient quantum algorithms. In this paper, we study such problem within the framework of the Quantum Query Model, which represents the probability of output as a function . We present a classical simulation for output probabilities , whose error depends on the Fourier -norm of . Such dependence implies upper-bounds for the quotient between the number of queries applied by an optimal classical algorithm and our quantum algorithm, respectively. These upper-bounds show a strong relation between Fourier -norm and quantum parallelism. We show applications to query complexity.
arXiv comment16 pages, 1 figure, changed title, improved text, added applications
References in corpus (9)
- Efficient classical simulation of slightly entangled quantum computations
- Quantum discord and the power of one qubit
- On the Power of One Bit of Quantum Information
- On the role of entanglement in quantum computational speed-up
- Contextuality supplies the magic for quantum computation
- On the role of entanglement and correlations in mixed-state quantum computation
- Some applications of hypercontractive inequalities in quantum information theory
- Quantum Query as a State Decomposition
- Understanding the Quantum Computational Speed-up via De-quantisation