On Quantum Algorithm for Exptime Problem

S. Iriyama; M. Ohya

doi:10.1142/9789814343763_0014

On Quantum Algorithm for Exptime Problem

S. Iriyama, M. Ohya

Department of Information Sciences

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

There exists a quantum algorithm with chaos dynamics solving an NP-complete problem in polynomial time, called OMV SAT algorithm. The language class EXPTIME is larger class than NP, there is no classical algorithm to solve it in polynomial time. In this paper we propose a quantum algorithm for one of the problems in EXPTIME, Pebble Game, and compare the computational complexity of it with the classical one. We show that a quantum algorithm with Oracle solves it in polynomial time while a classical algorithm with same Oracle does in exponential time.

Original language	English
Title of host publication	Quantum Bio-informatics IV
Subtitle of host publication	From Quantum Information to Bio-informatics
Publisher	World Scientific Publishing Co.
Pages	173-183
Number of pages	11
ISBN (Electronic)	9789814343763
ISBN (Print)	9789814343756
DOIs	https://doi.org/10.1142/9789814343763_0014
Publication status	Published - 1 Jan 2011

Access to Document

10.1142/9789814343763_0014

Cite this

@inbook{2030531cc34847a683721cd38c38d50a,

title = "On Quantum Algorithm for Exptime Problem",

abstract = "There exists a quantum algorithm with chaos dynamics solving an NP-complete problem in polynomial time, called OMV SAT algorithm. The language class EXPTIME is larger class than NP, there is no classical algorithm to solve it in polynomial time. In this paper we propose a quantum algorithm for one of the problems in EXPTIME, Pebble Game, and compare the computational complexity of it with the classical one. We show that a quantum algorithm with Oracle solves it in polynomial time while a classical algorithm with same Oracle does in exponential time.",

author = "S. Iriyama and M. Ohya",

note = "Publisher Copyright: {\textcopyright} 2011 World Scientific Publishing Co.",

year = "2011",

month = jan,

day = "1",

doi = "10.1142/9789814343763_0014",

language = "English",

isbn = "9789814343756",

pages = "173--183",

booktitle = "Quantum Bio-informatics IV",

publisher = "World Scientific Publishing Co.",

}

TY - CHAP

T1 - On Quantum Algorithm for Exptime Problem

AU - Iriyama, S.

AU - Ohya, M.

PY - 2011/1/1

Y1 - 2011/1/1

N2 - There exists a quantum algorithm with chaos dynamics solving an NP-complete problem in polynomial time, called OMV SAT algorithm. The language class EXPTIME is larger class than NP, there is no classical algorithm to solve it in polynomial time. In this paper we propose a quantum algorithm for one of the problems in EXPTIME, Pebble Game, and compare the computational complexity of it with the classical one. We show that a quantum algorithm with Oracle solves it in polynomial time while a classical algorithm with same Oracle does in exponential time.

AB - There exists a quantum algorithm with chaos dynamics solving an NP-complete problem in polynomial time, called OMV SAT algorithm. The language class EXPTIME is larger class than NP, there is no classical algorithm to solve it in polynomial time. In this paper we propose a quantum algorithm for one of the problems in EXPTIME, Pebble Game, and compare the computational complexity of it with the classical one. We show that a quantum algorithm with Oracle solves it in polynomial time while a classical algorithm with same Oracle does in exponential time.

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

U2 - 10.1142/9789814343763_0014

DO - 10.1142/9789814343763_0014

M3 - Chapter

AN - SCOPUS:85129083760

SN - 9789814343756

SP - 173

EP - 183

BT - Quantum Bio-informatics IV

PB - World Scientific Publishing Co.

ER -

On Quantum Algorithm for Exptime Problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this