Grant: Alliance Grants
University of Saskatchewan
$25,000.00
Quantum Algorithms and Complexity for Computational Geometry Problems
EF 2024-25
Résumé
Computational geometry problems often appear in data analytics, geospatial navigation, robot motion planning, graphics rendering, developing computer games, and industrial automation. Many fundamental geometric problems are very well studied in classical computing models and have known time-complexity bottlenecks that restrict researchers from designing fast algorithms. However, for some computing tasks such as searching and counting, quantum computing offers techniques that are significantly faster than the time-complexity lower bounds known for these tasks in the classical computing context. We propose to design quantum algorithm frameworks for computational geometry problems. We will specifically focus on geometric partitioning techniques and data structures that are fundamental tools to solve geometric decision and optimization problems, and thus accelerating them by leveraging quantum computing would speed up a plethora of well-known geometric problems on quantum computers.
Programme
Alliance Grants
Bénéficiaire
Emplacement
Saskatchewan, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
585462-2023
Name nom
Mondal, Debajyoti D
Department département
Computer Science
Organization id
16
Institution établissement
University of Saskatchewan
Province en
Saskatchewan
Province fr
Saskatchewan
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2023
Award amount
25000
Program id
ALLRP
Program name en
Alliance Grants
Program name fr
Subventions Alliance
Group en
RESEARCH PARTNERSHIPS
Group fr
PARTENARIATS DE RECHERCHE
Committee code
96
Committee name en
RPP Internal Decision Cttee
Committee name fr
Cté de décision interne - PPR
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Quantum Algorithms and Complexity for Computational Geometry Problems
Keywords
complexity; computational geometry; data structure; optimization; quantum altgorithms
Application summary
Computational geometry problems often appear in data analytics, geospatial navigation, robot motion planning, graphics rendering, developing computer games, and industrial automation. Many fundamental geometric problems are very well studied in classical computing models and have known time-complexity bottlenecks that restrict researchers from designing fast algorithms. However, for some computing tasks such as searching and counting, quantum computing offers techniques that are significantly faster than the time-complexity lower bounds known for these tasks in the classical computing context. We propose to design quantum algorithm frameworks for computational geometry problems. We will specifically focus on geometric partitioning techniques and data structures that are fundamental tools to solve geometric decision and optimization problems, and thus accelerating them by leveraging quantum computing would speed up a plethora of well-known geometric problems on quantum computers.