Хорошая разминка для ума в понедельник. Ran Raz из университета Принсетона и Avishay Tal из Стэнфорда показали, что существует класс задач, которые эффективно размеришимы квантовыми компьютерами, но принципиально не разрешими классическими (даже если вдруг окажется, что P=NP). Фактически, это означает не только существенное ускорение (уже доказано, что принципиально квантовый компьютер может эффективно решать все P-задачи), но и вообще заход на новые типы задач, которые еще нужно научиться формулировать.

В статье ниже Wired дает кратку вводную для тех, кто подзабыл о классах алгоритмической сложности, и описывает пример такой задачи.

p.s. Важное уточнение: разделение на классы в задаче происходит в постановке с оракулом.

https://www.wired.com/story/finally-a-problem-only-quantum-computers-will-ever-be-able-to-solve/ #quantum #computing