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

Введение

Это моя вторая статья на данном ресурсе на тему праздных рассуждений. Рассуждение в этой статье - по-прежнему офф-топ моей основной деятельности, но да-да "надо быть разносторонним". Тем не менее, физика для меня гораздо ближе экономики, политики и истории, так что должно получиться лучше.

Тема статьи была "сжата" намеренно: чтобы ограничить круг уместных размышлений. Большую часть статьи можно применить не только к трассировке и расстановке, но я хотел в конечном счёте ±раскрыть именно тот небольшой кусочек "квантовой темы", который закрепил в заголовке статьи, так как это было темой "сочинения на случайную тему".

Введение 2: что-то по теме

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

Главное отличие квантовых компьютеров от выполненных на основе транзисторов, которые сейчас используются всеми, состоит в том, как они выполняют работу с данными. Привычные всем устройства – от микрокомпьютеров и встроенных компьютеров до суперкомпьютеров представляют все свои данные в виде битов.

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

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

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

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

Квантовое превосходство

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

В последние несколько лет был достигнут заметный прогресс в развитии материалов для сверхпроводников. Можно сказать, что один из прорывов совершился в конце октября 2019 года, когда специалисты из корпорации Google заявили, что собрали прототип полноценного квантового компьютера – Google Sycamore: как утверждается, система примерно за двести секунд смогла решить задачу, которая заняла бы порядка 10 тысяч лет работы передового суперкомпьютера. Тогда Google и стали утверждать, что смогли достичь «квантового превосходства». Однако, тут важно сделать оговорку о том, что:

1. Алгоритм, выполнявшийся на квантовом компьютере Google, был изначально рассчитан на особенности квантового компьютера, а точнее – выполнение известной случайной последовательности команд, считывание финального состояния кубитов в виде строки и повторения этой операции миллионы раз. Затем статистику получившегося распределения ответов сравнивают с ожидаемой. Эта задача обладает весьма ограниченным потенциалом в плане практических приложений, но автор термина «квантовое превосходство» не делал различия между полезными в реальности и сугубо технически возможными вычислениями.

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

Как можно заметить, с частью «превосходства» всё оказалось не так однозначно.

Цифра и аналог

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

Имеет ли квантовый компьютер что-то общее с аналоговым компьютером?

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

Где же схожесть с аналоговым компьютером? Всё дело в том, что квантовые элементы выдают не точный, а вероятностный результат, что связано с принципами квантовой физики (а также с наличием шумов). Именно поэтому для получения правильного результата, вычисления на квантовом компьютере нужно повторить множество раз, – для получения статистического распределения. Распределение вероятностей везде является непрерывным, так что его можно назвать аналоговой величиной. Непрерывным является распределение вероятностей и в суперпозиции. Например, при разрушении суперпозиции, вероятность возникновения состояния «единица» может быть 75%, а «ноль» – 25%, а может быть 75,004% на 24,996% и др.

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

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

Размещение и трассировка

Здесь приведу цитату некоторой части некоторой книги: https://docplayer.com/37141267-5-proektirovanie-topologii-pechatnyh-plat-i-integralnyh-shem-5-1-vvedenie.html

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

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

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

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

Остальная часть этого раздела написана на основе сведений из ранее указанной части книги.

Алгоритмы размещения можно разделить на следующие основные группы:

1. алгоритмы, использующие силовые функции, в которых задача размещения сводится к задаче определения статического состояния модельной механической системы материальных точек – алгоритмы этой группы сложны для реализации на ЭВМ.;

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

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

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

Несколько конкретных примеров алгоритмов размещения:

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

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

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

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

Алгоритмы трассировки соединений:

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

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

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

Наконец, самый важный раздел.

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

Фактически, единственным способом найти гарантированно самый лучший вариант расположения элементов и дорожек остаётся полный перебор.

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

Тем не менее, до сих пор ещё не удалось применить квантовую систему для решения подобной задачи. Почему же? Основная проблема в том, что для решения комбинаторной задачи с N элементами, нужно N кубитов, а с увеличением числа кубитов, управлять системой (получать корректный результат) становится всё сложнее.

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

Даже с одной характеристикой, на момент написания статьи, максимум кубитов в одном процессоре ­– 127. Этого может хватить на площадь в 11 миллиметров квадратных при точности в 1 миллиметр, чего для современных схем явно недостаточно.

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

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

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

Выводы

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

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

P.S.

Буду рад конструктивной критике. Это довольно интересная тема, уточнения (поправки) по которой мне было бы интересно прочитать.