Shor算法的量子物理基础(shor算法的基本原理和步骤)

摘  要   利用量子力学的叠加和纠缠等特性进行的量子计算事计算技术的巨大飞跃，它能够比经典计算远为有效地解决一些问题。例如最为著名的shor算法原则上能够以多项式的时间因子化大的合数，从而使得经典计算机难以计算的一些问题得以解决。本文通过对shor算法的基本原理和步骤的说明，来剖析shor算法的量子物理基础。
关键词   叠加原理   幺正变换   量子纠缠   量子傅立叶变换                                                                                                                                                  
THE QUANTUM PHYSICS BASIS OF SHOR’ALGORITHM
Abstract   By exploiting quantum mechanical features such as super-position and entanglement, quantum computing is a huge leap forward for computing technology. It can solve certain problems much more effectively than classical computing. For example,Shor’s algorithm could in principle factor large composite integers in polynomial time,thus solving a problem that classical computers still find difficult to calculate. This text passes to the calculate way of shor basic principle with the elucidation of the step, analyze the calculate way of shor quantum physics foundation.
Key words Superposition Principle        Quantum Entanglement                                
Quantum Fourier Transform

Shor算法
Shor在这个时候被提出来了。
求一大数N的因子可用一数p（0﹤p﹤ ）去除N，如果余数为0，则p为N的因子。这是原始的算法，计算的时间复杂度为O（   ），其中n为N的位数。经过数学家们多年的努力，到目前为止，最有效的传统算法的时间复杂度为O（exp[n1/3(lgn)2/3]）,如果N很大时，例如是129位数，在1994年曾用1600个工作站协同计算，8也月算出了N的因子。如果N有250位，用同样的计算环境，估计约需要80万年。1994年，Shor提出了大数因子分解的量子算法，如果在量子计算机上计算，求一个n为大数的两个质子的时间复杂度为   ，这是n的多项式。所以shor量子算法将NP问题变成P问题。

目    录
摘 要………………………………………………………………………………   1
Abstract…………………………………………………………………………… 1
第一章 引言……………………………………………………………………1
1.1  算法提出的背景…………………………………………………………… 1
1.1.1硬件发展的极限性……………………………………………………… 1 
1.1.2 NP问题  …………………………………………………………  2
第二章  Shor算法 ………………………………………………………………    2
2.1  简介………………………………………………………………………2
2.2  Shor算法的主要步骤……………………………………………………2
2.3  f(x) 周期的具体求解步骤…………………………………………… 3
2.4   求f(x)周期的例子………………………………………………… 5
第三章    Shor算法的量子物理基础…………………………………………  6
3．1 态叠加原理………………………………………………………………   6
3.1.1 量子态……………………………………………………………      6 
3.1.2  态叠加原理……………………………………………………………    7 
3．2 幺正变换…………………………………………………………………   8
3．3   纠缠态………………………………………………………………… 9
3．4   量子傅立叶变换………………………………………………………10
第四章 总结…………………………………………………………………… 12
参考文献…………………………………………………………………… 13