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

Татарин> Есть ещё один момент: нейросети и БОЛЬШИЕ нейросети.
С этим я соглашусь полностью. Осталось решить вопрос с когерентностью, хотя бы, миллиарда кубитов. Дело плёвое.

П.З.> Наверное они и сейчас где-то там применяются?
Ты сам-то когда-нибудь щупал хоть один аналоговый "компьютер"?

Татарин>> Есть ещё один момент: нейросети и БОЛЬШИЕ нейросети.
pokos> С этим я соглашусь полностью. Осталось решить вопрос с когерентностью, хотя бы, миллиарда кубитов. Дело плёвое.
Тебе не нужно запихивать в КК нейросеть целиком. Достаточно быстро относительно небольшой кусок, но как можно быстрее. Ты можешь "сводить" нейросеть кусками, просто это гораздо дороже. В конце-то концов, сейчас вообще каждый вес считается отдельно.
Тысячи-десятки тысяч логических кубитов - будет уже достаточно хорошо для обучения НС.

...
Тут есть ещё какой нюанс: КК, в принципе, термодинамически предельный компьютер. То есть, термодинамическая стоимость его вычислений - теоретический предел с точки зрения Второго Начала. Ну да, есть огромные траты на обслуживание вычислений (охлаждение, ввод-вывод, коррекция ошибок и т.п.), но сами вычисления не то чтоб просто очень энергоэффективны, но энергоэффективны предельно.
При больших объёмах вычислений (на сходимость, в частности) это важно. Мы уже сейчас уткнулись в то, что стоимость вычислений измеряется в кВт*ч, но пока это ещё скрыто быстрым прогрессом в энергоэффективности классических энтропийных вычислений.
Замедление роста энергоэффективности есть уже сейчас, на среднесроке мы вполне можем подойти к пределу. Спинтроника и всё такое, но kT есть kT.

И вот тут либо КК, либо полумеры с классическими обратимыми компами (что не сильно-то проще; ибо единственная известная практическая реализация обратимой логики основана квантах магнитного потока в сверхпроводниках), либо остановка прогресса.

П.З.>> Наверное они и сейчас где-то там применяются?
pokos> Ты сам-то когда-нибудь щупал хоть один аналоговый "компьютер"?

Бог миловал, только на картинках. В книжках.

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

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

Татарин>> У тебя изначально в железе гораздо более сильные примитивы.
pokos> В чём их сила, брат?
Например, в возможности условно-бесплатно по "железу" и с бесконечной скоростью (точнее, вне времени), просто за счёт свойств вселенной, согласовывать информацию внутри сложной структуры данных.
Например, в возможности оперировать матрицей плотностей, которая гораздо сложнее, чем квантовый регистр.

Татарин> Чего именно не хватает в алгебре векторов?
Во-первых, это не алгебра. Во вторых, это основано не на алгебре векторов, а на алгебре спиноров.

Татарин> Например, в возможности условно-бесплатно по "железу" и с бесконечной скоростью ..
Сложная структура данных слаба. А скорость, и вовсе не входит в состав силы примитива.

Татарин> Например, в возможности оперировать матрицей плотностей, которая гораздо сложнее, чем квантовый регистр.
Так, как раз, это и есть очень плохо для алгоритмизации.

Татарин>> Чего именно не хватает в алгебре векторов?
pokos> Во-первых, это не алгебра. Во вторых, это основано не на алгебре векторов, а на алгебре спиноров.
Алгебре конкретных векторов с окончанием на (гипер-)сфере.
Почему это не алгебра? Чего по-твоему не хватает?

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

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

Татарин> Почему это не алгебра? Чего по-твоему не хватает?
Не хватает универсальных операций над объектами.

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

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

Татарин>> Почему это не алгебра? Чего по-твоему не хватает?
pokos> Не хватает универсальных операций над объектами.
Не понял. Разверни.
Если в чисто математическом смысле, то вращение единичного вектора (его легче представлять, чем манипуляции над спинором) - суть универсальная операция переводящая объект множества в объект множества, пустая операция определена, единичный элемент есть... чего тебе не хватает?
Если в "бытовом-электронном", то есть CNOT, универсальнее операции сложно придумать - он и "И", и "ИЛИ" и "НЕ" в одном флаконе.

Татарин>> А во-вторых, показано, что эти сложные объекты могут выполнять (при желании) логику имеющуюся простых. Алгоритмизация ничего не теряет.
pokos> Остаётся только удивляться, почему этих волшебных т.н. "квантовых алгоритмов" до сих пор придумали только несколько штук.
Эээ... с чего ты взял?
Алгоритмов тысячи-миллионы, просто значимы лишь несколько из них. Мы ведь называем "квантовым алгоритмом" не любой алгоритм, исполняемый на квантовом компутере, а только такой, который даёт существенное преимущество над классикой.
А сейчас все носятся с тем базовым десятком ещё и потому, что железо КК сейчас маленькое и плохое, и нужен какой-то чудовищный алгоритмический выигрыш, да ещё и с готовым применением на практике, чтобы оправдать использование КК.
Почему все и бегают вокруг Шора - кубит нужно мало, и есть прям практическое, понятное воякам и государству применение уже сейчас. Так-то сам по себе он частный узкий случай.

Если б КК спокойно оперировали миллионами кубит на гигагерцах (как нынешняя классика), у нас всё давно было бы квантовое.
Но вот какой смысл кому сейчас разбирать детально, например, квантовый qsort, который приближает практический o(n) к предельному o(nlog(n))? Да, как бы если б так можно было сделать с базовым qsort, это было бы офигенно во всех местах, где применяется сортировка, но как замануха для реализации КК такой выигрыш явно не смотрится.

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

Татарин> Эээ... с чего ты взял?
А кто не пьёт? Назови!

Татарин> Алгоритмов тысячи-миллионы...
Не верю.

Татарин> Если б КК спокойно оперировали миллионами кубит на гигагерцах (как нынешняя классика), у нас всё давно было бы квантовое.
Проходили уже.
„В фантастических романах главное это было радио. При нем ожидалось счастье человечества. Вот радио есть, а счастья нет.“

Татарин> Но вот какой смысл кому сейчас разбирать детально...
Разбери детально, какой алгоритм общего вида ты сможешь построить на базе твоего волшебного qsort.

Татарин>> Не понял. Разверни.
pokos> Алгебра - это манипулирование конечным числом символов.
? С хрена ли?
Алгебра - это множество элементов с определённым набором операций, переводящих элемент множества в другой элемент множества. Мощность множества может быть любой. Например, если над вещественными числами определить операцию сложения, это будет алгебра, конкретно группоид, и более того - даже абелева группа. (Да и если не определить ничего - тоже будет алгебра (универсальная) . Но это так, чисто ради точности.)
Множество определено, операция над ним есть - до хоть CNOT.

pokos> Для этого требуется универсальная операция, которая работает со всеми символами алгебры.
pokos> В твоих квантовых т.н. "алгоритмах" не существует никакой универсальной операции, кроме операции декогерентности, которая может быть применена к любой паре символов. Так понятно?
Нет, вообще не понял. Почему, допустим, CNOT не может быть применён к любой паре кубит?

Татарин>> Алгоритмов тысячи-миллионы...
pokos> Не верю.
ОК.

Татарин>> Если б КК спокойно оперировали миллионами кубит на гигагерцах (как нынешняя классика), у нас всё давно было бы квантовое.
pokos> Проходили уже.
pokos> „В фантастических романах главное это было радио. При нем ожидалось счастье человечества. Вот радио есть, а счастья нет.“
Тем не менее, радио везде есть. А мы как раз о наличии радио и его преимуществах над телеграфом.

Татарин>> Но вот какой смысл кому сейчас разбирать детально...
pokos> Разбери детально, какой алгоритм общего вида ты сможешь построить на базе твоего волшебного qsort.
Не понял про "общий вид". Что такое "алгоритм общего вида"? почему сам qsort - "не общего вида"?

Татарин> ? С хрена ли?
C Википедии.

Татарин> Алгебра - это множество элементов с определённым набором операций
А я что сказал?

Татарин> Множество определено, операция над ним есть - до хоть CNOT.
Определи множество.
"Надежность работы элемента составила около 90 %" И это, всего лишь, 2х2. Далее - обратный факториал.

Татарин> Что такое "алгоритм общего вида"?

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

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

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

pokos> "Надежность работы элемента составила около 90 %" И это, всего лишь, 2х2. Далее - обратный факториал.
Бррр... это вообще о чём? зачем? откуда?
Какая разница, какая была у кого-то надёжность этого элемента? Ты же об алгебрах?
У кого-то - 90%, у кого-то сейчас (на ионах) - 99.9%, у кого-то (с коррекциями ошибок) - 6 девяток уже. Это подробности аппаратуры вообще, при чём тут алгебра?
Как будто от того, что ламповые компутеры часто ломались, их двоичная логика как-то отличалась от двоичной логики нынешних компов. Математика в основе алгоритмов - это одно, аппаратная реализация - другое.

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

Татарин> А ты сказал, что "манипулирование конечным числом символов". Так вот это вообще никак не связано, мощность множества может быть любой.
Да. Ты не можешь манипулировать бесконечным множеством. Просто пойми это.
Всё, что ты можешь - оперировать символом, обозначающим бесконечное множество или символом, обозначающим его элемент (при принятии аксиомы выбора).

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

Татарин> Бррр... это вообще о чём? зачем? откуда?
- Сеня, откуда это???
- ОТТУДА.
.
Татарин> Какая разница, какая была у кого-то надёжность этого элемента? Ты же об алгебрах?
Разница такая, что алгебра - это не казино. Результат операции в алгебре определён на 100% всегда.

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

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

Я даже дам тебе подсказку. Чтобы решать задачи реального мира, тебе достаточно ограничиться вентилем 2х2, и не CNOT, а CSWAP.

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

pokos> Алгебра - это манипулирование конечным числом символов.

Терминология:
я бы назвал это "исчислением", а не алгеброй.
В формальном смысле алгебра может и как правила является бесконечной. Чисто "по определению".

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

 

В остальном все правильно.
Все алгоритмы и вычислительные процессы относятся к конечным исчислениям
И это их принципиальное свойство.

Татарин> В сущности, вся наша вычислительная техника решает предельно узкие задачи логического "И", логических "ИЛИ" и "НЕ" для одноразрядных двоичных чисел.
Татарин> И ничего, нормально так мы с этим развернулись.

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


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

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

А вот из сведения NP-полных к полиномиальным - не представляю даже близко.

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

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

П.З.> Бог миловал, только на картинках. В книжках.

Ну, а я щупал, и не один.
И расскажу тебе следующее.
В аналоговом компьютере нет никакого алгоритма. А есть начальные условия и зависимости.
Они определяют конфигурацию железа.
Далее, производится процедура решения, называемая в просторечьи "х**к!".
Результат выводится, обычно, в графическом виде.

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

П.З.> я бы назвал это "исчислением", а не алгеброй.
Я бы не стал. Исчисление - это процедура. А алгебра - это наиболее общие правила для этой процедуры.

Татарин>> А ты сказал, что "манипулирование конечным числом символов". Так вот это вообще никак не связано, мощность множества может быть любой.
pokos> Да. Ты не можешь манипулировать бесконечным множеством. Просто пойми это.
pokos> Всё, что ты можешь - оперировать символом, обозначающим бесконечное множество или символом, обозначающим его элемент (при принятии аксиомы выбора).
Я могу оперировать элементом из бесконечного множества. Собссно, КК так и делают - кубит в суперпозиции это вещественное значение без дискретизации. Число символов во множестве - бесконечно.

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

pokos> Я не прошу привести пример алгоритма, а прошу привести принцип его построения на основе CNOT. Понимаешь разницу?
ОК, разницу я понял, но не понял, что ты имеешь в виду под принципом.
В общем случае я всегда могу свести схему к классической, изобразив классические булевые И, ИЛИ, НЕ из КНЕ.
НЕ - понятно как, просто подав вечный ноль на контроль, И и ИЛИ - из нескольких КНЕ, инвертировав входы.

pokos> Я даже дам тебе подсказку. Чтобы решать задачи реального мира, тебе достаточно ограничиться вентилем 2х2, и не CNOT, а CSWAP.
Мне и CNOT хватит, он тоже 2х2 и у него тоже вполне универсальная матрица преобразований. Почему именно CSWAP?

pokos> Кстати, в реальной жизни часто требуется умножение чисел с десятичной разрядностью эдак 6-7. Распиши, пожста, квантовый алгоритм для этого. Он не так сложен.
Алгоритм Карацубы? Или ты про что?

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

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

Fakir> А вот из сведения NP-полных к полиномиальным - не представляю даже близко.
По-настоящему вычислительно сложны именно NP-полные задачи (например, задачи с растущим деревом вариантов).
Во всех остальных случаях можно надеяться на прогресс в вычтехнике, для NP-полных - нельзя.

Татарин> Татарин>> ...Это подробности аппаратуры вообще, при чём тут алгебра.
А вот тут, как раз, и нет. Твои квантовые операции всегда имеют вероятность верного результата <1.
Собсно, переключение и обычного полевого транзистора тоже, потому что он ТОЖЕ квантовый. Однако, у него уровней не два и не 500, а примерно (10⁵)! у самых маленьких. Соответсвенно, в масштабах времени жизни планеты Земля вероятность его правильного переключения можно смело принять за единицу.

Татарин> Логический кубит не имеет ошибок...
Ошибку имеет его переход в другое состояние.

Татарин> ОК, разницу я понял, но не понял, что ты имеешь в виду под принципом.
Да, просто, словами опиши,ч то нужно делать.

Татарин> Мне и CNOT хватит...
Для всех булевых операций тебе CNOT не хватит.

Татарин> Почему именно CSWAP?
Внимательно почитай, чем они отличаются.

Татарин> Алгоритм Карацубы? Или ты про что?
Да хоть Чикатило, любой.

Татарин>> Татарин>> ...Это подробности аппаратуры вообще, при чём тут алгебра.
pokos> А вот тут, как раз, и нет. Твои квантовые операции всегда имеют вероятность верного результата <1.
Это зависит от аппаратуры. Аппаратура так и делается, чтобы вероятность верного результата была практически неотличима от 1.

pokos> Собсно, переключение и обычного полевого транзистора тоже, потому что он ТОЖЕ квантовый. Однако, у него уровней не два и не 500, а примерно (10⁵)! у самых маленьких. Соответсвенно, в масштабах времени жизни планеты Земля вероятность его правильного переключения можно смело принять за единицу.
Мне кажется, ты мешаешь холодное с синим. Переключение обычного полевого транзистора связано с множественными редукциями ВФ электронов (или коллективов) в чистое состояние.

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

Татарин>> Логический кубит не имеет ошибок...
pokos> Ошибку имеет его переход в другое состояние.
Нет.

pokos> Для всех булевых операций тебе CNOT не хватит.
Любая булева операция сводится к комбинации {И, ИЛИ, НЕ}, CNOT или CSWAP.

Татарин>> Почему именно CSWAP?
pokos> Внимательно почитай, чем они отличаются.
Я знаю, чем они отличаются. Отличия будут не в логике, а в обслуживании инфомусора.

Татарин>> Алгоритм Карацубы? Или ты про что?
pokos> Да хоть Чикатило, любой.
Ну, так он и описан. Зачем мне повторять?

pokos> Я бы не стал. Исчисление - это процедура. А алгебра - это наиболее общие правила для этой процедуры.

Алгебра - это векторное пространство с умножением.

pokos> И расскажу тебе следующее.
pokos> В аналоговом компьютере нет никакого алгоритма

Ну, я, как бэ, в курсе.

pokos> Да, аналоговый компьютер очень сильно напоминает квантовый

Что я, собственно, и хотел сказать.
Но, видимо, плохо сформулировал.