Fourier 1-norm and quantum speed-up

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 x ∈ { 0 , 1 } n as a function π ( x ) . We pres...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2019-04, Vol.18 (4), p.1-15, Article 99
Main Authors: Grillo, Sebastián Alberto, de Lima Marquezino, Franklin
Format: Article
Language:English
Subjects:
Algorithms
Computer simulation
Data Structures and Information Theory
Dependence
Mathematical Physics
Physics
Physics and Astronomy
Quantum Computing
Quantum Information Technology
Quantum Physics
Spintronics
Upper bounds
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 x ∈ { 0 , 1 } n as a function π ( x ) . We present a classical simulation for output probabilities π , whose error depends on the Fourier 1-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 1-norm and quantum parallelism. We show applications to query complexity.
ISSN:1570-0755
1573-1332
DOI:10.1007/s11128-019-2208-7