The Бернштейн – Вазирани алгоритмішешеді Бернштейн – Вазирани проблемасы Бұл кванттық алгоритм ойлап тапқан Этан Бернштейн және Умеш Вазирани 1992 ж.[1] Бұл шектеулі нұсқасы Deutsch-Jozsa алгоритмі мұнда функциялардың екі түрлі кластарын ажыратудың орнына, ол функциямен кодталған жолды үйренуге тырысады.[2] Бернштейн-Вазирани алгоритмі дәлелдеуге арналған Oracle бөлу арасында күрделілік кластары BQP және BPP.[1]
Проблеманы шешу
Берілген Oracle функцияны жүзеге асыратын
онда
болып табылады уәде берді болу нүктелік өнім арасында
және құпия жіп
модуль 2,
, табу
.
Алгоритм
Классикалық түрде, құпия жолды табудың ең тиімді әдісі - бұл функцияны бағалау
рет қайда
,
[2]
![{ displaystyle { begin {aligned} f (1000 cdots 0_ {n}) & = s_ {1} f (0100 cdots 0_ {n}) & = s_ {2} f (0010 cdots) 0_ {n}) & = s_ {3} & , , , vdots f (0000 cdots 1_ {n}) & = s_ {n} end {aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a5cd6bf701e0b9076aa011de634746a448f4c14d)
Кем дегенде қажет классикалық шешімнен айырмашылығы
табу үшін функцияның сұраныстары
, кванттық есептеуді қолдану арқылы тек бір сұраныс қажет. Кванттық алгоритм келесідей: [2]
Қолдану а Хадамардтың өзгеруі дейін
кубит күйі
алу
![{ displaystyle { frac {1} { sqrt {2 ^ {n}}}} sum _ {x = 0} ^ {2 ^ {n} -1} | x rangle.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e97fee904c19e4fea87ec50004d2ae85626963f8)
Әрі қарай, оракулды қолданыңыз
түрлендіреді
. Мұны түрлендіретін стандартты оракул арқылы имитациялауға болады
осы оракулді қолдану арқылы
. (
қосудың екі модулін білдіреді.) Бұл суперпозицияны түрлендіреді
![{ displaystyle { frac {1} { sqrt {2 ^ {n}}}} sum _ {x = 0} ^ {2 ^ {n} -1} (- 1) ^ {f (x)} | x rangle.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff660e62e6a060c9f1a275fc8bc8c34a12264fe)
Әр кубитке тағы бір Хадамарды түрлендіру қолданылады, бұл оны кубиттер үшін қайда болады
, оның күйі түрлендіріледі
дейін
және кубиттер үшін қайда
, оның күйі түрлендіріледі
дейін
. Алу үшін
, өлшемі стандартты негіз (
) кубиттерде орындалады.
Графикалық түрде алгоритм келесі схемамен ұсынылуы мүмкін, мұндағы
Хадамардтың өзгеруін білдіреді
кубиттер:
![{ displaystyle | 0 rangle ^ {n} xrightarrow {H ^ { otimes n}} { frac {1} { sqrt {2 ^ {n}}}} sum _ {x in {0 , 1 } ^ {n}} | x rangle xrightarrow {U_ {f}} { frac {1} { sqrt {2 ^ {n}}}} sum _ {x in {0, 1 } ^ {n}} (- 1) ^ {f (x)} | x rangle xrightarrow {H ^ { otimes n}} { frac {1} {2 ^ {n}}} sum _ {x, y in {0,1 } ^ {n}} (- 1) ^ {f (x) + x cdot y} | y rangle = | s rangle}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fefd5d14347b32f33a83c32e64fc10b4334b168)
Соңғы күйдің себебі
өйткені, нақты үшін
,
![{ displaystyle { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} (- 1) ^ {f (x) + x cdot y} = { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} (- 1) ^ {x cdot s + x cdot y} = { frac {1} {2 ^ {n}}} sum _ {x in {0,1 } ^ {n}} (- 1) ^ {x cdot (s oplus y )} = 1 { text {if}} s oplus y = { vec {0}}, , 0 { text {әйтпесе}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/453b23dc62c24321e6cc8150618fec2f966c1692)
Бастап
болған кезде ғана дұрыс болады
, бұл тек нөлдік емес амплитуда қосулы дегенді білдіреді
. Сонымен, тізбектің шығуын есептеу негізінде өлшеу құпия жолды береді
.
Сондай-ақ қараңыз
Әдебиеттер тізімі