Fourier 1-norm and quantum speed-up

DOI10.1007/S11128-019-2208-7MaRDI QIDQ670032zbMATH OpenOpenAlexWikidataFDO

Authors Sebastián Alberto Grillo, Franklin de Lima Marquezino

Publication date 15 March 2019

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.08070

zbMATH Keywords

simulationquantum queryrandomized query

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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 $xin{0,1}^n$ as a function $pi(x)$. We present a classical simulation for output probabilities $pi$, whose error depends on the Fourier $1$-norm of $pi$. 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.

Recommendations

• Quantum computers speed up classical with probability zero
• Sharp quantum versus classical query complexity separations
• Quantum lower bounds by polynomials

Cites work

• scientific article; zbMATH DE number 5485521 (Why is no real title available?)
• scientific article; zbMATH DE number 1182474 (Why is no real title available?)
• scientific article; zbMATH DE number 6297720 (Why is no real title available?)
• Analysis of Boolean Functions
• BQP and the polynomial hierarchy
• Complexity measures and decision tree complexity: a survey.
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• On the Problem of Hidden Variables in Quantum Mechanics
• On the role of entanglement in quantum-computational speed-up
• Polynomials, quantum query complexity, and Grothendieck's inequality
• Quantum Walk Algorithm for Element Distinctness
• Quantum lower bounds by polynomials
• Quantum query as a state decomposition
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Rapid solution of problems by quantum computation
• Some applications of hypercontractive inequalities in quantum information theory
• The need for structure in quantum speedups
• Understanding the quantum computational speed-up via de-quantisation

This page was built for publication: Fourier 1-norm and quantum speed-up

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q670032)