Квантовый компьютер - это машина, предназначенная для использования квантовой механики для выполнения вещей, которые не могут быть сделаны ни одной машиной, основанной только на законах классической физики.
Возможности применения квантовых вычислений варьируют от разрушения криптографических систем до разработки новых лекарственных средств. Эти приложения основаны на квантовых алгоритмах, которые работают на квантовом компьютере и достигают ускорения, или другого повышения эффективности, по сравнению с любым возможным классическим алгоритмом. Хотя крупномасштабных квантовых компьютеров общего назначения пока не существует, теория квантовых алгоритмов активно изучается уже более 20 лет.
Вопреки широко распространенному мнению, что квантовые компьютеры имеют мало приложений, область квантовых алгоритмов развилась в достаточно обширную область исследования.
Алгоритмы
Одним из первых обнаруженных приложений квантовых компьютеров стал алгоритм Шора для целочисленной факторизации. Алгоритм эффективной факторизации Шора подразумевает, что эта криптосистема не защищена от атак со стороны большого квантового компьютера. В качестве более конкретного сравнения, в 2010 сообщили о классической факторизации 768-битного числа с использованием сотен современных компьютеров за период в 2 года, при общей вычислительной мощности ~ 1020 операций.
Детальный анализ одной отказоустойчивой квантовой вычислительной архитектуры, делающий разумные предположения о базовом оборудовании, предполагает, что 2000-битное число может быть разложено квантовым компьютером с использованием ~ 3 × 1011 квантовых ворот и приблизительно миллиарда кубитов, работающих чуть более одного дня при частоте 10 МГц.
Это явно выходит за рамки современных технологий, но не кажется нереалистичным в качестве долгосрочной цели. Подход Шора к факторизации целых чисел основан на сведении задачи к конкретному случаю математической задачи, известной как задача скрытой подгруппы (HSP) , и последующем предоставлении эффективного квантового алгоритма для этой задачи.
Два особенно интересных примера ГСП, для которых в настоящее время неизвестны полиномиально-временные квантовые алгоритмы, - это диэдрические и симметричные группы.
- Полиномиально-временной квантовый алгоритм даст эффективный алгоритм поиска кратчайших векторов в решетках ;
- Эффективный квантовый алгоритм даст эффективный тест на изоморфизм графов (эквивалентность при перемаркировке вершин).
Основное оборудование, предполагает, что 2000-битное число может быть разложено квантовым компьютером с использованием ~ 3 × 1011 квантовых ворот, и приблизительно миллиарда кубитов, работающих чуть более чем на при тактовой частоте 10 МГц. Это явно выходит за рамки современных технологий, но не кажется нереалистичным в качестве долгосрочной цели.
Симуляция квантума
В первые годы классических вычислений одним из основных применений компьютерных технологий было моделирование физических систем (такие приложения, вероятно, восходят, к механизму Антикитеры со II века до н.э.). Аналогичным образом, наиболее важным ранним применением квантовых компьютеров, вероятно, будет моделирование квантовых систем области применения моделирования включают квантовую химию, сверхпроводимость, метаматериалы и физику высоких энергий.
Действительно, можно было бы ожидать, что квантовое моделирование поможет понять любую систему, в которой квантовая механика играет определенную роль.
Слово "моделирование" может быть использовано для описания ряда задач, но в квантовых вычислениях часто используется для обозначения задачи вычисления динамических свойств системы. Поскольку все квантовые системы подчиняются уравнению Шредингера, это принципиально важная задача, однако экспоненциальная сложность полного описания общих квантовых состояний предполагает невозможность эффективного классического достижения и фактически неизвестен эффективный общий классический алгоритм квантового моделирования.
Квантовый компьютер общего назначения действительно может эффективно моделировать квантовую механику в этом смысле для многих физически реалистичных случаев, таких как системы с локальными ограничениями на их взаимодействия.
Цифровое моделирование
Квантовый компьютер может быть эффективно смоделирован в данном случае в случае для получения приблизительного значения, чтобы определить, какое именно квантовое состояние могло быть выполнено. Алгоритм работает во времени по полиномиальному размеру моделируемой системы (количество кубитов) и желаемому времени эволюции, обеспечивая экспоненциальное ускорение по сравнению с лучшими общеизвестными классическими алгоритмами. Тем не менее, есть еще возможности для совершенствования, и квантовое моделирование остается предметом активных исследований.
Для некоторых систем аналоговое квантовое моделирование может быть значительно проще в реализации, чем цифровое квантовое моделирование, за счет меньшей гибкости. Поэтому ожидается, что в первую очередь будут внедрены аналоговые тренажеры, превосходящие их классические аналоговые модели.
В классической компьютерной науке понятие случайного перемещения или марковской цепи является мощным алгоритмическим инструментом и часто применяется для решения задач поиска и отбора проб. Квантовые переходы обеспечивают такую же мощную и общую основу для разработки быстрых квантовых алгоритмов.
Подобно тому, как алгоритм случайной ходьбы основан на моделировании движения частиц, перемещающихся случайным образом в пределах некоторой базовой графовой структуры, квантовый ход основан на моделировании когерентной квантовой эволюции частиц, перемещающихся по графу. Алгоритмы квантовой ходьбы обычно используют один из двух способов, при которых квантовая ходьба превосходит случайную: более быстрое попадание (время, необходимое для нахождения вершины цели из исходной вершины) и более быстрое смешивание (время, необходимое для распределения по всем вершинам после начала от одной исходной вершины.
Область гамильтоновской сложности призвана характеризовать сложность вычислительных величин, представляющих интерес для квантово-механических систем. Прототипным примером и фундаментальной задачей в квантовой химии и физике конденсата является задача приблизительного вычисления энергии основного состояния физической системы, описываемая локальным гамильтонианом.
Использование модели квантовой информации в качестве математического инструмента может дать представление о других задачах чисто классического характера. Например, на основе квантовых информационно-теоретических принципов можно получить сильную нижнюю границу классической коммуникационной сложности внутренней функции продукта. Идеи квантовых вычислений также были использованы для доказательства новых ограничений на классические структуры данных, коды и формулы.
Почему неизвестно больше алгоритмов, в частности, более экспоненциальное ускорение?
Одна из причин заключается в том, что сильные нижние границы доказаны на мощности квантовых вычислений в модели сложности запроса, где в качестве меры сложности рассматривается только количество запросов на вход.
Например, сложность, достигаемая алгоритмом Гровера, не может быть улучшена ни на один запрос при сохранении той же вероятности успеха. В более общем плане, для достижения экспоненциального ускорения классических вычислений в модели сложности запроса на входе должно быть обещание, т.е. некоторые возможные входы должны быть запрещены.
Это одна из причин успеха квантовых алгоритмов в криптографии: существование скрытой структуры проблемы в компьютерах невозможно использовать классическими методами. Поиск такой скрытой структуры в других представляющих практический интерес проблемах остается важной открытой проблемой. Кроме того, известные квантовые алгоритмы в основном базируются на относительно небольшом количестве квантовых примитивов (таких как квантовое преобразование Фурье и квантовые шаги).
Таким образом, любой квантовый алгоритм может быть выражен как использование квантового преобразования Фурье, перемежающегося с классической обработкой!
Однако интуиция, лежащая в основе описанных выше квантовых алгоритмов, гораздо более разнообразна, чем это можно было бы предположить. Вдохновение для других квантовых алгоритмов, включает: топологическую теорию квантового поля, связи между квантовыми схемами и спиновыми моделями, тестер квантовых бомб и непосредственное решение полуопределенной задачи программирования, характеризующей сложность квантового запроса.
Как и разработка новых квантовых алгоритмов, важным направлением дальнейших исследований кажется разработка нового алгоритма применения квантовых задач. Это, вероятно, потребует значительного вклада со стороны специалистов - практиков в других областях и общения с ними.
