Alexey Rovdo wrote:
> C>Да и вообще, любой квантовый компьютер можно эмулировать на > классическом > C>компьютере с любой требуемой точностью. > И зачем тогда нужны квантовые компьютеры? В чем их преимущество перед > классическими?
Скорость. Многие задачи, требующие экспоненциального времени на
классическом компьютере, решаются за полиномиальное время на квантовом
компьютере. Полиномиальные алгоритмы тоже могут быть реализованы
быстрее: линейный поиск, например, реализуется за O(sqrt(n)) вместо O(n)
и т.п.
> Кстати, эмулируйте наконец задачу с бедной кошкой Шредингера и скажите > жива она или нет.
Берем датчик псевдослучайных целых чисел в диапазоне [a;b] и ждем пока
выпадет число x из этого диапазона.
Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>Alexey Rovdo,
AR>>И зачем тогда нужны квантовые компьютеры? В чем их преимущество перед классическими?
LCR>Кое-какие задачи можно решать существенно быстрее, только и всего.
Да, но быстрее за счет чего? Вы полагаете, что за счет банально большей скорости выполнения элементарных операций?
AndrewVK,
LCR>>Упс. А что за задача?
AVK>Это не задача, это эксперимент мысленный. Демонстрирует принцип неопределенности и необходимость в сворачивании волновой функции на коте.
Здравствуйте, Alexey Rovdo, Вы писали:
AR>Да, но быстрее за счет чего?
Любое вычисление происходит на основе того, что некие физические процессы реализуют некий набор операций, достаточных для выполнения универсальных операций. Такой набор называется базис. Разумеется базисов может быть сколько угодно. И в зависимости от базиса те или иные вычисления будут выполняться более или менее эффективно. Ряд вычислений намного лучше (десятки порядков) ложится на базис кубитов, нежели базис дискретной двоичной логики.
Здравствуйте, Cyberax, Вы писали:
C>Alexey Rovdo wrote:
C>Скорость. Многие задачи, требующие экспоненциального времени на C>классическом компьютере, решаются за полиномиальное время на квантовом C>компьютере. Полиномиальные алгоритмы тоже могут быть реализованы C>быстрее: линейный поиск, например, реализуется за O(sqrt(n)) вместо O(n) C>и т.п.
Опа. А что это за алгоритмы такие, которые можно реализовать на квантовом компьютере, но нельзя реализовать на классическом?
И корректно ли их вообще называть словом "алгоритм" (на самом деле уже прижился термин "квантовый алгоритм")?
Заметьте, здесь то вы и противоречите сами себе. Если бы работу квантового компьютера можно было целиком эмулировать, то и реализуемые им "квантовые алгоритмы" вычислений можно было бы реализовать на классическом компьютере. Но тогда и линейный поск можно было бы реализовать за O(sqrt(n)) именно на классическом компьютере (поскольку это характеристика именно алгоритма).
Поэтому не путайте две разных вещи: "эмуляцию работы квантового компьютера" и "моделирование квантового компьютера для конкретной задачи с точно определенными параметрами".
Alexey Rovdo wrote:
> C>Скорость. Многие задачи, требующие экспоненциального времени на > C>классическом компьютере, решаются за полиномиальное время на квантовом > C>компьютере. Полиномиальные алгоритмы тоже могут быть реализованы > C>быстрее: линейный поиск, например, реализуется за O(sqrt(n)) вместо > O(n) > C>и т.п. > Опа. А что это за алгоритмы такие, которые можно реализовать на > квантовом компьютере, но нельзя реализовать на классическом?
Теоретически — никакие. Квантовые и классические компьютеры полностью
эквивалентны (одни могут эмулировать другие).
Практически — есть квантовый алгоритм факторизации Шора, который
позволяет получить разложение числа на простые множители за квадратичное
время (от количества цифр в числе). Лучший классический алгоритм требует
экспоненциального времени, так что для факторизации числа с 10000 цифр
классическому компьютеру потребуется больше энергии, чем есть во Вселенной.
> И корректно ли их вообще называть словом "алгоритм" (на самом деле уже > прижился термин "квантовый алгоритм")?
Да, вполне.
> Заметьте, здесь то вы и противоречите сами себе. Если бы работу > квантового компьютера можно было целиком эмулировать, то и реализуемые > им "квантовые алгоритмы" вычислений можно было бы реализовать на > классическом компьютере.
Да, но вот только один шаг квантовых вычислений потребует экспоненциального (от сложности квантового алгоритма) числа шагов
классического.
> Поэтому не путайте две разных вещи: "эмуляцию работы квантового > компьютера" и "моделирование квантового компьютера для конкретной > задачи с точно определенными параметрами".
Наверное эту дискуссию можно закрывать. Мы уже вплотную подошли к тому моменту, когда по логике придется произносить всякие страшные слова, типа линейный оператор, гильбертово пространство, преобразование Адамара и т.п. А залазить в такие дебри просто нету времени.
) оказалось, что общий алгоритм для решения такой задачи составить нельзя. С другой стороны программист-человек с легкостью может определить эквивалентность двух алгоритмов (например, qsort-а и "пузырька") => соображалка человека использует не алгоримтический принцип работы, а какой-то иной => функционирование человеческого мозга нельзя описать алгоритмически с достаточной степенью точности => в основе функционирования человеческого мозга лежат неалгоритмизуемые физические процессы (такое вообще существует?)
Если физический процесс есть, то его можно алгоритмизировать. Другой вопрос в том, что пока настоящий уровень естествознание не позволяет алгоритимизировать функционирование человеческого мозга в целом.
Человеческое мышлене как алгоритмический процесс не похож на деятельность компьютера.
Мозг работает в аналоговорм формате и это не позволяет представлять информацию с высокой точностью.
Система кодирования также различается в корне. Для компьютера — это байты. Для мозга — это символы (слова). Причем связи между символами для разных людей разные (личный опыт — вещь неповторимая), даже в рамках одного социума. И тем боле для разных наций на разных сторонах света.
Здравствуйте, Alexey Rovdo, Вы писали:
AR>Наверное эту дискуссию можно закрывать. Мы уже вплотную подошли к тому моменту, когда по логике придется произносить всякие страшные слова, типа линейный оператор, гильбертово пространство, преобразование Адамара и т.п.
А при чем тут преобразование Адамара? Ты еще преобразование Фурье упомяни.
Здравствуйте, wilwill, Вы писали:
W>Если физический процесс есть, то его можно алгоритмизировать.
Не всегда можно точно сказать о том, что процесс есть (вот процесс гибели кошки Шредингера есть или нет?). Иногда это случайный процесс, иногда мы можем говорить только о вероятности этого процесса или только о его результатах. Опять же в ряде случаев похоже нарушается принцип причинности и результаты проявляются раньше самого процесса (или, например, место проявления этих результатов оказывается случайным).
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Alexey Rovdo, Вы писали:
AR>>Наверное эту дискуссию можно закрывать. Мы уже вплотную подошли к тому моменту, когда по логике придется произносить всякие страшные слова, типа линейный оператор, гильбертово пространство, преобразование Адамара и т.п.
AVK>А при чем тут преобразование Адамара? Ты еще преобразование Фурье упомяни.
Алгоритм Шора опирается на квантовое дискретное преобразование Фурье (ДПФ), которое выполняется на квантовом компьютере как чередующиеся друг за другом преобразования Адамара над отдельными кубитами и операции условного поворота фазы в одном кубите ...
Здравствуйте, Alexey Rovdo, Вы писали:
AR>Алгоритм Шора опирается на квантовое дискретное преобразование Фурье (ДПФ), которое выполняется на квантовом компьютере как чередующиеся друг за другом преобразования Адамара над отдельными кубитами и операции условного поворота фазы в одном кубите ...
Отлично. Только вот какое это имеет отношение к:
Поэтому не путайте две разных вещи: "эмуляцию работы квантового
компьютера" и "моделирование квантового компьютера для конкретной
задачи с точно определенными параметрами".
Для пояснения таких различий тонкости алгоритма Шора совершенно не нужны.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, Alexey Rovdo, Вы писали:
AR>>Алгоритм Шора опирается на квантовое дискретное преобразование Фурье (ДПФ), которое выполняется на квантовом компьютере как чередующиеся друг за другом преобразования Адамара над отдельными кубитами и операции условного поворота фазы в одном кубите ...
AVK>Отлично. Только вот какое это имеет отношение к: AVK>
Поэтому не путайте две разных вещи: "эмуляцию работы квантового
AVK>компьютера" и "моделирование квантового компьютера для конкретной
AVK>задачи с точно определенными параметрами".
AVK>Для пояснения таких различий тонкости алгоритма Шора совершенно не нужны.
Есть два понятия эмуляция и симуляция. Так вот отличие их как-раз в том, что в случае симуляции мы имеем дело с моделью (возможно, с приближенной моделью), а вот в случае эмуляции мы строим алгоритм (машину Тьюринга), который воспроизводит поведение эмулируемой системы (Тезис Тьюринга-Черча утверждает, что любой алгоритм может быть выполнен машиной Тьюринга).
Существует масса оговорок и пояснений к этой концепции. Долгое время искали математические задачи, которые не поддаются вычислению с помощью машины Тьюринга (т.е. не могут быть алгоритмизованы). Пытались сформулировать более сильное положение тезиса в виде:
Every function that can be physically computed can be computed by a Turing machine
(каждая функция, которая физически может быть вычислена, может быть вычислена на машине Тьюринга)
Считается, что это утверждение опровергнуто в работе: Willem Fouché, Arithmetical representations of Brownian motion, J. Symbolic Logic 65 (2000) 421-442
Т.е. существуют функции, которые человек может вычислить, но машина Тьюринга не может.
PS: Что же касается квантовых алгоритмов, то я не представляю себе "эмуляцию" линейного преобразования в гильбертовых пространствах ...
Дарней wrote: > AVK>Ровно как не факт, что любой алгоритм, выполняемый компьютером, > детерминирован. > > Ну да, бывают например такие вещи, как аппаратные генераторы случайных > чисел. Еще бывают случаи дефектов в железе, или даже дефектов в > проектировании оного. Но это только доказывает, что современный > компьютер — не машина Тьюринга Однако, одна "не машина Тьюринга" и > другая "не машина Тьюринга" — это совсем не эквивалентные вещи.
МТ бывает вероятностная, это вполне принято в науке. Далее, если
разговор не про feasible, а про computable, любой вероятностный
алгоритм эмулируется полным перебором выпадающих выборов (Ну, кроме
случаев бесконечных ветвей, которые обрываются на какой-то глубине).
Проблема ещё и в том, что на практике "невозможно" и "только за время
n^(n^..(n^n))" синонимы. Это тоже влияет на мысли на эту тему.
WFrag wrote: > Я знаю, мы на курсе когнитивной психологии подробно изучали творения > сего автора Там есть к чему прикопаться с точки зрения мат. логики — он > часто пользуется "интуитивными" доказательствами, которые неявно > используют аксиомы "извне" системы о которой идет доказательство > (например, когда он "доказывает" ложность Геделевского утверждения).
Ну, проблема в том, что это, кажется, повторимо в формальной логике
доказательств. В той, которая интуитивно кажется наиболее приближенной к
условиям. Но это как с аксиомой выбора — всегда есть произвол выбора
системы доказательств. И естественно, всё проходит, пока утверждение не
доберётся до встроенного предиката "доказывает". Но это уже как с
проблемой остановки — добавление оракула решает проблемы, пока
программа, исследуемая на остановку, не пользуется оракулом.
Cyberax wrote: >> C>А какие аксиомы? В этом-то вся и суть — откуда машина возьмет >> совершенно >> C>новые аксиомы, невыводимые в самой исследуемой теории? >> Возьмёт откуда-нибудь, научить можно. > > Вот как раз нельзя, в общем случае. > >> Плохо, что эти аксиомы будут заранее из ограниченного класса, мощности >> которого может нехватить. > > Гарантировано не хватит.
Может, имеет смысл говорить о проблеме "распознавателя доказательств"?
Потому что 1) эта задача решается людьми более (хотя и не идеально)
успешно и 2) никто не говорит о цене — все доказательства (все тексты на
русском/английском/формальном/эсперанто языке) — можно перебрать,
сказав, что человек это делает за счёт каких-то более физически эффективных, но моделируемых за неограниченное заранее
(гарантированно конечное)/фантастически большое время.
Cyberax wrote: > Видел статью про изучение МТ с генератором случайных чисел — пока ничего > особенного не нашли про нее, но вроде бы ее класс задач может быть шире.
Класс ВРР упоминался? Если да — то вопрос о решаемых задачах, до
получения ответа в которых мы доживём, а не о задачах, решаемых
принципиально.
Здравствуйте, WFrag, Вы писали:
FDS>>, а так же алгоритм, который мог бы по наблюдениям генерировать новые знания.
WF>Алгоритм да, алгоритм мы заложим. Будет предлагать теории и проверять их. Конечно, может и заблуждаться — как Ньютон, например.
Весь прикол в том, что такого алгоритма не существует самого по себе. Его надо разработать, и в ограниченности разработанного человеком алгоритма и заключаются все проблемы ИИ.
Здравствуйте, Alexey Rovdo, Вы писали:
AR>Здравствуйте, Lazy Cjow Rhrr, Вы писали:
LCR>>Alexey Rovdo,
AR>>>И зачем тогда нужны квантовые компьютеры? В чем их преимущество перед классическими?
LCR>>Кое-какие задачи можно решать существенно быстрее, только и всего.
AR>Да, но быстрее за счет чего? Вы полагаете, что за счет банально большей скорости выполнения элементарных операций?
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
