Создан квантовый чип

Сообщение доставлено в целости с вероятностью 95%

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

>Для порноигрушек и других некритичных приложений сойдёт...

Наверное, следует напомнить, что на реальных классических компьютерах _ВСЕ_ вычисления - вероятностные. Только вероятность эта крайне близка к единице :)

> 1) говорят что какой то индус придумал полиномиальный алгоритм. Не один, а несколько, и не алгоритм разложения, а проверки простоты. К тому же, на практике все всё равно используют старый добрый вероятностный метод. Но для теории это было достижением.

> Т.е. "Этого элемента нет с вероятностью 99.8%" :))

Насколько мне известно, уже придумали алгоритм с вероятностью на 0.2% лучшей ;)

> Программы (а, значит, и операционные системы) - это понятия машины Тьюринга. А квантовый компьютер таковой не является.

А можно поподробнее? Всю жизнь думал, что квантовый компьютер может считать всё то же, что и обычный... BPP, BQP, тезисы Church'а (не знаю, как по-русски) Вам ничего не говорят?

Ждём ебилдов

протоколы коммуникации между двумя независимыми машинами всегда имеют ненулевую вероятность сбоя.

Кстати, не подскажите: тезис Черча относится только к классической машине Тьюринга или к Недетерменированной МТ, а также квантовой МТ?

> Кстати, не подскажите: тезис Черча относится только к классической машине Тьюринга или к Недетерменированной МТ, а также квантовой МТ?

Тезисы Черча (их несколько - "слабый" и "сильный", с или без использования рандомальности) относятся к любой вычислительной модели.

"Слабый" относится к тому, что можно посчитать вообще и утверждает, что всё, что можно посчитать в какой-то модели вычислений, можно посчитать и на МТ.

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

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

Необходимо определить что значит термин "посчитать".

Относится ли термин посчитать к результатам типа "Элемента нет в массиве с вероятностью 99.999998%"?

У меня почему-то была убежденность, что во времена Черча подразумевалось, что алгоритм должен выдавать 100% результат, например, "Это уравнение не имеет решений в целых числах" и т.д.

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

По-видимому это также связано с принципом неопределенности Гейзенберга.

> Относится ли термин посчитать к результатам типа "Элемента нет в массиве с вероятностью 99.999998%"?

А главное, что за миллион операций вероятность ошибки будет уже 0.02, а для 10 миллионов вероятность ошибки станет равной 0.181269248473.

Так что для OLTP квантовые компы не подходят.

> А главное, что за миллион операций вероятность ошибки будет уже 0.02, а для 10 миллионов вероятность ошибки станет равной 0.181269248473

а повторить операцию для одного и того же элемента 2 раза и превратить 99.999998% в 99.9999999999998% башка перегреется?

>> А главное, что за миллион операций вероятность ошибки будет уже 0.02, а для 10 миллионов вероятность ошибки станет равной 0.181269248473

>а повторить операцию для одного и того же элемента 2 раза и превратить 99.999998% в 99.9999999999998% башка перегреется?

+1
я почему-то сразу об этом подумал, когда тут всякие умники о вероятностях заговорили...

>А главное, что за миллион операций вероятность ошибки будет уже 0.02, а для 10 миллионов вероятность ошибки станет равной 0.181269248473.

В некоторых алгоритмах ( например, переборных ) ошибка накапливаться не будет. Причем даже если и произошло некоторое накопление ошибки результат может оказаться полезным с практической точки зрения. В любом случае получить хоть какой-то результат за 1-2 года полезнее, чем за 1000-2000 лет.

Схема поиска решения может выглядеть так:

1) Быстрый перебор вариантов на квантовом компьютере 2) Проверка найденного результата на классическом компьютере

Люди, вы что думаете, что обычный компьютер дает 100% результат, если бы было так то почемуже не найти точное значение пи до скажем 1500000000 знака?, всего ничего. Насколько я помню даже машина Беббиджа давала вероятностный результат. и при работе с числами с плавающими запятыми вероятностный результат неминуем. что же даст квантовый компьютер? а он даст прежде всего решения чуть более грубые чем обычный зато в некоторых случаях он даст решения на сотни порядков (если не на тысячи) быстрее, причем что вам мешает полученный результат проверить на обычном компьютере? и вообще для примера не только процессоры но и вообще большинство электронных компонентов идут с вероятностью ошибки 10^-5 максимум 1^-7. Тут для того чтобы получить -11 степень которую требуют госты приходится вместо 1 контроллера типа PIC MSP или AVR использовать 3 процеммора и очень аккуратно их завязывать....

>даст решения на сотни порядков (если не на тысячи) быстрее

Сто порядков это круто. Это порядков на 50 больше, чем возраст Вселенной, выраженный в сингулярностях :D

как же вы это дело в сингулярностях выражать то собрались? разве что по минимальному размеру сингулярностей доживших со времен большого взрыва до наших дней? опять же расстояние прийдется учитывать.....