計(jì)算機(jī)科學(xué)中若干難解問(wèn)題的量子算法研究.pdf

1、摘 要計(jì)算機(jī)科學(xué)中的難解問(wèn)題是計(jì)算機(jī)算法和計(jì)算機(jī)理論界長(zhǎng)期研究的 課題， 它們大都具有深刻的應(yīng)用背景。 量子算法是一種新的 計(jì)算方法， 利用量子力學(xué)的迭加和糾纏等特性進(jìn)行的量子計(jì)算是計(jì)算技術(shù)的巨 大飛躍， 它能夠比 經(jīng)典 計(jì)算遠(yuǎn)為 有效地解決一些問(wèn) 題。 其中 最為著名的S h o r 的算法， 原則上能夠以多 項(xiàng)式的 時(shí)間因子化大的合數(shù)， 從而使得經(jīng)典計(jì)算機(jī)難以 計(jì)算的這一問(wèn) 題得以 解決。因此我們可以 考慮用量子計(jì)算技術(shù)來(lái)求解某些計(jì)

2、算機(jī)科學(xué)中的 N P難解問(wèn) 題， 本文正是 利用這種方法來(lái)求解某些典型的 N P難解問(wèn) 題， 并證明了 這樣做的確是可行和非常有效的。 今 文 圍 繞 計(jì) 算 機(jī) 科 學(xué) 中 若 干 難 解 問(wèn) 題 的 量 子 M A 進(jìn) 行 了 研 究 ， 主要做了以 下幾方面的工作:1 )介紹了研究量子信息學(xué)所必需的量子力學(xué)基本知識(shí)， 包括量子力學(xué)的五大假設(shè)， 特別是 H i l b e r t 空間， 量子態(tài)( 位) 的表示， 厄米算子和么 正變

3、換及其矩陣 表示。同時(shí)還介紹了 量子力學(xué)基本的哲學(xué)思 想， 各種量子測(cè)量方法。2 )研究了 量子計(jì)算機(jī)的概念和目 前的發(fā)展情況， 指出 其具體構(gòu)造， 幾種試驗(yàn)方案和與經(jīng)典計(jì)算機(jī)相比 較的優(yōu)越性。 敘述了 量子算法是在量子計(jì)算機(jī)上的具體操作和實(shí)現(xiàn)過(guò)程， 同時(shí) 指出 量子計(jì)算機(jī)目 前的困難及可能的解決方法。AB S T ARCT、N P h a r d p r o b l e m s a r e f a m o u s p r o

4、 b l e m s i n c o m p u t e r s c i e n c e .Q u a n t u m c o m p u t i n g i s v e r y n e w c o m p u t i n g t e c h n o l o g y , b y e x p l o i t i n gq u a n t u m m e c h a n i c a l f e a t u r e

5、s s u c h a s s u p 一, , w i t i o i i a n d e n t a n g l e m e n t ,q u a n t u m c o m p u t i n g i s a h u g e l e a p f o r w a r d f o r c o m p u t i n g t e c h n o l o g y . I tc a n s o l v e

6、 c e r t a i n p r o b l e m s m u c h m o r e e f e c t i v e l y t h a n c l a s s i c a lc o m p u t i n g . F o r e x a m p l e , S h o r ' s a l g o r i t h m c o u l d i n p r i n c i p l e f a c

7、t o r l a r g ec o m p o s i t e i n t e g e r s i n p o l y n o m i a l t i m e , t h u s s o l v i n g a p r o b l e m t h a tc l a s s i c a l c o m p u t e r s s t i l l f i n d d i f f i c u l t t o

8、c a l c u l a t e . A n i n t r o d u c t i o n i sg i v e n t o t h e f u n d a m e n t a l p r i n c i p l e s a n d p r o c e s s e s o f t h e m a i n q u a n t u ma l g o r i t h m s d i s c o v e r e

9、d s o f a r . T h e a d v a n t a g e s , c u r r e n t p r o g r e s s a n d f u t u r ep r o s p e c t s o f q u a n t u m c o m p u t i n g a r e m e n t i o n e d .T h i s p a p e r i n t r o d u c e s

10、 s o m e b a s i c k n o w l e d g e a b o u t a l g o r i t h m a n d N Ph a r d p r o b l e m s . I p u t o u t n e w q u a n t u m a l g o r i t h m s f o r 0 / 1 k n a p s a c kp r o b l e m a n d

11、i n t e g e r - p r o g r a m m i n g p r o b l e m . I n t h e o r y , w e c a n s o l v e t h e s eN P h a r d p r o b l e m s o n q u a n t u m c o m p u t e r . M y p a p e r g i v e s a q u a n t u

12、mm e c h a n i c a l a l g o r i t h m t o s o l v e 0 / 1 - k n a p s a c k p r o b l e m a n d i n t e g e r -p r o g r a m m i n g p r o b l e m , w h i c h i s b a s e d o n G r o v e r a l g o r i t h

13、m a n d q u a n t u me x p o n e n t i a l s e a r c h i n g a l g o r i t h m . T h e a l g o r i t h m d o e s n ' t i n v o l v e a n yc l a s s i c a l m e t h o d t o i m p r o v e s e a r c h e f