Fourier 1-norm and quantum speed-up

DOI10.1007/S11128-019-2208-7zbMATH Open1417.81086arXiv1612.08070OpenAlexW3105297487WikidataQ128389224 ScholiaQ128389224MaRDI QIDQ670032FDOQ670032

Authors: Sebastián Alberto Grillo, Franklin de Lima Marquezino 

Publication date: 15 March 2019

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

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.

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

Recommendations

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

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)

Cites Work

• Quantum theory, the Church–Turing principle and the universal quantum computer
• Some applications of hypercontractive inequalities in quantum information theory
• On the role of entanglement in quantum-computational speed-up
• Analysis of Boolean Functions
• Quantum Walk Algorithm for Element Distinctness
• On the Problem of Hidden Variables in Quantum Mechanics
• Rapid solution of problems by quantum computation
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• The need for structure in quantum speedups
• Complexity measures and decision tree complexity: a survey.
• Quantum lower bounds by polynomials
• BQP and the polynomial hierarchy
• Title not available (Why is that?)
• Polynomials, quantum query complexity, and Grothendieck's inequality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Quantum query as a state decomposition
• 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)