✖


Jump to content

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

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

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

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

Обзор [ править ]

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

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

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

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

Алгоритм Германа-Йожсы [ править ]

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

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

Алгоритм Бернштейна – Вазирани [ править ]

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

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

Алгоритм Саймона [ править ]

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

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

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

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

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

Алгоритм Шора [ править ]

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

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

Проблема скрытой подгруппы [ править ]

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

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

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

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

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

и хотя бы 1/4 удовлетворяют

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

Алгоритмы, основанные на усилении амплитуды [ править ]

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

Алгоритм Гровера [ править ]

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

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

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

Квантовый счёт [ править ]

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

Алгоритмы, основанные на квантовых блужданиях [ править ]

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

Квантовое блуждание — это квантовый аналог классического случайного блуждания . Классическое случайное блуждание можно описать распределением вероятностей по некоторым состояниям, а квантовое блуждание можно описать квантовой суперпозицией состояний. Известно, что квантовые блуждания приводят к экспоненциальному ускорению решения некоторых задач «черного ящика». [19] [20] Они также обеспечивают полиномиальное ускорение для решения многих задач. Фреймворк для создания алгоритмов квантового блуждания существует и является универсальным инструментом. [21]

бозонов Проблема выборки ​

Основная статья: Выборка бозонов

Проблема отбора бозонов в экспериментальной конфигурации предполагает [22] вход бозонов (например, фотонов) умеренного количества, которые случайным образом рассеиваются по большому количеству выходных мод, ограниченных определенной унитарностью . Когда используются отдельные фотоны, проблема изоморфна многофотонному квантовому блужданию. [23] Тогда проблема состоит в том, чтобы получить адекватную выборку распределения вероятностей выходных данных, которое зависит от входного расположения бозонов и унитарности. [24] Решение этой проблемы с помощью классического компьютерного алгоритма требует вычисления перманента матрицы унитарного преобразования, что может занять непомерно много времени или быть совершенно невозможным. В 2014 году было предложено [25] что существующие технологии и стандартные вероятностные методы генерации однофотонных состояний могут быть использованы в качестве входных данных для подходящей квантово-вычислимой линейной оптической сети и что выборка выходного распределения вероятностей будет явно лучше с использованием квантовых алгоритмов. В 2015 году следствие прогнозировало [26] проблема выборки имела аналогичную сложность для входных данных, отличных от фотонов в фоковском состоянии , и выявила переход вычислительной сложности от классически моделируемой к такой же сложной, как проблема выборки бозонов, в зависимости от размера входных когерентных амплитуд.

Проблема различимости элементов [ править ]

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

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

Задача нахождения треугольника [ править ]

Основная статья: Задача нахождения треугольника

Задача поиска треугольника — это задача определения того, содержит ли данный граф треугольник ( клику размера 3). Самая известная нижняя граница для квантовых алгоритмов равна , но лучший известный алгоритм требует O( N 1.297 ) запросы, [31] улучшение по сравнению с предыдущим лучшим O( N 1.3 ) запросы. [21] [32]

Оценка по формуле [ править ]

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

Хорошо изученная формула — это сбалансированное двоичное дерево, состоящее только из вентилей И-НЕ. [33] Этот тип формулы требует запросы, использующие случайность, [34] где . Однако с помощью квантового алгоритма эту задачу можно решить за запросы. Лучшего квантового алгоритма для этого случая не было известно, пока не был найден алгоритм для нетрадиционной гамильтоновой модели оракула. [7] Вскоре последовал тот же результат и для стандартной настройки. [35]

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

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

Проблема состоит в том, чтобы определить, является ли группа черного ящика , заданная k генераторами, коммутативной . Группа черного ящика — это группа с функцией оракула, которую необходимо использовать для выполнения групповых операций (умножение, инверсия и сравнение с тождеством). Интерес в этом контексте заключается в сложности запроса, то есть количестве вызовов оракула, необходимых для решения проблемы. Детерминированные и рандомизированные сложности запросов: и , соответственно. [37] Квантовый алгоритм требует запросы, в то время как самый известный классический алгоритм использует запросы. [38]

Проблемы с BQP [ править ]

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

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

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

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

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

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

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

Решение линейных систем уравнений [ править ]

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

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

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

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

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

КАОА [ править ]

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

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

Алгоритм вариационного квантового собственного решателя (VQE) применяет классическую оптимизацию для минимизации энергетического ожидания анзац-состояния и поиска основного состояния эрмитова оператора, такого как гамильтониан молекулы. [51] Его также можно расширить для поиска возбужденных энергий молекулярных гамильтонианов. [52]

квантовый решатель Сокращенный собственный

Алгоритм сокращенного квантового собственного решателя (CQE) минимизирует остаток от сжатия (или проекции) уравнения Шредингера на пространство двух (или более) электронов, чтобы найти энергию основного или возбужденного состояния и двухэлектронную приведенную матрицу плотности молекула. [53] Он основан на классических методах решения энергий и двухэлектронных приведенных матриц плотности непосредственно из антиэрмитова сжатого уравнения Шредингера. [54]

См. также [ править ]

Ссылки [ править ]

  1. ^ Нильсен, Майкл А .; Чуанг, Исаак Л. (2000). Квантовые вычисления и квантовая информация . Издательство Кембриджского университета . ISBN  978-0-521-63503-5 .
  2. ^ Моска, М. (2008). «Квантовые алгоритмы». arXiv : 0808.0369 [ квант-ph ].
  3. ^ Ланзагорта, Марко; Ульманн, Джеффри К. (1 января 2009 г.). Квантовая информатика . Издательство Морган и Клейпул. ISBN  9781598297324 .
  4. ^ Нильсен, Майкл А .; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (2-е изд.). Кембридж: Издательство Кембриджского университета. ISBN  978-1-107-00217-3 .
  5. ^ «Алгоритм Шора» .
  6. ^ «Руководство пользователя квантового композитора IBM: алгоритм Гровера» . Quantum-Computing.ibm.com . Проверено 7 июня 2022 г.
  7. ^ Jump up to: Перейти обратно: а б Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (2008). «Квантовый алгоритм для гамильтонова дерева NAND» . Теория вычислений . 4 : 169–190. arXiv : Quant-ph/0702144 . дои : 10.4086/toc.2008.v004a008 .
  8. ^ Чайлдс, Эндрю М .; Ван Дам, В. (2010). «Квантовые алгоритмы решения алгебраических задач». Обзоры современной физики . 82 (1): 1–52. arXiv : 0812.0380 . Бибкод : 2010РвМП...82....1С . дои : 10.1103/RevModPhys.82.1 . S2CID   119261679 .
  9. ^ Шор, П.В. (1997). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». Журнал SIAM по научным и статистическим вычислениям . 26 (5): 1484–1509. arXiv : Quant-ph/9508027 . Бибкод : 1995quant.ph..8027S . дои : 10.1137/s0097539795293172 . S2CID   2337707 .
  10. ^ Боне, Д.; Липтон, Р.Дж. (1995). «Квантовый криптоанализ скрытых линейных функций». В Копперсмите, Д. (ред.). Материалы 15-й ежегодной международной конференции по криптологии, посвященной достижениям в криптологии . Спрингер-Верлаг . стр. 424–437. ISBN  3-540-60221-6 .
  11. ^ Мур, К. ; Рассел, А.; Шульман, ЖЖ (2005). «Симметричная группа бросает вызов строгой выборке Фурье: Часть I». arXiv : Quant-ph/0501056 .
  12. ^ Регев, О. (2003). «Квантовые вычисления и проблемы решетки». arXiv : cs/0304005 .
  13. ^ ван Дам, В.; Серусси, Г. (2002). «Эффективные квантовые алгоритмы для оценки сумм Гаусса». arXiv : Quant-ph/0207131 .
  14. ^ Ааронсон, С. (2009). «BQP и полиномиальная иерархия». arXiv : 0910.4698 [ квант-ph ].
  15. ^ Гровер, Лов К. (1996). «Быстрый квантовомеханический алгоритм поиска в базе данных». arXiv : Quant-ph/9605043 .
  16. ^ Ааронсон, Скотт. «Квантовые вычисления и скрытые переменные» (PDF) .
  17. ^ Брассар, Г.; Хойер, П.; Тэпп, А. (1998). «Квантовый счет». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 1443. стр. 820–831. arXiv : Quant-ph/9805082 . дои : 10.1007/BFb0055105 . ISBN  978-3-540-64781-2 . S2CID   14147978 .
  18. ^ Брассар, Г.; Хойер, П.; Моска, М.; Тэпп, А. (2002). «Квантовое амплитудное усиление и оценка». В Сэмюэле Дж. Ломонако-младшем (ред.). Квантовые вычисления и квантовая информация . AMS Современная математика. Том. 305. стр. 53–74. arXiv : Quant-ph/0005055 . Бибкод : 2000quant.ph..5055B . дои : 10.1090/conm/305/05215 . ISBN  9780821821404 . S2CID   54753 .
  19. ^ Чайлдс, AM; Умный.; Деотто, Э.; Фархи, Э.; Гутманн, С.; Спилман, Д.А. (2003). «Экспоненциальное алгоритмическое ускорение за счет квантового блуждания». Материалы 35-го симпозиума по теории вычислений . Ассоциация вычислительной техники . стр. 59–68. arXiv : Quant-ph/0209131 . дои : 10.1145/780542.780552 . ISBN  1-58113-674-9 .
  20. ^ Чайлдс, AM; Шульман, LJ; Вазирани, У.Ф. (2007). «Квантовые алгоритмы для скрытых нелинейных структур». Материалы 48-го ежегодного симпозиума IEEE по основам информатики . ИИЭЭ . стр. 395–404. arXiv : 0705.2784 . дои : 10.1109/FOCS.2007.18 . ISBN  978-0-7695-3010-9 .
  21. ^ Jump up to: Перейти обратно: а б Манье, Ф.; Наяк, А.; Роланд, Дж.; Санта, М. (2007). «Поиск с помощью квантовой прогулки». Материалы 39-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . стр. 575–584. arXiv : Quant-ph/0608026 . дои : 10.1145/1250790.1250874 . ISBN  978-1-59593-631-8 .
  22. ^ Ральф, TC (июль 2013 г.). «Рисунок 1: Проблема выборки бозонов» . Природная фотоника . 7 (7). Природа: 514–515. дои : 10.1038/nphoton.2013.175 . S2CID   110342419 . Проверено 12 сентября 2014 г.
  23. ^ Перуццо, Альберт; Лобино, Меркурий; Мэтьюз, Джонатан CF; Мацуда, Нобуюки; Политика, Альберто; Пулиос, Константин; Чжоу, Сяо-Ци; Лахини, Иоав; Исмаил, Нур; Вёрхофф, Керстин; Бромберг, Ярон; Зильберберг, Ярон; Томпсон, Марк Г.; О'Брайен, Джереми Л. (17 сентября 2010 г.). «Квантовые блуждания коррелированных фотонов» . Наука 329 (5998): 1500–1503. arXiv : 1006.4764 . Бибкод : 2010Наука... 329.1500P дои : 10.1126/science.1193515 . hdl : 10072/53193 . ISSN   0036-8075 . ПМИД   20847264 . S2CID   13896075 .
  24. ^ Лунд, AP; Лэнг, А.; Рахими-Кешари, С.; Рудольф, Т.; О'Брайен, JL; Ральф, TC (5 сентября 2014 г.). «Выборка бозонов из гауссовских состояний». Физ. Преподобный Летт . 113 (10): 100502. arXiv : 1305.4346 . Бибкод : 2014PhRvL.113j0502L . doi : 10.1103/PhysRevLett.113.100502 . ПМИД   25238340 . S2CID   27742471 .
  25. ^ «Квантовая революция — на шаг ближе» . Физика.орг . Омикрон Технолоджи Лимитед . Проверено 12 сентября 2014 г.
  26. ^ Сешадрисан, Кошик П.; Олсон, Джонатан П.; Моутс, Кейт Р.; Роде, Питер П.; Даулинг, Джонатан П. (2015). «Выборка бозонов со смещенными однофотонными состояниями Фока по сравнению с когерентными состояниями с добавлением одиночных фотонов: квантово-классическое разделение и переходы сложности вычислений в линейной оптике». Физический обзор А. 91 (2): 022334. arXiv : 1402.0531 . Бибкод : 2015PhRvA..91b2334S . дои : 10.1103/PhysRevA.91.022334 . S2CID   55455992 .
  27. ^ Амбайнис, А. (2007). «Алгоритм квантового блуждания для различения элементов». SIAM Journal по вычислительной технике . 37 (1): 210–239. arXiv : Quant-ph/0311001 . дои : 10.1137/S0097539705447311 . S2CID   6581885 .
  28. ^ Ши, Ю. (2002). «Квантовые нижние оценки столкновений и проблемы различия элементов». 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы . Материалы 43-го симпозиума по основам информатики . стр. 513–519. arXiv : Quant-ph/0112086 . дои : 10.1109/SFCS.2002.1181975 . ISBN  0-7695-1822-2 .
  29. ^ Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым диапазоном» . Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .
  30. ^ Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном» . Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .
  31. ^ Александр Белов (2011). «Программы Span для функций с 1-сертификатами постоянного размера». arXiv : 1105.4024 [ квант-ph ].
  32. ^ Манье, Ф.; Санта, М.; Сегеди, М. (2007). «Квантовые алгоритмы решения проблемы треугольника». SIAM Journal по вычислительной технике . 37 (2): 413–424. arXiv : Quant-ph/0310134 . дои : 10.1137/050643684 . S2CID   594494 .
  33. ^ Ааронсон, С. (3 февраля 2007 г.). «NAND теперь для чего-то совершенно другого» . Shtetl-Оптимизированный . Проверено 17 декабря 2009 г.
  34. ^ Сакс, Мэн; Вигдерсон, А. (1986). «Вероятностные логические деревья решений и сложность оценки игровых деревьев» (PDF) . Материалы 27-го ежегодного симпозиума по основам информатики . ИИЭЭ . стр. 29–38. дои : 10.1109/SFCS.1986.44 . ISBN  0-8186-0740-8 .
  35. ^ Амбайнис, А. (2007). «Почти оптимальный квантовый алгоритм дискретных запросов для оценки формул NAND». arXiv : 0704.3628 [ квант-ph ].
  36. ^ Райхардт, BW; Спалек, Р. (2008). «Квантовый алгоритм вычисления формул на основе Span-программы». Материалы 40-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . стр. 103–112. arXiv : 0710.2630 . дои : 10.1145/1374376.1374394 . ISBN  978-1-60558-047-0 .
  37. ^ Пак, Игорь (2012). «Проверка коммутативности группы и силы рандомизации» . LMS Журнал вычислений и математики . 15 : 38–43. дои : 10.1112/S1461157012000046 .
  38. ^ Манье, Ф.; Наяк, А. (2007). «Квантовая сложность проверки групповой коммутативности». Алгоритмика . 48 (3): 221–232. arXiv : Quant-ph/0506265 . дои : 10.1007/s00453-007-0057-8 . S2CID   3163328 .
  39. ^ Майкл Нильсен и Исаак Чуанг (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. ISBN   0-521-63503-9 .
  40. ^ Ахаронов Д.; Джонс, В.; Ландау, З. (2006). «Полиномиальный квантовый алгоритм аппроксимации полинома Джонса». Материалы 38-го ежегодного симпозиума ACM по теории вычислений . Ассоциация вычислительной техники . стр. 427–436. arXiv : Quant-ph/0511096 . дои : 10.1145/1132516.1132579 . ISBN  1595931341 .
  41. ^ Фейнман, Р.П. (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6–7): 467–488. Бибкод : 1982IJTP...21..467F . CiteSeerX   10.1.1.45.9310 . дои : 10.1007/BF02650179 . S2CID   124545445 .
  42. ^ Абрамс, Д.С.; Ллойд, С. (1997). «Моделирование ферми-систем многих тел на универсальном квантовом компьютере». Письма о физических отзывах . 79 (13): 2586–2589. arXiv : Quant-ph/9703054 . Бибкод : 1997PhRvL..79.2586A . doi : 10.1103/PhysRevLett.79.2586 . S2CID   18231521 .
  43. ^ Кассал, И.; Джордан, СП; С любовью, Пи Джей; Мохсени, М.; Аспуру-Гузик, А. (2008). «Квантовый алгоритм полиномиального времени для моделирования химической динамики» . Труды Национальной академии наук Соединенных Штатов Америки . 105 (48): 18681–86. arXiv : 0801.2986 . Бибкод : 2008PNAS..10518681K . дои : 10.1073/pnas.0808245105 . ПМЦ   2596249 . ПМИД   19033207 .
  44. ^ Фридман, М.; Китаев А.; Ван, З. (2002). «Моделирование топологических теорий поля с помощью квантовых компьютеров». Связь в математической физике . 227 (3): 587–603. arXiv : Quant-ph/0001071 . Бибкод : 2002CMaPh.227..587F . дои : 10.1007/s002200200635 . S2CID   449219 .
  45. ^ Ахаронов Д.; Джонс, В.; Ландау, З. (2009). «Полиномиальный квантовый алгоритм аппроксимации полинома Джонса». Алгоритмика . 55 (3): 395–421. arXiv : Quant-ph/0511096 . дои : 10.1007/s00453-008-9168-0 . S2CID   7058660 .
  46. ^ Воцян, П.; Ярд, Дж. (2008). «Полином Джонса: квантовые алгоритмы и приложения в квантовой теории сложности». Квантовая информация и вычисления . 8 (1): 147–180. arXiv : Quant-ph/0603069 . Бибкод : 2006quant.ph..3069W . дои : 10.26421/QIC8.1-2-10 . S2CID   14494227 .
  47. ^ Алагич, Г.; Джордан, СП; Кениг, Р.; Райхардт, BW (2010). «Аппроксимация инвариантов трехмерного многообразия Тураева-Виро универсальна для квантовых вычислений». Физический обзор А. 82 (4): 040302. arXiv : 1003.0923 . Бибкод : 2010PhRvA..82d0302A . дои : 10.1103/PhysRevA.82.040302 . S2CID   28281402 .
  48. ^ Харроу, Арам В.; хасидим, Авинатан; Ллойд, Сет (2008). «Квантовый алгоритм решения линейных систем уравнений». Письма о физических отзывах . 103 (15): 150502. arXiv : 0811.3171 . Бибкод : 2009PhRvL.103o0502H . doi : 10.1103/PhysRevLett.103.150502 . ПМИД   19905613 . S2CID   5187993 .
  49. ^ Молл, Николай; Баркуцос, Панайотис; епископ Лев С.; Чоу, Джерри М.; Кросс, Эндрю; Эггер, Дэниел Дж.; Филипп, Стефан; Фюрер Андреас; Гамбетта, Джей М.; Ганцхорн, Марк; Кандала, Абхинав; Меццакапо, Антонио; Мюллер, Питер; Рисс, Уолтер; Салис, Джиан; Смолин, Джон; Тавернелли, Ивано; Темме, Кристан (2018). «Квантовая оптимизация с использованием вариационных алгоритмов на квантовых устройствах ближайшего будущего». Квантовая наука и технология . 3 (3): 030503. arXiv : 1710.01022 . Бибкод : 2018QS&T....3c0503M . дои : 10.1088/2058-9565/aab822 . S2CID   56376912 .
  50. ^ Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (14 ноября 2014 г.). «Квантовый приближенный алгоритм оптимизации». arXiv : 1411.4028 [ квант-ph ].
  51. ^ Перуццо, Альберто; МакКлин, Джаррод; Шедболт, Питер; Юнг, Ман-Хонг; Чжоу, Сяо-Ци; С любовью, Питер Дж.; Аспуру-Гузик, Алан; О'Брайен, Джереми Л. (23 июля 2014 г.). «Вариационный решатель собственных значений фотонного квантового процессора» . Природные коммуникации . 5 (1): 4213. arXiv : 1304.3061 . Бибкод : 2014NatCo...5.4213P . дои : 10.1038/ncomms5213 . ISSN   2041-1723 . ПМЦ   4124861 . ПМИД   25055053 .
  52. ^ Хигготт, Оскар; Ван, Даочэнь; Брирли, Стивен (2019). «Вариационные квантовые вычисления возбужденных состояний». Квантовый . 3 : 156. arXiv : 1805.08138 . Бибкод : 2019Количество...3..156H . doi : 10.22331/кв-2019-07-01-156 . S2CID   119185497 .
  53. ^ Умный, Скотт; Мацциотти, Дэвид (18 февраля 2021 г.). «Квантовый решатель сокращенных уравнений на собственные значения для масштабируемого молекулярного моделирования на квантовых вычислительных устройствах». Физ. Преподобный Летт . 125 (7): 070504. arXiv : 2004.11416 . Бибкод : 2021PhRvL.126g0504S . doi : 10.1103/PhysRevLett.126.070504 . PMID   33666467 . S2CID   216144443 .
  54. ^ Мацциотти, Дэвид (6 октября 2006 г.). «Антиэрмитово сокращенное уравнение Шредингера: прямое определение двухэлектронных приведенных матриц плотности многоэлектронных молекул». Физ. Преподобный Летт . 97 (14): 143002. Бибкод : 2006PhRvL..97n3002M . doi : 10.1103/PhysRevLett.97.143002 . ПМИД   17155245 .

Внешние ссылки [ править ]

Опросы [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Quantum_algorithm&oldid=1221761276"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: f8ab6d3920560da5d3c077c4bc18f1c5__1714586220
URL1:https://arc.ask3.ru/arc/aa/f8/c5/f8ab6d3920560da5d3c077c4bc18f1c5.html
Заголовок, (Title) документа по адресу, URL1:
Quantum algorithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)