量子計(jì)算機(jī)簡介

計(jì)算機(jī)可以算得更快嗎?

可以，量子計(jì)算機(jī)

&比如：

-大數(shù)分解的指數(shù)算法和多項(xiàng)式算法

■“千僖難題”之一：P（多項(xiàng)式算法）問題

對NP（非多項(xiàng)式算法）問題

■在一個(gè)周六的晚上，你參加了一個(gè)盛大的

晚會。由于感到局促不安，你想知道這一大廳

中是否有你已經(jīng)認(rèn)識的人。你的主人向你提議

說，你一定認(rèn)識那位正在甜點(diǎn)盤附近角落的女

士羅絲。不費(fèi)一秒鐘，你就能向那里掃視，并

且發(fā)現(xiàn)你的主人是正確的。然而，如果沒有這

樣的暗示，你就必須環(huán)顧整個(gè)大廳，一個(gè)個(gè)地

審視每一個(gè)人，看是否有你認(rèn)識的人。生成問

題的一個(gè)解通常比驗(yàn)證一個(gè)給定的解時(shí)間花費(fèi)

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

-目前：指數(shù)算法分解130位大數(shù)

-每秒10億次的計(jì)算機(jī)

-循環(huán)10

素?cái)?shù)兩千年

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

上帝是算術(shù)學(xué)

家

1數(shù)統(tǒng)治宇宙

Pythagoras

■Cs.560—

ca.480

Xt/iens

Intellectualone

ofthemost

importantmen

thatever[ive(f

Pythagoras

theratioscflengths

correspondingto

musicaCharmonies

Pythagoreans

provedthat72

isirrational.

*Prime素?cái)?shù)

23,5,7,

11,13,17,19,..

15不是素?cái)?shù)，因?yàn)?5=3x5

素?cái)?shù)是構(gòu)成整數(shù)的基本元素

_TTIATTIQ

劉一02…Pr

2475=32X52X11

2素?cái)?shù)的分布

素?cái)?shù)似乎是隨機(jī)分布的

素?cái)?shù)的個(gè)數(shù)

擊

0X

Thereareinfinitelymanyprimes

—>oo

71(x)一asx

Euclid

■325-270BC

Athens

Elements

thewoMsmost

definitivetext

ongeometry

SchoolofAthens

素?cái)?shù)定理

(Gauss-Legendre1792)

X

7T（X）?asx7

logx"

素?cái)?shù)的密度=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偉大的聯(lián)系

V6erdie

JLnz佩der

(primzahCen

untereiner

gegebenen

Qrosse,1859

TheRiemannzeta-function

00

n=l

*Rieman—n證明

■Zeta-函數(shù)有無窮多個(gè)零點(diǎn)P：

久夕)=o.

■這些零點(diǎn)都在帶形0WRe(s)Wl

內(nèi)，且關(guān)于直線Re⑶=1/2對稱。

IRiemann進(jìn)一步證明

帶形的邊界上沒有零點(diǎn)

「素?cái)?shù)定理

TheRiemannHypothesis

Zeta-函數(shù)的零點(diǎn)

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

▲

o

4素?cái)?shù)定理的證明

Jacques.Hadamard

18^1963------

(Paris

provedtheprimenumber

t/ieoremindependently

cf"adee(Poussinin

1896

C.delaVallee

Poussin(1866-1962)

Belgianmathematician

whoprovedtheprime

numbertheorem

independentlyof

Hadamardin1896.

5Riemann假設(shè)

Hardy證明

有無窮多個(gè)零點(diǎn)落在直線

Re(s)=l/2上

,——

G.H.Hardy

1877-1947

J?Mathematicianfs

JLpofogy

7bprovethe

nonexistenceof

0。1

Seiberg證明

有b%的零點(diǎn)落在直線

Re(s)=l/2上

P——

Atle.Seiberg

TieCdsMedaCCist1950

^Princeton

InstituteforAdvance

Study,(Princeton

目前最好結(jié)果

有66%的零點(diǎn)落在直線

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——-—

■奇數(shù)

N=PI+PZ+P3,

■偶數(shù)

N=P1+A2?

A-Ya.Shinchin

bheQo[(f6acft

conjectureisa

pearConthe

crown.

偶數(shù)猜想=>奇數(shù)猜想

N-3=pi+p2.

7奇數(shù)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偶數(shù)Goldbach猜想

N41+42?

例外偶數(shù)的個(gè)數(shù)

1X

2

Goldbach=石(x)=1.

Huaetal1938

x

?聲

i—例—外偶數(shù)密度二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.

潘承洞

>

與學(xué)生們在一起

陳景潤

三

駕

馬

車

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厘