![EITC-QI-QIF](https://eitca.org/wp-content/uploads/2015/10/EITC-QI-QIF-420x280_c.jpg)
EITC/QI/QIF Quantum Information Fundamentals — це європейська програма сертифікації ІТ з теоретичних і практичних аспектів квантової інформації та квантових обчислень, заснована на законах квантової фізики, а не на класичній фізики, і пропонує якісні переваги перед їх класичними аналогами.
Навчальна програма EITC/QI/QIF Quantum Information Fundamentals охоплює введення в квантову механіку (включаючи розгляд експерименту з подвійними щілинами та інтерференції хвиль матерії), введення в квантову інформацію (кубіти та їх геометричне представлення), поляризацію світла, принцип невизначеності, квант заплутаність, парадокс EPR, порушення нерівності Белла, відмова від локального реалізму, квантова обробка інформації (включаючи унітарне перетворення, однокубітні та двокубітні вентилі), теорема про відсутність клонування, квантова телепортація, квантове вимірювання, квантові обчислення (включаючи введення в мультикубітні -кубітні системи, універсальне сімейство вентилів, оборотність обчислень), квантові алгоритми (включаючи квантове перетворення Фур'є, алгоритм Саймона, розширену тезу Черха-Тьюринга, алгоритм квантового факторингу Шорка, алгоритм квантового пошуку Гровера, квантовий алгоритм спостережуваних квантів), Реалізація кубітів, квантова теорія складності, адіабатичні квантові обчислення ion, BQP, введення в спін, у наведеній нижче структурі, що включає повний відеодидактичний вміст як довідник для цієї сертифікації EITC.
Квантова інформація — це інформація про стан квантової системи. Це основний предмет дослідження в теорії квантової інформації, і ним можна маніпулювати, використовуючи методи квантової обробки інформації. Квантова інформація відноситься як до технічного визначення в термінах ентропії фон Неймана, так і до загального обчислювального терміна.
Квантова інформація та обчислення – це міждисциплінарна галузь, яка включає в себе квантову механіку, інформатику, теорію інформації, філософію та криптографію серед інших областей. Його вивчення також має відношення до таких дисциплін, як когнітивна наука, психологія та нейронаука. Його головне зосереджено на вилученні інформації з матерії в мікроскопічному масштабі. Спостереження в науці є фундаментальним відмінним критерієм реальності і одним з найважливіших способів отримання інформації. Тому вимірювання потрібне для кількісної оцінки спостереження, що робить його вирішальним для наукового методу. У квантовій механіці через принцип невизначеності некоммутовані спостережувані не можна точно виміряти одночасно, оскільки власний стан в одному базисі не є власним станом в іншому базисі. Оскільки обидві змінні не є одночасно чітко визначеними, квантовий стан ніколи не може містити остаточну інформацію про обидві змінні. Через цю фундаментальну властивість вимірювання в квантовій механіці цю теорію можна загалом охарактеризувати як недетерміновану на відміну від класичної механіки, яка повністю детермінована. Індетермінізм квантових станів характеризує інформацію, визначену як стани квантових систем. У математичному плані ці стани знаходяться в суперпозиціях (лінійних комбінаціях) станів класичних систем.
Оскільки інформація завжди закодована в стані фізичної системи, вона сама по собі є фізичною. У той час як квантова механіка займається вивченням властивостей матерії на мікроскопічному рівні, квантова інформаційна наука зосереджується на вилученні інформації з цих властивостей, а квантові обчислення маніпулюють і обробляють квантову інформацію – виконують логічні операції – використовуючи методи квантової обробки інформації.
Квантову інформацію, як і класичну інформацію, можна обробляти за допомогою комп’ютерів, передавати з одного місця в інше, маніпулювати за допомогою алгоритмів і аналізувати за допомогою інформатики та математики. Так само, як основною одиницею класичної інформації є біт, квантова інформація має справу з кубітами, які можуть існувати в суперпозиції 0 і 1 (одночасно є певною мірою істинним і хибним). Квантова інформація також може існувати в так званих заплутаних станах, які виявляють чисто некласичні нелокальні кореляції у своїх вимірюваннях, що дозволяє застосувати такі засоби, як квантова телепортація. Рівень заплутаності можна виміряти за допомогою ентропії фон Неймана, яка також є мірою квантової інформації. Останнім часом область квантових обчислень стала дуже активною дослідницькою сферою через можливість порушити сучасні обчислення, комунікацію та криптографію.
Історія квантової інформації почалася на рубежі 20-го століття, коли класична фізика перетворилася на квантову. Теорії класичної фізики передбачали такі абсурди, як ультрафіолетова катастрофа або електрони, що спіралі в ядро. Спочатку ці проблеми були відкинуті, додавши до класичної фізики спеціальні гіпотези. Незабаром стало очевидним, що для того, щоб зрозуміти ці абсурди, необхідно створити нову теорію, і народилася теорія квантової механіки.
Квантова механіка була сформульована Шредінгером за допомогою хвильової механіки, а Гейзенбергом — за допомогою матричної механіки. Пізніше була доведена рівноцінність цих методів. Їх формулювання описували динаміку мікроскопічних систем, але мали кілька незадовільних аспектів в описі процесів вимірювання. Фон Нейман сформулював квантову теорію за допомогою операторної алгебри таким чином, що вона описує вимірювання, а також динаміку. Ці дослідження акцентували увагу на філософських аспектах вимірювання, а не на кількісному підході до отримання інформації за допомогою вимірювань.
У 1960-х роках Стратонович, Гельстром і Гордон запропонували формулювання оптичних зв'язків з використанням квантової механіки. Це була перша історична поява квантової теорії інформації. В основному вони вивчали ймовірність помилок і пропускну здатність каналу зв'язку. Пізніше Холево отримав верхню межу швидкості зв’язку при передачі класичного повідомлення по квантовому каналу.
У 1970-х роках почали розроблятися методи маніпулювання одноатомними квантовими станами, такі як атомна пастка і скануючий тунельний мікроскоп, що дає змогу виділяти окремі атоми та упорядковувати їх у масиви. До цих розробок точний контроль над одиничними квантовими системами був неможливим, і в експериментах використовувався більш грубий, одночасний контроль над великою кількістю квантових систем. Розвиток життєздатних методів маніпулювання з одним станом привів до зростання інтересу до області квантової інформації та обчислень.
У 1980-х роках виник інтерес до того, чи можна використовувати квантові ефекти для спростування теорії відносності Ейнштейна. Якби можна було клонувати невідомий квантовий стан, можна було б використовувати заплутані квантові стани для передачі інформації швидше, ніж швидкість світла, що спростовує теорію Ейнштейна. Проте теорема про відсутність клонування показала, що таке клонування неможливе. Теорема була одним із перших результатів квантової теорії інформації.
Розробка з криптографії
Незважаючи на все хвилювання та інтерес до вивчення ізольованих квантових систем і спроб знайти спосіб обійти теорію відносності, дослідження в області квантової теорії інформації зайшли в застій у 1980-х роках. Однак приблизно в той же час до квантової інформації та обчислень почав займатися інший напрямок: криптографія. У загальному сенсі криптографія — це проблема здійснення комунікації або обчислень за участю двох або більше сторін, які можуть не довіряти одна одній.
Беннет і Брассард розробили канал зв'язку, за яким неможливо підслуховувати, не будучи виявлений, спосіб таємного спілкування на великих відстанях за допомогою квантового криптографічного протоколу BB84. Ключовою ідеєю було використання фундаментального принципу квантової механіки, згідно з яким спостереження заважає спостережуваному, а введення підслуховувача в захищену лінію зв’язку відразу дозволить двом сторонам, які намагаються спілкуватися, знати про присутність підслуховувача.
Розвиток з інформатики та математики
З появою революційних ідей Алана Тьюринга про програмований комп’ютер, або машину Тьюринга, він показав, що будь-які реальні обчислення можна перевести в еквівалентні обчислення з використанням машини Тьюринга. Це відомо як теза Черча-Тюрінга.
Досить скоро були створені перші комп’ютери, і комп’ютерне обладнання росло такими швидкими темпами, що зростання, завдяки досвіду виробництва, було кодифіковано в емпіричний зв’язок, який називається законом Мура. Цей «закон» є проективною тенденцією, яка стверджує, що кількість транзисторів в інтегральній схемі подвоюється кожні два роки. Оскільки транзистори почали ставати все менше і менше, щоб упакувати більше потужності на площу поверхні, квантові ефекти почали проявлятися в електроніці, що призвело до ненавмисних перешкод. Це призвело до появи квантових обчислень, які використовували квантову механіку для розробки алгоритмів.
На цьому етапі квантові комп’ютери обіцяли бути набагато швидшими за класичні комп’ютери для вирішення певних конкретних проблем. Одну з таких прикладів задачі розробили Девід Дойч і Річард Йозса, відомий як алгоритм Дойча–Йозса. Однак ця проблема практично не мала практичного застосування. Пітер Шор у 1994 році поставив дуже важливу і практичну проблему, одну з пошуків простих множників цілого числа. Проблему дискретного логарифма, як її називали, можна було ефективно вирішити на квантовому комп’ютері, але не на класичному комп’ютері, що показує, що квантові комп’ютери потужніші за машини Тьюринга.
Розвиток з теорії інформації
Приблизно в той час, коли інформатика робила революцію, так само, як і теорія інформації та комунікація через Клода Шеннона. Шеннон розробив дві фундаментальні теореми теорії інформації: теорему безшумного канального кодування і теорему кодування зашумленого каналу. Він також показав, що коди виправлення помилок можуть використовуватися для захисту інформації, що надсилається.
Квантова теорія інформації також йшла за схожою траєкторією, Бен Шумахер у 1995 році зробив аналог теореми безшумного кодування Шеннона, використовуючи кубіт. Також була розроблена теорія виправлення помилок, яка дозволяє квантовим комп’ютерам здійснювати ефективні обчислення незалежно від шуму та здійснювати надійний зв’язок через шумні квантові канали.
Кубіти та теорія інформації
Квантова інформація сильно відрізняється від класичної інформації, уособленої бітом, багатьма вражаючими і незнайомими способами. Хоча основною одиницею класичної інформації є біт, найосновнішою одиницею квантової інформації є кубіт. Класична інформація вимірюється за допомогою ентропії Шеннона, тоді як квантовомеханічний аналог — ентропія фон Неймана. Статистичний ансамбль квантовомеханічних систем характеризується матрицею густини. Багато мір ентропії в класичній теорії інформації також можна узагальнити на квантовий випадок, наприклад, ентропію Холево та умовну квантову ентропію.
На відміну від класичних цифрових станів (які є дискретними), кубіт є безперервним значенням, описуваним напрямком на сфері Блоха. Незважаючи на безперервну оцінку таким чином, кубіт є найменшою можливою одиницею квантової інформації, і незважаючи на те, що стан кубіта є безперервним, неможливо точно виміряти значення. П'ять відомих теорем описують обмеження маніпулювання квантовою інформацією:
- теорема про відсутність телепортації, яка стверджує, що кубіт не може бути (повністю) перетворений у класичні біти; тобто його неможливо повністю «прочитати»,
- теорема про відсутність клонування, яка запобігає копіюванню довільного кубіта,
- теорема без видалення, яка запобігає видаленню довільного кубіта,
- теорема про заборону трансляції, яка запобігає доставці довільного кубіта кільком одержувачам, хоча його можна транспортувати з місця на місце (наприклад, за допомогою квантової телепортації),
- теорема про відсутність приховування, яка демонструє збереження квантової інформації.Ці теореми доводять, що квантова інформація у Всесвіті зберігається, і відкривають унікальні можливості в обробці квантової інформації.
Квантова обробка інформації
Стан кубіта містить всю його інформацію. Цей стан часто виражається у вигляді вектора на сфері Блоха. Цей стан можна змінити, застосувавши до них лінійні перетворення або квантові вентилі. Ці унітарні перетворення описуються як обертання на блохівській сфері. У той час як класичні вентилі відповідають знайомим операціям булевої логіки, квантові вентилі є фізичними унітарними операторами.
Через мінливість квантових систем і неможливість копіювання станів зберігання квантової інформації набагато складніше, ніж зберігання класичної інформації. Тим не менш, із застосуванням квантової корекції помилок квантова інформація все ще може надійно зберігатися в принципі. Існування квантових кодів для виправлення помилок також призвело до можливості відмовостійких квантових обчислень.
Класичні біти можуть бути закодовані і згодом отримані з конфігурацій кубітів за допомогою квантових вентилів. Сам по собі один кубіт може передати не більше одного біта доступної класичної інформації про його приготування. Це теорема Холево. Однак у надщільному кодуванні відправник, діючи на один із двох заплутаних кубітів, може передати одержувачу два біти доступної інформації про їхній спільний стан.
Квантова інформація може переміщатися по квантовому каналу, аналогічно концепції класичного каналу зв’язку. Квантові повідомлення мають кінцевий розмір, що вимірюється в кубітах; квантові канали мають кінцеву пропускну здатність каналу, що вимірюється в кубітах в секунду.
Квантова інформація та зміни в квантовій інформації можуть бути кількісно виміряні за допомогою аналога ентропії Шеннона, який називається ентропією фон Неймана.
У деяких випадках квантові алгоритми можна використовувати для виконання обчислень швидше, ніж будь-який відомий класичний алгоритм. Найвідомішим прикладом цього є алгоритм Шора, який може розкласти числа за поліноміальний час, порівняно з найкращими класичними алгоритмами, які використовують субекспоненційний час. Оскільки факторізація є важливою частиною безпеки шифрування RSA, алгоритм Шора розпочав нову область постквантової криптографії, яка намагається знайти схеми шифрування, які залишаються безпечними, навіть коли в грі працюють квантові комп’ютери. Інші приклади алгоритмів, які демонструють квантову перевагу, включають пошуковий алгоритм Гровера, де квантовий алгоритм дає квадратичне прискорення порівняно з найкращим можливим класичним алгоритмом. Клас складності задач, які ефективно розв’язуються квантовим комп’ютером, відомий як BQP.
Квантовий розподіл ключів (QKD) дозволяє безумовно безпечну передачу класичної інформації, на відміну від класичного шифрування, яке завжди можна зламати в принципі, якщо не на практиці. Зауважте, що деякі тонкі моменти щодо безпеки QKD досі гаряче обговорюються.
Дослідження всіх перерахованих вище тем і відмінностей включає в себе квантову теорію інформації.
Відношення до квантової механіки
Квантова механіка вивчає, як мікроскопічні фізичні системи динамічно змінюються в природі. У галузі квантової теорії інформації досліджувані квантові системи абстрагуються від будь-якого аналога в реальному світі. Кубіт, наприклад, фізично може бути фотоном у лінійно-оптичному квантовому комп’ютері, іоном у затриманому іонному квантовому комп’ютері, або це може бути велика сукупність атомів, як у надпровідному квантовому комп’ютері. Незалежно від фізичної реалізації, обмеження та особливості кубітів, передбачені квантовою теорією інформації, зберігаються, оскільки всі ці системи математично описуються одним і тим же апаратом матриць щільності над комплексними числами. Ще одна важлива відмінність від квантової механіки полягає в тому, що, хоча квантова механіка часто вивчає нескінченновимірні системи, такі як гармонічний осцилятор, квантова теорія інформації стосується як систем з безперервними змінними, так і скінченновимірних систем.
Квантові обчислення
Квантові обчислення — це тип обчислень, який використовує колективні властивості квантових станів, такі як суперпозиція, інтерференція та заплутаність, для виконання обчислень. Пристрої, які виконують квантові обчислення, відомі як квантові комп’ютери. I-5 Хоча сучасні квантові комп’ютери занадто малі, щоб перевершити звичайні (класичні) комп’ютери для практичних застосувань, вважається, що вони здатні вирішувати певні обчислювальні проблеми, такі як цілочисельне розкладання. (що лежить в основі шифрування RSA), значно швидше, ніж класичні комп'ютери. Вивчення квантових обчислень є розділом квантової інформатики.
Квантові обчислення почалися в 1980 році, коли фізик Пол Беніофф запропонував квантовомеханічну модель машини Тьюринга. Пізніше Річард Фейнман і Юрій Манін припустили, що квантовий комп'ютер має потенціал для моделювання того, що класичний комп'ютер не може зробити. У 1994 році Пітер Шор розробив квантовий алгоритм для розкладання цілих чисел на множники з потенціалом для розшифровки RSA-зашифрованих комунікацій. У 1998 році Ісаак Чуанг, Ніл Гершенфельд і Марк Кубінец створили перший двокубітний квантовий комп'ютер, який міг виконувати обчислення. Незважаючи на постійний експериментальний прогрес з кінця 1990-х років, більшість дослідників вважають, що «відмовостійкі квантові обчислення [це] все ще досить далека мрія». За останні роки зросли інвестиції в дослідження квантових обчислень у державному та приватному секторах. 23 жовтня 2019 року Google AI у партнерстві з Національним управлінням з аеронавтики і дослідження космічного простору США (NASA) стверджували, що провели квантові обчислення, які були нездійсненними на будь-якому класичному комп’ютері, але питання про те, чи була ця заява дійсною чи залишається актуальною, – це питання. активне дослідження.
Існує кілька типів квантових комп’ютерів (також відомих як квантові обчислювальні системи), включаючи модель квантової схеми, квантову машину Тьюринга, адіабатичний квантовий комп’ютер, односторонній квантовий комп’ютер та різні квантові клітинні автомати. Найбільш широко використовуваною моделлю є квантовий ланцюг, заснований на квантовому біті, або «кубіті», який дещо аналогічний біту в класичних обчисленнях. Кубіт може перебувати в квантовому стані 1 або 0 або в суперпозиції станів 1 і 0. Однак, коли він вимірюється, він завжди дорівнює 0 або 1; ймовірність того чи іншого результату залежить від квантового стану кубіта безпосередньо перед вимірюванням.
Зусилля щодо створення фізичного квантового комп’ютера зосереджені на таких технологіях, як трансмони, іонні пастки та топологічні квантові комп’ютери, які спрямовані на створення високоякісних кубітів.: 2–13 Ці кубіти можуть бути розроблені по-різному, залежно від повної обчислювальної моделі квантового комп’ютера, чи то квантові логічні вентилі, квантовий відпал чи адіабатичні квантові обчислення. В даний час існує ряд істотних перешкод на шляху побудови корисних квантових комп’ютерів. Підтримувати квантові стани кубітів особливо важко, оскільки вони страждають від квантової декогерентності та вірності стану. Тому квантові комп’ютери вимагають виправлення помилок.
Будь-яку обчислювальну задачу, яку можна розв’язати класичним комп’ютером, також можна вирішити квантовим комп’ютером. І навпаки, будь-яку задачу, яку можна розв’язати квантовим комп’ютером, можна вирішити і класичним комп’ютером, принаймні в принципі, якщо достатньо часу. Іншими словами, квантові комп’ютери підкоряються тезі Черча-Тюрінга. Це означає, що в той час як квантові комп’ютери не мають додаткових переваг перед класичними комп’ютерами з точки зору обчислюваності, квантові алгоритми для певних задач мають значно меншу тимчасову складність, ніж відповідні відомі класичні алгоритми. Примітно, що квантові комп’ютери, як вважають, здатні швидко вирішувати певні проблеми, які жоден класичний комп’ютер не міг би вирішити за будь-який можливий проміжок часу — подвиг, відомий як «квантова перевага». Вивчення обчислювальної складності задач щодо квантових комп’ютерів відоме як квантова теорія складності.
Переважаюча модель квантових обчислень описує обчислення в термінах мережі квантових логічних вентилів. Цю модель можна розглядати як абстрактне лінійно-алгебраїчне узагальнення класичної схеми. Оскільки ця модель схеми підкоряється квантовій механіці, вважається, що квантовий комп’ютер, здатний ефективно запускати ці схеми, є фізично реалізованим.
Пам'ять, що складається з n біт інформації, має 2^n можливих станів. Таким чином, вектор, що представляє всі стани пам’яті, має 2^n записів (по одному для кожного стану). Цей вектор розглядається як вектор ймовірності і представляє той факт, що пам’ять знаходиться в певному стані.
У класичному уявленні один запис мав би значення 1 (тобто 100% ймовірність перебувати в цьому стані), а всі інші записи дорівнювали б нулю.
У квантовій механіці вектори ймовірності можна узагальнити на оператори щільності. Формалізм квантового вектора стану зазвичай вводиться першим, оскільки він концептуально простіший і тому, що його можна використовувати замість формалізму матриці щільності для чистих станів, де відома вся квантова система.
квантові обчислення можна описати як мережу квантових логічних вентилів і вимірювань. Однак будь-яке вимірювання можна відкласти до кінця квантових обчислень, хоча це відстрочення може мати витрати на обчислення, тому більшість квантових схем зображують мережу, що складається лише з квантових логічних вентилів і без вимірювань.
Будь-яке квантове обчислення (яке в наведеному вище формалізмі є будь-якою унітарною матрицею над n кубітами) може бути представлено як мережа квантових логічних вентилів із досить невеликого сімейства вентилів. Вибір сімейства вентилів, що дозволяє цю конструкцію, відомий як універсальний набір воріт, оскільки комп’ютер, який може запускати такі схеми, є універсальним квантовим комп’ютером. Один загальний такий набір включає всі однокубітні вентилі, а також вентиль CNOT зверху. Це означає, що будь-які квантові обчислення можна виконати шляхом виконання послідовності однокубітних вентилів разом із вентилями CNOT. Хоча ця множина воріт нескінченна, її можна замінити скінченною множиною воріт, звернувшись до теореми Соловая-Кітаєва.
Квантові алгоритми
Прогрес у пошуку квантових алгоритмів зазвичай зосереджується на цій моделі квантової схеми, хоча існують винятки, такі як квантовий адіабатичний алгоритм. Квантові алгоритми можна приблизно класифікувати за типом прискорення, досягнутого в порівнянні з відповідними класичними алгоритмами.
Квантові алгоритми, які пропонують більше, ніж поліноміальне прискорення в порівнянні з найвідомішим класичним алгоритмом, включають алгоритм Шора для розкладання на множники і пов’язані з ним квантові алгоритми для обчислення дискретних логарифмів, розв’язування рівняння Пелла і більш загального вирішення проблеми прихованої підгрупи для абелевих скінченних груп. Ці алгоритми залежать від примітиву квантового перетворення Фур'є. Не знайдено жодного математичного доказу, який би показував, що такий же швидкий класичний алгоритм неможливо виявити, хоча це вважається малоймовірним.[самопублікуване джерело?] Деякі проблеми оракула, як-от проблема Саймона та проблема Бернштейна–Вазірані, дають доказові прискорення, хоча це і є. знаходиться в моделі квантового запиту, яка є обмеженою моделлю, де нижні межі набагато легше довести, і це не обов’язково означає прискорення практичних завдань.
Інші проблеми, включаючи моделювання квантових фізичних процесів з хімії та фізики твердого тіла, апроксимацію деяких поліномів Джонса та квантовий алгоритм для лінійних систем рівнянь, мають квантові алгоритми, які дають суперполіноміальні прискорення та є BQP-повними. Оскільки ці проблеми є BQP-повними, однаково швидкий класичний алгоритм для них означатиме, що жоден квантовий алгоритм не дає суперполіноміального прискорення, яке вважається малоймовірним.
Деякі квантові алгоритми, як-от алгоритм Гровера та амплітудне посилення, дають поліноміальне прискорення порівняно з відповідними класичними алгоритмами. Хоча ці алгоритми дають порівняно скромне квадратичне прискорення, вони широко застосовні і, таким чином, дають прискорення для широкого кола задач. Багато прикладів доказуваних квантових прискорень для задач запиту пов’язані з алгоритмом Гровера, включно з алгоритмом Брасарда, Хойєра та Таппа для пошуку колізій у функціях «два до одного», який використовує алгоритм Гровера, а також алгоритм Фархі, Голдстоуна та Гутмана для оцінки NAND. дерева, що є варіантом задачі пошуку.
Криптографічні програми
Помітним застосуванням квантових обчислень є атаки на криптографічні системи, які зараз використовуються. Вважається, що цілочисельне розкладання, яке лежить в основі безпеки криптографічних систем із відкритим ключем, є неможливим із обчислювальної точки зору на звичайному комп’ютері для великих цілих чисел, якщо вони є добутком кількох простих чисел (наприклад, добуток двох 300-значних простих чисел). Для порівняння, квантовий комп’ютер міг ефективно вирішити цю проблему, використовуючи алгоритм Шора, щоб знайти її фактори. Ця здатність дозволила б квантовому комп’ютеру зламати багато криптографічних систем, які використовуються сьогодні, у тому сенсі, що існував би алгоритм поліноміального часу (за кількістю цифр цілого) для вирішення проблеми. Зокрема, більшість популярних шифрів із відкритим ключем засновані на складності розкладання цілих чисел на множники або задачі дискретного логарифма, обидві з яких можна вирішити за допомогою алгоритму Шора. Зокрема, алгоритми Діффі-Хеллмана RSA, Діффі-Хеллмана та еліптична крива можуть бути порушені. Вони використовуються для захисту захищених веб-сторінок, зашифрованої електронної пошти та багатьох інших типів даних. Порушення їх матиме значні наслідки для електронної конфіденційності та безпеки.
Виявлення криптографічних систем, які можуть бути захищені від квантових алгоритмів, є активно досліджуваною темою в області пост-квантової криптографії. Деякі алгоритми з відкритим ключем засновані на проблемах, відмінних від цілочисельної факторізації та проблем дискретного логарифма, до яких застосовується алгоритм Шора, як криптосистема МакЕліса, заснована на задачі в теорії кодування. Також відомо, що криптосистеми на основі решітки не можуть бути порушені квантовими комп’ютерами, і пошук алгоритму поліноміального часу для вирішення проблеми двогранної прихованої підгрупи, яка б зламала багато криптосистем на основі решітки, є добре вивченою відкритою проблемою. Було доведено, що застосування алгоритму Гровера для порушення симетричного (секретного ключа) алгоритму грубою силою вимагає часу, що дорівнює приблизно 2n/2 викликів основного криптографічного алгоритму, порівняно з приблизно 2n в класичному випадку, що означає, що симетричні довжини ключа є фактично зменшено вдвічі: AES-256 матиме такий самий захист від атаки з використанням алгоритму Гровера, що й AES-128 проти класичного пошуку методом грубої сили (див. Розмір ключа).
Квантова криптографія потенційно може виконувати деякі функції криптографії з відкритим ключем. Таким чином, криптографічні системи на основі квантів можуть бути більш безпечними, ніж традиційні системи від квантового злому.
Проблеми з пошуком
Найвідомішим прикладом проблеми, що допускає поліноміальне квантове прискорення, є неструктурований пошук, пошук позначеного елемента зі списку з n елементів у базі даних. Це можна вирішити за допомогою алгоритму Гровера, використовуючи O(sqrt(n)) запитів до бази даних, що квадратично менше, ніж запитів Omega(n), необхідних для класичних алгоритмів. У цьому випадку перевага є не тільки доказовою, але й оптимальною: було показано, що алгоритм Гровера дає максимально можливу ймовірність знайти потрібний елемент для будь-якої кількості пошуків оракула.
Проблеми, які можна вирішити за допомогою алгоритму Гровера, мають такі властивості:
- У колекції можливих відповідей немає структури для пошуку,
- Кількість можливих відповідей для перевірки дорівнює кількості введених даних в алгоритм, і
- Існує булева функція, яка оцінює кожен вхід і визначає, чи є він правильною відповіддю
Для задач з усіма цими властивостями час роботи алгоритму Гровера на квантовому комп’ютері масштабується як квадратний корінь з числа вхідних даних (або елементів у базі даних), на відміну від лінійного масштабування класичних алгоритмів. Загальним класом задач, до яких можна застосувати алгоритм Гровера, є булева задача на виконання, де база даних, через яку виконує ітерації алгоритм, є тією з усіх можливих відповідей. Прикладом і (можливим) застосуванням цього є програма для злому паролів, яка намагається вгадати пароль. Симетричні шифри, такі як Triple DES і AES, є особливо вразливими до такого роду атак.[Потрібна цитата] Це застосування квантових обчислень є основним інтересом державних установ.
Моделювання квантових систем
Оскільки хімія та нанотехнології покладаються на розуміння квантових систем, а такі системи неможливо змоделювати ефективним класичним способом, багато хто вважає, що квантове моделювання буде одним з найважливіших застосувань квантових обчислень. Квантове моделювання також можна використовувати для моделювання поведінки атомів і частинок в незвичайних умовах, таких як реакції всередині колайдера. Квантове моделювання може бути використане для прогнозування майбутніх шляхів руху частинок і протонів під час суперпозиції в експерименті з подвійними щілинами. [Потрібна цитата] Близько 2% річної глобальної виробленої енергії використовується для фіксації азоту для виробництва аміаку для процесу Габера в сільському господарстві. промисловість добрив, тоді як природні організми також виробляють аміак. Для розуміння цього процесу збільшення виробництва можна використовувати квантове моделювання.
Квантовий відпал та адіабатична оптимізація
Квантовий відпал або адіабатичні квантові обчислення ґрунтуються на адіабатичній теоремі для проведення обчислень. Система поміщається в основний стан для простого гамільтоніана, який повільно еволюціонує до більш складного гамільтоніана, основний стан якого представляє розв’язок розглянутої проблеми. Адіабатична теорема стверджує, що якщо еволюція досить повільна, система буде залишатися в своєму основному стані протягом усього процесу.
навчання за допомогою машини
Оскільки квантові комп’ютери можуть виробляти результати, які класичні комп’ютери не можуть виробляти ефективно, і оскільки квантові обчислення по суті є лінійними алгебраїчними, деякі висловлюють надію на розробку квантових алгоритмів, які можуть прискорити виконання завдань машинного навчання. Наприклад, вважається, що квантовий алгоритм для лінійних систем рівнянь, або «алгоритм HHL», названий на честь його першовідкривачів Харроу, Хасидіма та Ллойда, забезпечує прискорення порівняно з класичними аналогами. Деякі дослідницькі групи нещодавно досліджували використання апаратних засобів квантового відпалу для навчання машин Больцмана і глибоких нейронних мереж.
Обчислювальна біологія
У галузі обчислювальної біології квантові обчислення зіграли велику роль у вирішенні багатьох біологічних проблем. Одним із добре відомих прикладів може бути обчислювальна геноміка та те, як обчислення різко скоротили час на секвенування геному людини. З огляду на те, як обчислювальна біологія використовує загальне моделювання та зберігання даних, очікується, що також з’являться її застосування до обчислювальної біології.
Комп'ютерне проектування ліків і генеративна хімія
Моделі глибокої генеративної хімії стають потужними інструментами для прискорення відкриття ліків. Однак величезний розмір і складність структурного простору всіх можливих лікоподобних молекул створюють значні перешкоди, які в майбутньому можуть бути подолані квантовими комп’ютерами. Квантові комп’ютери, природно, хороші для вирішення складних квантових проблем із багатьма тілами, і, таким чином, можуть бути корисними для застосування, пов’язаного з квантовою хімією. Таким чином, можна очікувати, що генеративні моделі, удосконалені квантами, включаючи квантові GAN, з часом можуть бути розроблені в остаточні генеративні хімічні алгоритми. Гібридні архітектури, що поєднують квантові комп’ютери з глибокими класичними мережами, такими як квантові варіаційні автокодери, вже можна навчати на комерційно доступних відпалителях і використовувати для створення нових подібних до ліків молекулярних структур.
Розробка фізичних квантових комп'ютерів
Виклики
Побудова великомасштабного квантового комп’ютера має ряд технічних проблем. Фізик Девід ДіВінченцо перерахував ці вимоги до практичного квантового комп’ютера:
- Фізично масштабований для збільшення кількості кубітів,
- Кубіти, які можна ініціалізувати до довільних значень,
- Квантові ворота, які швидші за час декогерентності,
- Універсальний комплект воріт,
- Кубіти, які легко читаються.
Також дуже важко знайти деталі для квантових комп’ютерів. Багатьом квантовим комп’ютерам, на кшталт тих, що створені Google і IBM, потрібен гелій-3, побічний продукт ядерних досліджень, і спеціальні надпровідні кабелі, виготовлені тільки японською компанією Coax Co.
Управління мультикубітними системами вимагає генерації та координації великої кількості електричних сигналів із жорсткою та детермінованою роздільною здатністю. Це призвело до розробки квантових контролерів, які забезпечують взаємодію з кубітами. Масштабування цих систем для підтримки все більшої кількості кубітів є додатковою проблемою.
Квантова декогерентність
Однією з найбільших проблем, пов’язаних із побудовою квантових комп’ютерів, є контроль або усунення квантової декогерентності. Зазвичай це означає ізоляцію системи від середовища, оскільки взаємодія із зовнішнім світом призводить до декогерації системи. Однак існують і інші джерела декогерентності. Приклади включають квантові ворота, вібрації решітки та фоновий термоядерний спін фізичної системи, що використовується для реалізації кубітів. Декогерентність необоротна, оскільки вона фактично не є унітарною, і зазвичай це те, чого слід строго контролювати, якщо не уникати. Час декогерентності для систем-кандидатів, зокрема, час поперечної релаксації T2 (для технологій ЯМР і МРТ, також званий часом дефазування), зазвичай коливається від наносекунд до секунд при низькій температурі. В даний час деякі квантові комп’ютери вимагають, щоб їхні кубіти були охолоджені до 20 мілікельвінів (зазвичай з використанням холодильника для розведення), щоб запобігти значній декогерентності. Дослідження 2020 року стверджує, що іонізуюче випромінювання, таке як космічні промені, тим не менш, може спричинити декогерентність певних систем протягом мілісекунд.
В результаті виконання трудомістких завдань може зробити деякі квантові алгоритми непрацездатними, оскільки підтримка стану кубітів протягом достатньо тривалого часу призведе до пошкодження суперпозицій.
Ці проблеми є складнішими для оптичних підходів, оскільки часові масштаби на порядки коротші, і часто цитується підхід до їх подолання — формування оптичного імпульсу. Частота помилок, як правило, пропорційна відношенню часу роботи до часу декогерентності, тому будь-яка операція повинна виконуватися набагато швидше, ніж час декогерентності.
Як описано в квантовій пороговій теоремі, якщо рівень помилок досить малий, вважається, що можна використовувати квантову корекцію помилок для придушення помилок і декогерентності. Це дозволяє загальний час обчислення бути довшим, ніж час декогеренції, якщо схема виправлення помилок може виправляти помилки швидше, ніж декогерентність їх вносить. Часто цитується цифра для необхідної частоти помилок у кожному вентилі для відмовостійкого обчислення становить 10-3, припускаючи, що шум деполяризується.
Виконання цієї умови масштабованості можливе для широкого кола систем. Однак використання виправлення помилок тягне за собою вартість значно збільшеної кількості необхідних кубітів. Число, необхідне для розкладання цілих чисел за допомогою алгоритму Шора, все ще є поліноміальним, і вважається, що воно знаходиться між L і L2, де L — кількість цифр числа, яке потрібно розкласти; Алгоритми виправлення помилок збільшують цей показник на додатковий коефіцієнт L. Для 1000-бітового числа це означає потребу приблизно в 104 біта без виправлення помилок. З виправленням помилок цифра збільшиться приблизно до 107 біт. Час обчислення становить близько L2 або близько 107 кроків, а на частоті 1 МГц близько 10 секунд.
Зовсім інший підхід до проблеми стабільності-декогерентності полягає у створенні топологічного квантового комп’ютера з аніонами, квазічастинок, які використовуються як нитки та спираючись на теорію коси для формування стабільних логічних вентилів.
Квантове верховенство
Квантова перевага — це термін, введений Джоном Прескіллом, що стосується інженерного подвигу, який демонструє, що програмований квантовий пристрій може вирішити проблему, що виходить за межі можливостей сучасних класичних комп’ютерів. Проблема не обов’язково має бути корисною, тому деякі розглядають тест квантової переваги лише як потенційний майбутній еталон.
У жовтні 2019 року Google AI Quantum за допомогою NASA став першим, хто заявив про досягнення квантового переваги, виконуючи обчислення на квантовому комп’ютері Sycamore більш ніж в 3,000,000 XNUMX XNUMX разів швидше, ніж на Summit, який зазвичай вважається найшвидшим у світі. комп'ютер. Пізніше це твердження було оскаржено: IBM заявила, що Summit може виконувати вибірки набагато швидше, ніж заявлено, і з тих пір дослідники розробили кращі алгоритми для проблеми вибірки, яка використовується для заявлення про квантове перевагу, що значно скорочує або скорочує розрив між Sycamore і Sycamore класичні суперкомп'ютери.
У грудні 2020 року група з USTC реалізувала вибірку бозона на 76 фотонах за допомогою фотонного квантового комп’ютера Jiuzhang, щоб продемонструвати квантову перевагу. Автори стверджують, що класичному сучасному суперкомп’ютеру знадобиться обчислювальний час 600 мільйонів років, щоб створити кількість зразків, які їх квантовий процесор може створити за 20 секунд. 16 листопада 2021 року на саміті квантових обчислень IBM представила 127-кубітний мікропроцесор під назвою IBM Eagle.
Фізичні реалізації
Для фізичної реалізації квантового комп’ютера шукається багато різних кандидатів, серед них (відрізняються фізичною системою, яка використовується для реалізації кубітів):
- Надпровідні квантові обчислення (кубіт, реалізований за допомогою стану малих надпровідних ланцюгів, джозефсонівських переходів)
- Квантовий комп'ютер із захопленими іонами (кубіт, реалізований внутрішнім станом захоплених іонів)
- Нейтральні атоми в оптичних ґратках (кубіт, реалізований внутрішніми станами нейтральних атомів, уловлених в оптичній ґратці)
- Квантово-точковий комп'ютер, заснований на спіні (наприклад, квантовий комп'ютер Loss-DiVincenzo) (кубіт, заданий спіновими станами захоплених електронів)
- Квантово-точковий комп'ютер, просторовий (кубіт задається положенням електрона в подвійній квантовій точці)
- Квантові обчислення з використанням сконструйованих квантових ям, які в принципі можуть уможливити створення квантових комп’ютерів, які працюють при кімнатній температурі
- Зв’язаний квантовий дріт (кубіт, реалізований парою квантових дротів, з’єднаних квантовим точковим контактом)
- Квантовий комп'ютер ядерного магнітного резонансу (NMRQC), реалізований за допомогою ядерного магнітного резонансу молекул у розчині, де кубіти забезпечуються ядерними спінами всередині розчиненої молекули та досліджуються радіохвилями.
- Твердотільний ЯМР квантовий комп'ютер Кейна (кубіт, реалізований за допомогою ядерного спінового стану донорів фосфору в кремнії)
- Квантові комп'ютери електрони на гелії (кубіт - це спін електрона)
- Квантова електродинаміка порожнини (CQED) (кубіт забезпечується внутрішнім станом захоплених атомів, пов’язаних з високоточними порожнинами)
- Молекулярний магніт (кубіт, заданий спіновими станами)
- Квантовий комп'ютер ESR на основі фулеренів (кубіт, заснований на електронному спіні атомів або молекул, укладених у фулерени)
- Нелінійно-оптичний квантовий комп'ютер (кубіти, реалізовані шляхом обробки станів різних режимів світла як через лінійні, так і нелінійні елементи)
- Лінійно-оптичний квантовий комп'ютер (кубіти, реалізовані шляхом обробки станів різних режимів світла за допомогою лінійних елементів, наприклад, дзеркал, роздільників променя та фазообертів)
- Квантовий комп'ютер на основі алмазів (кубіт, реалізований електронним або ядерним спіном азотних вакансійних центрів в алмазі)
- Квантовий комп'ютер на основі конденсату Бозе-Ейнштейна
- Квантовий комп'ютер на основі транзисторів - струнні квантові комп'ютери з захопленням позитивних дірок за допомогою електростатичної пастки
- Квантові комп’ютери на основі неорганічних кристалів, легованих іонами рідкісноземельних металів (кубіт, реалізований внутрішнім електронним станом легованих домішок в оптичних волокнах)
- Квантові комп’ютери на основі металевих вуглецевих наносфер
- Велика кількість кандидатів демонструє, що квантові обчислення, незважаючи на швидкий прогрес, все ще перебувають у зародковому стані.
Існує ряд моделей квантових обчислень, які відрізняються основними елементами, в яких розкладається обчислення. Для практичної реалізації існують чотири відповідні моделі обчислень:
- Квантовий масив воріт (обчислення розкладається на послідовність квантових вентилів з кількома кубітами)
- Односторонній квантовий комп'ютер (обчислення розкладається на послідовність вимірювань за один кубіт, що застосовуються до сильно заплутаного початкового стану або стану кластера)
- Адіабатичний квантовий комп'ютер, заснований на квантовому відпалі (обчислення розкладається на повільне безперервне перетворення початкового гамільтоніана в кінцевий гамільтоніан, основні стани якого містять розчин)
- Топологічний квантовий комп'ютер (обчислення, розкладене на сплетення аніонів у 2D-решітці)
Квантова машина Тьюринга теоретично важлива, але фізична реалізація цієї моделі неможлива. Було показано, що всі чотири моделі обчислень еквівалентні; кожен може моделювати іншу з не більше ніж поліноміальними накладними витратами.
Для більш детального ознайомлення з навчальною програмою сертифікації Ви можете розгорнути та проаналізувати наведену нижче таблицю.
Навчальна програма сертифікації основ квантової інформації EITC/QI/QIF посилається на дидактичні матеріали відкритого доступу у формі відео. Навчальний процес поділений на покрокову структуру (програми -> уроки -> теми), що охоплює відповідні частини навчального плану. Також надаються необмежені консультації з експертами в галузі.
Детальніше про процедуру сертифікації див Як це працює?.
Основні конспекти лекцій
У. Вазірані конспект лекції:
https://people.eecs.berkeley.edu/~vazirani/quantum.html
Допоміжні конспекти лекцій
L. Jacak та ін. конспект лекцій (з додатковими матеріалами):
https://drive.google.com/open?id=1cl27qPRE8FyB3TvvMGp9mwBFc-Qe-nlG
https://drive.google.com/open?id=1nX_jIheCHSRB7pYAjIdVD0ab6vUtk7tG
Основний опорний підручник
Підручник з квантових обчислень та квантової інформації (Nielsen, Chuang):
http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf
Додаткові конспекти лекцій
J. Preskill конспект лекції:
http://theory.caltech.edu/~preskill/ph219/index.html#lecture
Конспект лекції А. Чайлдса:
http://www.math.uwaterloo.ca/~amchilds/teaching/w08/co781.html
Конспект лекції С. Ааронсона:
https://scottaaronson.blog/?p=3943
Р. де Вольф конспект лекції:
https://arxiv.org/abs/1907.09415
Інші рекомендовані підручники
Класичні та квантові обчислення (Китаєв, Шень, Вялий)
http://www.amazon.com/exec/obidos/tg/detail/-/082182161X/qid=1064887386/sr=8-3/ref=sr_8_3/102-1370066-0776166
Квантові обчислення від Демокріта (Ааронсон)
http://www.amazon.com/Quantum-Computing-since-Democritus-Aaronson/dp/0521199565
Теорія квантової інформації (Ватрус)
https://www.amazon.com/Theory-Quantum-Information-John-Watrous/dp/1107180562/
Квантова теорія інформації (Уайльд)
http://www.amazon.com/Quantum-Information-Theory-Mark-Wilde/dp/1107034256
Завантажте повні підготовчі матеріали для офлайн-самонавчання для програми EITC/QI/QIF Quantum Information Fundamentals у файлі PDF
Підготовчі матеріали EITC/QI/QIF – стандартна версія
Підготовчі матеріали EITC/QI/QIF – розширена версія з контрольними запитаннями