Квантовый алгоритм - Quantum algorithm

В квантовые вычисления, а квантовый алгоритм является алгоритм который работает на реалистичной модели квантовые вычисления, наиболее часто используемой моделью является квантовая схема модель вычисления.[1][2] Классический (или неквантовый) алгоритм - это конечная последовательность инструкций или пошаговая процедура решения проблемы, в которой каждый шаг или инструкция может выполняться на классическом компьютер. Точно так же квантовый алгоритм - это пошаговая процедура, в которой каждый шаг может быть выполнен на квантовый компьютер. Хотя все классические алгоритмы также могут выполняться на квантовом компьютере,[3]:126 термин квантовый алгоритм обычно используется для тех алгоритмов, которые кажутся по своей сути квантовыми, или используют некоторые существенные особенности квантовых вычислений, такие как квантовая суперпозиция или квантовая запутанность.

Проблемы, которые неразрешимый использование классических компьютеров остается неразрешимым с помощью квантовых компьютеров.[4]:127 Что делает квантовые алгоритмы интересными, так это то, что они могут решать некоторые проблемы быстрее, чем классические алгоритмы, потому что квантовая суперпозиция и квантовая запутанность, которые используют квантовые алгоритмы, вероятно, не могут быть эффективно смоделированы на классических компьютерах (см. Квантовое превосходство ).

Наиболее известные алгоритмы: Алгоритм Шора для факторинга и Алгоритм Гровера для поиска в неструктурированной базе данных или неупорядоченном списке. Алгоритмы Шора работают намного (почти экспоненциально) быстрее, чем самый известный классический алгоритм факторизации, общее числовое поле сито.[5] Алгоритм Гровера работает квадратично быстрее, чем лучший из возможных классический алгоритм для той же задачи,[нужна цитата ] а линейный поиск.

Обзор

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

Квантовые алгоритмы можно разделить на категории по основным методам, используемым в алгоритме. Некоторые часто используемые методы / идеи в квантовых алгоритмах включают: фазовый откат, оценка фазы, то квантовое преобразование Фурье, квантовые прогулки, усиление амплитуды и топологическая квантовая теория поля. Квантовые алгоритмы также могут быть сгруппированы по типу решаемой проблемы, например, см. Обзор квантовых алгоритмов для алгебраических задач.[7]

Алгоритмы на основе квантового преобразования Фурье

В квантовое преобразование Фурье квантовый аналог дискретное преобразование Фурье, и используется в нескольких квантовых алгоритмах. В Преобразование Адамара также является примером квантового преобразования Фурье над n-мерным векторным пространством над полем F2. Квантовое преобразование Фурье может быть эффективно реализовано на квантовом компьютере, используя только полиномиальное число квантовые ворота.[нужна цитата ]

Алгоритм Дойча – Йожи

Основная статья: Алгоритм Дойча – Йожи

Алгоритм Дойча – Йожи решает черный ящик Проблема, которая, вероятно, требует экспоненциально большого числа запросов к черному ящику для любого детерминированного классического компьютера, но может быть решена с помощью ровно одного запроса на квантовом компьютере. Если мы разрешаем как квантовые алгоритмы с ограниченной ошибкой, так и классические алгоритмы, то ускорения не будет, поскольку классический вероятностный алгоритм может решить проблему с постоянным числом запросов с малой вероятностью ошибки. Алгоритм определяет, ж является либо постоянным (0 на всех входах, либо 1 на всех входах), либо сбалансированным (возвращает 1 для половины входной области и 0 для другой половины).

Алгоритм Бернштейна – Вазирани

Основная статья: Алгоритм Бернштейна – Вазирани

Алгоритм Бернштейна – Вазирани - это первый квантовый алгоритм, который решает проблему более эффективно, чем самый известный классический алгоритм. Он был разработан для создания разделение оракула между BQP и BPP.

Алгоритм Саймона

Основная статья: Алгоритм Саймона

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

Алгоритм квантовой оценки фазы

Основная статья: Алгоритм квантовой оценки фазы

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

Алгоритм Шора

Основная статья: Алгоритм Шора

Алгоритм Шора решает дискретный логарифм проблема и целочисленная факторизация задача за полиномиальное время,[8] тогда как самые известные классические алгоритмы занимают суперполиномиальное время. Эти проблемы неизвестны п или НП-полный. Это также один из немногих квантовых алгоритмов, который решает проблему не-черного ящика за полиномиальное время, тогда как наиболее известные классические алгоритмы выполняются за суперполиномиальное время.

Проблема скрытой подгруппы

В абелевский проблема скрытой подгруппы является обобщением многих проблем, которые могут быть решены с помощью квантового компьютера, таких как проблема Саймона, решая Уравнение Пелла, тестирование главный идеал из кольцо R и факторинг. Для решения проблемы скрытых абелевых подгрупп известны эффективные квантовые алгоритмы.[9] Более общая проблема скрытой подгруппы, когда группа не обязательно абелева, является обобщением ранее упомянутых проблем и изоморфизм графов и некоторые проблемы решетки. Для некоторых неабелевых групп известны эффективные квантовые алгоритмы. Однако эффективных алгоритмов для симметричная группа, что даст эффективный алгоритм изоморфизма графов[10] и группа диэдра, что решило бы некоторые задачи решетки.[11]

Проблема взятия проб бозона

Основная статья: Отбор проб бозона

Проблема отбора проб бозона в экспериментальной конфигурации предполагает[12] ввод бозоны (например, фотоны света) умеренного количества случайным образом рассеиваются на большое количество выходных мод, ограниченных определенным унитарность. Тогда проблема состоит в том, чтобы получить точную выборку распределение вероятностей выхода, который зависит от входного расположения бозонов и Унитарности.[13] Решение этой проблемы с помощью классического компьютерного алгоритма требует вычисления постоянный матрицы унитарного преобразования, что может быть либо невозможно, либо занять чрезмерно долгое время. В 2014 году было предложено[14] что существующие технологии и стандартные вероятностные методы генерации однофотонных состояний могут быть использованы в качестве входных данных в подходящую квантово-вычислимую линейная оптическая сеть и что выборка выходного распределения вероятностей будет явно лучше при использовании квантовых алгоритмов. В 2015 году расследование предсказало[15] проблема выборки имела аналогичную сложность для входных данных, кроме Состояние Фока фотонов и идентифицировали переход в вычислительная сложность от классической моделируемой до такой же сложной, как проблема дискретизации бозона, в зависимости от размера входных сигналов когерентной амплитуды.

Оценка сумм Гаусса

А Сумма Гаусса это тип экспоненциальная сумма. Самый известный классический алгоритм оценки этих сумм занимает экспоненциальное время. Поскольку проблема дискретного логарифмирования сводится к оценке суммы Гаусса, эффективный классический алгоритм для оценки сумм Гаусса предполагает эффективный классический алгоритм для вычисления дискретных логарифмов, что считается маловероятным. Однако квантовые компьютеры могут оценивать суммы Гаусса с полиномиальной точностью за полиномиальное время.[16]

Фурье-рыбалка и проверка Фурье

У нас есть оракул состоящий из n случайных логических функций, отображающих n-битные строки в логическое значение. Нам нужно найти n n-битных строк z1, ..., zп такое, что для преобразования Адамара-Фурье по крайней мере 3/4 строк удовлетворяют

и по крайней мере 1/4 удовлетворяет

Это можно сделать в квантово-полиномиальное время с ограниченной ошибкой (BQP).[17]

Алгоритмы на основе амплитудного усиления

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

Алгоритм Гровера

Основная статья: Алгоритм Гровера

Алгоритм Гровера ищет в неструктурированной базе данных (или неупорядоченном списке) с N записями отмеченную запись, используя только запросы вместо запросы требуются классически.[18] Классически запросы требуются даже при использовании вероятностных алгоритмов с ограниченной ошибкой.

Теоретики рассмотрели гипотетическое обобщение стандартного квантового компьютера, который мог бы получить доступ к истории скрытых переменных в Бомовская механика. (Такой компьютер полностью гипотетичен и будет не быть стандартным квантовым компьютером или даже возможным в рамках стандартной теории квантовой механики.) Такой гипотетический компьютер мог бы реализовать поиск в базе данных из N элементов не более чем в шаги. Это немного быстрее, чем шаги, предпринятые Алгоритм Гровера. Ни один из методов поиска не позволил бы ни одной модели квантового компьютера решить НП-полный задачи за полиномиальное время.[19]

Квантовый счет

Квантовый счет решает обобщение задачи поиска. Он решает проблему подсчета количества отмеченных записей в неупорядоченном списке, вместо того, чтобы просто определять, существует ли он. В частности, он подсчитывает количество отмеченных записей в -элементный список с ошибкой только изготовление запросы, где - количество отмеченных элементов в списке.[20][21] Точнее, алгоритм выдает оценку для , количество отмеченных записей со следующей точностью: .

Алгоритмы на основе квантовых блужданий

Основная статья: Квантовая прогулка

Квантовое блуждание - это квантовый аналог классического случайная прогулка, который можно описать распределение вероятностей по некоторым штатам. Квантовую прогулку можно описать квантовая суперпозиция по штатам. Квантовые прогулки, как известно, дают экспоненциальное ускорение для некоторых задач черного ящика.[22][23] Они также обеспечивают полиномиальное ускорение для многих задач. Фреймворк для создания алгоритмов квантового блуждания существует и представляет собой довольно универсальный инструмент.[24]

Проблема отличимости элементов

Основная статья: Проблема отличимости элементов

Проблема отличимости элементов - это проблема определения, все ли элементы списка различны. Классически Ω (N) запросы необходимы для списка размера N. Однако ее можно решить в запросы на квантовом компьютере. Оптимальный алгоритм: Андрис Амбайнис.[25] Яоюнь Ши впервые доказал жесткую нижнюю границу, когда размер диапазона достаточно велик.[26] Амбаинис[27] и Кутин[28] независимо (и с помощью различных доказательств) расширил свою работу, чтобы получить нижнюю оценку для всех функций.

Задача поиска треугольника

Основная статья: Проблема поиска треугольника

Проблема поиска треугольника - это проблема определения, содержит ли данный граф треугольник ( клика размера 3). Самая известная нижняя оценка квантовых алгоритмов - это Ω (N), но лучший из известных алгоритмов требует O (N1.297) запросы,[29] улучшение по сравнению с предыдущим лучшим O (N1.3) запросы.[24][30]

Формула оценки

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

Хорошо изученной формулой является сбалансированное двоичное дерево только с вентилями NAND.[31] Формула этого типа требует Θ (Nc) запросы с использованием случайности,[32] где . Однако с помощью квантового алгоритма ее можно решить за Θ (N0.5) запросы. Лучшего квантового алгоритма для этого случая не было, пока он не был найден для нетрадиционной гамильтоновой модели оракула.[6] Вскоре последовал тот же результат для стандартных настроек.[33]

Известны также быстрые квантовые алгоритмы для более сложных формул.[34]

Групповая коммутативность

Проблема состоит в том, чтобы определить, группа черного ящика, данный k генераторы, это коммутативный. Группа черного ящика - это группа с функцией оракула, которая должна использоваться для выполнения групповых операций (умножения, инверсии и сравнения с идентичностью). Нас интересует сложность запроса, то есть количество вызовов оракула, необходимых для решения проблемы. Сложности детерминированного и рандомизированного запроса и соответственно.[35] Квантовый алгоритм требует запросы, но самый известный алгоритм использует запросы.[36]

BQP-Complete проблемы

В класс сложности BQP (квантово-полиномиальное время с ограниченной ошибкой) - это набор проблемы решения решаемый квантовый компьютер в полиномиальное время с вероятностью ошибки не более 1/3 для всех экземпляров.[37] Это квантовый аналог классического класса сложности. BPP.

Проблема в том BQP-полный, если он в BQP и любая проблема в BQP может быть уменьшенный к нему в полиномиальное время. Неформально класс BQP-полные задачи - это те, которые сложнее самых сложных в BQP и сами эффективно решаются квантовым компьютером (с ограниченной ошибкой).

Вычисление инвариантов узлов

Виттен показал, что Черн-Симонс топологическая квантовая теория поля (TQFT) можно решить в терминах Полиномы Джонса. Квантовый компьютер может моделировать TQFT и, таким образом, аппроксимировать полином Джонса,[38] что, насколько нам известно, трудно вычислить классическим способом в худшем случае.[нужна цитата ]

Квантовое моделирование

Идея о том, что квантовые компьютеры могут быть более мощными, чем классические, возникла из наблюдения Ричарда Фейнмана о том, что классическим компьютерам, похоже, требуется экспоненциальное время для моделирования многочастичных квантовых систем.[39] С тех пор идея о том, что квантовые компьютеры могут моделировать квантовые физические процессы экспоненциально быстрее, чем классические компьютеры, была значительно переработана и переработана. Эффективные (т.е. полиномиальные) квантовые алгоритмы были разработаны для моделирования как бозонных, так и фермионных систем.[40] и, в частности, для моделирования химических реакций, выходящих за рамки возможностей современных классических суперкомпьютеров, требуется всего несколько сотен кубитов.[41] Квантовые компьютеры также могут эффективно моделировать топологические квантовые теории поля.[42] В дополнение к собственному интересу этот результат привел к созданию эффективных квантовых алгоритмов для оценки квантовые топологические инварианты такие как Джонс[43] и Полиномы ХОМФЛИ,[44] и Инвариант Тураева-Виро трехмерных многообразий.[45]

Решение линейной системы уравнений

Основная статья: Квантовый алгоритм для линейных систем уравнений

В 2009 Арам Харроу, Авинатан Хасидим и Сет Ллойд, сформулировал квантовый алгоритм решения линейные системы. В алгоритм оценивает результат скалярного измерения вектора решения данной линейной системы уравнений.[46]

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

Гибридные квантовые / классические алгоритмы

Гибридные квантовые / классические алгоритмы сочетают подготовку и измерение квантового состояния с классической оптимизацией.[47] Эти алгоритмы обычно нацелены на определение собственного вектора основного состояния и собственного значения эрмитова оператора.

QAOA

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

Вариационный квантовый собственный преобразователь

Алгоритм VQE применяет классическую оптимизацию, чтобы минимизировать ожидаемую энергию состояние анзаца чтобы найти энергию основного состояния молекулы.[49] Это также можно расширить, чтобы найти возбужденные энергии молекул.[50]

Смотрите также

использованная литература

  1. ^ Нильсен, Майкл А.; Чуанг, Исаак Л. (2000). Квантовые вычисления и квантовая информация. Издательство Кембриджского университета. ISBN  978-0-521-63503-5.
  2. ^ Моска, М. (2008). «Квантовые алгоритмы». arXiv:0808.0369 [Quant-ph ].
  3. ^ Ланзагорта, Марко; Ульманн, Джеффри К. (1 января 2009 г.). Квантовая информатика. Издатели Morgan & Claypool. ISBN  9781598297324.
  4. ^ Нильсен, Майкл А.; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN  978-1-107-00217-3.
  5. ^ https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm
  6. ^ а б Farhi, E .; Goldstone, J .; Гутманн, С. (2007). «Квантовый алгоритм для гамильтонова дерева НЕ-НЕ». arXiv:Quant-ph / 0702144.
  7. ^ Чайлдс, Эндрю М.; ван Дам, В. (2010). «Квантовые алгоритмы для алгебраических задач». Обзоры современной физики. 82 (1): 1–52. arXiv:0812.0380. Bibcode:2010РвМП ... 82 .... 1С. Дои:10.1103 / RevModPhys.82.1. S2CID  119261679.
  8. ^ Шор, П. В. (1997). "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере". Журнал SIAM по научным и статистическим вычислениям. 26 (5): 1484–1509. arXiv:Quant-ph / 9508027. Bibcode:1995квант.ч..8027S. Дои:10.1137 / s0097539795293172. S2CID  2337707.
  9. ^ Boneh, D .; Липтон, Р. Дж. (1995). «Квантовый криптоанализ скрытых линейных функций». В Копперсмит, Д. (ред.). Труды 15-й Ежегодной Международной конференции по криптологии по достижениям криптологии. Springer-Verlag. С. 424–437. ISBN  3-540-60221-6.
  10. ^ Мур, К.; Russell, A .; Шульман, Л. Дж. (2005). «Симметричная группа не поддается строгой выборке Фурье: Часть I». arXiv:Quant-ph / 0501056.
  11. ^ Регев, О. (2003). «Квантовые вычисления и решеточные задачи». arXiv:cs / 0304005.
  12. ^ Ральф, Т. "Рисунок 1: Проблема отбора проб бозонов". Природа Фотоника. Природа. Получено 12 сентября 2014.
  13. ^ Lund, A.P .; Laing, A .; Рахими-Кешари, С .; Рудольф, Т .; O'Brien, J.L .; Ральф, Т. (5 сентября 2014 г.). «Отбор проб бозонов из гауссовских состояний». Phys. Rev. Lett. 113 (10): 100502. arXiv:1305.4346. Bibcode:2014PhRvL.113j0502L. Дои:10.1103 / PhysRevLett.113.100502. PMID  25238340. S2CID  27742471.
  14. ^ «Квантовая революция - на шаг ближе». Phys.org. Omicron Technology Limited. Получено 12 сентября 2014.
  15. ^ Seshadreesan, Kaushik P .; Олсон, Джонатан П .; Motes, Keith R .; Роде, Питер П .; Доулинг, Джонатан П. (2015). «Выборка бозона со смещенными однофотонными состояниями Фока по сравнению с когерентными состояниями с добавлением однофотонов: квантово-классическое разделение и переходы вычислительной сложности в линейной оптике». Физический обзор A. 91 (2): 022334. arXiv:1402.0531. Bibcode:2015PhRvA..91b2334S. Дои:10.1103 / PhysRevA.91.022334. S2CID  55455992.
  16. ^ van Dam, W .; Серусси, Г. (2002). «Эффективные квантовые алгоритмы для оценки гауссовых сумм». arXiv:Quant-ph / 0207131.
  17. ^ Ааронсон, С. (2009). «BQP и полиномиальная иерархия». arXiv:0910.4698 [Quant-ph ].
  18. ^ Гровер, Лов К. (1996). «Быстрый квантово-механический алгоритм поиска по базам данных». arXiv:Quant-ph / 9605043.
  19. ^ Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF).
  20. ^ Brassard, G .; Hoyer, P .; Тэпп, А. (1998). Квантовый счет. Конспект лекций по информатике. 1443. С. 820–831. arXiv:Quant-ph / 9805082. Дои:10.1007 / BFb0055105. ISBN  978-3-540-64781-2. S2CID  14147978.
  21. ^ Brassard, G .; Hoyer, P .; Моска, М .; Тэпп, А. (2002). «Квантовое амплитудное усиление и оценка». В Сэмюэле Дж. Ломонако младшем (ред.). Квантовые вычисления и квантовая информация. AMS Contemporary Mathematics. 305. С. 53–74. arXiv:Quant-ph / 0005055. Bibcode:2000квант.ч..5055B.
  22. ^ Чайлдс, А. М .; Умный.; Deotto, E .; Farhi, E .; Gutmann, S .; Спилман, Д. А. (2003). «Экспоненциальное алгоритмическое ускорение квантовым блужданием». Материалы 35-го симпозиума по теории вычислений.. Ассоциация вычислительной техники. С. 59–68. arXiv:Quant-ph / 0209131. Дои:10.1145/780542.780552. ISBN  1-58113-674-9.
  23. ^ Чайлдс, А. М .; Schulman, L.J .; Вазирани, У. В. (2007). «Квантовые алгоритмы для скрытых нелинейных структур». Материалы 48-го ежегодного симпозиума IEEE по основам информатики. IEEE. С. 395–404. arXiv:0705.2784. Дои:10.1109 / FOCS.2007.18. ISBN  978-0-7695-3010-9.
  24. ^ а б Magniez, F .; Nayak, A .; Roland, J .; Сантха, М. (2007). «Поиск через квантовую прогулку». Материалы 39-го ежегодного симпозиума ACM по теории вычислений. Ассоциация вычислительной техники. С. 575–584. arXiv:Quant-ph / 0608026. Дои:10.1145/1250790.1250874. ISBN  978-1-59593-631-8.
  25. ^ Амбайнис, А. (2007). «Алгоритм квантового блуждания для определения различимости элементов». SIAM Журнал по вычислениям. 37 (1): 210–239. arXiv:Quant-ph / 0311001. Дои:10.1137 / S0097539705447311. S2CID  6581885.
  26. ^ Ши, Ю. (2002). Квантовые нижние оценки проблемы столкновения и различимости элементов. Материалы 43-го Симпозиум по основам информатики. С. 513–519. arXiv:Quant-ph / 0112086. Дои:10.1109 / SFCS.2002.1181975.
  27. ^ Амбайнис, А. (2005). «Полиномиальная степень и нижние границы квантовой сложности: столкновение и различимость элементов с малым радиусом действия». Теория вычислений. 1 (1): 37–46. Дои:10.4086 / toc.2005.v001a003.
  28. ^ Кутин, С. (2005). «Квантовая нижняя граница для проблемы столкновений с малым радиусом действия». Теория вычислений. 1 (1): 29–36. Дои:10.4086 / toc.2005.v001a002.
  29. ^ Александр Беловс (2011). «Программы Span для функций с постоянным размером 1-сертификатов». arXiv:1105.4024 [Quant-ph ].
  30. ^ Magniez, F .; Santha, M .; Сегеди, М. (2007). «Квантовые алгоритмы для задачи треугольника». SIAM Журнал по вычислениям. 37 (2): 413–424. arXiv:Quant-ph / 0310134. Дои:10.1137/050643684. S2CID  594494.
  31. ^ Ааронсон, С. (3 февраля 2007 г.). «NAND теперь для чего-то совершенно другого». Штетл-Оптимизированный. Получено 17 декабря 2009.
  32. ^ Saks, M.E .; Вигдерсон, А. (1986). "Вероятностные булевы деревья решений и сложность оценки игровых деревьев" (PDF). Материалы 27-го ежегодного симпозиума по основам информатики. IEEE. С. 29–38. Дои:10.1109 / SFCS.1986.44. ISBN  0-8186-0740-8.
  33. ^ Амбайнис, А. (2007). «Практически оптимальный дискретный квантовый алгоритм запроса для вычисления формул NAND». arXiv:0704.3628 [Quant-ph ].
  34. ^ Reichardt, B.W .; Спалек, Р. (2008). «Квантовый алгоритм вычисления формул на основе Span-программы». Материалы 40-го ежегодного симпозиума ACM по теории вычислений. Ассоциация вычислительной техники. С. 103–112. arXiv:0710.2630. Дои:10.1145/1374376.1374394. ISBN  978-1-60558-047-0.
  35. ^ Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации». Журнал вычислений и математики LMS. 15: 38–43. Дои:10.1112 / S1461157012000046.
  36. ^ Magniez, F .; Наяк, А. (2007). «Квантовая сложность проверки групповой коммутативности». Алгоритмика. 48 (3): 221–232. arXiv:Quant-ph / 0506265. Дои:10.1007 / s00453-007-0057-8. S2CID  3163328.
  37. ^ Майкл Нильсен и Исаак Чуанг (2000). Квантовые вычисления и квантовая информация. Кембридж: Издательство Кембриджского университета. ISBN  0-521-63503-9.
  38. ^ Ааронов, Д .; Джонс, В .; Ландау, З. (2006). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». Материалы 38-го ежегодного симпозиума ACM по теории вычислений. Ассоциация вычислительной техники. С. 427–436. arXiv:Quant-ph / 0511096. Дои:10.1145/1132516.1132579.
  39. ^ Фейнман, Р. П. (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики. 21 (6–7): 467–488. Bibcode:1982IJTP ... 21..467F. CiteSeerX  10.1.1.45.9310. Дои:10.1007 / BF02650179. S2CID  124545445.
  40. ^ Abrams, D. S .; Ллойд, С. (1997). «Моделирование многочастичных ферми-систем на универсальном квантовом компьютере». Письма с физическими проверками. 79 (13): 2586–2589. arXiv:Quant-ph / 9703054. Bibcode:1997ПхРвЛ..79.2586А. Дои:10.1103 / PhysRevLett.79.2586. S2CID  18231521.
  41. ^ Kassal, I .; Jordan, S.P .; Любовь, П. Дж .; Мохсени, М .; Аспуру-Гузик, А. (2008). «Полиномиальный квантовый алгоритм для моделирования химической динамики». Труды Национальной академии наук Соединенных Штатов Америки. 105 (48): 18681–86. arXiv:0801.2986. Bibcode:2008PNAS..10518681K. Дои:10.1073 / pnas.0808245105. ЧВК  2596249. PMID  19033207.
  42. ^ Freedman, M .; Китаев, А .; Ван, З. (2002). "Моделирование топологических теорий поля на квантовых компьютерах". Коммуникации по математической физике. 227 (3): 587–603. arXiv:Quant-ph / 0001071. Bibcode:2002CMaPh.227..587F. Дои:10.1007 / s002200200635. S2CID  449219.
  43. ^ Ааронов, Д .; Джонс, В .; Ландау, З. (2009). «Полиномиальный квантовый алгоритм для аппроксимации полинома Джонса». Алгоритмика. 55 (3): 395–421. arXiv:Quant-ph / 0511096. Дои:10.1007 / s00453-008-9168-0. S2CID  7058660.
  44. ^ Wocjan, P .; Ярд, Дж. (2008). «Полином Джонса: квантовые алгоритмы и приложения в квантовой теории сложности». Квантовая информация и вычисления. 8 (1): 147–180. arXiv:Quant-ph / 0603069. Bibcode:2006квант.ч..3069Вт.
  45. ^ Alagic, G .; Jordan, S.P .; König, R .; Райхард, Б. В. (2010). «Аппроксимация инвариантов трехмерного многообразия Тураева-Виро универсальна для квантовых вычислений». Физический обзор A. 82 (4): 040302. arXiv:1003.0923. Bibcode:2010PhRvA..82d0302A. Дои:10.1103 / PhysRevA.82.040302. S2CID  28281402.
  46. ^ Харроу, Арам В; Хасидим, Авинатан; Ллойд, Сет (2008). «Квантовый алгоритм решения линейных систем уравнений». Письма с физическими проверками. 103 (15): 150502. arXiv:0811.3171. Bibcode:2009PhRvL.103o0502H. Дои:10.1103 / PhysRevLett.103.150502. PMID  19905613. S2CID  5187993.
  47. ^ Молл, Николай; Баркуцос, Панайотис; Епископ Лев С .; Чоу, Джерри М .; Крест, Андрей; Эггер, Дэниел Дж .; Филипп, Стефан; Фюрер Андреас; Гамбетта, Джей М .; Ганжорн, Марк; Кандала, Абхинав; Меццакапо, Антонио; Мюллер, Питер; Рис, Уолтер; Салис, Джиан; Смолин, Джон; Тавернелли, Ивано; Темме, Кристан (2018). «Квантовая оптимизация с использованием вариационных алгоритмов на краткосрочных квантовых устройствах». Квантовая наука и технологии. 3 (3): 030503. arXiv:1710.01022. Дои:10.1088 / 2058-9565 / aab822. S2CID  56376912.
  48. ^ Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (14 ноября 2014 г.). «Квантовый приближенный алгоритм оптимизации». arXiv:1411.4028 [Quant-ph ].
  49. ^ Перуццо, Альберто; Макклин, Джаррод; Шедболт, Питер; Юнг, Ман-Хонг; Чжоу, Сяо-Ци; С любовью, Питер Дж .; Аспуру-Гузик, Алан; О’Брайен, Джереми Л. (23 июля 2014 г.). "Вариационный решатель собственных значений на фотонном квантовом процессоре". Nature Communications. 5 (1): 4213. arXiv:1304.3061. Bibcode:2014НатКо ... 5Э4213П. Дои:10.1038 / ncomms5213. ISSN  2041-1723. ЧВК  4124861. PMID  25055053.
  50. ^ Хигготт, Оскар; Ван, Даочэнь; Бриерли, Стивен (2019). «Вариационный квантовый расчет возбужденных состояний». Квантовая. 3: 156. arXiv:1805.08138. Дои:10.22331 / q-2019-07-01-156. S2CID  119185497.

внешние ссылки

Обзоры