Квантовые компьютеры - принципиально другие

Два математики обнаружили проблему, которую не в силах решить классический компьютер, даже значительно мощнее, чем современный. Однако эта проблема вполне по силам квантовом компьютеру. Так ученые продемонстрировали, что квантовый компьютер не только мощнее, но и лучший во всех планах.

Ран Рац (Ran Raz) из Научно-исследовательского института имени Вейцмана (Израиль) и Авиш Тал (Avishay Tal) из Стэнфордского университета (США) сообщили: на вопрос, две последовательности казалось бы случайных чисел имеют скрытую общность, можно ответить с помощью квантовых алгоритмов. Зато классический компьютер не смог бы даже проверить полученный ответ. Согласно описанными данным, квантовый компьютер - это действительно что-то совершенно новое.

С ранних девяностых годов ХХ века эксперты ломают голову над этим вопросом: действительно ли квантовый компьютер отличается от классического. Предпосылкой для поисков ответа есть классы сложности: PH , что охватывает классы Р [полиномични: множество задач, время работы которых полиномиальной зависит от размера входных данных] и NP [неопределенно полиномични : множество задач, решение которых возможно при наличии некоторых дополнительных сведений], которые мог бы решить гипотетический бесконечно мощный классический компьютер, [Bounded error quantum polynomial time, квантовый аналог BPP, ищущих ответ задачи с определенной вероятностью, зависит от времени вычисления], который уже в силу реальном квантовом компьютеру.

Но есть проблемы, которые существуют в BQP, однако не в PH? Рац и Тал сказали «да». Их новая публикация содержит доказательство, что проблема числовой последовательности недоступна классическим методам, поэтому даже на бесконечно мощном классическом компьютере ее решение длился бы вечно. Тот факт, что для решения проблемы уже существует квантовый алгоритм, проще доказать, поскольку это уже давно известно.

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

Этот метод, который называется «методом оракула», измеряет количество подсказок, которые нужны компьютеру для того, чтобы решить проблему. Количество этих подсказок - мера необходимого времени вычислений. Согласно полученных данных классический компьютер не сможет решить задачу даже с бесконечным количеством подсказок - вместо квантовые алгоритмы требуют лишь одну.

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

Видео обзор

Квантовые компьютеры - принципиально другие