Квантавыя вылічэнні: падручнік

Сэмюэл Л. Браунштейн

Анатацыя:

У гэтым артыкуле мы дадзім падручнік пра тое, як квантавая механіка можа быць выкарыстана для паляпшэння разлікаў. Наша задача: рашэнне экспаненцыяльная складанай праблемай для звычайнага кампутара --- што факторынгу вялікае лік. У якасці прэлюдыі, мы разгледзім стандартныя сродкі вылічэнняў, універсальны брамы і машыны. Гэтыя ідэі, то прымяняецца ў першую чаргу да класічным, бездиссипативного кампутараў, а затым у квантавых кампутарах. Схематычна мадэль квантавай кампутара апісваецца, а таксама некаторыя тонкасці ў свае праграмы. Алгарытм Шора [ 1, 2 ] для эфектыўнага факторынгу нумары на квантавага кампутара складаецца з двух частак: квантавая працэдуры ў рамках алгарытму і класічны алгарытм, які выклікае квантавай працэдуры. Матэматычнай структуры, што робіць факторынг алгарытму Шора магчымая абмяркоўваецца. У заключэнне прагноз на магчымасці і перспектывы для квантавых вылічэнняў у бліжэйшыя гады.

Давайце пачнем з апісання праблемы на руку: факторынг лік N ў яго простых множнікаў (напрыклад, колькасць 51688 можа быць раскладзены як ). Зручны спосаб колькасна, як хутка прыватнасці алгарытм можа вырашыць праблемы спытаць, як шэраг крокаў для завяршэння алгарытму шалі з памерам уваходнага ``''алгарытму падаецца. Для факторынгу праблемы, гэта сігнал на ўсё лікі N мы хочам фактар, таму даўжыня ўваход . (Падстава лагарыфма вызначаецца нашай сістэмай нумарацыі;. Такім чынам база 2 дае даўжынёй у двайковай базы 10 у дзесятковай.) "Разумны" алгарытмы з'яўляюцца тыя, якія маштабу, як невялікі ступені паліном памеру ўваходных дадзеных (са ступенню, магчыма, 2 ці 3).

На звычайных кампутарах самы вядомы алгарытм факторынг працуе ў крокаў [ 3 ]. Гэты алгарытм, таму, шалі экспаненцыяльная з уваходнай памер . Напрыклад, у 1994 годзе 129 лічбаў (вядомы як RSA129 [ 3 ' ]) быў паспяхова ўлічаны выкарыстаннем гэтага алгарытму на каля 1600 рабочых станцый раскіданых па ўсім свеце; за ўсё факторизации спатрэбілася восем месяцаў [ 4 ]. З дапамогай гэтай ацэнкі префактора з вышэй экспаненцыяльная маштабавання, мы знаходзім, што гэта зойме прыкладна 800000 гадоў фактар ??250 знакавым лікам, з той жа магутнасці кампутара, аналагічна 1000 значны нумар запатрабуе гадоў (значна Lon Германіі, чым ўзрост Сусвету). Цяжкасць факторизации вялікіх лікаў вырашальнае значэнне для криптосистем з адкрытым ключом, такія, як тыя, якія выкарыстоўваюцца банкамі. Там, такіх кодаў спадзявацца на цяжкасці факторынгу нумары з каля 250 лічбаў.

Нядаўна, алгарытм быў распрацаваны для факторынгу нумары на квантавай кампутары, якая праходзіць у крокаў, дзе мала [ 1 ]. Гэта прыкладна ў квадратычнай памеру ўваходных дадзеных, таму факторынг 1000 значны нумар з такой алгарытм будзе патрабаваць толькі некалькі мільёнаў крокаў. Маецца на ўвазе, што адкрыты ключ крыптасістэмы на аснове факторынгу можа быць далікатным.

Каб даць вам прадстаўленне аб тым, як гэта экспанентныя паляпшэнне можа быць магчыма, мы разгледзім элементарны квант механічнага эксперымент, які паказвае, дзе такая ўлада можа схаваныя [ 5 ]. Двух шчылін эксперымент прототипных для назірання квантавых механічнага паводзінаў: крыніца выпускае фатоны, электроны і іншыя часціцы, якія прыйшлі на пару шчылін. Гэтыя часціцы праходзяць унітарнае эвалюцыі і, нарэшце, вымярэння. Мы бачым інтэрферэнцыйную карціну, як з разрэзамі адкрытай, якая знікае, калі wholely альбо шчыліны пакрытая. У пэўным сэнсе, часціцы праходзяць праз абедзве шчыліны паралельна. Калі такі унітарнае эвалюцыі павінны былі прадстаўляць разлік (або аперацыі ў разлік), то квантавая сістэма будзе выконваць вылічэнні паралельна. Квантавы паралелізм пастаўляецца бясплатна. Выхад з гэтай сістэмы будзе прадастаўлена па канструктыўнай інтэрферэнцыі паміж паралельных вылічэнняў.

• Вылічальны на атамным узроўні:
• Рэверсіўныя вылічэнняў:
• Класічныя універсальныя машыны і лагічных вентыляў:
• Разгалінаваная і выдаліць:
• Вылічэнне без ERASE:
• Элементарны квант абазначэння:
• Лагічныя вентылі для квантавых бітаў:
• Мадэль квантавых кампутараў і квантавай код:
• Квантавы паралелізм: Перыяд паслядоўнасці:
• Факторынг нумары:
• Перспектывы:
• Дадатак:
• Падзякі:
• Спіс літаратуры
• Аб гэтым дакуменце...