Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/58266
Type: Artigo de periódico
Title: TIGHT QUANTUM BOUNDS FOR COMPUTATIONAL GEOMETRY PROBLEMS
Author: Volpato, N
Moura, A
Abstract: We present new quantum lower bounds and upper bounds for several computational geometry problems. The bounds presented here improve on currently known results in a number of ways. We give asymptotically optimal bounds for one of the problems considered, and we provide, up to logarithmic factors, optimal bounds for a number of other problems and, in particular, we settle an open problem of Bahadur et al. Some of these new bounds are obtained using a general algorithm for finding a minimum pair over a given arbitrary order relation.
Subject: Quantum computing
quantum algorithm
lower bound
upper bound
computational geometry
Country: Singapura
Editor: World Scientific Publ Co Pte Ltd
Rights: fechado
Identifier DOI: 10.1142/S0219749909005572
Date Issue: 2009
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000269123400006.pdf225.42 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.