Record Details

Quantum query complexity in computational geometry revisited

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Quantum query complexity in computational geometry revisited
 
Creator BAHADUR, A
DURR, C
LAFAYE, T
KULKARNI, R
 
Description We are interested in finding quantum algorithms for problems in the area of computation geometry. Many of the problems we study have already polynomial time algorithms. But since in this area the input sizes are huge,, quadratic time algorithms are often not good enough. Bounded error quantum algorithms can actually have sublinear running time. To our knowledge there have been two works on the subject. One is by K. Sadakane, N. Sugawara, T. Tokuyama [6],[7] and the other by W. Smith [8]. These papers do not contain lower bounds. The main quantum ingredient in their algorithms is a quantum algorithm for the Element Distinctness problem based on Grover's quantum search algorithm. We revisit the problems using the recent quantum algorithm for Element Distinctness based on a quantum walk [1]. We also show new lower bounds and study new problems, in particular problems on polygons and the 3-Sum problem.
 
Publisher SPIE-INT SOC OPTICAL ENGINEERING
 
Date 2011-10-24T02:43:42Z
2011-12-15T09:11:23Z
2011-10-24T02:43:42Z
2011-12-15T09:11:23Z
2006
 
Type Proceedings Paper
 
Identifier QUANTUM INFORMATION AND COMPUTATION IV,6244,
0-8194-6300-0
0277-786X
http://dx.doi.org/10.1117/12.661591
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15310
http://hdl.handle.net/100/2035
 
Source Conference on Quantum Information and Computation IV,Kissimmee, FL,APR 17-19, 2006
 
Language English