計算機科學中若干難解問題的量子算法研究.pdf

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

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

3、換及其矩陣 表示。同時還介紹了 量子力學基本的哲學思 想， 各種量子測量方法。2 )研究了 量子計算機的概念和目 前的發(fā)展情況， 指出 其具體構造， 幾種試驗方案和與經(jīng)典計算機相比 較的優(yōu)越性。 敘述了 量子算法是在量子計算機上的具體操作和實現(xiàn)過程， 同時 指出 量子計算機目 前的困難及可能的解決方法。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