Доказана эквивалентность алгоритмов для разных квантовых компьютеров

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

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

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

Адиабатические квантовые компьютеры создать проще. Например, именно к этому классу относится вычислитель D-Wave. Ранее ученые доказали, что алгоритмы для адиабатических квантовых компьютеров и компьютеров на основе квантовых цепей полиномиально эквивалентны. Это значит, что если один решает задачу за время t, то этот алгоритм можно преобразовать для использования на другом, но он будет решать задачу за время, пропорциональное t в n-ной степени. В новой работе физики из Пекинского университета доказали, что эти алгоритмы эквивалентны, то есть время t для одного превращается в t умножить на константу для другого. Авторы называют достижение хорошей новостью для создателей адиабатических квантовых компьютеров, так как теперь оказывается, что с их помощью можно решать более обширное множество задач.