Quantum separation of local search and fixed point computation

DOI10.1007/S00453-009-9289-0MaRDI QIDQ848947zbMATH OpenOpenAlexFDO

Authors Xi Chen, Xiaoming Sun, Shang-Hua Teng

Publication date 23 February 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-009-9289-0

zbMATH Keywords

local searchSperner's lemmaquantum query complexityfixed-point computationquantum adversary method

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Quantum Separation of Local Search and Fixed Point Computation
• Tight bounds for randomized and quantum local search
• Lower bounds for local search by quantum arguments
• Lower Bounds for Local Search by Quantum Arguments
• New upper and lower bounds for randomized and quantum local search

Cites work

• scientific article; zbMATH DE number 5485488 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• Automata, Languages and Programming
• Discrete fixed point theorem reconsidered
• Equilibrium points in n -person games
• Existence of an Equilibrium for a Competitive Economy
• Exponential lower bounds for finding Brouwer fixed points
• Fundamentals of Computation Theory
• Lower bounds for local search by quantum arguments
• Minimization algorithms and random walk on the d-cube
• New upper and lower bounds for randomized and quantum local search
• On algorithms for discrete and approximate brouwer fixed points
• On the complexity of price equilibria
• On the power of Ambainis lower bounds
• Quantum and classical query complexities of local search are polynomially related
• Quantum lower bounds by polynomials
• Quantum lower bounds by quantum arguments
• The Approximation of Fixed Points of a Continuous Mapping

Cited in

(4)

• scientific article; zbMATH DE number 5320369 (Why is no real title available?)
• Engineering local optimality in quantum Monte Carlo algorithms
• Quantum Separation of Local Search and Fixed Point Computation
• On barren plateaus and cost function locality in variational quantum algorithms

This page was built for publication: Quantum separation of local search and fixed point computation

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