Здравствуйте, 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 
