Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function

Koji Nagata; Tadao Nakamura; Han Geurdes; Josep Batle; Ahmed Farouk; Do Ngoc Diep; Santanu Kumar Patro

doi:10.1007/s10773-018-3776-5

Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function

Koji Nagata^*, Tadao Nakamura, Han Geurdes, Josep Batle, Ahmed Farouk, Do Ngoc Diep, Santanu Kumar Patro

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

Two quantum algorithms of finding the roots of a polynomial function f(x) = x^m + a_{m− 1}x^{m− 1} +.. + a₁x + a₀ are discussed by using the Bernstein-Vazirani algorithm. One algorithm is presented in the modulo 2. The other algorithm is presented in the modulo d. Here all the roots are in the integers Z. The speed of solving the problem is shown to outperform the best classical case by a factor of m in both cases.

Original language	English
Pages (from-to)	2546-2555
Number of pages	10
Journal	International Journal of Theoretical Physics
Volume	57
Issue number	8
DOIs	https://doi.org/10.1007/s10773-018-3776-5
Publication status	Published - 1 Aug 2018
Externally published	Yes

Keywords

Quantum algorithms
Quantum computation

Access to Document

10.1007/s10773-018-3776-5

Cite this

@article{f2072e5d863441289f319727cb5cf175,

title = "Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function",

abstract = "Two quantum algorithms of finding the roots of a polynomial function f(x) = xm + am− 1xm− 1 +.. + a1x + a0 are discussed by using the Bernstein-Vazirani algorithm. One algorithm is presented in the modulo 2. The other algorithm is presented in the modulo d. Here all the roots are in the integers Z. The speed of solving the problem is shown to outperform the best classical case by a factor of m in both cases.",

keywords = "Quantum algorithms, Quantum computation",

author = "Koji Nagata and Tadao Nakamura and Han Geurdes and Josep Batle and Ahmed Farouk and Diep, {Do Ngoc} and Patro, {Santanu Kumar}",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2018",

month = aug,

day = "1",

doi = "10.1007/s10773-018-3776-5",

language = "English",

volume = "57",

pages = "2546--2555",

journal = "International Journal of Theoretical Physics",

issn = "0020-7748",

publisher = "Springer New York",

number = "8",

}

TY - JOUR

T1 - Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function

AU - Nagata, Koji

AU - Nakamura, Tadao

AU - Geurdes, Han

AU - Batle, Josep

AU - Farouk, Ahmed

AU - Diep, Do Ngoc

AU - Patro, Santanu Kumar

PY - 2018/8/1

Y1 - 2018/8/1

N2 - Two quantum algorithms of finding the roots of a polynomial function f(x) = xm + am− 1xm− 1 +.. + a1x + a0 are discussed by using the Bernstein-Vazirani algorithm. One algorithm is presented in the modulo 2. The other algorithm is presented in the modulo d. Here all the roots are in the integers Z. The speed of solving the problem is shown to outperform the best classical case by a factor of m in both cases.

AB - Two quantum algorithms of finding the roots of a polynomial function f(x) = xm + am− 1xm− 1 +.. + a1x + a0 are discussed by using the Bernstein-Vazirani algorithm. One algorithm is presented in the modulo 2. The other algorithm is presented in the modulo d. Here all the roots are in the integers Z. The speed of solving the problem is shown to outperform the best classical case by a factor of m in both cases.

KW - Quantum algorithms

KW - Quantum computation

UR - http://www.scopus.com/inward/record.url?scp=85047162066&partnerID=8YFLogxK

U2 - 10.1007/s10773-018-3776-5

DO - 10.1007/s10773-018-3776-5

M3 - Article

AN - SCOPUS:85047162066

SN - 0020-7748

VL - 57

SP - 2546

EP - 2555

JO - International Journal of Theoretical Physics

JF - International Journal of Theoretical Physics

IS - 8

ER -

Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this