Передумови створення квантових ком’ютерів

Главная » Каталог статей » Статьи на украинском » Квантовий комп’ютер » Передумови створення квантових ком’ютерів

3fbac11617017b097779192c225bc948_full

Вже зараз існує безліч систем, в роботі яких квантові ефекти виконують істотну роль. Одним з найвідоміших прикладів є лазер: поле його випромінювання породжується квантово-механічними подіями — спонтанним і індукованим випромінюванням світла. Іншим важливим прикладом таких систем є сучасні мікросхеми — безперервне посилювання проектних норм приводить до того, що квантові ефекти починають виконувати в їх поведінці істотну роль. У діодах Ганна виникають осциляції електронних струмів, в напівпровідниках утворюються зонні структури: електрони або дірки в різних замкнутих станах можуть зберігати інформацію, а один або декілька електронів можуть бути замкнуті в так званих квантових ямах.

Зараз ведуться розробки нового класу квантових пристроїв — квантових комп’ютерів. Ідея квантового комп’ютера виникла так…

Все почалося в 1982 році, коли Фейнман написав дуже цікаву статтю [119], в якій розглянув два питання. Він підійшов до процесу обчислення як фізик: є чисто логічні обмеження на те, що можна обчислити (можна придумати задачу, для якої взагалі немає алгоритму, можна придумати задачу, для якої будь-який алгоритм довго працюватиме). А чи є обмеження фізичні? Ось є закон збереження енергії — вічний двигун неможливий; а чи є яке-небудь фізичне обмеження на функціонування комп’ютера, яке накладає якісь заборони на можливість реалізації алгоритмів? І. Фейнман показав, що термодинамічних обмежень, таких як другий закон термодинаміки, немає. Якщо ми зменшуватимемо втрати енергії, шуми, то ми можемо зробити скільки завгодно довгі обчислення із скільки завгодно малими витратами енергії. Це означає, що обчислення можна зробити оборотним чином — тому що в необоротних процесах ентропія зростає. Власне, Фейнмана це і зацікавило: адже реальне обчислення на реальному комп’ютері необоротне. І одержаний ним результат полягає у тому, що можна так переробити будь-яке обчислення — без особливої втрати ефективності, — щоб воно стало оборотним. Ті обчислення, які робляться «просто так», звичайно, необоротні, але «зростання необоротності» досить мале у порівнянні, скажімо, із шумами в сучасному комп’ютері. Тобто необоротність — це тонкий ефект; тут питання не практичне а принципове: якщо уявити собі, що технологія дійде до такого рівня, що цей ефект стане істотним, то можна так перебудувати обчислення, щоб добитися оборотності.

І в цій же роботі Фейнман звернув увагу на те, що якщо у нас є пристрій квантовий, тобто такий, який підкоряється законам квантової механіки, то його обчислювальні можливості абсолютно не обов’язково повинні збігатися з можливостями звичайного пристрою. Виникають деякі додаткові можливості. Але поки незрозуміло, дозволяють вони одержати якийсь виграш чи ні. Фактично він і поставив своєю статтею таке питання.

До речі, Ю.І. Манін в кінці сімдесятих років написав дві відомі книжки з логіки — «Вычислимое и невычислимое» і «Доказуемое и недоказуемое», і в одній з них є сюжет про квантові автомати, де він говорить про деякі кардинальні відмінності цих автоматів від класичних [120].

У середині вісімдесятих років з’явилися роботи Дойча (D. Deutsch), Бернстайна і Вазірані (Е. Bernstein, U. Vazirani), Яo (А. Уао). У них були побудовані формальні моделі квантового комп’ютера — наприклад, квантова машина Тюрінга [121-124].

Наступний етап — стаття Шора (Р.W. Shor) 1994 року [125], що викликала лавиноподібне зростання числа публікацій про квантові обчислення. Шор побудував квантовий (тобто реалізований на квантовому комп’ютері) алгоритм факторизації (розкладання цілих чисел на множники — використовується зокрема для розкриття зашифрованих повідомлень). Всі відомі алгоритми для звичного комп’ютера — експоненціальні (час їх роботи зростає як експонента від числа знаків в записі числа, яке факторизується). Факторизація 129-розрядного числа вимагала б 500 MIPS-років, або вісім місяців безперервної роботи системи з 1600 робочих станцій, об’єднаних через Інтернет. А при числі розрядів порядку 300 цей час істотно перевершить вік Всесвіту — навіть якщо працювати одночасно на всіх існуючих в світі машинах. Вважається (хоча це і не доведено!), що швидкого алгоритму рішення цієї задачі не існує. Більш того, гарантією надійності більшості існуючих шифрів є саме складність рішення задачі факторизації або однієї із споріднених їй теоретико-числових задач, наприклад — дискретного логарифма. І раптом з’ясовується, що на квантовому комп’ютері ця задача має всього лише кубічну складність. Перед квантовим комп’ютером класичні банківські, військові і інші шифри миттєво втрачають усяку цінність. Коротше кажучи, робота Шора показала, що вся ця вишукана академічна діяльність безпосередньо торкається такої первісної стихії, як гроші. Після цього і почалася справжня популярність…

Втім, з’ясовується, що не тільки класична, але і квантова криптографія (наука про шифрування повідомлень) часто не здатна протистояти квантовій криптоаналітиці (науці про розшифровку). Деякі важливі криптографічні протоколи, такі як «підкидання монети по телефону», руйнуються при переході до квантових обчислень. Точніше, гарантією їх надійності є відтепер не складність тих або інших алгоритмів, а складність задачі створення квантового комп’ютера.

Таким чином виникає нова галузь обчислень – квантові обчислення. Квантові обчислення (КО) — це, як можна здогадатися, обчислення на квантовому комп’ютері. Квантових комп’ютерів на світі поки немає. Більш того, дотепер неясно, коли з’являться практично корисні конструкції і чи з’являться взагалі. Проте, квантові обчислення — предмет, надзвичайно модний зараз в математиці і фізиці, як теоретичний, так і експериментальний, і займається ним досить багато людей. Судячи з усього, саме інтерес стимулював першопрохідців — Річарда Фейнмана, що написав піонерську роботу, в якій ставилося питання про обчислювальні можливості пристроїв на квантових елементах; Девіда Дойча, що формалізував це питання в рамках сучасної теорії обчислень; і Пітера Шора, що придумав перший нетривіальний квантовий алгоритм.

Оставьте комментарий к статье