Comments 21
Можно было написать статью более кратко
Перспектив нет
Операции, которые может делать квантовый компьютер, ограничены и программирование специфическое
Я пытался понять, является ли квантовый компьютер Turing complete, но информация в сети противоречива
Квантовый компьютер это труба, которой на вход подают данные, а на выходе считывают данные. В трубе есть некоторая логика без регистров, переходов, без циклов. Пока все.
Причем, что важно, везде можно прочитать размышления о том, как кардинально сокращается количество операций при вычислениях на квантовом компьютере, но никто никогда не говорит о рабочей частоте этах процессов и никто не говорит о небходимости многократных повторных вычислений для получения достоверной статистики.
Может быть когда нибудь в будущем это и даст толчек, но пока еще нет.
Про "повторные вычисления" и так понятно, что о них говорить? Хотя таки временами говорят, когда нужно оценить их количество.
"Квантовый компьютер это труба, которой на вход подают данные, а на выходе считывают данные. В трубе есть некоторая логика без регистров, переходов, без циклов. "
Никто не запрещает делать измерения тех или иных кубитов по мере выполнения квантового алгоритма и модифицировать алгоритм в зависимости от того, что показали измерения. В частности, именно так работают коды коррекции ошибок. Или можно проверять неизменность какого-нибудь инварианта, если таковой есть в решаемой задаче, а если он изменился из-за ошибок гейтов, то прерывать алгоритм и начинать считать заново.
Тут не квантовый компьютер виноват, а сам способ натягивания совы на глобус. Качественных автоматов нет даже у дорогих продуктов (из тех что можно купить). Везде предлагается ручная разводка, с разной степенью крутости. Ну это как молоток за 100р и за 50к - разницы не ощущается. Потому как этими молотками забиваются и гвозди и шурупы, и даже болты с левой резьбой. Буквально всё руками.
Качественный способ работает иначе - описание свойств для каждой электрической цепи, для каждого контакта, для комнат, для зон, + схема замещения для каждого компонента на плате.
Очень много рутинной работы, которая к счастью выполняется всего один раз при создании компонента. И немного креатива при создании схемы, с последующей прогонкой в симуляторах и тестах.
Вот когда обьёма дополнительной информации достаточно - уже может работать автоматическая разводка. При этом ей не нужны блоки ИИ, обучение и прочая хрень. У неё чёткий алгоритм - найти кротчайший путь по условиям. Такая программа уже может осмысленно двигать компоненты, потому как их положение уже описано в условии задачи. И это не чёткая позиция на ПП - а положение относительно других компонентов.
Качественный способ работает иначе - описание свойств для каждой электрической цепи, для каждого контакта, для комнат, для зон, + схема замещения для каждого компонента на плате.
Вот именно на это я намекал в статье. Выполнить идеальную разводку с учётом всех требований современному компьютеру не под силу. Он может выполнить просто неплохую разводку, но не идеальную.
Помимо этого, большинство САПР делают только разводку, а размещение компонентов "не совсем их дело". Если бы САПР мог гарантировать идеальное размещение и разводку, возможно, за получилось бы ещё уменьшить схему и добиться лучших характеристик.
У неё чёткий алгоритм - найти кротчайший путь по условиям.
Но выполнить все эти условия может оказаться так сложно, что условия упростят, принебрегая каким-нибудь радиоизлучением (антенным эффектом) с дорожек и т.п.
Сейчас САПР может либо хорошо выполнить разводку с небольшим количеством условий, либо просто выполнить разводку как-то, если условий много (речь про схемы вроде материнской платы).
И это не чёткая позиция на ПП - а положение относительно других компонентов.
В идеале САПР сам должен расставлять компоненты так, как будет лучше для схемы.
Но выполнить все эти условия может оказаться так сложно, что условия упростят, принебрегая каким-нибудь радиоизлучением (антенным эффектом) с дорожек и т.п.
Звучит как либо да, либо нет. Спектра умела находить решения по сложным условиям, использовала минимум памяти и очень простые алгоритмы. Самостоятельно осмыслено двигала компоненты, и даже могла перекидывать на обратную сторону. Но для того чтобы магия работала, нужно было написать страницы смецификаций. Не одну строчку, не поле, а десятки страниц в ручном режиме. Это был очень гибкий инструмент написания заданий, который допускал максимальное упрощение до базового уровня. Вот с этим базовым уровнем почти все и работали, и плевались от результатов.
Я считаю ошибкой стратегии развития спектры, которые полностью игнорировали пользовательский интерфейс, так-же как и наследия с генератора схемы. Типа у нас всё работает, а вы там сами разбирайтесь. Не разобрались и просто забили.
В результате уникальный продукт, который на голову превосходит по возможностям всё существующее на данный момент пакеты - стал не актуальным с переходом на новые версии виндовс.
В система с жосткими правилами - ИИ избыточен. Это больше похоже на ленивого программиста, которому лень самостоятельно писать алгоритм, и он перекладывает всю ответсвенность на машинное обучение. Получается крайне медленно, и не всегда то что задумывалось.
Кажется многие, кто не особо знаком с трассировкой соверенной электроники(речь только об печатных платах далее если что, не о внутренностях микросхем), или кто хоббийно занималься ею и в основном игрался с транзисторами, логическими микросхемами (а не МК и тем более CPU) представляют себе автоматический трассировщик плат примерно вот так:
Полностью автоматическая трассировка для печатных плат (с расстановкой компонентов видимо) неактуальна уже много лет:
1 в силу очень высокой интеграции микросхем, посольку сейчас на платах отсилу пара крупных ИС , ну стоят они гдето посередине платы, к ним подводятся шины, расположение всех выводов разьемов и прочего уже известно и особо ничего тут не поменяешь.
Тут особо кратчайший путь искать и не надо(кроме спец требований для высокоскоростных сигналов, но и тут речь не о автоматической трассировки, а просто по удовлетворению некоторых требований кторые и вручную с наличием нужных проверок спокойно реализуются), просто оптимизировать рутину. А если FPGA то там вообще FPGA planner используется, который оптимизирует распиновку в чипе, чтобы удобнее всего подвести сигналы которые уже как то расположены на плате.
2 относительно дешевая возможность делать много слоев и тем самым упрощать ручную трассировку (и не только)
3 опять же в сложных цифровых системах кроме больших ИС на плате остались только цепи питания, в которых компоненты должны быть например максимально близко друг другу (минимизация импеданса проводников питания к примеру), после расстановки компонентов по гайдам и на основе опыта разработчика идет симуляция , которая как по цене лицензий так по времени стоит ой как недешего, и некий автоматический алгоритм:
1 расстановка компонентов как то рандомом
2 проверка оптимальности расстановки при помощи симуляции, если ок то выходим, если нет то п1
будет безумно дорогим и долгим занятием.
Ну и да, как сказано выше, это актуально для очень специфичных проектов и все долго и нудно описывается правилами, без которых даже квантовый блокчейн ну никак не поможет.
1 в силу очень высокой интеграции микросхем
Да, микросхемы упрощают дело, но от этого не становится меньше условий. Например, пусть микросхемы 3, но у каждой по 50 ножек с частотами порядка нескольких гигагерц. Такие дорожки достаточно сложно вести, если пытаться минимизироваь нежелательные последствия (рассинхронизацию, антенный эффект на приём шума и на создание шума другим элементам, отражения и др.).
А если FPGA то там вообще FPGA planner используется
Да, но проблема трассировки всё равно не решена как минимум по 2 причинам:
FPGA - тоже микросхема, которую сначала надо сделать перед тем, как использовать;
внутри имплементаторов языков программирования аппаратуры задача трассировки сигналов между LUT и др. всё равно остаётся. Если "аппаратная программа" сложная, то и задача трассировки не из простых и может занять приличное время.
2 относительно дешевая возможность делать много слоев и тем самым упрощать ручную трассировку (и не только)
Да, но шумы, наводки и т.д.
Конечно, там, насколько мне известно, часто чередуют слои: слой чистого минуса и слои сигналов, но это только для цифры подходит. Если же на такой схеме появляются аналоговые компоненты, всё сильно усложняется.
осле расстановки компонентов по гайдам и на основе опыта разработчика идет симуляция , которая как по цене лицензий так по времени стоит ой как недешего, и некий автоматический алгоритм: 1 расстановка компонентов как то рандомом 2 проверка оптимальности расстановки при помощи симуляции, если ок то выходим, если нет то п1 будет безумно дорогим и долгим занятием.
Вот как раз на количестве неободимых симуляций и времени подготовки (предварительной расстановки и трассировки) к ним в целом и можно сэкономить, используя квантовый компьютер.
А с помощью какого именно квантового алгоритма предлагается проводить оптимизацию? Это ведь только на словах квантовый компьютер способен очень хорошо решать задачи оптимизации. Дьявол в деталях.
Конкретного алгоритма пока нет, насколько мне известно.
Тем не менее, "ещё не вечер" - когда-нибудь придумают.
Квантовые алгоритмы оптимизации таки есть, но у них есть множество недостатков, так что полезность-бесполезность их далеко не очевидна. Например, это QAOA (quantum approximate optimization algorithm - квантовый алгоритм приблизительной оптимизации) и метод квантового отжига.
И утверждение "когда-нибудь придумают" абсолютно не убедительно, так как ниоткуда не следует.
Квантовые алгоритмы оптимизации таки есть, но у них есть множество недостатков, так что полезность-бесполезность их далеко не очевидна.
Необязательно говорить о существующих алгоритмах.
Тем не менее, если посмотреть на свойства квантового процессора, понятно, что они бы пригодились для решения комбинаторных задач. Задача расстановки и трассировки - комбинаторная.
И утверждение "когда-нибудь придумают" абсолютно не убедительно
Может, и не придумают. Однако, я считаю, что это слишком пессимистичный взгляд. Всё-таки учёные - люди не глупые.
Всё дело в сути преимущества, которое даёт квантовый компьютер, а именно
– параллельности. Квантовый компьютер способен одновременно обработать
исходы со всеми возможными состояниями кубитов, то есть одновременно
«проверить» соответствие всех возможных значений кубитов заданным
условиям.
Это не совсем верно. КК не обрабатывает все значения одновременно/параллельно. Он работает с интерференцией волновых функций, чтобы реализовать нужное распределение вероятностей исходов измерения.
Традиционно, разговор о том самом в виде комикса
Квантовые вычисления я понимаю так:
Вот у меня задача: вычислить 3+9.
Я беру восемь кубитов. В первую четвёрку «записываю» 0011, во вторую 1001. Затем начинаю «кастовать квантовую магию» (многократно) и я получаю что в третьей четвёрке (или в одной из исходных) с вероятностью 99% декогеренция даёт 1011, а другие распределение значений — встречается гораздо реже и решаю что именно таков ответ.
Очевидно, что для такой задачи все преимущества — у классических вычислений.
Если мы, например, так попытаемся найти делители 2048-битного числа — таким образом мы найдём их все. Но не одновременно. Чтобы набрать статистику на них на все — нам, очевидно, надо провести вычисление довольно много раз (чем больше делителей — тем больше раз, чтоб для каждого «вывести» вероятность ошибки в малое значение).
Т.е. в некотором смысле у нас идёт такой же перебор как и в классическом алгоритме. И «параллельность» — это следствие большого количества повторений (как и в классическом алгоритме). Не «съедается» ли здесь весь выигрыш? Не является ли квантовое преимущество аналогом «газодинамического преимущества» аэродинамических труб?
Чтобы набрать статистику на них на все — нам, очевидно, надо провести
вычисление довольно много раз (чем больше делителей — тем больше раз,
чтоб для каждого «вывести» вероятность ошибки в малое значение).
Все верно, так и есть. Просто в классическом случае рост сложности вычисления - экспоненециальный. А в квантовом - полиномиальный. Как раз за счет того, что это не просто параллельный перебор, а за счет сложного алгоритма, который основан на интерференции волновой функции. Собственно, суть в том, что квантовый аналог вероятности - амплитуда волновой функции - может быть отрицательной. То есть, в отличие от просто случайного перебора всех вариантов (пусть и параллельно), мы можем складывать амплитуды так, что амплитуда нужного ответа увеличивается, а остальных - уменьшается (за счет прибавления отрицательной амплитуды).
И «параллельность» — это следствие большого количества повторений (как и в классическом алгоритме).
Нет, это не так. Да, повторения нужны в любом случае, но их нужно гораздо меньше, чем в классическом алгоритме. Как раз за счет "усиления" правильного ответа через интерференцию.
Порекомендую статью Вастрика про квантовый компьютер, там все отлично объяснено. Если хочется больше: у издательства Питер есть целый цикл книг про квантовые вычисления, для всех уровней мастерства)
Это не совсем верно. КК не обрабатывает все значения одновременно/параллельно.
Да, КК не обрабатывает значения параллельно. Я в статье писал так:
Квантовый компьютер способен одновременно обработать исходы со всеми возможными состояниями кубитов, то есть одновременно «проверить» соответствие всех возможных значений кубитов заданным условиям.
Закладывался такой смысл, что квантовый компьютер может обработавть все возможные состояния кубит согласно условиям обработки. Я хотел дать наиболее близкое к реальности понятное объяснение без вплетания математики.
Он работает с интерференцией волновых функций
Ну вот что и требовалось доказать: интерференция - понятние физическое, а функция - математическое. Снова получаетсся замечательное смешение, которое способно запутать почти всех и вся, потому что не понятно, где кончается физическая "магия" (то есть то что есть на самом деле) и начинается математическая "магия" (то есть разные математические фокусы вроде применения квантовых операций в виде умножения на матрицу).
Традиционно, разговор о том самом в виде комикса
Вот как раз в этом самом комиксе и сглажен переход от физике к математике, что как раз и путает многих, чего я хотел избежать.
Очевидно, что комплексная сфера, которой в комиксе объясняется работа квантовых эффектов и функции плотности вероятности - чисто математические абстракции, которые могут описывать реальность, но не являются ею. Это крайне удобные абстракции, но важно понимать, что эти абстракции сами по себе не являются объяснением.
Подход к объяснению квантовых эффектов "shut up and calc" я не разделяю...
то есть одновременно «проверить» соответствие всех возможных значений кубитов заданным условиям.
Ну вот этот момент как раз не совсем точен.
Ну вот что и требовалось доказать: интерференция - понятние физическое, а функция - математическое.
Это как посмотреть. Многомировая интерпретация (как и некоторые другие) утверждает, что волновая функция - это буквально реально физический объект. Я, как и Скотт Ааронсон, придерживаюсь этой интерпретации, как наиболее полно описывающей наблюдаемую физику.
Я понимаю желание сгладить некоторые моменты, и мой комментарий - не критика, а дополнение. Для желающих покопаться глубже.
Многомировая интерпретация (как и некоторые другие) утверждает, что волновая функция - это буквально реально физический объект.
Да, нужно отметить иногда очень сложно найти переход между физикой и математикой. При том, эта граница, если приблизить, всегда размыта, и очертить её можно только начиная с определённого масштаба.
Волновая функция очень хорошо описывает реальность, но если вспомнить, математика для того и была придумана, чтобы хорошо описывать реальность.
В реальности много всего, что обладает свойствами, описываемыми волновой функцией. Объяснения почему, насколько мне известно, нет - есть только формулы и коэффициенты... Здесь вообще сложно говорить о том, что на самом деле есть в реальности.
Не то что бы многомировая интерпретация означала, что волновая функция реальна... Это скорее означает, что некоторые свойства могут быть описаны такой функцией, значит, свойства функции соответствуют свойствам физического объекта (собственно, математическая модель для того и нужна). Многомировая интерпретация интерпретирует не просто свойства математической абстракции, она интерпретирует поведение физических свойств, описываемых волновой функцией.
Граница физики и математики тут уже довольно размыта, поэтому дальше уже только философия "истинности бытия"...
Не то что бы многомировая интерпретация означала, что волновая функция реальна...
Это именно то, что ММИ говорит. Более того, реальна только волновая функция.
Это скорее означает, что некоторые свойства могут быть описаны такой функцией
Нет, весь мир целиком является волновой функцией. Не нравится слово функция? Это просто дань традиции. Замените на квантовое поле в определенном состоянии.
Перспективы использования квантовых компьютеров для расстановки элементов схем и трассировки соединений