Квантование времени работы процессора

Алгоритмы планирования, основанные на квантовании

В основе многих
вытесняющих алгоритмов планирования
лежит концепция квантования. В соответствии
с этой концепцией каждому потоку
поочередно для выполнения предоставляется
ограниченный непрерывный период
процессорного времени — квант. Смена
активного потока происходит, если:

 поток завершился
и покинул систему;

 произошла
ошибка;

 поток перешел
в состояние ожидания;

 исчерпан квант
процессорного времени, отведенный
данному потоку.

Поток, который
исчерпал свой квант, переводится в
состояние готовности и ожидает, когда
ему будет предоставлен новый квант
процессорного времени, а на выполнение
в соответствии с определенным правилом
выбирается новый поток из очереди
готовых. Граф состояний потока,
изображенный на рис. 4.6, соответствует
алгоритму планирования, основанному
на квантовании.

Рис. 4.6. Граф
состояний потока в системе с квантованием

Кванты, выделяемые
потокам, могут быть одинаковыми для
всех потоков или различными. Рассмотрим,
например, случай, когда всем потокам
предоставляются кванты одинаковой
длины q (рис. 4.7). Если в системе имеется
п потоков, то время, которое поток
проводит в ожидании следующего кванта,
можно грубо оценить как q(n-l). Чем больше
потоков в системе, тем больше время
ожидания, тем меньше возможности вести
одновременную интерактивную работу
нескольким пользователям. Но если
величина кванта выбрана очень небольшой,
то значение произведения q(n-l) все равно
будет достаточно мало для того, чтобы
пользователь не ощущал дискомфорта от
присутствия в системе других пользователей.
Типичное значение кванта в системах
разделения времени составляет десятки
миллисекунд.

Рис. 4.7. Иллюстрация
расчета времени ожидания в очереди

Если квант короткий,
то суммарное время, которое проводит
поток в ожидании процессора, прямо
пропорционально времени, требуемому
для его выполнения (то есть времени,
которое потребовалось бы для выполнения
этого потока при монопольном использовании
вычислительной системы). Действительно,
поскольку время ожидания между двумя
циклами выполнения равно q(n-l), а количество
циклов B/q, где В — требуемое время
выполнения, то W*B(n-l). Заметим, что эти
соотношения представляют собой весьма
грубые оценки, основанные на предположении,
что В значительно превышает q. При этом
не учитывается, что потоки могут
использовать кванты не полностью, что
часть времени они могут тратить на
ввод-вывод, что количество потоков в
системе может динамически меняться и
т. д.

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

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

Потоки получают
для выполнения квант времени, но некоторые
из них используют его не полностью,
например из-за необходимости выполнить
ввод или вывод данных. В результате
возникает ситуация, когда потоки с
интенсивными обращениями к вводу-выводу
используют только небольшую часть
выделенного им процессорного времени.
Алгоритм планирования может исправить
эту «несправедливость». В качестве
компенсации за неиспользованные
полностью кванты потоки получают
привилегии при последующем обслуживании.
Для этого планировщик создает две
очереди готовых потоков (рис. 4.8). Очередь
1 образована потоками, которые пришли
в состояние готовности в результате
исчерпания кванта времени, а очередь 2
— потоками, у которых завершилась
операция ввода-вывода. При выборе потока
для выполнения прежде всего просматривается
вторая очередь, и только если она пуста,
квант выделяется потоку из первой
очереди.

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

Рис. 4.8. Квантование
с предпочтением потоков, интенсивно
обращающихся к вводу-выводу

ПРИМЕЧАНИЕ 

В алгоритмах,
основанных на квантовании, какую бы
цель они не преследовали (предпочтение
коротких или длинных задач, компенсация
недоиспользованного кванта или
минимизация накладных расходов, связанных
с переключениями), не используется
никакой предварительной информации о
задачах. При поступлении задачи на
обработку ОС не имеет никаких сведений
о том, является ли она короткой или
длинной, насколько интенсивными будут
ее запросы к устройствам ввода-вывода,
насколько важно ее быстрое выполнение
и т. д. Дифференциация обслуживания при
квантовании базируется на «истории
существования» потока в системе.

Соседние файлы в папке Лекции

• #
• #
• #
• #
• #
• #
• #
• #
• #

Состояния потоков и планирование их выполнения

Для каждого созданного потока в системе предусматриваются три возможных его состояния:

• состояние выполнения, когда код потока выполняется процессором; на однопроцессорных платформах в этом состоянии в каждый момент времени может находиться только один поток;
• состояние готовности к выполнению, когда поток готов продолжать свою работу и ждет освобождения ЦП;
• состояние ожидания наступления некоторого события; в этом случае поток не претендует на время ЦП, пока не наступит определенное событие (завершение операции ввода/вывода, освобождение необходимого потоку занятого ресурса, сигнала от другого потока); часто такие потоки называют блокированными.

Изменение состояния потока происходит в результате соответствующих действий. Удобно для этих целей использовать следующую диаграмму состояний и переходов.

Переходы между состояниями можно описать следующим образом:

• «готовность» → «выполнение»: система в соответствии с алгоритмом планирования выбирает для выполнения текущий поток, предоставляя ему ЦП
• «выполнение» → «готовность»: поток готов продолжать свою работу, но система принимает решение прервать его выполнение; чаще всего это происходит по следующим двум причинам:
  • завершается выделенное потоку время владения процессором;
  • в числе готовых к выполнению появляется более приоритетный поток по сравнению с текущим;
• «выполнение» → «ожидание»: дальнейшее исполнение кода текущего активного потока невозможно без наступления некоторого события, и поэтому активный поток прерывает свое выполнение и переводится системой в состояние ожидания (блокируется);
• «ожиданием» → «готовность»: в системе происходит некоторое событие, наступление которого ожидает один из блокированных потоков, и поэтому система переводит этот поток в состояние готовности (разблокирует), после чего он будет учитываться системой при планировании порядка предоставления ЦП;
• наконец, поток может нормально или аварийно завершить свое выполнение, после чего система удаляет его дескриптор из своей внутренней структуры, и тем самым поток перестает существовать.

В состояниях готовности и ожидания может находиться несколько потоков, поэтому система создает для хранения их дескрипторов отдельные списковые структуры. Организация этих списков зависит от тех принципов, которые положены в основу планирования потоков для данной ОС.

Цель планирования потоков вполне очевидна — определение порядка выполнения потоков в условиях внешней или внутренней многозадачности. Однако способы достижения этой цели существенно зависят от типа ОС. Рассмотрим сначала принципы планирования для универсальных ОС. Для таких ОС нельзя заранее предсказать, сколько и какие потоки будут запущены в каждый момент времени и в каких состояниях они будут находиться. Поэтому планирование должно выполняться динамически на
основе сбора и анализа информации о текущем состоянии вычислительной системы.

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

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

• обеспечение максимально возможной загрузки ЦП;
• обеспечение равномерной загрузки ресурсов вычислительной системы;
• обеспечение справедливого обслуживания всех процессов и потоков;
• минимизация времени отклика для интерактивных процессов.

За время существования ОС было предложено и реализовано несколько принципов управления потоками. В настоящее время большинство универсальных ОС используют метод вытесняющей многозадачности (preemptive multitasking), который тоже имеет несколько разновидностей. В основе метода лежат два важнейших и достаточно понятных принципа: квантование времени ЦП и приоритеты потоков.

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

Для эффективной работы ОС большое значение имеет выбор величины кванта. Очень маленькие значения кванта приводят к частым переключениям ЦП, что повышает непроизводительные расходы из-за необходимости постоянного сохранения контекста прерываемого потока и загрузки контекста активизируемого потока. Наоборот, большие значения кванта уменьшают иллюзию одновременного выполнения нескольких приложений. Некоторые планировщики умеют изменять кванты в определенных пределах, увеличивая их для тех потоков, которые не используют до конца выделенное время, например, из-за частых обращений к операциям ввода/вывода. Типичный диапазон изменения кванта – от 10 до 50 миллисекунд. При этом необходимо учитывать все возрастающие скорости работы современных процессоров: за 10 миллисекунд (т.е. за 1/100 секунды) процессор успеет выполнить около 10 млн. элементарных команд.

Можно связать величину кванта с приоритетом потока. Приоритет определяет важность потока и влияет на частоту запуска потока и, возможно, на величину выделяемого кванта. Интуитивно понятно, что потоки могут иметь разную степень важности: системные – более высокую (иначе ОС не сможет решать свои задачи), прикладные – менее высокую. Многие ОС позволяют группировать потоки по их важности, выделяя три группы, или класса:

• потоки реального времени с максимально высоким уровнем приоритета;
• системные потоки с меньшим уровнем приоритета;
• прикладные потоки с самым низким приоритетом.

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

Если приоритет потока может меняться системой, то такие приоритеты называют динамическими, иначе – фиксированными. Конечно, реализация фиксированных приоритетов гораздо проще, тогда как динамические приоритеты позволяют реализовать более справедливое распределение процессорного времени. Например, потоки, интенсивно использующие внешние устройства, очень часто блокируются до завершения выделенного кванта времени, т.е. не используют эти кванты полностью. Справедливо при разблокировании таких потоков дать им более высокий приоритет для быстрой активации, что обеспечивает большую загрузку относительно медленных внешних устройств. С другой стороны, если поток полностью расходует выделенный квант, система может после его приостановки уменьшить приоритет. Тем самым, более высокие приоритеты получают более короткие потоки, быстро освобождающие процессор, и следовательно, достигается более равномерная загрузка вычислительной системы в целом.

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

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

Схематично массив приоритетных очередей представлен на следующем рисунке, где для удобства более приоритетные потоки собраны в левой части массива, менее приоритетные – в правой, а сами приоритеты изменяются от 1 (максимум) до n (минимум). Условное обозначение «поток i.2» показывает, что данный поток имеет приоритет i и стоит вторым по порядку в своей очереди.

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

В итоге, планировщик включается в работу при возникновении одного из следующих событий:

• завершение кванта времени для текущего активного потока (сигнал от системного таймера);
• нормальное завершение кода текущего активного потока;
• аварийное завершение кода текущего активного потока;
• запрос активным потоком занятого системного ресурса;
• появление среди готовых потоков более приоритетного потока.

При этом запускается код планировщика, который просматривает приоритетные очереди и выбирает наиболее приоритетный поток. После этого происходит собственно само переключение потоков:

• формируется контекст прерываемого потока;

с помощью контекста вновь активизируемого потока восстанавливается необходимое состояние вычислительной системы, в частности, загружаются необходимые значения во все регистры процессора;

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

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

Автор этого материала — я — Пахолков Юрий. Я оказываю услуги по написанию программ на языках Java, C++, C# (а также консультирую по ним) и созданию сайтов. Работаю с сайтами на CMS OpenCart, WordPress, ModX и самописными. Кроме этого, работаю напрямую с JavaScript, PHP, CSS, HTML — то есть могу доработать ваш сайт или помочь с веб-программированием. Пишите сюда.

статьи IT, теория программирования, операционные системы, потоки

Квантовые компьютеры и квантовые вычисления — новый баззворд, который добавился в наше информационное пространство наряду с искусственным интеллектом, машинным обучением и прочими высокотехнологическими терминами. При этом мне так и не удалось найти в интернете материал, который бы сложил у меня в голове пазл под названием “как работают квантовые компьютеры”. Да, есть много прекрасных работ, в том числе и на хабре (см. Список ресурсов), комментарии к которым, как это обычно и бывает, еще более информативны и полезны, но картинка в голове, что называется, не складывалась.

А недавно ко мне подошли коллеги и спросили “Ты понимаешь как работает квантовый компьютер? Можешь нам рассказать?” И тут я понял, что проблема со складыванием в голове целостной картинки есть не только у меня.

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

Оглавление

• Дисклеймер
• Введение
  • Как все начиналось
  • Ведущие игроки
  • Направления развития
• Основы. Квантовый объект и квантовые системы
• Сравнение квантового компьютера и обычного
• Физические реализации кубитов
• Основы. Принцип работы квантового компьютера
• Квантовые алгоритмы
  • Алгоритм Шора.
  • Алгоритм Гровера
  • Алгоритм Дойча-Йожи
• Проблемы квантовых компьютеров
  • Декогеренция
  • Ошибки
  • Архитектура процессора
  • Итоги
• Пути решения проблем
• D-Wave
• Немного об эмуляции квантовых компьютеров
• Квантовое вычислительное превосходство.
• Заявление Google
• Резюме
• Заключение
• Благодарности
• Список ресурсов

Дисклеймер

(к оглавлению)

Автор не является специалистом в квантовых вычислениях, и целевая аудитория статьи — такие же ИТ-шники, не квантовые специалисты, которые тоже хотят собрать в голове картинку под названием “Как работают квантовые компьютеры”. Из-за этого многие понятия в статье сознательно упрощены для лучшего понимания квантовых технологий на “базовом” уровне, но без совсем уж сильного упрощения с потерей информативности и адекватности.

В статье, в некоторых местах используются материалы из других источников, список которых приведен в конце статьи. Везде где это было возможно, вставлены прямые ссылки и указания на оригинал текста, таблицы или рисунка. Если где-то что-то (или кого-то) забыл, пишите — поправлю.

Введение

(к оглавлению)

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

Как все начиналось

(к оглавлению)

Точкой отсчета квантовой эры принято считать 1900 год, когда М. Планк впервые выдвинул гипотезу о том, что энергия испускается и поглощается не непрерывно, а отдельными квантами (порциями). Идею подхватили и развили многие выдающиеся ученые того времени — Бор, Эйнштейн, Гейзенберг, Шредингер, что, в конечном счете, привело к созданию и развитию такой науки как квантовая физика. Про становление квантовой физики как науки в Сети есть много хороших материалов, в этой статье мы не будем подробно останавливаться на этом, но указать дату, когда мы вошли в новую квантовую эпоху, было необходимо.

Квантовая физика принесла в нашу обычную жизнь много изобретений и технологий, без которых сейчас трудно себе представить окружающий мир. Например, лазер, который сейчас используется везде, от бытовой техники (лазерные нивелиры и прочее) до высокотехнологичных систем (лазеры для коррекции зрения, привет meklon ). Логично было бы предположить, что рано или поздно кто-то выдвинет идею о том, что почему бы не использовать квантовые системы для вычислений. И вот в 1980 году это случилось.

Википедия указывает на то, что первым идею квантовых вычислений высказал в 1980 году наш ученый Юрий Манин. Но реально заговорили о ней только в 1981, когда небезызвестный Р. Фейнман в докладе на первой конференции по физике вычислений, проведенной в Массачусетском технологическом институте, отметил, что невозможно моделировать эволюцию квантовой системы на классическом компьютере эффективным способом. Он предложил элементарную модель квантового компьютера, который будет способен провести такое моделирование.

В Сети есть вот такая работа, в которой хронология развития квантовых вычислений рассматривается более академически и подробно, мы же пробежимся коротко:

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

• [1994]. П.Шор. Разработан квантовый алгоритм факторизации чисел
• [1998]. Создан первый 2-х кубитный квантовый компьютер
• [2001]. IBM представил выполнение алгоритма Шора для разложения числа 15
• [2007-2016]. D-Wave создает и развивает компьютер с 128-2000 кубитов
• [2012]. В Университете Калифорнии реализовали алгоритм Шора для числа 21
• [2016]. Google смоделировал молекулу водорода на 9-и кубитном компьютере
• [2017]. IBM смоделировала гидрид бериллия BeH2 (три атома)
• [2019]. IBM Q System One. 20-и кубитный компьютер в облаке
• [2019]. Google Sycamore. 53-х кубитный компьютер. Квантовое превосходство?

Как вы видите прошло 17 лет (с 1981 до 1998) с момента идеи до ее первой реализации в компьютере с 2-мя кубитами, и 21 год (с 1998 до 2019) до момента, когда количество кубитов увеличилось до 53-х. Потребовалось 11 лет (с 2001 до 2012) чтобы улучшить результат выполнения алгоритма Шора (мы остановимся на нем подробнее чуть далее) с числа 15 до 21. Также только три года назад мы подошли к тому, чтобы реализовать то, о чем говорил Фейнман, и научиться моделировать простейшие физические системы.

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

Ведущие игроки

(к оглавлению)

Слайды для этого раздела взяты из статьи Квантовый компьютер: большая игра на повышение. Лекция в Яндексе, от научного сотрудника Российского квантового центра Алексея Фёдорова. Позволю себе прямые цитаты:

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

В квантовой гонке участвуют не только государства, но и частные компании. Суммарно Google, IBM, Intel и Microsoft вложили около 0,5 млрд долларов в развитие квантовых компьютеров за последнее время, создали крупные лаборатории и исследовательские центры.

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

Направления развития

(к оглавлению)

На текущий момент (могу ошибаться, поправьте) основные усилия (и более-менее значимые результаты) у всех ведущих игроков сосредоточены на двух направлениях:

• Специализированные квантовые компьютеры, которые направлены на решение одной конкретной специфической задачи, например, задачи оптимизации. Примером продукта являются квантовые компьютеры D-Wave.
• Универсальные квантовые компьютеры — которые способны реализовать произвольные квантовые алгоритмы (Шора, Гровера, и т.д.). Реализации от IBM, Google.

Прочие же вектора развития, которые дает нам квантовая физика, такие как:

• квантовые сенсоры
• квантовая сеть как основа для квантовой криптографии
• и многое другое

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

Дополнительно можно почитать дорожную карту развития квантовых технологий, ну и гуглите “развитие квантовых технологий”, например, вот, вот и вот.

Основы. Квантовый объект и квантовые системы

(к оглавлению)

Самое главное, что надо понять из этого раздела, это то, что

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

Что же такое квантовый объект?

Квантовый объект — объект микромира (квантового мира), который проявляет квантовые свойства:

• Имеет определенное состояние с двумя граничными уровнями
• Находится в суперпозиции своего состояния до момента измерения
• Запутывается с другими объектами для создания квантовых систем
• Выполняет теорему о запрете клонирования (нельзя скопировать состояние объекта)

Разберем каждое свойство более подробно:

Имеет определенное состояние с двумя граничными уровнями (конечное состояние)

Классический пример из реального мира — монета. У нее есть состояние “сторона”, которая принимает два граничных уровня — “орел” и “решка”.

Находится в суперпозиции своего состояния до момента измерения

Подбросили монетку, она летит и вращается. Пока она вращается невозможно сказать в каком из граничных уровней находится ее состояние “сторона”. Но стоит нам ее прихлопнуть и посмотреть на результат — как суперпозиция состояний тут же схлопывается в одно из двух граничных — “орел” и “решка”. Прихлопывание монетки в нашем случае и есть измерение.

Запутывается с другими объектами для создания квантовых систем

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

Выполняет теорему о запрете клонирования (нельзя скопировать состояние объекта)

Пока монетки летят и вращаются, мы никаким образом не можем создать отдельную от системы копию вращающегося состояния любой из монеток. Система живет сама в себе и очень ревностно относится к тому, чтобы выдать наружу какую-либо информацию.

Еще пара слов о самом понятии “суперпозиции”, практически во всех статьях суперпозицию объясняют как “находится во всех состояниях одновременно”, что, конечно, верно, но временами излишне запутывает. Суперпозицию состояний можно представить себе также как то, что в каждый момент времени у квантового объекта есть определенные вероятности схлопнуться в каждый из своих граничных уровней, и в сумме эти вероятности, естественно, равны 1. Далее при рассмотрении кубита мы остановимся на этом более подробно.

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

Любой объект, для которого выполняются вышеуказанные свойства и который мы можем создать и управлять, может использоваться как носитель информации в квантовом компьютере.

Чуть дальше мы поговорим о текущем состоянии дел с физической реализацией кубитов как квантовых объектов, и что сейчас ученые используют в этом качестве.

Итак, третье свойство гласит, что квантовые объекты могут запутываться для создания квантовых систем. Что же такое квантовая система?

Квантовая система — система запутанных квантовых объектов, обладающая следующими свойствами:

• Квантовая система находится в суперпозиции всех возможных состояний объектов, из которых она состоит
• Нельзя узнать состояние системы до момента измерения
• В момент измерения система реализует один из возможных вариантов своих граничных состояний

(и, забегая чуть вперед)

Следствие для квантовых программ:

• Квантовая программа имеет заданное состояние системы на входе, суперпозицию внутри, суперпозицию на выходе
• На выходе программы после измерения имеем вероятностную реализацию одного из возможных конечных состояний системы (плюс возможные ошибки)
• Любая квантовая программа имеет архитектуру дымоходной трубы (вход -> выход. Нет циклов, нельзя посмотреть состояние системы в середине процесса.)

Сравнение квантового компьютера и обычного

(к оглавлению)

Давайте теперь сравним обычный компьютер и квантовый.

Логический уровень

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

Для этого придумали кубит. В своих граничных состояниях он реализует похожие на 0 и 1 состояния |0> и |1>, а в суперпозиции представляет собой вероятностное распределение над своими граничными состояниями |0> и |1>:

 a|0> + b|1>, такое, что a^2+b^2=1

a и b при этом представляют собой амплитуды вероятностей, а квадраты их модулей — собственно вероятности получить именно такие значения граничных состояний |0> и |1>, если схлопнуть кубит измерением прямо сейчас.

Физический уровень

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

Носитель информации

Для обычного компьютера это электрический ток — уровни напряжения, наличие или отсутствие тока, и т.д., для квантового — то самое состояние квантового объекта (направление поляризации, спин, и т.д.), которое может находится в состоянии суперпозиции.

Операции

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

Примеры квантовых вентилей:

Есть понятие универсального набора вентилей, которых достаточно для выполнения любого квантового вычисления. Например, универсальным является набор, включающий вентиль Адамара, вентиль фазового сдвига, вентиль CNOT и вентиль π⁄8. С их помощью можно выполнить любое квантовое вычисление на произвольном наборе кубитов.

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

• Операции над квантовыми объектами требуют создания новых логических операторов (квантовых вентилей)
• Квантовые вентили бывают однокубитные и двухкубитные
• Существуют универсальные наборы вентилей, с помощью которых можно выполнить любое квантовое вычисление

Взаимосвязь

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

Один кубит нам тоже совершенно бесполезен (ну если только в академическом плане),

чтобы производить вычисления нам нужна система кубитов (квантовых объектов)

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

Алгоритмы

Стандартные алгоритмы, которые накопило человечество к текущему моменту, совершенно не подходят для реализации на квантовом компьютере. Да в общем-то и незачем. Квантовые компьютеры, основанные на вентильной логике над кубитами, требуют создания совершенно иных алгоритмов, квантовых алгоритмов. Из наиболее известных квантовых алгоритмов можно выделить три:

• Алгоритм Шора (факторизация)
• Алгоритм Гровера (быстрый поиск в неупорядоченной базе данных)
• Алгоритм Дойча-Йожи (ответ на вопрос, постоянная или сбалансированная функция)

Принцип

И самое главное отличие — это принцип работы. У стандартного компьютера это цифровой, жестко детерминированный принцип, основанный на том, что если мы задали какое-то начальное состояние системы и пропустили его через заданный алгоритм, то результат вычислений будет один и тот же, сколько бы раз мы это вычисление не запускали. Собственно, такое поведение это именно то, что мы от компьютера и ждем.

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

Такая вероятностная природа квантовых вычислений обусловлена самой вероятностной сутью квантового мира. “Бог не играет в кости со вселенной”, — говорил старик Эйнштейн, но все эксперименты и наблюдения пока (в текущей научной парадигме) подтверждают обратное.

Физические реализации кубитов

(к оглавлению)

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

“Если мы умеем помещать атом в два разных уровня и управлять ими, то вот вам и кубит. Если мы можем это сделать с ионом, — кубит. С током то же самое. Если мы запускаем его по часовой стрелке и против часовой стрелки одновременно, вот вам кубит.” (С)

Есть прекрасный комментарий к статье, в котором текущее многообразие физических реализаций кубита рассматривается более подробно, мы же просто перечислим наиболее известные и распространенные:

• сверхпроводниковые кубиты
• зарядовые кубиты
• ионные ловушки
• квантовые точки
• и множество других экзотических идей (анионы и прочее)

Из всего этого многообразия наиболее проработанным является первый метод получения кубитов, основанный на сверхпроводниках. Google, IBM, Intel и прочие ведущие игроки используют именно его для построения своих систем.

Ну и еще почитайте обзор возможных физических реализаций кубитов от Andrew Daley,2014.

Основы. Принцип работы квантового компьютера

(к оглавлению)

Материалы для данного раздела (задача и картинки) взяты из статьи “Просто о сложном. Как работает квантовый компьютер”.

Итак, представим, что у нас есть следующая задача:

Есть группа из трех человек: (А)ндрей, (B)олодя и (С)ережа. Есть два такси (0 и 1).

Известно также, что :

• (А)ндрей, (B)олодя — друзья
• (А)ндрей, (С)ережа — враги
• (B)олодя и (С)ережа — враги

Задача: Разместить народ по такси так, чтобы Max(друзья) и Min(враги)

Оценка: L = (кол-во друзей) — (кол-во врагов) для каждого варианта размещения

ВАЖНО: Предположим, что эвристик нет, оптимального решения нет. В этом случае задача решается только полным перебором вариантов.

Решение на обычном компьютере

Как решать эту задачу на обычном (супер)компьютере (или кластере) — понятно, что надо перебрать в цикле все возможные варианты. Если у нас мультипроцессорная система, то можно распараллелить расчет решений на несколько процессоров и потом собрать результаты.

У нас 2 возможных варианта размещения (такси 0 и такси 1) и 3 человека. Пространство решений 2^3 = 8. Перебрать 8 вариантов можно даже на калькуляторе, это не проблема. А теперь усложним задачу — у нас 20 человек и два автобуса, пространство решений 2^20 = 1 048 576. Тоже ничего сложного. Увеличим количество людей в 2.5 раза — возьмем 50 человек и два поезда, пространство решений теперь 2^50 = 1.12 x 10^15. У обычного (супер)компьютера уже начинаются серьезные проблемы. Увеличим кол-во людей в 2 раза, 100 человек дадут нам уже 1.2 x 10^30 возможных вариантов.

Все, за разумное время эту задачу не посчитать.

Подключаем суперкомпьютер

Самый мощный компьютер в настоящее время — номер 1 из Top500, это Summit, производительностью 122 Пфлопс. Предположим, что на расчет одного варианта нам достаточно 100 операций, тогда для решения задачи для 100 человек нам потребуется:

(1.2 x 10^30 100) / 122×10^15 / (606024365) = 3 х 10^37 лет.

Как мы видим, при увеличении размерности исходных данных пространство решений растет по степенному закону, в общем случае для N битов у нас есть 2^N возможных вариантов решения, которые при сравнительно небольших N (100) дают нам непросчитываемое (на текущем технологическом уровне) пространство решений.

Есть ли альтернативы? Как вы уже догадались, таки да, есть.

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

Совсем немного комбинаторики, теории вероятностей и странного экспериментатора

Возьмем мешок и положим в него 1000 белых и 1000 черных шаров. Будем проводить эксперимент — вынимать шар, записывать цвет, возвращать шар в мешок и перемешивать шары в мешке.

Провели эксперимент 10 раз, вытащили 10 черных шаров. Возможно? Вполне. Дает нам эта выборка какое-то разумное понятие об истинном распределение в мешке? Очевидно, что нет. Что надо сделать — правильно, повторить эксперимент миллион раз и рассчитать частоты выпадения черных и белых шаров. Получим, например 49.95% черных и 50.05% белых. В этом случае уже более-менее понятна структура распределения из которого мы семплируем (вынимаем один шарик).

Главное, что надо понять, что сам эксперимент имеет вероятностную природу, одним семплом (шариком) мы не узнаем истинную структуру распределения, нам надо многократно повторить эксперимент и усреднить результаты.

Добавим в наш мешок 10 красных и 10 зеленых шаров (ошибки). Повторим эксперимент 10 раз. Вытащили 5 красных и 5 зеленых. Возможно? Да. Можем что-то сказать об истинном распределении — Нет. Что надо сделать — ну вы поняли.

Для получения понимания о структуре вероятностного распределения надо многократно просемплировать единичные исходы из этого распределения и усреднить результаты.

Связываем теорию с практикой

Теперь вместо черных и белых шаров давайте возьмём бильярдные шары, и положим в мешок 1000 шаров с номером 2, 1000 с номером 7 и 10 шаров с другими номерами. Представим себе экспериментатора, который обучен простейшим действиям (достать шар, записать номер, положить шар обратно в мешок, перемешать шары в мешке) и делает он это за 150 микросекунд. Ну такой экспериментатор на спидах (не реклама наркотиков!!!). Тогда за 150 секунд он сможет провести наш эксперимент 1 миллион раз и предоставить нам результаты усреднения.

Усадили экспериментатора, дали мешок, отвернулись, подождали 150 секунд — получили:

номер 2 — 49.5%, номер 7 — 49.5%, остальные номера в сумме — 1%.

Да, все верно, наш мешок — это квантовый компьютер с алгоритмом, решающим нашу задачу, а шары — возможные варианты решения. Поскольку правильных решений два, то квантовый компьютер будет выдавать нам равновероятно любое из этих возможных решений, и 0.5% (10/2000) ошибок, о которых мы поговорим позднее.

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

Масштабируемость квантового компьютера

Теперь представим себе, что для задачи, в которой участвуют 100 человек (пространство решений 2^100 мы помним об этом), правильных решений тоже только два. Тогда, если взять 100 кубитов и написать алгоритм, вычисляющий нашу целевую функцию (L, см. выше) над этими кубитами, то мы получим мешок, в котором будет 1000 шаров с номером первого правильного ответа, 1000 с номером второго правильного ответа и 10 шаров с другими номерами. И наш экспериментатор за те же 150 секунд выдаст нам оценку вероятностного распределения правильных ответов.

Время выполнения квантового алгоритма (с некоторыми допущениями) можно считать константным О(1) по отношению к размерности пространства решений (2^N).

И вот именно это свойство квантового компьютера — константность времени выполнения по отношению к возрастающей по степенному закону сложности пространства решений и является ключевым.

Кубит и параллельные миры

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

Смотрите, мы говорили, что кубит как квантовый объект реализует одно из двух своих состояний при его наблюдении, но в “живой природе” находится в суперпозиции состояний, то есть находится в обоих своих граничных состояниях одновременно (с некоторой вероятностью).

Возьмем (А)ндрея и представим его состояние (в каком он транспортном средстве — 0 или 1) как кубит. Тогда у нас возникает (в квантовом пространстве) два параллельных мира, в одном (А) сидит в такси 0, в другом мире — в такси 1. Одновременно в двух такси, но с некоторой вероятность найти его в каждом из них при наблюдении.

Возьмем (В)олодю и тоже представим его состояние как кубит. Возникает два других параллельных мира. Но пока эти пары миров (А) и (В) никак не взаимодействуют. Что надо сделать, чтобы создать связанную систему? Правильно, надо эти кубиты связать (запутать). Берем и запутываем (А) с (В) — получаем квантовую систему из двух кубитов (А, В), реализующую внутри себя четыре взаимозависимых параллельных мира. Добавляем (С)ергея и получаем систему из трех кубитов (АВС), реализующую восемь взаимозависимых параллельных миров.

Сутью квантовых вычислений (реализации цепочки квантовых вентилей над системой связанных кубитов) является тот факт, что вычисление происходит во всех параллельных мирах одновременно.

И неважно сколько их у нас, 2^3 или 2^100, квантовый алгоритм выполнится за конечное время над всеми этими параллельными мирами и выдаст нам результат, представляющий собой семпл из вероятностного распределения ответов алгоритма.

Для лучшего понимания можно себе представить, что квантовый компьютер на квантовом уровне запускает 2^N параллельных процессов решения, каждый из которых работает над одним возможным вариантом, потом собирает результаты работы — и выдает нам ответ в виде суперпозиции решения (вероятностного распределения ответов), из которого мы каждый раз (при каждом эксперименте ) семплируем одно.

Запомните время, необходимое нашему экспериментатору (150 мкс) для проведения эксперимента, это пригодится нам чуть дальше, когда мы будем говорить об основных проблемах квантовых компьютеров и о времени декогеренции.

Квантовые алгоритмы

(к оглавлению)

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

Наиболее известные на сегодняшний день алгоритмы это:

• Алгоритм Шора
• Алгоритм Гровера
• Алгоритм Дойча — Йожи

В отличие от классических, квантовые компьютеры не универсальны.
До сих пор найдено лишь небольшое число квантовых алгоритмов.(С)

Спасибо oxoron за ссылку на Quantum Algorithm Zoo, место, где, по уверениям автора («Stephen Jordan»), собраны и продолжают собираться лучшие представители квантово-алгоритмического мира.

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

Алгоритм Шора.

(к оглавлению)

Наиболее известным квантовым алгоритмом является алгоритм Шора (придумал в 1994 году английский математик Питер Шор), который нацелен на решение задачи разложения чисел на простые множители (задача факторизации, дискретного логарифма).

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

На сегодняшний день результаты более чем скромные. Лучшие результаты факторизации с помощью алгоритма Шора — числа 15 и 21, что сильно меньше, чем 2048 бит. Для остальных результатов из таблицы применялся иной алгоритм расчетов, но даже лучший по этому алгоритму результат (291311) сильно далек от реального применения.

Подробнее про алгоритм Шора можно почитать, например, вот тут. Про практическую реализацию — тут.

Одна из текущих оценок сложности и необходимой мощности для факторизации числа из 2048 бит это компьютер с 20 миллионами кубитов. Спим спокойно.

Алгоритм Гровера

(к оглавлению)

Алгоритм Гровера — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году.

Алгоритм Гровера может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.(С)

Подробнее можно почитать вот тут, или тут. Еще вот тут есть хорошее объяснение алгоритма на примере ящиков и мяча, но, к сожалению, по независящим ни от кого причинам, данный сайт у меня из России не открывается. Если у вас этот сайт тоже заблокирован, то вот краткая выжимка:

Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).

Как решать эту задачу? Самым тупым способом, по очереди открывать коробки, и рано или поздно вы наткнетесь на коробку с мячиком. А сколько в среднем коробок нужно проверить до того, как будет обнаружена коробка с мячиком? В среднем нужно открыть примерно половину коробок N/2. Главное здесь то, что если мы увеличим число коробок в 100 раз, то в те же 100 раз увеличится и среднее число коробок, которые нужно открыть до того, как будет найдена коробка с мячиком.

Теперь сделаем ещё одно уточнение. Пусть мы не сами открываем коробки руками и проверяем наличие мячика в каждой, а имеется некий посредник, назовем его Оракул (Oracle). Мы говорим Оракулу — «проверь коробку номер 732», и Оракул честно проверяет и отвечает «в коробке номер 732 мячика нет». Теперь вместо слов о том, сколько коробок нам нужно в среднем открыть, мы говорим «сколько раз в среднем мы должны обратиться к Оракулу для того, чтобы найти номер коробки с мячиком»

Оказывается, что если перевести эту задачу с коробками, мячиком и Оракулом на квантовый язык, то выходит замечательный результат: для поиска номера коробки с мячиком среди N коробок нам нужно потревожить Оракула всего примерно SQRT(N) раз!

То есть сложность задачи перебора используя алгоритм Гровера снижается в квадратный корень раз.

Алгоритм Дойча-Йожи

(к оглавлению)

Алгоритм Дойча — Йожи (упоминается также как алгоритм Дойча — Джозы) — [квантовый алгоритм](https://ru.wikipedia.org/wiki/%D0%9A%D0%B2%D0%B0%D0%BD%D1%82%D0%BE%D0%B2%D1%8B%D0%B9%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC), предложенный Давидом Дойчем и Ричардом Йожей в 1992 году, и ставший одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. _

Задача Дойча — Йожи заключается в определении, является ли функция нескольких двоичных переменных F(x1, x2, … xn) постоянной (принимает либо значение 0, либо 1 при любых аргументах) или сбалансированной (для половины области определения принимает значение 0, для другой половины 1). При этом считается априорно известным, что функция либо является константой, либо сбалансирована. (С)

Еще можно почитать тут. Более простое объяснение:

Алгоритм Дойча (Дойча — Йожи) основан на переборе, но позволяет делать его быстрее обычного. Представьте, что на столе лежит монета и необходимо узнать фальшивая ли она или нет. Для этого нужно дважды посмотреть на монету и определить: «орел» и «решка» – настоящая, два «орла», две «решки» — фальшивая. Так вот, если использовать квантовый алгоритм Дойча, то это определение можно сделать одним взглядом – измерением. (С)

Проблемы квантовых компьютеров

(к оглавлению)

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

• Чувствительность к окружению и взаимодействию с окружением
• Накопление ошибок при вычислениях
• Сложности с начальной инициализации состояний кубитов
• Сложности с созданием многокубитных систем

Крайне рекомендую прочитать статью “Характеристики квантовых компьютеров”, особенно комментарии к ней.

Давайте организуем все основные проблемы в три большие группы и рассмотрим поподробнее каждую из них:

Декогеренция

(к оглавлению)

Описание от N+1.

Квантовое состояние очень хрупкая штука, кубиты в запутанном состоянии крайне нестабильны, любое внешнее воздействие может разрушить (и разрушает) эту связь. Изменение температуры на мельчайшую долю градуса, давление, пролетевший рядом случайный фотон — все это дестабилизирует нашу систему.

Для решения этой проблемы строят низкотемпературные саркофаги, в которых температура (-273.14 градуса цельсия) чуть-чуть выше абсолютного ноля, с максимальной изоляцией внутренней камеры с процессором от всех (возможных) воздействий внешней среды.

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

На текущий момент время декогеренции в лучших квантовых решениях составляет порядка десятков и сотен микросекунд.

Есть прекрасный сайт, на котором можно посмотреть сравнительные таблицы параметров всех созданных квантовых систем. В эту статью для примера вынесены только два топовых процессора — от IBM IBM Q System One и от Google Sycamore. Как мы видим, время декогеренции (Т2) не превышает 200 мкс.

Я не нашел точных данных по Sycamore, но в самой статье о квантовом превосходстве приводятся две цифры — 1 миллион вычислений за 200 секунд, в другом месте — за 130 секунд без потерь на управляющие сигналы и прочее. В любом случае это дает нам время декогеренции порядка 150 мкс. Помните нашего экспериментатора с мешком? Ну так вот он.

Чем нам грозит декогеренция?

Основная проблема в том, что через 150 мкс наша вычислительная система из N запутанных кубитов начнет выдавать на выходе вместо вероятностного распределения правильных решений — вероятностный белый шум.

То есть нам надо:

• Инициализировать систему кубитов
• Провести вычисление (цепочка вентильных операций)
• Считать результат

И сделать все это за 150 мкс. Не успел — результат превратился в тыкву.

Но это еще не все…

Ошибки

(к оглавлению)

Как мы уже говорили, квантовые процессы и квантовые вычисления имеют вероятностную природу, мы не можем быть уверены на 100% ни в чем, а только с какой-то вероятностью. Ситуация усугубляется еще и тем, что квантовые вычисления подвержены ошибкам. Основные типы ошибок при квантовых вычислениях это:

• Ошибки декогеренции, обусловлены сложностью системы и взаимодействием с внешней средой
• Вычислительные ошибки гейтов (обусловлены квантовой природой вычислений)
• Ошибки считывания финального состояния (результата)

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

Вычислительные ошибки гейтов — любая операция (вентиль) над кубитами может с некоторой вероятностью завершиться с ошибкой, а нам для реализации алгоритма нужно выполнить сотни вентилей, вот и представьте, что мы получим в конце выполнения нашего алгоритма. Классический вариант ответа на вопрос — “Какова вероятность встретить динозавра в лифте?” — 50х50, или встретишь или нет.

Проблема еще усугубляется тем, что стандартные методы коррекции ошибок (дублирование вычислений и усреднение) в квантовом мире не работают из-за теоремы о запрете клонирования. Для коррекции ошибок в квантовых вычислениях пришлось придумать квантовые же методы коррекции. Грубо говоря мы берем N обычных кубитов и делаем из них 1 логический кубит с меньшим уровнем ошибок.

Но тут возникает другая проблема — общее количество кубитов. Смотрите, допустим у нас есть процессор со 100 кубитами, из которых 80 кубитов заняты коррекцией ошибок, тогда нам для вычислений остается только 20.

Ошибки считывания финального результата — как мы помним, результат квантовых вычислений нам представлен в виде вероятностного распределения ответов. Но считывание финального состояния тоже может завершиться с ошибкой.

На том же сайте есть сравнительные таблицы процессоров по уровням ошибок. Для сравнения возьмем те же процессоры, что и в предыдущем примере — IBM IBM Q System One и Google Sycamore:

Здесь фиделити — мера схожести двух квантовых состояний. Величину ошибки можно грубо представить как 1-Fidelity. Как мы видим, ошибки на 2-х кубитных гейтах и ошибки считывания являются главным препятствием к выполнению сложных и длинных алгоритмов на существующих квантовых компьютерах.

Еще можно почитать роадмап от 2016 года от NQIT по решению задачи коррекции ошибок.

Архитектура процессора

(к оглавлению)

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

Если же нам надо запутать 1-й кубит, скажем, с 12-м, то нам придется строить цепочку дополнительных квантовых операций, задействовать дополнительные кубиты и прочее, что увеличивает общий уровень ошибок. Да, и не забывайте про время декогеренции, возможно к тому моменту, когда вы закончите связывать кубиты в нужную вам схему, время закончится и вся схема превратится в симпатичный генератор белого шума.

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

Максимальная связность и максимальное количество кубитов для тех же топовых чипов:

И, для сравнения, таблица с данными предыдущего поколения процессоров. Сравните количество кубитов, время декогеренции и процент ошибок с тем, что мы имеем сейчас у нового поколения. Все-таки прогресс потихоньку, но движется.

Итак:

• На текущий момент нет полносвязных архитектурных схем из > 6 кубитов
• Чтобы на реальном процессоре запутать кубит 0 с, например, 15-м может потребоваться несколько десятков дополнительных операций
• Больше операций -> больше ошибок -> сильнее влияние декогерентности

Итоги

(к оглавлению)

Декогеренция — прокрустово ложе современных квантовых вычислений. В 150 мкс мы должны уложить все:

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

Пока результаты неутешительные, хотя вот тут заявляют о достижении 0.5с времени удержания когерентности на квантовом компьютере, основанном на ионных ловушках:

We measure a qubit coherence time in excess of 0.5 s, and with magnetic shielding we expect this to improve to be longer than 1000 s

Про эту технологию еще можно почитать здесь или, например, здесь.

Ситуация осложняется еще и тем, что при совершении сложных вычислений необходимо использовать квантовые схемы коррекции ошибок, что тоже отъедает и время, и доступные кубиты.

Ну и, наконец, современные архитектуры не позволяют с минимальными затратами реализовать схемы запутанности лучше, чем 1 к 4 или 1 к 6.

Пути решения проблем

(к оглавлению)

Для решения вышеуказанных проблем, в настоящее время используют следующие подходы и методы:

• Использование криокамер с низкими температурами (10 мК (–273,14°C))
• Использование максимально защищенных от внешних воздействий процессорных блоков
• Использование систем квантовой коррекции ошибок (Логический кубит)
• Использование оптимизаторов при программировании схем для конкретного процессора

Также проводятся исследования, направленные на увеличение времени декогеренции, на поиск новых (и доработку известных) физических реализаций квантовых объектов, на оптимизацию схем коррекции и прочее и прочее. Прогресс есть (посмотрите выше на характеристики более ранних и топовых на сегодняшний день чипов), но пока идет медленно, очень очень медленно.

D-Wave

(к оглавлению)

2000-кубитный компьютер D-Wave 2000Q. Источник: D-Wave Systems

На фоне заявления Google о достижении квантового превосходства используя процессор с 53-мя кубитами, компьютеры и анонсы от компании D-Wave, в которых число кубитов исчисляется тысячами, несколько сбивает с толку. Ну действительно, если 53 кубита смогли достичь квантового превосходства, то на что же способен компьютер с 2048 кубитами? Но не все так хорошо…

Если коротко (взято из вики):

Компьютеры D-Wave работают на принципе квантовой релаксации (квантовый отжиг), могут решать крайне ограниченный подкласс задач оптимизации, и не подходят для реализации традиционных квантовых алгоритмов и квантовых вентилей.

Более подробно можно почитать, например, тут, тут (осторожно, может не открываться из России), или у Scott Aaronson в статье из его блога. Кстати, очень рекомендую почитать вообще его блог, там много хорошего материала

Вообще с самого начала анонсов у научного сообщества возникали вопросы к компьютерам D-Wave. Например, в 2014 году IBM поставила под сомнение факт, что D-Wave использует квантовые эффекты. Дело дошло до того, что в 2015 году Google вместе с NASA купила один из таких квантовых компьютеров и после исследований подтвердила, что таки да, компьютер работает и вычисляет задачу быстрее, чем обычный. Еще про заявление Google можно почитать тут и, например, тут.

Главное, что компьютеры D-Wave, с их сотнями и тысячами кубитов нельзя использовать для вычисления и запуска квантовых алгоритмов. На них нельзя запустить алгоритм Шора, например. Все, что они могут — это используя определенные квантовые механизмы решать определенную задачу оптимизации. Можно считать, что D-Wave это такой квантовый ASIC для конкретной задачи.

Немного об эмуляции квантовых компьютеров

(к оглавлению)

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

• Состояние кубита можно представить комплексным числом, занимающим от 2х32 до 2х64 бита (8-16 байт) в зависимости от архитектуры процессора
• Состояние N связанных кубитов можно представить в виде 2^N комплексных чисел, т.е. 2^(3+N) для 32-х битной архитектуры и 2^(4+N) для 64-х битной.
• Квантовую операцию над N кубитами можно представить матрицей 2^N x 2^N

Тогда:

• Для хранения эмулируемых состояний 10 кубитов нужны 8 КБ
• Для хранения состояний 20 кубитов нужны 8 МБ
• Для хранения состояний 30 кубитов нужны 8 ГБ
• Для хранения состояний 40 кубитов нужны 8 Терабайт
• Для хранения состояний 50 кубитов нужны 8 Петабайт и т.д.

(С)

Для сравнения, Summit (Top-1 из Top-500) несет на себе всего 2.8 Петабайт памяти.

Текущий рекорд симуляций — 49 кубит поставленный в прошлом году на крупнейшем китайском суперкомпьютере (Sunway Taihu Light)

Предел симуляции квантового компьютера на классических системах обусловлен количеством оперативной памяти необходимой для хранения состояния кубитов.

Рекомендую еще прочитать вот этот комментарий. Оттуда:

По операциям — для точной эмуляции схемы на 49 кубитов из каких-то 39 «тактов» (независимых слоев вентилей) потребовалось 2^63 комплексных умножений — 4 Пфлопс суперкомпьютера на протяжении 4 часов

Эмуляция квантового компьютера из 50+ кубит на классических системах считается невыполнимой за разумное время. В том числе из-за этого факта Google использовал для своего эксперимента с квантовым превосходством процессор с 53-мя кубитами.

Квантовое вычислительное превосходство.

(к оглавлению)

Википедия дает нам следующее определение квантового вычислительного превосходства:

Ква́нтовое превосхо́дство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить.

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

Но в формулировке определения есть некоторая лазейка, “которые классические компьютеры практически не могут решить”. Фактически это означает, что если создать квантовый компьютер из 50+ кубитов и запустить на нем некоторую квантовую схему, то, как мы рассматривали выше, результат работы этой схемы невозможно будет сэмулировать на обычном компьютере. То есть классический компьютер воссоздать результат работы такой схемы будет не в состоянии.

Является ли такой результат реальным квантовым превосходством или нет, вопрос скорее философский. Но понимать, что сделал Google, и на чем основано его недавнее заявление о достижении квантового превосходства на своем новом процессоре Sycamore надо.

Заявление Google о достижении квантового превосходства

(к оглавлению)

54-кубитный процессор Sycamore

Итак, в октябре 2019 года разработчики Google опубликовали в научном издании Nature статью «Квантовое превосходство с применением программируемого сверхпроводящего процессора». Авторы объявили о достижении впервые в истории квантового превосходства с помощью 54-кубитного процессора «Sycamore».

В сети в статьях Sycamore часто упоминают то как 54-х кубитный процессор, то как 53-х. Истина в том, что согласно оригинальной статье, процессор физически состоит из 54-х кубитов, но один из них нерабочий и выведен из эксплуатации. Таким образом, в реальности мы имеем 53-х кубитный процессор.

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

Позднее сотрудники отдела квантовых вычислений компании IBM заявили, что Google ложно сообщила о достижении квантового превосходства. В компании утверждают, что обычный вычислитель справится с этой задачей в худшем случае за 2,5 дня, и при этом полученный ответ будет точнее, чем у квантового компьютера. Такой вывод был сделан по итогам проведенного теоретического анализа нескольких способов оптимизации.

Ну и, конечно, Scott Aaronson в своем блоге не смог обойти своим вниманием это заявление. Его анализ вместе со всеми ссылками и Scott’s Supreme Quantum Supremacy FAQ! как обычно стоят того, чтобы потратить на них свое время. На хабре есть перевод этого FAQ, и обязательно почитайте комментарии, там есть ссылки на предварительные документы, утекшие в Сеть до официального объявления.

Что же в реальности сделал Google? Для детального понимания почитайте Ааронсона, а кратко вот:

Я могу, конечно, вам сказать, но чувствую себя при этом глуповато. Вычисление такое: экспериментатор генерирует случайную квантовую схему С (т.е. Случайную последовательность 1-кубитных и 2-кубитных — между ближайшими соседями — вентилей, с глубиной к примеру в 20, действующую на 2D сеть n=50-60 кубитов). После этого экспериментатор посылает С на квантовый компьютер, и просит его применить С к начальному состоянию из 0, измерить результат в базисе {0,1}, послать обратно n-битную наблюдаемую последовательность (строку) и повторить несколько тысяч или миллионов раз. Наконец, используя свое знание о С, экспериментатор проводит статистическую проверку на соответствие результата с ожидаемым выходом от квантового компьютера.

Совсем коротко:

• Создается случайная схема длиной 20 из 53 кубитов используя вентили
• Схема запускается с начальным состоянием [0…0] на выполнение
• Выход схемы представляет собой случайную битовую строку (семпл)
• Распределение результата не является случайным (интерференция)
• Распределение полученных семплов сравнивается с ожидаемым
• Делается вывод о квантовом превосходстве

То есть Google реализовал синтетическую задачу на 53-х кубитном процессоре, и свое заявление о достижении квантового превосходства основывает на факте невозможности эмуляции такого процессора на стандартных системах за разумное время.

Для понимания — в этом разделе нисколько не умаляется достижение Google, инженеры действительно молодцы, а вопрос о том можно считать это реальным квантовым превосходством или нет, как уже говорилось ранее, скорее философский, чем инженерный. Но надо понимать, что достигнув такого вычислительного превосходства мы ни на шаг не продвинулись к возможности запускать алгоритм Шора на 2048-и битных числах.

Резюме

(к оглавлению)

Квантовые компьютеры и квантовые вычисления — очень многообещающая, очень молодая и пока малоприменимая в промышленном плане область информационных технологий.

Развитие квантовых вычислений позволит (когда-нибудь) решать задачи:

• Моделирования сложных физических систем на квантовом уровне
• Нерешаемые на обычном компьютере из-за вычислительной сложности

Основные проблемы при создании и эксплуатации квантовых компьютеров:

• Декогеренция
• Ошибки (декогеренции и вентильные)
• Архитектура процессоров (полносвязные схемы кубитов)

Состояние дел на текущий момент:

• По факту — самое начальное R&D.
• РЕАЛЬНОЙ коммерческой эксплуатации еще нет (и непонятно, когда будет)

Что может помочь:

• Какое-то физическое открытие, снижающее затраты на обвязку и эксплуатацию процессоров
• Открытие чего-то, что на порядок увеличит время декогеренции и/или снизит число ошибок

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

Ну а пока — нарабатываем опыт в квантовом программировании, собираем и создаем квантовые алгоритмы, тестируем идеи и прочее и прочее. Ждем прорыва.

Заключение

(к оглавлению)

В этой статье мы с вами прошлись по основным вехам развития квантовых вычислений и квантовых компьютеров, разобрали принцип их работы, рассмотрели основные проблемы, стоящие перед инженерами при разработке и эксплуатации квантовых процессоров, а также посмотрели что на самом деле представляют из себя многокубитные компьютеры D-Wave и недавнее заявление Google о достижении квантового превосходства.

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

Спасибо за внимание, надеюсь эта статья будет кому-нибудь полезной.

(С) Kruegger

Благодарности

(к оглавлению)

@Oxoron за вычитку и замечания по исходному тексту, а также за статью “Характеристики квантовых компьютеров”

@a5b за информационно-насыщенные комментарии к “Характеристики квантовых компьютеров”, да и не только к ней, которые во многом помогли мне разобраться с этим пазлом.

Всем авторам статей и публикаций, материалы которых были использованы при написании этой статьи.

Список ресурсов

(к оглавлению)

Если операционная система поддерживает многопоточность, она может распределять процессорное время либо между процессами, либо между потоками. В операционной системе Windows процессор предоставляется потокам, иначе говоря, осуществляется планирование на уровне потоков.

Таким образом, если один процесс имеет пять потоков, а второй – десять, то первый процесс будет занимать процессор в два раза больше времени, чем второй (при условии, конечно, что все потоки имеют равный приоритет и выполняют примерно одинаковую работу).

Алгоритмы планирования

Существуют разные алгоритмы планирования. Рассмотрим основные виды.

1. Вытесняющие/невытесняющие алгоритмы.

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

2. Алгоритмы с квантованием.

Каждому потоку предоставляется квант времени, в течение которого поток может выполняться на процессоре. По истечении кванта операционная система переключает процессор на следующий поток в очереди. Квант обычно равен целому числу интервалов системного таймера^{1Системный таймер – электронное устройство на материнской плате или в процессоре, которое вырабатывает сигнал прерывания через строго определенные промежутки времени (интервал системного таймера).}.

3. Алгоритмы с приоритетами.

Каждому потоку назначается приоритет (priority) – целое число, обозначающее степень привилегированности потока. Операционная система при наличии нескольких готовых к выполнению потоков выбирает из них поток с наибольшим приоритетом.

В Windows реализован смешанный алгоритм планирования – вытесняющий, на основе квантования и приоритетов.

Состояния потоков

За время своего существования поток может находиться в нескольких состояниях. Перечислим основные состояния:

1. Готовность (Ready) – поток готов к выполнению и ждет своей очереди занять процессор.
2. Выполнение (Running) – поток выполняется на процессоре.
3. Ожидание (Waiting) – поток не может выполняться, поскольку ждет наступление некоторого события (например, завершения операции ввода-вывода или сообщения от другого потока)

Кроме основных существует ещё несколько состояний – Инициализация (Init), Завершение (Terminate), Состояние простоя (Standby), Переходное состояние (Transition), Состояние отложенной готовности (Deferred ready). Подробнее о них можно узнать в [5; 2].

На рис.9.1 показаны основные состояния потока, возможные переходы между состояниями и условия переходов.

Кванты

В Windows имеется два базовых размера кванта – 2 интервала системного таймера и 12 интервалов. Если квант времени короткий, то потоки будут переключаться быстрее и «отзывчивость» (responsiveness) системы улучшится – это важное свойство для пользователя, поэтому в клиентских системах Windows по умолчанию используются короткие кванты. При этом производительность системы в целом снижается, поскольку потоки не будут успевать выполнять свои задачи в течение выделенного кванта, а частые переключения создадут высокие накладные расходы (служебные операции системы при смене потоков). Вследствие этого в серверных версиях Windows по умолчанию применяются длинные кванты.

Длительность интервала системного таймера (в сотнях наносекунд) хранится в переменной KeMaximumIncrement (для x86 – файл basentosexi386splocks.asm, строка 140; для x64 – файл basentosexamd64hifreqlk.asm, строка 147) и устанавливается функцией KeSetTimeIncrement (файл basentoskemiscc.c, строка 711 на основе значения, предоставляемого HAL.

Каждый процесс хранит величину кванта в поле QuantumReset структуры KPROCESS (файл basentosincke.h, строка 1029). Значение в этом поле равно количеству интервалов таймера, умноженному на 3. Например, для длинных квантов (12 интервалов) значение QuantumReset будет равно 36. Таким образом, при каждом срабатывании таймера (возникает прерывание) система уменьшает квант выполняющегося потока на 3 единицы.

Умножение на три введено для того чтобы можно было в разной степени уменьшать квант в двух различных ситуациях – срабатывании таймера (квант уменьшается на 3 единицы) и выходе из состояния ожидания (квант уменьшается на единицу). Уменьшение кванта при выходе потока из состояния ожидания применяется чтобы избежать ситуации бесконечно выполняющегося потока: если при каждом срабатывании таймера поток находится в состоянии ожидания, а при выходе из ожидания значение кванта не изменяется, то теоретически поток может выполняться бесконечно. Поэтому при выходе из состояния ожидания текущее значение его кванта уменьшается на единицу.

Значение кванта может быть изменено пользователем. Например, на Windows 7 нужно проделать следующее: Компьютер – Свойства – Дополнительные параметры системы – вкладка «Дополнительно» – раздел «Быстродействие» – Параметры – вкладка «Дополнительно» – раздел «Распределение времени процессора». Можно выбрать короткие кванты («Оптимизировать работу программ») или длинные («Оптимизировать работу служб, работающих в фоновом режиме») (рис.9.2).

За изменение величины кванта отвечает функция KeSetQuantumProcess (файл basentoskeprocobj.c, строка 1393).

Кроме длинных и коротких квантов в Windows реализовано динамическое увеличение размера кванта для потоков активного процесса (т.е. того процесса, окно которого в настоящий момент активно). За повышение кванта (и приоритета) отвечает функция PspComputeQuantumAndPriority (файл basentospspsquery.c, строка 4415). Более подробную информацию о динамическом увеличении кванта см. [5, стр. 361].

Приоритеты

В операционной системе Windows имеется 32 уровня приоритета – от 0 до 31 (рис.9.3).

Приоритеты назначаются процессам и потокам. У процесса имеется единственный приоритет, который называется базовым. Значение этого приоритета хранится в поле BasePriority структуры KPROCESS (файл basentosincke.h, строка 1028). В WinAPI для работы с базовым приоритетом процесса используются классы приоритета (например, REALTIME, NORMAL и т. д.); соответствие классов приоритета числовым значениям показано на рис.9.3. Например, при создании процесса можно указать класс приоритета в качестве параметра WinAPI-функции CreateProcess, иначе будет установлен приоритет по умолчанию (см. лекцию 6 «Процессы и потоки», раздел «Создание процесса»). В дальнейшем класс приоритета процесса можно изменить при помощи WinAPI-функции SetPriorityClass.

В WRK структура PROCESS_PRIORITY_CLASS и значения соответствующих констант (заметьте, что эти значения не совпадают с числовыми значениями приоритетов) определены в файле publicsdkincntpsapi.h (строка 399). Класс приоритета процесса хранится в поле PriorityClass структуры EPROCESS (см. лекцию 7 «Процессы и потоки», раздел «Структуры данных для процессов и потоков»). Таким образом, если, например, процессу назначен класс приоритета High, то в поле PriorityClass запишется число 3 (значение константы PROCESS_PRIORITY_CLASS_HIGH), в поле BasePriority – значение 13 (соответствующее числовое значение приоритета).

Поток имеет два значения приоритета – базовый и текущий. При создании потока базовый приоритет потока принимается равным базовому приоритету процесса-владельца. Можно изменить базовый приоритет потока при помощи WinAPI-функции SetThreadPriority. Параметрами этой функции являются дескриптор потока и относительный приоритет, который определяет смещение базового приоритета (таблица 7.1).

Пример. Имеется процесс с базовым приоритетом Below Normal (6). Поток, принадлежащий этому процессу, имеет такой же базовый приоритет. Вызов функции SetThreadPriority с параметром Highest сделает базовый приоритет потока равным 8, а с параметром Time Critical – равным 15.

Текущий приоритет потока при создании потока равен базовому, но в дальнейшем может динамически повышаться и понижаться операционной системой (эта процедура будет рассмотрена далее). Заметим, что для потоков с базовым приоритетом Real Time текущий приоритет не изменяется и всегда равен базовому.

Базовый приоритет потока хранится в поле BasePriority, а текущий – в поле Priority структуры KTHREAD (файл basentosincke.h, строки 1123 и 1237).

ВикиЧтение

Разработка ядра Linux
Лав Роберт