On the quantum query complexity of local search in two and three dimensions
type: Item
instance of: scholarly article
title: On the quantum query complexity of local search in two and three dimensions
zbMATH Open document ID: 1192.68283
author: Xiaoming Sun
author: Andrew Chi-Chih Yao
published in: Algorithmica
publication date: 2009-08-31T00:00:00Z
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 81P68
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5600042
zbMATH Keywords: local search
zbMATH Keywords: quantum query complexity
MaRDI profile type: Publication
full work available at URL: s00453-008-9170-6
OpenAlex ID: W2032556376
cites work: Lower Bounds for Local Search by Quantum Arguments
cites work: Minimization algorithms and random walk on the d-cube
cites work: Quantum lower bounds by quantum arguments
cites work: Polynomial degree vs. quantum query complexity
cites work: Strengths and Weaknesses of Quantum Computing
cites work: Theorems in the additive theory of numbers
cites work: On algorithms for discrete and approximate brouwer fixed points
cites work: Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
cites work: Fundamentals of Computation Theory
cites work: Estimates for the concentration function of combinatorial number theory and probability
cites work: How easy is local search?
cites work: Local optimization on graphs
cites work: Quantum and classical query complexities of local search are polynomially related
cites work: Über ein Problem von Erdös und Moser
cites work: Enhanced algorithms for local search
cites work: On the power of Ambainis lower bounds
cites work: New upper and lower bounds for randomized and quantum local search
DOI: 10.1007/S00453-008-9170-6
Recommended article: Quantum and classical query complexities of local search are polynomially related
Recommended article: Tight Bounds for Randomized and Quantum Local Search
Recommended article: Lower bounds for local search by quantum arguments
Recommended article: Lower Bounds for Local Search by Quantum Arguments
Recommended article: Quantum and Randomized Lower Bounds for Local Search on Vertex-Transitive Graphs
Recommended article: Q3172447
Recommended article: New upper and lower bounds for randomized and quantum local search
Recommended article: On exact quantum query complexity
Recommended article: Quantum Separation of Local Search and Fixed Point Computation
description: scientific article; zbMATH DE number 5600042