С 1990-х годов накапливаются доказательства того, что квантовые компьютеры способны решать ряд особенно сложных вычислительных задач, которые применяются в управлении цепочками поставок, медицине и других областях.
Новое [исследование](https://iopscience.iop.org/article/10.1088/2058-9565/ae0364), опубликованное на этой неделе в журнале Quantum Science and Technology, предлагает новый план достижения этой цели. В нём подробно рассматривается, как сложность задачи определяет предельную скорость квантового компьютера, и как мы можем научиться доводить эту скорость до предела.
«Некоторые математические задачи просты. Другие математические задачи сложны, но что делает задачу простой или сложной?» — задаётся вопросом Ачим Кемпф, доцент кафедры физики информации и искусственного интеллекта в Университете Ватерлоо и ассоциированный член Института Периметра.
«Оказывается, когда вы помещаете задачу на квантовый компьютер, сложность задачи переводится в необходимость использования квантовой запутанности. Чем сложнее вопрос, тем более сложной должна быть запутанность», — поясняет Кемпф.
Это означает, что вычислительная задача становится физической реальностью, где частицы или кубиты внутри квантового компьютера должны вести себя по-разному в зависимости от сложности. То, что раньше было математикой, стало физикой, где запутанность выступает в качестве ключевого процесса.
Новое исследование, соавторами которого являются Кемпф и Эйнар Габбасов, аспирант Института квантовых вычислений Университета Ватерлоо и Института Периметра, впервые подробно описывает эту взаимосвязь.
Математики и информатики разработали сложную систему классификации, которая группирует задачи по их сложности, показывая, какие задачи являются вычислительно сложными, а какие — нет. Наиболее сложный класс этих задач известен как NP-сложные задачи. Хотя нет доказательств того, что квантовые компьютеры могут быстро решить их все, исследователи надеются, что они смогут обеспечить значительное ускорение для некоторых из наиболее сложных и практически применимых задач, таких как оптимизация сложных систем.
Для написания квантовых алгоритмов, которые могут обеспечить такое ускорение, невероятно полезно иметь возможность классифицировать и описывать сложность задачи в физических терминах. Одна из давних визуализаций, которую используют эксперты для этого, — описание сложности задачи через рельеф местности.
«Представьте, что вы спрыгнули с парашютом на местность с холмами, долинами и скалами, и вы хотите найти самую низкую точку, где, как вам сказали, вы найдёте сундук с сокровищами. Когда мы имеем дело с простой задачей, соответствующий ландшафт имеет пологий склон или состоит из одной долины», — говорит Кемпф.
«Но для сложной задачи соответствующий ландшафт пересечённый, и вы можете легко оказаться на дне долины без сокровищ, потому что фактическая самая низкая точка находится в более глубокой пропасти в 20 километрах отсюда. Тогда решение задачи становится очень сложным», — объясняет Кемпф.
Сила квантовых компьютеров заключается в том, что они позволяют искать все долины одновременно, используя запутанность, вместо того чтобы проверять каждую из них последовательно. И для этого запутанность должна быть буквально такой же сложной, как география ландшафта задачи.
Запутанность была известна как «жуткий дальнодействующий эффект», по словам Альберта Эйнштейна, который имел в виду, что одна частица, по-видимому, мгновенно влияет на другую, независимо от того, как далеко они находятся друг от друга. Запутанные частицы могут соединяться таким образом, что при измерении состояния одной из них вы сразу узнаете состояние другой.
«Вы можете иметь два отдельных объекта, две частицы или два кубита, и как только они запутываются, они становятся как бы одним целым. Невозможно рассматривать их отдельно: они становятся одним целым в одном состоянии», — объясняет Габбасов.
Кемпф сравнивает это с бросанием дюжины запасных зарядных кабелей в ящик, которые неизбежно выходят запутанными и слипшимися вместе. Уникальные свойства запутанности — это то, что даёт квантовым вычислениям преимущество перед классическими компьютерами.
Габбасов и Кемпф показывают, что аналогия с «пересечённой местностью» для вычислительной сложности — это больше, чем просто метафора. Она даёт прямое указание на то, какую запутанность квантовый компьютер должен создать для решения задачи. Пересечённый, сложный ландшафт требует столь же сложной и изощрённой сети запутанности между квантовыми битами.
«Мы обнаружили, что сложные математические задачи сложны, потому что они требуют от квантовых компьютеров манипулировать, создавать и перераспределять высокосложную запутанность внутри системы. По мере развития системы кубиты начинают создавать сложную сеть», — говорит Габбасов.
«Отношения могут меняться, частицы могут распутываться и снова запутываться с чем-то другим — в соответствии с холмами и долинами ландшафта, перетекающими друг в друга. Сложные задачи требуют много манипуляций с запутанностью при постоянных изменениях, и это определяет, насколько быстрой может быть вычисление», — добавляет он.
Благодаря этому исследованию команда создала совершенно новый способ измерения скорости, с которой задача может быть решена на квантовом компьютере, основанный на количестве необходимой запутанности. Этот «предел скорости» сможет информировать о разработке квантовых алгоритмов в будущем, позволяя им «сглаживать» вычислительный путь, предвидеть узкие места и достигать максимально быстрых решений.
Эти результаты были получены для особого типа квантового компьютера, известного как адиабатический (или квантовый аналог) квантовый компьютер, но известно, что любое адиабатическое квантовое вычисление также может быть выполнено на квантовых компьютерах, основанных на схемах (или квантовых цифровых) квантовых компьютерах, и наоборот. Это означает, что новое понимание может быть применено во всей отрасли квантовых вычислений.
Многие лидеры в области квантовых вычислений, включая D-Wave, Quantinuum, IonQ, QuEra Computing, Pasqal, Atom Computing, Microsoft, Google и IBM, разрабатывают квантовое оборудование, и некоторые аппаратные средства могут даже выполнять как адиабатические, так и основанные на схемах квантовые вычисления.
Габбасов и Кемпф считают, что это исследование станет плодотворной почвой для последующей работы, и надеются, что оно вдохновит других учёных применить эти идеи в своих областях, где могут появиться новые открытия.
«Я думаю, что это исследование ускорит экономическую жизнеспособность квантовых вычислений. Мы теперь лучше понимаем, как превратить математическую задачу в физическую», — говорит Кемпф. «Мы по сути предоставили новый мост между математикой и физикой, и мы думаем, что по этому мосту может быть организовано много движения. Этот результат будет полезен при эксплуатации квантовых компьютеров, улучшении их конструкции и создании программного обеспечения для них».
Предоставлено [Perimeter Institute for Theoretical Physics](http://www.perimeterinstitute.ca/)