Первое доказательство преимущества квантового компьютера

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

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

Однако в квантовом компьютере бит может быть как нулем, так и единицей одновременно. Это связано с тем, что законы квантовой физики позволяют электронам занять несколько состояний за один раз. Квантовые биты или кубиты, таким образом, существуют в нескольких перекрывающихся состояниях.

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

Роберт Кениг, профессор теории сложных квантовых систем в TUM и его коллеги теперь убедительно продемонстрировали преимущество квантовых компьютеров. С этой целью они разработали квантовую схему, которая может решить определенную сложную алгебраическую задачу.

Новая схема имеет простую структуру — она ​​выполняет только фиксированное количество операций на каждом кубите. Такая схема называется постоянной глубиной. В своей работе исследователи доказывают, что проблема не может быть решена с использованием классических схем постоянной глубины. Кроме того, они отвечают на вопрос о том, почему квантовый алгоритм превосходит любую сравнимую классическую схему: квантовый алгоритм использует нелокальность квантовой физики.

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

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

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

«Quantum advantage with shallow circuits,» Science (2018). science.sciencemag.org/cgi/doi … 1126/science.aar3106