Математики придумали новую задачу с возможность решения только квантовым компьютером
Сформулирован вариант первого примера задачи, условия которой принципиально не может решить электроника классического компьютера, она под силу только квантовой логике. Для поиска такого условия специалистам пришлось затрать 25 лет. Результаты работы можно найти на сервере форума Electronic Colloquium on Computational Complexity.
Теория алгоритмов определяет вычислительные задачи по разным уровням классам сложности. С целью унификации, рассматриваются исключительно задачи разрешимости, с ответом «да» или «нет». Распространены сложности с классами P и NP. Первый класс легко решается классической детерминированной машиной Тьюринга (в форме универсального вычислителя) в период полиномиального времени. В данном случае, количество операций, необходимое машине представляется как многочлен, с зависимостью от длины сообщения на входе. Стандартную задачу подобного определяет вычислитель и проверяет, является ли число простым.
NP задачи проверяются за время, с условием не превышения полинома от показателя входных данных. На сегодня неизвестно - есть или нет равенство классов P и NP, это остается открытой проблемой математики. Причем за ее решение можно получить миллион долларов от Математического института Клэя.
В новой работе учеными представлена задача класса BQP, с проблемами, решаемыми квантовым компьютером за полиномиальный промежуток времени. До этой работы было неизвестно, есть ли попадающие примеры в BQP, попадающие в PH – который обобщает NP-класс. Теперь доказано, оракульнуе разделение (Oracle Separation) — это случай такого решения.
В новой работе математиками организован анализ уровня количества обращений к «оракулу», которым формируются только ответы правильного содержания и по правильной последовательности. Как оказалось, квантовому компьютеру хватает одной подсказки, при этом любой классический компьютер с бесконечным потоком числа подсказок, с такой задачей не разберется.
Теория алгоритмов определяет вычислительные задачи по разным уровням классам сложности. С целью унификации, рассматриваются исключительно задачи разрешимости, с ответом «да» или «нет». Распространены сложности с классами P и NP. Первый класс легко решается классической детерминированной машиной Тьюринга (в форме универсального вычислителя) в период полиномиального времени. В данном случае, количество операций, необходимое машине представляется как многочлен, с зависимостью от длины сообщения на входе. Стандартную задачу подобного определяет вычислитель и проверяет, является ли число простым.
NP задачи проверяются за время, с условием не превышения полинома от показателя входных данных. На сегодня неизвестно - есть или нет равенство классов P и NP, это остается открытой проблемой математики. Причем за ее решение можно получить миллион долларов от Математического института Клэя.
В новой работе учеными представлена задача класса BQP, с проблемами, решаемыми квантовым компьютером за полиномиальный промежуток времени. До этой работы было неизвестно, есть ли попадающие примеры в BQP, попадающие в PH – который обобщает NP-класс. Теперь доказано, оракульнуе разделение (Oracle Separation) — это случай такого решения.
В новой работе математиками организован анализ уровня количества обращений к «оракулу», которым формируются только ответы правильного содержания и по правильной последовательности. Как оказалось, квантовому компьютеру хватает одной подсказки, при этом любой классический компьютер с бесконечным потоком числа подсказок, с такой задачей не разберется.
