Квантовый компьютер.

lexpartizan — 16.04.2017
Итак, совсем недавно я писал о физических ограничениях для быстродействия компьютеров будущего.
Обычный процессор подчиняется законам физики макромира. Посему он имеет ограничение на техпроцесс и тд и тп.
Теперь же мы рассмотрим, что будет, если воспользоваться абсолютно безумной (как по мне) квантовой физикой, где рулят коты Шредингера и вполне разумно звучат бредни героев комиксов о мультиВселенной.
Так как квантовая физика мне абсолютно непонятна (то, что я не знаю жив или мёртв кот, не значит, что он жив и мёртв одновременно. Это значит, что я не знаю и не узнаю, пока не посмотрю. Но кот-то точно знает).
Попытаемся разобраться вместе, что нам обещает использование квантовых эффектов в вычислительных процессах и что мы получим от квантового компьютера.

Итак, в чём фишка квантового компьютера? Как он работает? Что именно обещает прирост быстродействия?

Кубит.

В обычном компе бит в ячейке памяти может быть равен 0 либо 1. И никак иначе. Это просто и логично.
В квантовом компьютере кубит - это кот Шредингера (не просите, я не могу это объяснить с точки зрения логики) и может быть и 0 и 1 одновременно. И живой и дохлый. Это называется квантовой суперпозицией. Которая описывается в виде , где 0 и 1 обозначают уровни логического нуля и единицы, а А и В - комплексные числа, удовлетворяющие условию
Пока мы не смотрим в коробку(не проведём измерение), там и 0 и 1 одновременно.
Так как информация о квантовых состояниях нам недоступна (кот и жив и мёртв, пока мы не посмотрим), нужно произвести измерение (открыть коробку). В результате чего мы получим случайную величину, принимающую значения с различными вероятностями.
Однако, когда мы измеряем спин, квантовая суперпозиция разрушается(происходит коллапс волновой функции, природа которого неясна) и фотон\электрон\ядро принимает значение с вероятностью будет 0 и с вероятностью будет 1.
Проведя множество измерений, мы сможем судить о исходном квантовом состоянии кубита, так как узнаем вероятность его перехода в состояние 0 или 1.
Например, у нас есть кубит в квантовом состоянии

(4/5)²=16/25= 0,64 вероятность получить 0 при измерении.
(-3/5)²=9/25= 0,36 вероятность получить 1 при измерении.

Но вернёмся к суперпозиции. Получается, что в состоянии суперпозиции в кубите одновременно присутствуют и 0 и 1. А значит, в квантовом 64-кубитном регистре содержится сразу 2 в 64 степени значений. То есть, практически все возможные значения. Одновременно. Таково свойство квантовой суперпозиции. Таким образом, одна операция над группой кубитов вычисляется сразу над всеми возможными ее значениями, в отличие от группы классических битов, когда может быть использовано лишь одно текущее значение. Это и обеспечивает беспрецедентный параллелизм вычислений.

Квантовые логические элементы (квантовые вентили) совершают операции не над нулями и единицами, а над суперпозициями. Повышая вероятность одних состояний при измерении и понижая вероятность других.
Таким образом мы обрабатываем целую кучу данных и проводим вычисления над целыми массивами одновременно, за одну операцию.
Как было сказано выше, ответ мы можем получить только при измерении. И этот ответ будет с какой-то вероятностью 0 или 1. С той вероятностью, в котором находится его квантовое состояние.
Квантовая система даёт результат, только с некоторой вероятностью являющийся правильным. Но за счёт небольшого увеличения операций в алгоритме можно сколь угодно приблизить вероятность получения правильного результата к единице. Это и есть ответ на главный вопрос жизни, вселенной и всего такого Не точный ответ, а вероятности. Которые можно увеличить дополнительными операциями.

Как пример, есть функция y=f(x). Получив в регистре х суперпозицию (все возможные значения с равной вероятностью) мы применяем к нему унитарные операторы (квантовые вентили), которые реализуют функцию f. И получаем сразу все возможные значения y в виде суперпозиции в регистре y. И, измеряя y, мы получим какое-то из значений y для какого-то из значений x. Для поиска точного значения нам потребуются дополнительные вычисления. Так что я не очень понимаю, в чём тут выигрыш и как его использовать. Ведь, получив какое-то из значений y, при измерении происходит коллапс волновой функции и состояние суперпозиции исчезает. И для получения другого значения вычисления надо проводить снова.
Казалось бы, тут тупик. Однако люди нашли хитроумные алгоритмы, которым нет аналогов в классических теориях и требуют особых приёмов программирования. С помощью одних приёмов можно манипулировать квантовым состоянием так, чтобы выделить общее свойство всех результирующих значений. Определить свойства функции, её периодичность\симметричность, пересечения с другими функциями и тд. В других случаях можно увеличивать вероятность получения конкретного искомого результата.
В общем суперпозиции и результат работы квантовых вентилей (то есть суперпозиции с другими результирующими вероятностями) можно пропустить через другие функции(квантовые вентили) и алгоритмы и узнать экстремумы функции или точки пересечения сложных функций. Ведь одновременно на пересечения мы сможем проверить сразу все точки функций сразу! И получить конкретный результат. По крайней мере так понимаю квантовую магию я.

Кроме того, с помощью квантовых вентилей можно реализовать такие логические операции, как и-или-не, а значит можно легко реализовать классическую работу компьютера на основе кубитов. При измерении мы получаем уже не квантовое состояние суперпозиции, а вполне обычные нули и единицы, так что квантовый компьютер вполне может исполнять обычные алгоритмы, причём с не меньшей производительностью. Квантовый компьютер вполне может быть универсален. Но значительный прирост он даст только на определённых алгоритмах. Это свойство называется квантовым ускорением. Какие же это алгоритмы?

Что на нём вообще считать? И зачем?
Во-первых, квантовый компьютер не решает задачи, которые невозможно решить на других компьютерах.
Просто некоторые алгоритмы имеют возрастающую по экспоненте сложность. Например, задача коммивояжёра, где сложность растёт по экспоненте. Например, после 100 точек, если мы добавим ещё 1, то количество необходимых вычислений вырастет в сто раз. И тд. Это можно решить, но за долгое время. Возрастающее в просто пипец раз с каждой новой точкой.
Либо отказаться от оптимального варианта и согласиться на приближённый к нему. Который будет хотя бы не в два раза длиннее оптимального. Это считается куда веселей.
К таким же задачам можно и отнести и решение громадных систем линейных уравнений. Что необходимо, например, для плановой экономики. Опять же, там тоже можно упрощать и жертвовать идеальной оптимальностью. А ещё можно выстроить иерархию и разбить на группы товаров.
А можно заюзать эти самые ваши квантовые компьютеры. Которые поднимут логистику и планирование до абсолютного идеала.
Квантовые компьютеры ускоряют прежде всего комбинаторные алгоритмы и перебор. Случаи квантового ускорения, на фоне общей массы классических алгоритмов, очень редки. Их где-то около 60 на данный момент.
Вот довольно устаревшая карта области задач для квантового компьютера.


В общем, загибайте пальцы.
1. Поиск. Ускорение по сравнению с классическими квадратичное, то есть не экспоненциальное и чувствительно только на больших объёмах данных.
2. Задачи оптимизации, поиски экстремумов и пересечений. Те самые задачи плановой экономики.
3. Математические алгоритмы, связанные с системами уравнений и матрицами. Не смотря на занудность, их область применения довольно велика и они смогут ускорить множество приложений. Честно говоря, это, пожалуй, единственное, что можно было бы применить в обычных компьютерах.
4. Моделирование систем частиц. Квантовые компьютеры способны моделировать за счёт своей природы суперпозиции просто громадное число частиц. Кроме того, они способны моделировать их взаимодействие на квантовом уровне. Это поможет в аэродинамике, поиске нефтегаза, позволит быстрее рассчитывать цепочки ДНК, лекарства, новые материалы. В общем, решать сегодняшние задачи суперкомпьютеров.
5. Позволят добиться абсолютной безопасности связи, используя связанные частицы. Любая попытка "подслушать"(то есть измерить) выведет из состояния квантовой суперпозиции. В этом деле серьёзно продвигаются китайцы.
6. Вся современная криптография основана на недостатке вычислительной мощности для подбора "пароля". Мы все без труда раскладываем на простые множители числа вида 15 = 3*5, 55 = 5*11, 91 = 13*7 и т.д. Но можете ли вы разложить на два простых множителя число 853, или 13297, или 99487? Компьютер решает эту задачу перебором, умножая простые числа, пока не получит совпадение. Но для больших чисел это трудоёмкий процесс с экспоненциально возрастающей сложностью. Именно это и используют в криптографии, зная, что за разумный срок эти числа не подобрать. Так работает биткойн (майнинг - это именно подбор таких чисел, произведение которых должно дать открытый ключ) и другие криптовалюты. А вот квантовый компьютер делает это на раз два. И если бы кто-то имел производительный квантовый компьютер, он мог бы обвалить все криптовалюты (да и классические банки) и получить доступ к большинству подключенных к сети устройств. Постквантовая криптография, основанная на других принципах, пока не очень распространена.
Вот интересная статья по последним двум пунктам.

В общем, несмотря на небольшое количество алгоритмов, квантовый компьютер всё же представляет собой серьёзный интерес для человечества. Государство, получившее такой компьютер, получило бы серьёзные преимущества.
Так что же мешает заполучить цацку?

Ну, для начала, это квантовая физика, Карл! Не так уж просто до неё добраться (уровень фотонов и электронов), не так уж легко это понять даже на бытовом уровне, и не так уж легко добиться нормальной работы.

Например, любое внешнее воздействие разрушает нежную квантовую суперпозицию. Например, магнитные поля. Так что надо хорошо экранировать кубит. Или тепло, которое заставляет электроны хаотично метаться. Квантовые компьютеры охлаждают почти до температуры абсолютного нуля вовсе не потому, что там заядлые оверклокеры и квантовый комп сильно греется. Нет. Потому что тепло заставляет электроны двигаться там, где это не нужно.
Продолжая тему нежной суперпозиции, она постоянно коллапсирует время от времени. Поэтому результаты не всегда предсказуемы. Более того, компьютер должен "дожить" до конца рассчётов. Когда измерение разрушит суперпозицию. А это удаётся не всегда. Потому что живёт он нестабильно и недолго.
Насколько недолго? Ну, совсем недавно было прорывом аж 2 секунды. Правда, зато удалось добиться этого при комнатной температуре. Кстати, на алмазной основе. Через год другие уже смогли добиться 39 минут, но запись кубита была при температуре, близкой к абсолютному нулю. А потом охлаждение было отключено. На кремнии.
Также учёные научились предсказывать время разрушения суперпозиции.

Кроме того, нежность процессов и всякие влияния требуют коррекции ошибок.
В информации, хранимой в классическом компьютере, может произойти ошибка только одного типа, бит-флип, когда 0 ошибочно переворачивается в 1 или наоборот. Кубиты тоже страдают от перевернутых битов, также и от фазовых ошибок. Состояние суперпозиции кубита, или когда он принимает значения 0 и 1 одновременно, обозначается как 0 + 1. Фазовая ошибка переворачивает знаковое отношения между 0 и 1.0 + 1 и 0 — 1 очень разные с точки зрения информации, которая находится в этом состоянии. Можно представить это как стрелку, указывающую вдоль сферы. Вы можете указать в направлении южного полюса, и это будет ноль. Вы также можете указать в направлении северного полюса, и это будет один. Вы можете указать вдоль экватора, и это будет 0 + 1, но если вы укажете в противоположном направлении, это будет 0 — 1». При этом фишка в том, что ИЗМЕРЯТЬ КУБИТЫ НЕЛЬЗЯ. Потому что это разрушит суперпозицию же. А как проверить, если нельзя измерить? Впрочем, яйцеголовые таки напридумали разные схемы коррекции ошибок.

Ну и ещё одной из многих проблем является проверка результата. Как я и говорил выше, мы получаем вероятность, а не точное значение. В некоторых случаях, например в криптографии, где нужно разложить число на простые множители, результат проверить легко. Достаточно просто умножить. А в некоторых всё не так и результат квантового компьютера вовсе не означает верный результат.

Ну и проблема масштабирования довольно таки велика. Очень трудно наращивать количество кубитов. Не спрашивайте меня почему. Однако, считается, что до 50 кубитов не имеет смысла, потому что для этого хватит и банального компьютера.

Состояние дел.
Множество лабораторий имеют некие квантовые компьютеры\прототипы из нескольких кубитов. IBM даже создала облачный сервис для желающих поиграться.
На данный момент лучше всего идут дела у компании D-Wave Systems.

Она УЖЕ продаёт квантовые компьютеры с 2000 кубитов (на самом деле сумасшедшее число состояний 2 в 2000 степени). За жалкие 15 млн баксов.
Да, Вы правильно поняли. Основная часть компьютера это холодильник, который охлаждает до -273(данные для прошлой модели) градусов Цельсия вот такой вот мелкий процессор.


Вообще они продают квантовые компы аж с 2007 года.
В числе их клиентов Temporal Defence Systems, которая занимается компьютерной безопасностью, Lockheed Martin и Google c NASA на пару.
При этом такой компьютер на самом деле не является универсальным квантовым компьютером и умеет только алгоритм квантового отжига для нахождения глобального минимума. Что используется, например, в задаче коммивояжера.
Кстати, в прошлом году учёные придумали таки как сделать квантовый компьютер перепрограммируемым без изменения физической архитектуры.
Интересно, что в 2014 у Гугла совсем не получилось получить результат. Квантовый компьютер был медленнее обыкновенного. Гугловцам не удавалось найти задачи, на которых возможно квантовое ускорение. Однако, через год возни с новой игрушкой гуглу удалось получить впечатляющее ускорение в 100 млн раз при квантовом методе Монте-Карло.

Были заявления и о преимуществе таких компьютеров в 3600 раз над обычными суперкомпьютерами на определённых алгоритмах.

Естественно, квантовым компьютером хочет обзавестись АНБ, так как это позволит получить доступ к любой компьютерной системе. Алгоритмы шифрования просто неустойчивы к такому подходу. Это сродни супероружию в наше время.
Естественно, такие компьютеры и именно для такой же цели разрабатывает Китай. В Китае в 2015 году на тему квантовых вычислений потратили больше 100 млрд долларов. Зато запустили первый спутник квантовой связи и создали квантовый радар. Идея обычного радара в том, что электроны отражаются от самолёта и возвращаются на приёмную антенну. Современные самолёты-невидимки оптимизируют форму для того, чтобы они не возвращались. Технология стелс и всё такое. Китайцы же запутывают частицы и выстреливают одной из них в сторону самолёта. И измеряют, изменилась ли вторая. По её изменению можно понять, столкнулась ли частица с самолётом или нет. Отражаться ей уже необязательно. Опять же, насколько он работоспособен - вопрос дискуссионный. Я лично думаю, что при "выстреле" произойдёт коллапс волновой функции и суперпозиция будет потеряна вместе со спутанностью.

Лично я пока отношусь к квантовым компьютерам с неким скепсисом. Ускорение получается лишь на ограниченной области задач, результаты не точны, ибо вероятности. Некоторые не самые глупые люди вообще сомневаются в "квантовой магии".
https://geektimes.ru/post/285378/
https://geektimes.ru/post/285490/
https://geektimes.ru/post/285546/
Впрочем, запас моих знаний и уровень понимания не позволяет мне адекватно судить о квантовой физике либо критике. Я попытался разобраться с темой квантового компьютера и вот что у меня вышло. Надеюсь, больших косяков не наделал. Не считайте это научной работой)) Но общее понимание, думаю, верно. А если не понятно, попытайтесь понять комикс по ссылке ниже. Впрочем, его я тоже особо не понял))
http://cs9.pikabu.ru/post_img/big/2016/12/15/3/1481769128157175454.png
Так что пока я в состоянии "будем посмотреть". Особенно, учитывая, что квантовая физика - это что-то вроде тёмной энергии или тёмной материи. НЕХ и магия.
ЗЫ. Рекомендуемая литература http://extremal-mechanics.org/wp-content/uploads/2017/02/RIFFEL.pdf

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

Популярные посты:

• Ранее
• Архив