вроде как эта игра и появилась как популяризация этих неравенств.
По поводу квантовых компьютеров - есть такой абстрактный аргумент в их пользу: если какие-то вещи долгое время кажутся трудными (не удаётся придумать быстрый алгоритм для них), то они иногда (и даже часто) оказываются полными - то есть к ним многое сводится. Это даёт надежду на то, что если, скажем, расчёты квантовых систем из первых принципов вычислительно сложны, хотя вроде теория есть и в простых случаях подтверждается, то поведение специально построенных систем может быть ответом к вычислительно сложной задаче (типа того же разложения на множители)
Так что, может, не обязательно прямо-таки кубиты строить - может быть, есть какой-то реализуемый эксперимент, в котором много параметров (десятки тысяч битов), устойчиво воспроизводимые, но сложно вычисляемые (хотя теоретически ясно, как их вычислять) результаты - и можно доказать его полноту?
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
ну да,
Date: 2010-08-15 10:47 am (UTC)По поводу квантовых компьютеров - есть такой абстрактный аргумент в их пользу: если какие-то вещи долгое время кажутся трудными (не удаётся придумать быстрый алгоритм для них), то они иногда (и даже часто) оказываются полными - то есть к ним многое сводится. Это даёт надежду на то, что если, скажем, расчёты квантовых систем из первых принципов вычислительно сложны, хотя вроде теория есть и в простых случаях подтверждается, то поведение специально построенных систем может быть ответом к вычислительно сложной задаче (типа того же разложения на множители)
Так что, может, не обязательно прямо-таки кубиты строить - может быть, есть какой-то реализуемый эксперимент, в котором много параметров (десятки тысяч битов), устойчиво воспроизводимые, но сложно вычисляемые (хотя теоретически ясно, как их вычислять) результаты - и можно доказать его полноту?