Japan Advanced Institute of Science and Technology

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

Author(s)

Citation

Issue Date

Type

Text version

URL

Rights

Description

TakashiMihara

Scho ol of InformationScience

Japan Advanced Instituteof Scienceand Technology

January 16, 1997

Abstract

In this thesis, we show some results on the complexity and algorithmsbased on a quantum

Turingmachine,which isa newtyp eof computing modelproposedin1980's.

In Chapter1, wedescribe backgroundsand motivationsof studying quantum computers. In

1985, Deutschprop osed a computing mo del involvinga superposition of physicalstates, which

is one of inherent properties of quantum physics, as a quantum Turing machine (QTM) and

in 1993, Bernstein and Vazirani mathematically formalized the QTM. After that,some results

have indicated thattheQTMmaybe more powerfulthan ordinarycomputers.

In Chapter 2, wedescribe elementary denitionsand notations. We deneTuring machines

(TMs) that are standard theoretical models of computing devices. A QTM is dened based

on these mo dels. Since the execution of the QTM is evolved byunitary matrices, it is also a

modelof reversiblecomputation. Therefore, inthis chapter,wealso describ ethedenition ofa

reversibleTuringmachinethat wasproposed byBennett.

In Chapter 3, we review several models of quantum computers. A quantum computer was

rstlyproposedasaQTMbyDeutsch. Hisquantumcomputer,forthersttime,involvesinher-

ent properties of quantum physics asthecomputationalprinciples. Nowadays,manycomputer

scientists study the complexity and algorithms based on his model. However, since there are

other quantum computing models such as quantum circuits and quantum cellular automata,

we also describe these models briey. Finally, we summarize the realizabilities of quantum

computers.

InChapter4,wedenetypicalcomplexityclassesbasedonTMsandcomplexityclassesbased

on QTMs. Moreover,wealso showthe relationshipsb etweencomplexityclasses.

InChapter5,wediscussmethodstondthep eriodsoffunctionseciently. Sometechniques

forsolvingproblems ecientlyon QTMshave b eenprop osed. Especially,the mostwell-known

techniques, a quantum Fourier transform and a quantum iterating method, have b een used.

A quantum Fourier transform is a quantum version of discrete Fourier transforms and can

ecientlyobtain some prop erties of functions. By this technique, we showthat the perio ds in

somekindsofperiodicfunctions,f(x)=f(x+r) andx=f r

(x)forap eriodr,canbefound in

polynomialtimewith b ounded error probabilityon QTMs. Some of the functions proposed as

pseudo-random generatorsarealso included inthesefunctions.

InChapter 6, wediscuss quantumsearchalgorithmsfor a table search. A quantum iterating

method is a method to increase the probability of accepting states by using an algorithm re-

peatedly. By this technique,weshowthatforan unsortedtable T of nitems and aquery item

q, there is a quantum search algorithm that nds a pair of indices (j;k ) corresponding to two

successive items, T[j] and T[k], which satisfy that T[j] q T[k], in exp ected time O(n )

withbounded errorprobability. As aspecial case,this algorithm cannd the minimumor the

maximum value of T in exp ected time O (n 1=2

) with b ounded error probability. Moreover, we

alsoshowthatQTMscansolvesomeproblemsincomputationalgeometrymoreecientlythan

ordinarycomputers.

In Chapter 7, we investigate the relationships between the computational complexity and

quantum physics. Although NP-complete problems appear in manysituations, nobodyknows

whether ordinary computers can eciently solve these problems or not. On the other hand,

the problem of measurement is one of the most interesting problems in physics and nobo dy

can explain suciently what happens when we measure yet. Here, we propose the following

two assumptions on measurement: (i) Assumption 5

1

: a sup erposition of physical states is

preservedaftermeasurementsandallofthestatesinthesup erpositioncanbemeasuredintime

proportional tothenumberof thestatesinthesuperposition,and (ii)Assumption 5

2

: wecan

measure theexistence of a specic physicalstate C in a given superp osition with certainty in

polynomialtime ifthe stateC existsinthesuperp osition. Then,weshowthatthere isa QTM

thatsolvesthesatisabilityproblem(SAT)inO(2 n=4

)timeunderAssumption5

1

andthereisa

QTMthatsolvesSATinn O (1)

timeunderAssumption5

2

,wherenisthelengthof aninstance

of SAT.SATisa typicalNP-complete problem.

InChapter 8,wedenote someconcluding remarksand a futurework.

Finally,in AppendixA, we summarize thefundamentalparts of quantum physics needed to

understand quantumcomputers.

Key Words: quantum computation, quantum Turing machine, quantum com-

plexity class, periodic function, pseudo-random generator, quan-

tum search algorithm, NP-complete problem, satisability prob-

lem