20-22 May 2015
Asia/Bangkok timezone
The Centennial Celebration of General Relativity Theory and 80 Years of Thai Physics Graduate

Quantum Algorithm for Finding Roots of $n^\mathrm{th}$ Degree Polynomials

21 May 2015, 09:45
15m
Hemingways' Lounge ()

Hemingways' Lounge

Oral presentation Atomic Physics, Quantum Physics, Molecular and Chemical Physics Atomic Physics, Quantum Physics, Molecular and Chemical Physics

Speaker

Mr Theerapat Tansuwannont (Department of Physics, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand)

Description

Quantum algorithm is an algorithm for solving mathematical problems using quantum systems encoded as information, which is found to outperform classical algorithms. The objective of this study is to develop a quantum algorithm for finding the roots of $n^{\mathrm{th}}$ degree polynomials where $n$ is any positive integer. In classical algorithm, the resources required for solving this problem increase drastically when $n$ increases and it would be impossible to practically solve the problem when $n$ is large. It was found that any polynomial can be rearranged into a corresponding companion matrix, whose eigenvalues are roots of the polynomial. This leads to a possibility to perform a quantum algorithm where the number of computational resources increases as a polynomial of $n$. In this study, we construct a quantum circuit representing the companion matrix and use eigenvalue estimation technique to find roots of polynomial. The complexity of this quantum algorithm is also compared with a classical algorithm for solving the same problem.

Primary author

Mr Theerapat Tansuwannont (Department of Physics, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand)

Co-authors

Mr Pruet Kalasuwan (Department of Physics, Faculty of Science, Prince of Songkla University, Hat-Yai, Songkla 90112, Thailand) Mr Surachate Limkumnerd (Department of Physics, Faculty of Science, Chulalongkorn University, Bangkok 10330, Thailand)

Presentation Materials

There are no materials yet.