量子计算机简介

计算机可以算得更快吗?

可以，量子计算机

&比如：

-大数分解的指数算法和多项式算法

■“千僖难题”之一：P（多项式算法）问题

对NP（非多项式算法）问题

■在一个周六的晚上，你参加了一个盛大的

晚会。由于感到局促不安，你想知道这一大厅

中是否有你已经认识的人。你的主人向你提议

说，你一定认识那位正在甜点盘附近角落的女

士罗丝。不费一秒钟，你就能向那里扫视，并

且发现你的主人是正确的。然而，如果没有这

样的暗示，你就必须环顾整个大厅，一个个地

审视每一个人，看是否有你认识的人。生成问

题的一个解通常比验证一个给定的解时间花费

直观：算得快和慢2人x和O(lgx)

-目前：指数算法分解130位大数

-每秒10亿次的计算机

-循环10

素数两千年

C.F.Gauss

■1777-1855

Rottingen

Mathematicsisthe

queenofsciences,

andnumber

theoryisthe

crownof

mathematics.

Joseph.L.Lagrange

■1736-1813

①arts

■thegreatest

mathematicianofthe

eighteenthcentury

Torme,arithmeticisthe

mostdifficuCt.

C.GJ.Jacobi

1804-1851

Germany

themost

inspiringteacher

ofhistime

上帝是算术学

家

1数统治宇宙

Pythagoras

■Cs.560—

ca.480

Xt/iens

Intellectualone

ofthemost

importantmen

thatever[ive(f

Pythagoras

theratioscflengths

correspondingto

musicaCharmonies

Pythagoreans

provedthat72

isirrational.

*Prime素数

23,5,7,

11,13,17,19,..

15不是素数，因为15=3x5

素数是构成整数的基本元素

_TTIATTIQ

刘一02…Pr

2475=32X52X11

2素数的分布

素数似乎是随机分布的

素数的个数

击

0X

Thereareinfinitelymanyprimes

—>oo

71(x)一asx

Euclid

■325-270BC

Athens

Elements

thewoMsmost

definitivetext

ongeometry

SchoolofAthens

素数定理

(Gauss-Legendre1792)

X

7T（X）〜asx7

logx"

素数的密度=0

77（X）x/logX_1

>0.

XXlogX

C.F.Gauss

么出・Rottingen

■M3

kDEUISCHEBUNDESBANK

A.-M.Legendre

452-1833

Paris

T)iscipCecfEider

andLagrange

Heprovedthe

insofjvabidtyof

Fermat/last

theoremforn=5.

Chebyshev'sinequality

XX

0.99-——<7T（x）<1.11-——

logXlogX

P.Chebyshev

1821-1894

St.^Petersburg

3伟大的联系

V6erdie

JLnz佩der

(primzahCen

untereiner

gegebenen

Qrosse,1859

TheRiemannzeta-function

00

n=l

*Rieman—n证明

■Zeta-函数有无穷多个零点P：

久夕)=o.

■这些零点都在带形0WRe(s)Wl

内，且关于直线Re⑶=1/2对称。

IRiemann进一步证明

带形的边界上没有零点

「素数定理

TheRiemannHypothesis

Zeta-函数的零点

都在直线Re(s)=l/2上

▲

o

4素数定理的证明

Jacques.Hadamard

18^1963------

(Paris

provedtheprimenumber

t/ieoremindependently

cf"adee(Poussinin

1896

C.delaVallee

Poussin(1866-1962)

Belgianmathematician

whoprovedtheprime

numbertheorem

independentlyof

Hadamardin1896.

5Riemann假设

Hardy证明

有无穷多个零点落在直线

Re(s)=l/2上

,——

G.H.Hardy

1877-1947

J?Mathematicianfs

JLpofogy

7bprovethe

nonexistenceof

0。1

Seiberg证明

有b%的零点落在直线

Re(s)=l/2上

P——

Atle.Seiberg

TieCdsMedaCCist1950

^Princeton

InstituteforAdvance

Study,(Princeton

目前最好结果

有66%的零点落在直线

Re(s)=l/2上

月(Proofof丁heRiemannhypothesis

$1,000,000

6Goldbach猜想

4

L.Euler

1707~1783

St.(Petersburg

-31----------

C.Goldbach

1690-1764

1742,letterto

Euler

Goldbach

Goldbach猜想

ih——-—

■奇数

N=PI+PZ+P3,

■偶数

N=P1+A2・

A-Ya.Shinchin

bheQo[(f6acft

conjectureisa

pearConthe

crown.

偶数猜想=>奇数猜想

N-3=pi+p2.

7奇数Goldbach猜想

N=P\+P/P3・

解决!

■HardyLittlewood1921,

RiemannJiypotdesis

■Vinogradov1937,proved

>-----

G.H.Hardy

Cambridge

John.E.

Littlewood

Cambridge

EngGsfi

mathematicianwho

workeddose(ywith

J

LM.Vinogradov

1891-1983

Ste^Cov

Hi---------

Cartoonby

Vinogradov

Sowingthe

QoCdbacfiproblem

SolvingtheGoldbachproblem

8偶数Goldbach猜想

N41+42・

例外偶数的个数

1X

2

Goldbach=石(x)=1.

Huaetal1938

x

«声

i—例—外偶数密度二0

仆―-。,

x!2log"x

asxfoo.

Withhissiudcnt%(1080)

FrontrowI'MtTiengdong.LuQikvng,lliuLoo-Keng.('!)cnJinanin.VueMmyi

Secondio**l.iZhyifi,WanZlx.xiun.WuFnng,GongShcny.VuinW;mg

IhirdrnwChenDvquun.tulhw;ucn.J)Lilt

Montgomery&Vaughan1975

E(x)«x*5^8<1.

Chen&Pan1979

5=0.99.

潘承洞

>

与学生们在一起

陈景润

三

驾

马

车

Besttoday:Li2000

3=0.92.

Hardy&Littlewood1921

Riemann।〉$

Hypothesis—2

李红泽

>----

G.H.Hardy

&

J.E.

Littlewood

Cambridge

HardyandLittlewoodinNewCourt,TrinityCollege.

9敏锐的洞察力

Hilbert&Polya

ZerosoftheRiemann

zeta-functionarethe

eigenvaluesofsome

linearoperator.

GPolya

JB_____

TW5-1985

StanforcC

Mathematics

andpCausibCe

reasoning

J-Cungarian

immigrate

P.Sarnak&A.Seiberg,(Princeton

10狂想

Goldbach猜想的证明

(Princeton

A.Wiles

1953--

^Princeton

TermatfsLast

^Theorem1995

P.Fermat

1601-1665

PIERREDEFERMAT间】海5RF

育.7厘