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

Татарин> Потрясающе! А зачем нужна обычная машина Тюринга?

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

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

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

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

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

Татарин> ...Но с КК-ускорением большинство алгоритмов точно так же можно исполнять быстрее...
Это утверждение ложно.
Я утверждаю, что большинство алгоритмов не могут быть выполнены на т.н. "квантовом компьютере" и пытаюсь объяснить тебе, почему.
Тащемта, т.н. ноучное сообщество со мной согласно, а не с тобой.

Татарин> Потрясающе! А зачем нужна обычная машина Тюринга?
Обычная машина Тьюринга обобщает понятие алгоритма. А т.н. "недетерминированная" просто является узким частным случаем нормальной машины Тьюринга.

Татарин>> Потрясающе! А зачем нужна обычная машина Тюринга?
П.З.> Обычная "сыграла роль" (историческую, в "становлении ключевых технологий"), ...

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

П.З.> а "недетерминированная" - чисто от безделья.

Её нет. Не согласен — приведи описание, что это такое, каким образом работает, и как построить.

П.З.> Надо же народу статьи писать и диссертации на чем-то защищать

Вот именно. См, почему в НИИЧАВО перестали принимать на рассмотрение диссертации о радиусе Колеса.

Татарин>> В теории алгоритмов она определена и используется, значит, существует.
pokos> То, что ты там читаешь, есть фиктивное определение частного случая нормальной машины.
Что такое "фиктивное определение"?
И нет, недетерменированная машина НЕ является частным случаем детерменированной ("нормальной").

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

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

Татарин>> ...Но с КК-ускорением большинство алгоритмов точно так же можно исполнять быстрее...
pokos> Это утверждение ложно.
В той же мере, в которой ложно утверждение "большинство алгоритмов выигрывают от наличия аппаратного умножения".
Строго, ессно, его доказать невозможно - ибо "большинство алгоритмов" понятие смутное.
По сути же оно очевидно. Ускорение любого поиска, перебора или получения обратного значения - это очень сильная вещь.

pokos> Я утверждаю, что большинство алгоритмов не могут быть выполнены на т.н. "квантовом компьютере" и пытаюсь объяснить тебе, почему.
Ты не понимаешь, как ты можешь объяснить?

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

pokos> Тащемта, т.н. ноучное сообщество со мной согласно, а не с тобой.
Приведи какие-то подтверждения от ноучного сообщества.
А то сейчас может выясниться выяснится, что это фрик Джон Сноу, знаменитый историк биологии, и его ты тоже понял неверно.

П.З.>> а "недетерминированная" - чисто от безделья.
Sandro> Её нет. Не согласен — приведи описание, что это такое, каким образом работает, и как построить.
Это теоретический конструкт для более удобного (в смысле доказательств) выделения NP-полных задач из множества NP.
В каком смысле ещё оно должно "работать"?

Татарин> Что такое "фиктивное определение"?
Это примерно то же, что дать отдельное определение полицейскому автомобилю, противопоставив его автомобилю вообще.

Татарин> И нет, недетерменированная машина НЕ является частным случаем детерменированной ("нормальной").
Она не просто является частным случаем, а даже в той же Википедии ДАН алгоритм ОБЫЧНОЙ машины Тьюринга, реализующей т.н. "недетерминированную".

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

Татарин> Строго, ессно, его доказать невозможно - ибо "большинство алгоритмов" понятие смутное.
Зато, легко применяемое к твоим "квантовым": "обычных" алгоритмов ныне можно придумать сколько угодно, а "квантовых" - по пальцам пересчитать.
Я тебе пытаюсь объяснить, почему и дальше так будет, но ты не воспринимаешь эти объяснения по простой причине: ты не знаешь базы как алгоритмов вообще, так и вычислений, в частности. Хотя бы, обычной (не школьной) алгебры, в которой и живут те самые линейные пространства, поля, кольца и всякие модули. Даже само понятие алгоритма у тебя смутное. Ты путаешь управляющую последовательность, данные и результат операций, что ярко продемонстрировал твой случай с "недетерминированной" машиной.

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

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

Татарин>> И нет, недетерменированная машина НЕ является частным случаем детерменированной ("нормальной").
pokos> Она не просто является частным случаем, а даже в той же Википедии ДАН алгоритм ОБЫЧНОЙ машины Тьюринга, реализующей т.н. "недетерминированную".
Ага. Википедия. Нет, ты не понял хода рассуждений.

pokos> Зато, легко применяемое к твоим "квантовым": "обычных" алгоритмов ныне можно придумать сколько угодно, а "квантовых" - по пальцам пересчитать.
Ну да, алгоритмов с квантовым превосходством меньше, чем алгоритмов вообще. Это вполне очевидно. Но из этого вообще никак не следует твой вывод, что КК - узкоспециализированная машина в общем.
Тут у тебя нетривиальный "логический" переход, на котором ты и сбоишь.
Ну вот сложение - очень частный случай логических операций: на МТ доказано, что сложение не нужно для выполнения любого алгоритма. На практике наличие сложения даёт огромные выгоды почти везде (давай сложение, оно ещё нагляднее, чем умножение).
Точно так же с квантовым поиском или выборкой - это очень частный случай, да. Но это очень ЧАСТЫЙ частный случай.

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

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

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

Sandro> Ой. Машина Тьюринга нужна, как доказательство аппаратной вычислимости

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

П.З.>> а "недетерминированная" - чисто от безделья.
Sandro> Её нет. Не согласен — приведи описание

Она есть , описание - в википедии.
Но таких "самовоспроизводящихся автоматов" в эпоху "штурма и натиска" в день по сотне рожали.
А потом выкидывали как использованное одноразовое средство.

Sandro> См, почему в НИИЧАВО перестали принимать на рассмотрение диссертации о радиусе Колеса.

Вот именно.

Татарин> ...доказывал, что КК не может быть заменой классическому на том основании

Может оказаться версией на тему термоядерной энергетики или возвращения на Луну.
"Пришла пора тормозить процесс и ставить заглушку".
В АйТи "заглушки" "сетки" и КК

Татарин>> ...доказывал, что КК не может быть заменой классическому на том основании
П.З.> Может оказаться версией на тему термоядерной энергетики или возвращения на Луну.
Запросто. Но может и не оказаться.

Sandro>> Её нет. Не согласен — приведи описание
П.З.> Она есть , описание - в википедии.

А есть нормальное описание, а не от википедиков? Я что-то не наблюдаю.

А педивикия — это тот же забор, на котором пишут, что попало.

Есть нормальные источники?

Sandro> А педивикия — это тот же забор, на котором пишут, что попало.
Sandro> Есть нормальные источники?

Татарин> https://trpl7.ru/t-books/Martin/Martinenko_09_Ch-06_TM_1.pdf

Вертеть-колотить. "6.4.3. Недетерминированная машина Тьюринга есть устройство с конеч-
ным управлением и одной бесконечной в обе стороны лентой."

Вообще-то, это классическая машина Тьюринга. Что в ней недетерминированного?

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

АХ, да: "Теорема 6.3. Если язык L принимается недетерминированной машиной
Тьюринга T1, то он принимается некоторой детерминированной машиной Тью-
ринга T2"

Замечательно. Т.е. недетерминированная машина является домыслом, всё можно делать на детерминированной.

Ну и чисто вишенка на торте: "Теорема 6.5. Каждая машина Тьюринга может быть смоделирована ма-
шиной Тьюринга с входной лентой только для чтения и лентой памяти с двумя
символами (пробел и другой символ) при условии, что машина может печатать
пробелы.
Доказательство. Большая часть доказательства будет оставлена читателю."

Я в полном офигении от этого трактата.

Татарин> ...Но из этого вообще никак не следует твой вывод, что КК - узкоспециализированная машина в общем.
Именно это и следует.

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

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

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

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

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

П.З.>> Может оказаться версией
Татарин> Запросто. Но может и не оказаться.

Может и не оказаться, но не запросто

pokos> Ты не просто не можешь нарисовать тракт с переменной длиной данных,
С чего ты взял, что не могу?!
Я взял паузу потому, что я не уверен, что он мне вообще нужен (в контексте разговора о машине с переменной длиной данных).

pokos> ты даже не понимаешь, в чём разница между CNOT и CSWAP, да что там далеко ходить, ты даже не понимаешь, в чём принципиальная разница между "и-не" и "исключающее или"! Другими словами
...другими словами, ты несёшь какой-то бессвязный бред.
Где у нас вообще был хоть какой-то разговор о "разница между "и-не" и "исключающее или""?! что ты себе придумал?
Что ты несёшь?

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

Татарин> Ну очевидно, уравнение Шредингера она решает хорошо (за линейное время для любого размера системы).

Ну, не знаю даже...
На первый-то взгляд очевидно.
А чуть подумавши - уже не очень.

Ну вот моделирование какой-нибудь большой молекулы - это сотни и тысячи атомов, у каждого десятки орбиталей, суперпозиции десятков тысяч волновых функций.
А КК - это ну пусть сотни кубитов, где куда меньше "значимых" состояний.
Как "переформулировать" УШ для эффективного решения при помощи КК - я навскидку не вижу Может, и есть способы, но, видимо, сильно нетривиальные. Втупую едва ли сводится.

Fakir> Ну вот моделирование какой-нибудь большой молекулы - это сотни и тысячи атомов, у каждого десятки орбиталей, суперпозиции десятков тысяч волновых функций.
У Залки — Визнера число свобод моделируемой системы должно быть <= числу кубит. Увы.

Fakir> А КК - это ну пусть сотни кубитов, где куда меньше "значимых" состояний.
Ну да, поэтому для пруф-оф-концепт и получения финансирования распиарили практически куда менее важного Шора. Причина того, что об алгоритме Шора знают все, а о куда более важном и применимом Гровере - гм... не все, как раз в этом.
В том, что для практически примененимого Шора достаточно сотен-тысяч логических кубит работающих с частотами да хоть в миллигерцы, а для практического применения Гровера - нужны уже миллионы кубит, причём, квантовые операции должны проводиться со скоростью сравнимой с классикой.

Татарин> У Залки — Визнера число свобод моделируемой системы должно быть <= числу кубит. Увы.

...при этом время сохранения когерентности обратно пропорционально числу кубит.
Квантовая коррекция и всё такое - ну... как идея-то красиво.

Как-то всё это оптимизмом не сказать чтоб лучится.

Fakir> Квантовые компьютеры: можно ли их сделать «большими»?
Fakir> Квантовые компьютеры и квантовые вычисления

Выделил бы следующие ключевые моменты и выводы (всё ИМХО).

1. КК - цифровой вероятностный компьютер. Т.е. он выдаёт ответ, который правилен лишь с некоторой вероятностью, пусть стремящейся к единице, но никогда ей на равной.
2. КК - цифровой компьютер с аналоговым управлением.

Из п.1 следует, что КК годятся для задач таких классов, что подразумевают трудоёмкий поиска путём перебора большого числа вариантов ответа при сравнительно простой проверке каждого отдельного варианта. К таким относится разложение на простые множители или, скажем, решение диффура (про диффур - моё личное мнение, не знаю, годится ли тут КК).
Т.к. заведомого точного решения он в принципе не может выдать, нужна проверка более классическими средствами. Следовательно, НЯП, для любых задач, в которых проверка подстановкой трудоёмка - КК даже теоретически не могут дать значимого ускорения.
Вот по некотором размышлении - не очень уверен, что даже задачи по определению структур и свойств молекул к ним относятся. Фолдинг - пожалуй, да.

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

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

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

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

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