.RU

Предпосылки создания квантовых компьютеров


Квантовые компьютеры: мечты и реальность

Дмитрий Плохов. Доклад 19 октября 2005 года.
Предпосылки создания квантовых компьютеров


В настоящее время существует множество систем, в работе которых квантовые эффекты играют существенную роль. Одним из наиболее известных примеров может служить лазер, другим важным примером таких систем являются современные микросхемы.

В 1982 Фейнман пишет статью [1], в которой рассматриваются два вопроса:


  1. есть чисто логические ограничения на то, что можно вычислить (можно придумать задачу, для которой вообще нет алгоритма).

  2. Есть ли ограничения физические?


Фейнман показал, что термодинамических ограничений, типа второго начала термодинамики, нет. В этой же работе Фейнман обратил внимание на то, что если у нас имеется устройство квантовое, то возникают некоторые дополнительные возможности.

-------

Примечание

1970 - Ю.И. Манин две популярные книжки по логике – «Вычислимое и невычислимое» и «Доказуемое и недоказуемое», и в одной из них есть сюжет про квантовые автоматы, где он говорит о некоторых кардинальных отличиях этих автоматов от классических [2].

-----------------------------------------------

В середине восьмидесятых годов появились работы Дойча (D. Deutsch), Бернстайна и Вазирани (Е. Bernstein, U. Vazirani), Яo (A. Уао). В них были построены формальные модели квантового компьютера – например, квантовая машина Тьюринга [3–6].

Следующий этап – статья Шора (Р.W. Shor) 1994 года [7], вызвавшая лавинообразный рост числа публикаций о квантовых вычислениях. Шор построил квантовый (то есть реализуемый на квантовом компьютере) алгоритм факторизации (разложения целых чисел на множители – используется в том числе для вскрытия зашифрованных сообщений). Все известные алгоритмы для обычного компьютера – экспоненциальные (при числе разрядов порядка 300 время расчетов существенно превзойдет возраст Вселенной). Гарантией надежности большинства существующих шифров является именно сложность решения задачи факторизации. В квантовом компьютере эта задача имеет всего лишь кубическую сложность!


Математические основы функционирования квантовых компьютеров. Кубиты

Классический компьютер состоит, грубо говоря, из некоторого числа битов, с которыми можно выполнять арифметические операции. Основным элементом квантового компьютера (КК) являются квантовые биты, или кубиты (quantum bit = qubit). Обычный бит – это классическая система, у которой есть только два возможных состояния. Математически кубит – это двумерное комплексное пространство. В такой системе можно выполнять унитарные преобразования пространства состояний системы. С точки зрения геометрии такие преобразования – прямой аналог вращении и симметрий обычного трехмерного пространства.

Фазовое пространство КК есть тензорное произведение кубитов. Если в каждом кубите фиксирован базис (он будет состоять из двух векторов), то фазовое пространство – это комплексное линейное пространство, базис которого индексирован словами из нулей и единиц.


Нетривиальные задачи, реализуемые на квантовом компьютере (КК)

– задача разложения целых чисел на простые множители. Решил ее Шор в конце 1994 года. Независимо от него, Алексей Китаев из ИТФ им. Ландау построил квантовый алгоритм для этой и некоторых более общих задач [8]. Кубическое решение.

- вторая задача предложена Гровером (L. Grover) [9]. Поиск записи в базе данных, содержащих N записей. Для квантового компьютера достаточно числа запросов порядка корня из числа записей.

- моделирование самих квантовых систем (задача важна для химии, молекулярной биологии, физики).


Проблемы создания КК

Задача получения достоверного результата для обычных компьютеров решается просто за счет введения дополнительных битов. В случае КК эта проблема гораздо глубже. Сцепленные состояния – линейные комбинации базисных векторов фазового пространства. Биты находятся в некоем смешанном состоянии, причем согласованно-смешанном. Техническая сторона дела: в настоящий момент сообщения, что создаются реальные квантовые системы с небольшим числом битов (до семи). Для факторизации, чтобы вскрывать шифры, необходимо тысяча кубитов. Чтобы моделировать молекулу белка, нужно порядка ста тысяч кубитов.


Критерии Ди-Винченцо

Физической системе, реализующей квантовый компьютер, можно предъявить пять требований:

1. Система должна состоять из точно известного числа частиц.

2. Должна быть возможность привести систему в точно известное начальное состояние.

3. Степень изоляции от внешней среды должна быть очень высока.

4. Надо уметь менять состояние системы согласно заданной последовательности унитарных преобразований ее фазового пространства.

5. Необходимо иметь возможность выполнять «сильные измерения» состояния системы (то есть такие, которые переводят ее в одно из чистых состояний).

Из этих пяти задач наиболее трудными считаются третья и четвертая. От того, насколько точно они решаются, зависит точность выполнения операций. Пятая задача тоже весьма неприятна, так как измерить состояние отдельной частицы нелегко.


^ Физические реализации

- Ионы или атомы в лазерных ловушках.

- Электронные спины как кубиты


Заключение

He исключено, что в информационном обществе появление квантового компьютера сыграет ту же роль, что в свое время, в индустриальном, – изобретение атомной бомбы. Действительно, если последняя является средством «уничтожения материи», то первый может стать средством «уничтожения информации» – ведь очень часто то, что известно всем, не нужно никому 


Литература

1. Feynman R. Int. J. Theor. Phys. 21, 1982.

2. Манин Ю.И. Вычислимое и невычислимое. – М.: Советское радио, 1980.

3. Feynman R. Quantum mechanical computers. // Optics News, February 1985, 11, p.11.

4. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. – Proc. R. Soc. London A 400, 97, 1985.

5. Deutsch D. Quantum computational networks. – Proc. R. Soc. London A 425, 73, 1989.

6. Yao А. С.-С. Quantum circuit complexity. // Proceedings of the 34th Annual Symposium on the Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, p. 352.

7. Shor P.W. Algorithms for Quantum Computation: Discrete log and Factoring. // Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser, IEEE Computer Society Press, Los Alamitos, CA, 1994, p.124.

8. Китаев A.Ю. Квантовые вычисления: алгоритмы и исправление ошибок. // Успехи математических наук.

9. Grover L. A fast quantum mechanical algorithm for database search. // Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 1996, pp. 212-219.

10. Kitaev A.Yu. Quantum measurements and the Abelian stabilizer problem. – LANL e-print quant-ph/9511026, http://xxx.lanl.gov.

11. Shor P.W. Fault-Tolerant Quantum Computation. – LANL e-print quant-ph/9005011, http://xxx.lanl.gov.

12. Bennett С.Н., Bernstein E., Brassard G., Vazirany U. Strengths and Weaknesses of Quantum Computing. – LANL e-print quant-ph/9701001, http://xxx.lanl.gov, to appear in SIAM J. On Computing.

programma-disciplini-istoriya-ekonomicheskih-uchenij-dlya-napravleniya-040100-62-sociologiya-podgotovki-bakalavrov-avtor-d-e-n-g-d-gloveli-k-e-n-kalmichkova-e-n.html
programma-disciplini-istoriya-ekonomicheskih-uchenij-dlya-napravleniya-ekonomika-podgotovki-bakalavra-specialnosti-podgotovki-specialista.html
programma-disciplini-istoriya-filosofii-dlya-napravleniya-032700-62-filologiya-podgotovki-bakalavra-avtori-programmi.html
programma-disciplini-istoriya-finansovogo-prava-rossii-dlya-specialnosti-030501-65-yurisprudenciya-avtor-d-yu-n-prof-a-a-yalbulganov.html
programma-disciplini-istoriya-gosudarstva-i-prava-zarubezhnih-stran-021100-yurisprudenciya-stranica-3.html
programma-disciplini-istoriya-gosudarstvennosti-tatarstana-problemi-razvitiya.html
  • lecture.largereferat.info/4-organizaciya-proektirovaniya-i-zashita-proekta-metodicheskie-ukazaniya-po-kursovomu-proektirovaniyu-dlya-studentov.html
  • tasks.largereferat.info/3-1-obshie-trebovaniya-k-izlozheniyu-teksta.html
  • otsenki.largereferat.info/skazka-o-nauke-psihologii-prolegomeni-nikolaj-kozlov.html
  • spur.largereferat.info/lavrenova-g-v-lavrenov-v-k-stranica-4.html
  • tasks.largereferat.info/22-tematika-seminarskih-zanyatij-uchebno-metodicheskij-kompleks-po-etnologii-dlya-dnevnogo-otdeleniya-sostavitel-k-i-n-docent.html
  • exchangerate.largereferat.info/konduktometricheskij-metod-analiza-i-ego-ispolzovanie-v-analize-obektov-okruzhayushej-prirodnoj-sredi.html
  • kontrolnaya.largereferat.info/rabochaya-programma-po-anglijskomu-yaziku-dlya-7-klassa-na-2010-2011uchebnij-god.html
  • ucheba.largereferat.info/poryaz-a-vozrozhdenie-stranica-21.html
  • reading.largereferat.info/meropriyatiya-po-uhodu-i-zashite-plodovih-i-yagodnih-kultur-ot-vreditelej-boleznej-i-sornyakov.html
  • university.largereferat.info/eshil-y-525-456-gg-do-n-e-spravochnik-adresovan-shirokomu-krugu-chitatelej.html
  • nauka.largereferat.info/vibor-teploobmennika-chast-2.html
  • lecture.largereferat.info/63-marketingovaya-sluzhba-predpriyatiya-praktikum-po-marketingu-uchebnoe-posobie.html
  • abstract.largereferat.info/1125-teoriya-mezhdunarodnih-otnoshenij-vneshnyaya-politika-i-diplomatiya-gosudarstvennij-rubrikator-nauchno-tehnicheskoj.html
  • learn.largereferat.info/glava-iv-izbiratelnaya-tolpa-kniga-i-psihologiya-narodov-vvedenie.html
  • tasks.largereferat.info/1-mhametzhan-seralinn-mr-men-ataran-izmet.html
  • portfolio.largereferat.info/otchet-po-provedeniyu-vistavki-desant-zdorovya-i-krasoti.html
  • lektsiya.largereferat.info/posleslovie-o-svyazi-etogo-romana-s-ovodom-etel-lilian-vojnich.html
  • urok.largereferat.info/poslerodovie-ceremonii-indijskaya-predskazatelnaya-astrologiya.html
  • lecture.largereferat.info/bakalavrskaya-programma-kafedra-istorii-filosofii-napravlenie-filosofiya-disciplina-problema-cheloveka-v-kitajskoj-filosofii-status-disciplini.html
  • nauka.largereferat.info/v-ivanovskoj-oblasti-gotovyatsya-k-pavodku-internet-izdanie-regionsru-08022011.html
  • predmet.largereferat.info/ris-4-ideologiya-novih-obrazovatelnih-standartov-k-d-chermit-v-g-levchenko.html
  • holiday.largereferat.info/navigator-zonakznet-almati-12012012-v-ozhidanii-chernogo-dnya-monitoring-smi-rf-po-pensionnoj-tematike-13-yanvarya-2012-goda.html
  • laboratornaya.largereferat.info/razdel-iv-obosnovanie-nachalnoj-maksimalnoj-ceni-dogovora-statya-zakazchik-specializirovannaya-organizaciya.html
  • credit.largereferat.info/perspektivnij-plan-vospitatelno-obrazovatelnoj-raboti-v-podgotovitelnoj-k-shkole-gruppe-na-mesyac.html
  • uchitel.largereferat.info/programma-uchebnoj-disciplini-filosofiya-istorii-napravlenie.html
  • zanyatie.largereferat.info/mommzen-fuler-renan-annibal-yulij-cezar-mark-avrelij-stranica-2.html
  • kontrolnaya.largereferat.info/programma-razvitiya-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya-oktyabrskaya-srednyaya-obsheobrazovatelnaya-shkola-tomskogo-rajona-shkola-polnogo-dnya-stranica-3.html
  • esse.largereferat.info/rabochaya-programma-po-matematike-vklyuchaet-razdeli-poyasnitelnuyu-zapisku-soderzhanie-tem-uchebnogo-kursa-s-primernim-raspredeleniem-uchebnih-chasov-po-razdelam-kursa.html
  • znaniya.largereferat.info/rabochaya-programma-disciplini-teoriya-prinyatiya-reshenij-napravlenie-oop.html
  • college.largereferat.info/-1-ponyatie-i-vidi-prava-sobstvennosti-knigi-razdela-elektronnaya-biblioteka.html
  • kolledzh.largereferat.info/73-3311-praktikum-po-ekonomike-organizacii-i-byulleten-novih-postuplenij-uchebnoj-i-nauchnoj-literaturi-v-biblioteku.html
  • knigi.largereferat.info/sovremennie-metodi-optimizacii-pitaniya-zdorovogo-i-bolnogo-cheloveka-aktualnie-voprosi-pitaniya-naseleniya.html
  • prepodavatel.largereferat.info/tema-1-1-istoriya-ekonomicheskih-uchenij-predmet-i-metod-avtori-programmi-d-e-n-professor-holopov-a-v-k-e.html
  • assessments.largereferat.info/chast-tretya-k-sovetskim-chitatelyam.html
  • shpora.largereferat.info/yonovich-mineralogo-geohimicheskie-osobennosti-rudonosnih-metasomatitov-i-perspektivi-viyavleniya-kompleksnogo-blagorodnometallno-medno-nikelevogo-orudeneniya-v-belomorskom-podvizhnom-poyase.html
  • © LargeReferat.info
    Мобильный рефератник - для мобильных людей.