В библиотеке Колхоза есть пара очень хороших книг.
Это сообщение написано при активной поддержке 1997 — Белая Стена
Слова, пустые слова, подумал Стормгрен. Слова, за которые прежде люди дрались и умирали, но никогда больше не станут за них ни умирать, ни драться. И от этого мир станет лучше.
Здравствуйте, WoldemaR, Вы писали:
WR>Вот некоторые издания, типа компутерры, уже давно напрягается и вовсю "жгут" про квантовые компутеры.
WR>Объясните на пальцах, если кто врубился, — в чём фишка?
А ДНК-компьютер не интересует? Тоже интересная вещь. Массовая параллельность, компланарность Уотсона-Крика...
Здравствуйте, WoldemaR, Вы писали:
WR>Вот некоторые издания, типа компутерры, уже давно напрягается и вовсю "жгут" про квантовые компутеры.
WR>Объясните на пальцах, если кто врубился, — в чём фишка?
Можно посмотреть книжку
А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления, доступную здесь
Если на пальцах, то основным элементом вычислений является квантовый бит, который может находиться в одном из нескольких наблюдаемых состояний с некоторой вероятностью. Т.е. в отличии от обычного бита, который либо точно 0, либо точно 1, обращаясь к одному и тому же квантовому биту можно найти его в различных состояниях, каждое из которых обладает определенной вероятностью появления.
И квантовые алгоритмы заключаются в том, чтобы проводить вычисления, при которых вероятность появления правильного ответа в целевой ячейке памяти стремится к единице. За счет отхода от детерминированного ответа удается получить теоретическую полиномиальную сложность для задач, которые на классических компьютерах полиномиально не решаются.
Проблема только в том, что пока теоретическая разработка существенно опережает технологическую.
Здравствуйте, WoldemaR, Вы писали:
WR>Вот некоторые издания, типа компутерры, уже давно напрягается и вовсю "жгут" про квантовые компутеры.
WR>Объясните на пальцах, если кто врубился, — в чём фишка?
фишка, как обычно, в деньгах.
лет 7-10 назад за просто добавление web к названию проекта или компании, можно было увеличить приток капиталла в разы.
сейчас тот же самый эффект наблюдается при использовании других ключевых слов.
Здравствуйте, kfmn, Вы писали:
K>Можно посмотреть книжку K>А.Китаев, А.Шень, М.Вялый. Классические и квантовые вычисления, доступную здесь
СПАСИБО. Посмотрим на досуге.
K>И квантовые алгоритмы заключаются в том, чтобы проводить вычисления, при которых вероятность появления правильного ответа в целевой ячейке памяти стремится к единице. За счет отхода от детерминированного ответа удается получить теоретическую полиномиальную сложность для задач, которые на классических компьютерах полиномиально не решаются.
Вот из этого я понял, что квантовый компьютер — это способ задать вопрос богу.
Звонок в пейджинговую компанию:
— Здравствуйте, до меня не дошло сообщение.
— Попробуйте перечитать его ещё раз.
Что именно тебе непонятно? Принцип работы? Области применения? Возможность реализации в домашних условиях? Зачем и кому это надо? Стоит ли сейчас покупать квантовый компьютер домой? Сколько это стоит? Конкретезируй... Или напиши письмо авторам статей (адреса электронной почты в КТ указывают), попроси у них консультации по интересующим вопросам...
Здравствуйте, SeLarin, Вы писали:
SL>Что именно тебе непонятно? Принцип работы? Области применения? Возможность реализации в домашних условиях? Зачем и кому это надо? Стоит ли сейчас покупать квантовый компьютер домой? Сколько это стоит? Конкретезируй... Или напиши письмо авторам статей (адреса электронной почты в КТ указывают), попроси у них консультации по интересующим вопросам...
Ты прикалываешся? Да они сами непонимают о чём пишут.
Здравствуйте, WoldemaR, Вы писали:
WR>Ты прикалываешся? Да они сами непонимают о чём пишут.
Я никогда не прикалываюсь. У меня вообще отстутствует чувство юмора. В КT #643 есть интервью с людьми, работающими в области квантового компьютинга. В той же статье есть врезка "Квантовый компьютинг в двух словах". В ней основные принципы кратко описаны, причем на достаточно понятном уровне.
К тому же, если в Google ввести запрос quantum computing, то ты получишь примерно 35300000 результатов, примерно соответствующих этой теме... Хотя бы одна из них будет содержать нужную тебе информацию. Удачи!
SeLarin пишет: > К тому же, если в Google ввести запрос quantum computing, то ты получишь примерно 35300000 результатов, примерно соответствующих этой теме... Хотя бы одна из них будет содержать нужную тебе информацию. Удачи!
Интересно, сколько бы результатов ты получил 6 лет назад, погуглив по
запросу "проблема 2000"?
Здравствуйте, WoldemaR, Вы писали:
WR> квантовые компутеры. WR> в чём фишка?
Почему ими все заинтересовались? В первую голову это произошло после того, как была доказана возможность с помощью QC разложить число на множители за "разумное" время. (Строго говоря, никто не доказал, что это невозможно на "классическом" компьютере). Об алгоритме Шора.Оценки классического времени..
Соответственно, сначала появилось много желающих ускорить все подряд. Но — увы. Как было доказано Юрием Ожиговым (ссылки на статью, к сожалению, под руками нет), вероятность того, что наугад взятый алгоритм будет выполняться на квантовом компьютере быстрее, чем на классическом, равна нулю. Впрочем, этот "нуль" говорит лишь о том, что поиск таких алгоритмов должен вестись не методом случайной выборки. И интерес не угас.
Axc wrote:
> Соответственно, сначала появилось много желающих ускорить все подряд. Но > — увы. Как было доказано Юрием Ожиговым (ссылки на статью, к сожалению, > под руками нет), вероятность того, что наугад взятый алгоритм будет > выполняться на квантовом компьютере быстрее, чем на классическом, равна > нулю. Впрочем, этот "нуль" говорит лишь о том, что поиск таких > алгоритмов должен вестись не методом случайной выборки. И интерес не угас.
Не понял, интересное доказательство, только пользы от него? По-моему, можно доказать, что наугад взятый алгоритм решает
поставленную задачу — тоже равна нулю, но это не умаляет значение программисткой деятельности.
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, kan_izh, Вы писали:
>> вероятность того, что наугад взятый алгоритм будет >> выполняться на квантовом компьютере быстрее, чем на классическом, равна >> нулю.
_>Не понял, интересное доказательство, только пользы от него?
Может, не совсем корректно сформулировал: вероятность того, что решение задачи вообще поддается "квантовому ускорению".
Axc wrote:
>> > вероятность того, что наугад взятый алгоритм будет >> > выполняться на квантовом компьютере быстрее, чем на классическом, равна >> > нулю. > > _>Не понял, интересное доказательство, только пользы от него? > > Может, не совсем корректно сформулировал: вероятность того, что решение > задачи вообще поддается "квантовому ускорению".
А можно какую-нибудь ссылку? Просто непонятно всё равно. Ну и что, что не каждую задачу можно ускорить? Если существует
хотя бы одна, и она может пригодится на практике (а с факторизацией дело обстоит так, имхо) — этого уже предостаточно.
Зачем оценивать вероятность?
Posted via RSDN NNTP Server 2.0
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, WoldemaR, Вы писали:
WR>Вот некоторые издания, типа компутерры, уже давно напрягается и вовсю "жгут" про квантовые компутеры.
WR>Объясните на пальцах, если кто врубился, — в чём фишка?
Насколько я понял, кубит (квантовый бит) после установки системы в т.н. "начальное состояние" находится сразу во всех возможных состояниях (т.н. "суперпозиция квантовых состояний" — описываемых вероятностной (волновой) фукнцией в комплексном поле). После приложения к этому кубиту специальных обратимых квантовых логических преобразований с кубита "снимается результат" (как раз момент когда из набора всех состояний с определенной долей вероятности мы получим конткретный ответ). Т.е. фишка в том, что преобразованиям подвергаются все возможные состояний кубита (ну, которых для кубита естественно только два квантовая 1 и квантовый 0). Мощность этого дела проявляе6тся когда у нас есть регистр квантовых кубитов (имея 8 штук мы можем производить операции сразу над всеми 256 значениями). Плюс тут играет такой квантовый феномен как "entanglement"..
Т.е. совсем на пальцах — суть в офигительной параллельности квантовых вычислений.
Возможные применения: есть в общем-то не очень широкий спектр задач на которых квантовые вычисления рулят и самый интригующий — это разложение на простые сомножетели больших простых чисел (типа, большая часть асимметричной криптографии должна быть выброшена на помойку с приходом практических квантовых компьютеров).
Реально же пока кажется даже экспериментально регистра больше 7 кубитов создано не было...
Здравствуйте, kan_izh, Вы писали:
_>Axc wrote:
>> Может, не совсем корректно сформулировал: вероятность того, что решение >> задачи вообще поддается "квантовому ускорению". _>А можно какую-нибудь ссылку?
Увы, книжка, кажется, у родителей. В инете — не нашел. (На русском, на английском — не искал) _> Ну и что, что не каждую задачу можно ускорить? Если существует хотя бы одна, и она может пригодится _> на практике (а с факторизацией дело обстоит так, имхо) — этого уже предостаточно. _>Зачем оценивать вероятность?
Некто изобретает чудодейственный эликсир, лечащий от всех болезней, только для каждой нужно догадаться — как. Потом другой некто доказывает, что наугад взятую болезнь этим эликсиром не вылечишь.
Эликсир не перестал быть эликсиром. И какие-то болезни он лечит весьма эффективно. Но теперь мы знаем, чего от него можно ожидать.
RegisteredUser wrote: > Возможные применения: есть в общем-то не очень широкий спектр задач на > которых квантовые вычисления рулят и самый интригующий — это разложение > на простые сомножетели больших простых чисел (типа, большая часть > асимметричной криптографии должна быть выброшена на помойку с приходом > практических квантовых компьютеров).
На самом деле сейчас открыта проблема можно ли квантово ускорить NP до
полиномиального времени с большой вероятностью правильного (притом
заметим, проверяемого) ответа. Если не выйдет, то факторизация не
обломит всю асимметричнуб криптографию, хотя обрушит RSA и распределение
ключей по Диффи-Хеллмену. А если выйдет, то окажется, что квантовый
компьютер уничтожает всю криптографию (неважно какую), но, возможно,
создаёт принципиально новые возможности для создания квантовой криптографии.
Здравствуйте, raskin, Вы писали:
R>На самом деле сейчас открыта проблема можно ли квантово ускорить NP до R>полиномиального времени с большой вероятностью правильного (притом R>заметим, проверяемого) ответа.
Ну NP-задача по определению NP должна быть "проверяема" за полиномиальное время. Плюс нетождественность P и NP, насколько я понимаю, тоже еще строго не доказана А так замах хороший конечно же...
RegisteredUser wrote: > R>На самом деле сейчас открыта проблема можно ли квантово ускорить NP до > R>полиномиального времени с большой вероятностью правильного (притом > R>заметим, проверяемого) ответа. > > Ну NP-задача по определению NP должна быть "проверяема" за
Я знаю, поэтому это и отметил только в скобках. > полиномиальное время. Плюс нетождественность P и NP, насколько я > понимаю, тоже еще строго не доказана А так замах хороший конечно же...
Угу, никак не доказана. Но надежда на то, что квантовые вычисления
позволят решать NP, больше.
Axc wrote: > _>Не понял, интересное доказательство, только пользы от него? > Может, не совсем корректно сформулировал: вероятность того, что решение > задачи вообще поддается "квантовому ускорению".
Тут ведь как, есть уже СУЩЕСТВУЮЩИЕ квантовые алгоритмы, работающие
быстрее классических алгоритмов. Например, квантоый поиск в
неупорядоченой базе данных занимает O(sqrt(N)) времени, а не O(n) как в
классическом случае.
raskin wrote: >> полиномиальное время. Плюс нетождественность P и NP, насколько я >> понимаю, тоже еще строго не доказана А так замах хороший конечно же... > Угу, никак не доказана. Но надежда на то, что квантовые вычисления > позволят решать NP, больше.
Да даже если и докажут, что P=NP, то это еще ничего не значит.
Квантовые алгоритмы могут иметь намного более лучшие характеристики по
скорости. Скажем, квантовый алгоритм с временем O(N^2) может быть лучше
классического (полиномиального!) алгоритма O(N^10).
Квантовые алгоритмы просто работают на совершенно других принципах. Их
теоретическое обоснование никем не оспаривается, вопрос только в их
реальной реализации.
icq# 348-436-436 Играет Elton John — Friends Never Say Goodbye
Слова, пустые слова, подумал Стормгрен. Слова, за которые прежде люди дрались и умирали, но никогда больше не станут за них ни умирать, ни драться. И от этого мир станет лучше.
Здравствуйте, Cyberax, Вы писали:
C>Axc wrote: >> _>Не понял, интересное доказательство, только пользы от него? >> Может, не совсем корректно сформулировал: вероятность того, что решение >> задачи вообще поддается "квантовому ускорению". C>Тут ведь как, есть уже СУЩЕСТВУЮЩИЕ квантовые алгоритмы, работающие C>быстрее классических алгоритмов. Например, квантоый поиск в C>неупорядоченой базе данных занимает O(sqrt(N)) времени, а не O(n) как в C>классическом случае.
в ассциативной памяти поиск вообще идёт O(1) времени. и её кстати широко используют для кешей. всего лишь активная память, в которой каждая ячейка снабжена своим компараитором, так что общее кол-во операций оказывается всё равно O(n)
BulatZiganshin wrote: > C>Тут ведь как, есть уже СУЩЕСТВУЮЩИЕ квантовые алгоритмы, работающие > C>быстрее классических алгоритмов. Например, квантоый поиск в > C>неупорядоченой базе данных занимает O(sqrt(N)) времени, а не O(n) как в > C>классическом случае. > в ассциативной памяти поиск вообще идёт O(1) времени. и её кстати широко > используют для кешей. всего лишь активная память, в которой каждая > ячейка снабжена своим компараитором, так что общее кол-во операций > оказывается всё равно O(n)
Причем тут ассоциативная память? Я говорю про поиск в обычном
неупорядоченом списке.
Играет Elton John — Friends Never Say Goodbye 
