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

Татарин> Все квантовые вычисления - это про реализацию очень узкого класса квантовых алгоритмов.
Я бы сказал иначе: т.н. квантовые компьютеры способны работать в весьма ограниченном ЧИСЛЕ алгебр.

Татарин> Вне этого класса квантовый компутер сводится к классическому обратимому, и в чём тогда вообще смысл?

При капитализме бывает только один смысл - извлечение максимального навара.

Татарин>> Все квантовые вычисления - это про реализацию очень узкого класса квантовых алгоритмов.
pokos> Я бы сказал иначе: т.н. квантовые компьютеры способны работать в весьма ограниченном ЧИСЛЕ алгебр.
Ну да. Гиперсфера Блоха и вот это всё.

pokos> При капитализме бывает только один смысл - извлечение максимального навара.
И какой навар ты извлёк из написания этого поста при капитализме?

Татарин> И какой навар ты извлёк из написания этого поста при капитализме?
К сожалению, никакого. Выходит, что я тут написаю только для развлечения.

Татарин>> И какой навар ты извлёк из написания этого поста при капитализме?
pokos> К сожалению, никакого. Выходит, что я тут написаю только для развлечения.
Ну, не. Смысл при капитализме бывает только один. По pokos'y так.

Татарин> Ну, не. Смысл при капитализме бывает только один. По pokos'y так.
Именно так. Либо один единственный смысл, либо никакого смысла. Познай всю глубину Ничто.

Татарин>> Ну, не. Смысл при капитализме бывает только один. По pokos'y так.
pokos> Именно так. Либо один единственный смысл, либо никакого смысла. Познай всю глубину Ничто.
Только Ситхи так абсолютизируют вещи.

Бинарная дискретизация а-ля манихеи - суть Зло сама по себе.

Татарин> Бинарная дискретизация а-ля манихеи - суть Зло сама по себе.
Ловко ты заклеймил капитализм и отцов его, сам Маркс так не смог.

Татарин>> Бинарная дискретизация а-ля манихеи - суть Зло сама по себе.
pokos> Ловко ты заклеймил капитализм и отцов его, сам Маркс так не смог.
Тем более ловко, что никто кроме тебя, этого не понял, меня самого включая.
Умею, да.

Fakir> 1. (и это главный вопрос) Другие квантовые алгоритмы будет реализовать сложнее, чем Шора? Если да - то насколько? Действительно ли это порядки?
Наверное, да, Шор самый "простой" и "выгодный" в сравнении с классическими.

Остальные квантовые алгоритмы по цена/эффективность не так хороши.
Возьми алгоритм Гровера, например.
Это возможность выборки любого элемента из массива по любому заданному критерию (любой известной функции оракла) за корень из n шагов. Тут даже без всяких теорий алгоритма... представь себе миллион элементов, и тебе нужно выбрать из них нужный/подходящий, за сколько попыток ты в половине случаев найдёшь искомое? Например, из миллиона лиц выбрать нужное. В среднем за 500000, так?
А тут - за тысячу. Круто? Офигенно!
...а нюанс©анекдот в том, что этот миллион объектов нужно держать в квантовой памяти.

Fakir> 2. На собственно Шора мне, честно говоря, плевать. Ну, с широкой точки зрения. Вообще пофиг, насколько он там выигрышен. Потому что это по построению способ решения очень узкого класса задач.
Нет, ничуть. Потому что лежащее в основе квантовое Фурье, вообще говоря, куда более универсально и куда примененимее.

Но вот возьмём того же Гровера. В узком смысле - это поиск объекта в массиве по какому-то критерию. Но при творческом применении это поиск любого объекта по любому критерию. По факту, это "волшебная палочка" NP=P для почти всего подкласса NP задач, в которых исходно представим перечень вариантов. Это обобщённое решение почти любой обратной задачи, для которой ты имеешь формулировку и заполненное пространство возможных решений (кстати GSA имеет и непрерывную формулировку, идея усиления состояния - она универсальна).

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

GSA - это очень и очень сильная штука. Просто вот ну ОЧЕНЬ.

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

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

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

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

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

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

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

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

Системы уравнений в частных производных оно позволит лучше исследовать и решать?
Еще какие-то задачи матфизики - интегральные, интегродифференциальные уравнения, и т.д. и т.п.

Fakir> У меня ощущение, что ты говоришь о чём-то довольно в сущности узком и по большей части целочисленном.
Я не понимаю тогда вот этой "сущности".
В сущности, вся наша вычислительная техника решает предельно узкие задачи логического "И", логических "ИЛИ" и "НЕ" для одноразрядных двоичных чисел. Ну или вот посмотри на машину Тюринга, в сущности любой компутер - несколько улучшенный и разжиревший её вариант.
И ничего, нормально так мы с этим развернулись.

Если сложность o(sqrt(n)) для подбора значения из списка по любому критерию - это в "сущности узкое"?
Что же тогда вообще считать глобальным изменением?

Fakir> Системы уравнений в частных производных оно позволит лучше исследовать и решать?
Fakir> Еще какие-то задачи матфизики - интегральные, интегродифференциальные уравнения, и т.д. и т.п.
Блин, я говорю, что есть возможность свести целые классы NP-полных задач к полиномиальной сложности, а тебя волнуют такие частные мелочи.

Fakir> Так вопрос в том, что такое этот класс квантовых алгоритмов. Узкий он потому, что он в принципе узкий, или лишь потому, что мы пока только с краешку ковырнули.
Ты как-то очень узко смотришь на алгоритмы вообще, как-то... предельно пользовательски, знаешь, из серии "мне нужен принтер для распечатки годовых отчётов".

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

Татарин> ...включи воображение...
Ну, у меня воображение включается только вместе со статистическим модулем.
Поэтому, я сразу вспоминаю, что 99.999% существующих компьютеров используются для задач управления.
Так что, никакой т.н. революции в замене менее 0.001% компьютеров на квантовые моё воображение не видит.

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

А твоё сравнение с двоичной логикой абсолютно неуместно.
Двоичная логика тем и хороша, что позволяет построить ЛЮБОЙ алгоритм. Она УНИВЕРСАЛЬНА, потому что именно атомарна. А твои квантовые навороты так узки именно потому, что они неатомарны. Если ты на них сумеешь построить хоть какую-нибудь алгебру, тогда дело пойдёт. Но, насколько я знаком с этим делом и с алгебрами вообще, перспектив тут ну совсем не видно (пока).

Татарин>> ...включи воображение...
pokos> Ну, у меня воображение включается только вместе со статистическим модулем.
pokos> Поэтому, я сразу вспоминаю, что 99.999% существующих компьютеров используются для задач управления.
И именно там получается выигрыш фантастических масштабов.
Тот же алгоритм Гровера - абсолютный же выигрыш всего и везде.

pokos> Двоичная логика тем и хороша, что позволяет построить ЛЮБОЙ алгоритм. Она УНИВЕРСАЛЬНА, потому что именно атомарна.
Вообще говоря, замена {0, 1} на {0..1} никак универсальности не вредит.

pokos> А твои квантовые навороты так узки именно потому, что они неатомарны.
В каком-то смысле ты прав: главная разница квантового компа с обычным в том, что в квантовой операции система когерентных регистров участвует целиком, что даёт возможность проворачивать "квантовые операции" в один ход над регистром в целом без увеличения сложности железа. Причём элементарная квантовая операция гораздо "сильнее", чем любая из элементарных двоичных.

pokos> Если ты на них сумеешь построить хоть какую-нибудь алгебру, тогда дело пойдёт. Но, насколько я знаком с этим делом и с алгебрами вообще, перспектив тут ну совсем не видно (пока).
Не понимаю. Зачем строить то, что существует?
n-мерный вектор на гиперсфере - алгебра уже сама по себе. Очевидно же, что единичная операция над этим вектором много "сильнее", чем операции над единичными битами.
Чтобы объединить элементарные битовые операции во что-то более сложное (например, сложение регистров) требуется очень много железа, проводящего промежуточные операции над битами в регистре, а в КК тебе доступны (как элементарные, не требующие допжелеза) операции над регистром целиком. Любой поворот вектора, представляющего весь регистр - для КК элементарная операция, не требующая дополнительного железа синхронизации.
Соотвественно, вопрос лишь в том, как этим воспользоваться с максимальной пользой.

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

pokos> Двоичная логика тем и хороша, что позволяет построить ЛЮБОЙ алгоритм.

Аналоговым компьютерам стопицот тыщу лет назад исполнилось.
Наверное они и сейчас где-то там применяются?
И там где применяются, кроют цифровые "как бык овцу"?

П.З.> И там где применяются, кроют цифровые "как бык овцу"?

Ну, например, в нейровычислениях - "спайковые" нейрочипы или нейросхемы на мемристорах по сути аналоговые. Но есть нюанс.

Татарин> И именно там получается выигрыш фантастических масштабов.
Татарин> Тот же алгоритм Гровера - абсолютный же выигрыш всего и везде.

Прямо уж так и всего ...

Как считать на КК — относительно понятно. А вот как на нём делать, например, сортировку? Там случайно не получится количество кубитов, равное всем возможным перестановкам входного вектора?

Татарин> Потому что будущее вычислений и автоматизации - очевидно в нейросетях

Нет.
Скорее даже очевидно нет.
И потому "вызывает раздражение" ваша навязчивая реклама нейросетей.

Выглядит как диверсия.
Притом, что "ниша"-то у нейросетей есть и даже "еще какая".

Татарин>> Потому что будущее вычислений и автоматизации - очевидно в нейросетях
П.З.> Скорее даже очевидно нет.
Понимаешь, если б ты разбирался в теме лучше меня, я б принял, что неправ и начал бы искать, в чём.
Если б ты вообще как-то разбирался - я б поспорил.

А так...

Татарин>> И именно там получается выигрыш фантастических масштабов.
Татарин>> Тот же алгоритм Гровера - абсолютный же выигрыш всего и везде.
Sandro> Прямо уж так и всего ...
Sandro> Как считать на КК — относительно понятно. А вот как на нём делать, например, сортировку? Там случайно не получится количество кубитов, равное всем возможным перестановкам входного вектора?
Нет.
Находишь минимальный элемент (составляешь оракл так, чтобы переворачивать амплитуду минимального элемента, после этого амплификацией и переворотами находишь этот элемент за sqrt(n) шагов), добавляешь в сортированную (в смысле, будущую результирующую) последовательность, повторяешь с учётом того, что каждый следующий выбранный элемент больше или равен предыдущему выбранному.
То есть, если гровера запихать в самый примитивный алгоритм сортировки (ну или один из самых), он, внезапно, превращается в довольно эффективный с o(n^1.5) (если точнее, то чуть меньше, мне влом писать точно). При этом количество задействованной памяти ~n (+регистры).

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

...подумал, что сейчас ты возразишь в духе "есть же qsort!". Он есть, но он же и редко используется в реальной жизни из-за стоимости шага. Ну и опять же: гровером по тому же принципу можно найти среднее и медиану (только ораклы чуть меняются), то есть, идеальные опорные элементы для реальных применений того же qsort.

Татарин> Понимаешь, если б ты разбирался в теме лучше меня

Ты думаешь не о том.
"Ну вот просто вообще".

Татарин>> Понимаешь, если б ты разбирался в теме лучше меня
П.З.> Ты думаешь не о том.
Ну ОК.

Татарин> n-мерный вектор на гиперсфере - алгебра уже сама по себе.
В алгебре нужно кое-то ещё.

Татарин> Чтобы объединить элементарные битовые операции во что-то более сложное (например, сложение регистров) требуется очень много железа...
я помню прошлый разговор с тобой про "много железа"...

Татарин> У тебя изначально в железе гораздо более сильные примитивы.
В чём их сила, брат?