Квантовые вычисления - Quantum computing

IBM Q System One (2019), первый коммерческий квантовый компьютер на основе схем

Квантовые вычисления - это тип вычислений, который использует коллективные свойства квантовых состояний, такие как суперпозиция , интерференция и запутанность , для выполнения вычислений. Устройства, выполняющие квантовые вычисления, известны как квантовые компьютеры . Считается, что они способны решать определенные вычислительные задачи , такие как целочисленная факторизация (которая лежит в основе шифрования RSA ), значительно быстрее, чем классические компьютеры. Изучение квантовых вычислений - это одна из областей квантовой информатики . Расширение ожидается в ближайшие несколько лет, поскольку область смещается в сторону реального использования в фармацевтике, защите данных и других приложениях.

Квантовые вычисления начались в 1980 году, когда физик Пол Бениофф предложил квантово-механическую модель машины ТьюрингаРичард Фейнман  и  Юрий Манин  позже предположили, что квантовый компьютер может моделировать то, что классический компьютер не может сделать. В 1994 году Питер Шор разработал квантовый алгоритм разложения целых чисел на множители, способный расшифровать данные, зашифрованные RSA . Несмотря на продолжающийся экспериментальный прогресс с конца 1990-х годов, большинство исследователей считают, что « отказоустойчивые квантовые вычисления [являются] все еще довольно далекой мечтой». В последние годы инвестиции в исследования квантовых вычислений увеличились в государственном и частном секторах. 23 октября 2019 года Google AI в партнерстве с Национальным управлением США по аэронавтике и исследованию космического пространства ( НАСА ) заявил, что выполнил квантовые вычисления, которые невозможно было выполнить на любом классическом компьютере , но было ли это утверждение справедливым или до сих пор остается предметом обсуждения. активные исследования.

Существует несколько типов квантовых компьютеров (также известных как квантовые вычислительные системы), включая модель квантовой схемы , квантовую машину Тьюринга , адиабатический квантовый компьютер , односторонний квантовый компьютер и различные квантовые клеточные автоматы . Наиболее широко используемой моделью является квантовая схема , основанная на квантовом бите или « кубите », который в некоторой степени аналогичен биту в классических вычислениях. Кубит может находиться в квантовом состоянии 1 или 0 или в суперпозиции состояний 1 и 0. Однако при измерении он всегда равен 0 или 1; вероятность либо результат , зависит от квантового состояния кубитов непосредственно перед измерением.

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

Любая вычислительная задача, которую может решить классический компьютер, также может быть решена с помощью квантового компьютера. И наоборот, любая проблема, которую может решить квантовый компьютер, может быть решена и классическим компьютером, по крайней мере, в принципе, при наличии достаточного времени. Другими словами, квантовые компьютеры подчиняются тезису Чёрча – Тьюринга . Это означает, что, хотя квантовые компьютеры не обеспечивают дополнительных преимуществ перед классическими компьютерами с точки зрения вычислимости , квантовые алгоритмы для определенных задач имеют значительно меньшую временную сложность, чем соответствующие известные классические алгоритмы. Примечательно, что квантовые компьютеры, как полагают, способны быстро решать определенные проблемы, которые ни один классический компьютер не мог решить за любой возможный промежуток времени - подвиг, известный как «квантовое превосходство». Изучение вычислительной сложности задач применительно к квантовым компьютерам известно как квантовая теория сложности .

Квантовая схема

Сфера Блох является представление кубита , основной строительный блок квантовых компьютеров.

Определение

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

Память, состоящая из битов информации, имеет возможные состояния. Таким образом, вектор, представляющий все состояния памяти, имеет записи (по одной для каждого состояния). Этот вектор рассматривается как вектор вероятности и представляет тот факт, что память должна быть найдена в определенном состоянии.

В классическом представлении одна запись будет иметь значение 1 (т.е. 100% вероятность нахождения в этом состоянии), а все остальные записи будут нулевыми. В квантовой механике векторы вероятности могут быть обобщены на операторы плотности . Формализм вектора квантового состояния обычно вводится первым, потому что он концептуально проще и потому, что его можно использовать вместо формализма матрицы плотности для чистых состояний, когда известна вся квантовая система.

Начнем с рассмотрения простой памяти, состоящей только из одного бита. Эта память может находиться в одном из двух состояний: нулевом или единичном. Мы можем представить состояние этой памяти, используя нотацию Дирака, так что

Тогда квантовую память можно найти в любой квантовой суперпозиции двух классических состояний и :
В общем, коэффициенты и являются комплексными числами . В этом сценарии считается, что один кубит информации закодирован в квантовой памяти. Состояние само по себе не является вектором вероятности, но может быть связано с вектором вероятности посредством операции измерения. Если квантовая память измеряется, чтобы определить, является ли состояние или (это известно как измерение вычислительной базы), нулевое состояние будет наблюдаться с вероятностью, а единичное состояние - с вероятностью . Числа и называются квантовыми амплитудами .

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

Математически применение такого логического элемента к вектору квантового состояния моделируется умножением матриц . Таким образом и .

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

Затем вентиль CNOT может быть представлен с помощью следующей матрицы:
В качестве математического вследствие этого определения , , и . Другими словами, CNOT применяет вентиль НЕ ( из предыдущего) ко второму кубиту тогда и только тогда, когда первый кубит находится в состоянии . Если первый кубит есть , ни с одним из кубитов ничего не делается.

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

Любое квантовое вычисление (которое в приведенном выше формализме представляет собой любую унитарную матрицу над кубитами) может быть представлено как сеть квантовых логических вентилей из довольно небольшого семейства вентилей. Выбор семейства вентилей, обеспечивающий такую ​​конструкцию, известен как

универсальный набор вентилей , поскольку компьютер, который может запускать такие схемы, является универсальным квантовым компьютером . Один общий такой набор включает в себя все однокубитовые вентили, а также вентиль CNOT сверху. Это означает, что любое квантовое вычисление может быть выполнено путем выполнения последовательности однокубитных вентилей вместе с вентилями CNOT. Хотя этот набор вентилей бесконечен, его можно заменить конечным множеством вентилей, обратившись к теореме Соловая-Китаева .

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

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

Квантовые алгоритмы, которые предлагают более чем полиномиальное ускорение по сравнению с наиболее известным классическим алгоритмом, включают алгоритм Шора для факторизации и связанные квантовые алгоритмы для вычисления дискретных логарифмов , решения уравнения Пелла и , в более общем плане, решения проблемы скрытых подгрупп для абелевых конечных групп. Эти алгоритмы зависят от примитива квантового преобразования Фурье . Не было найдено никаких математических доказательств, показывающих, что такой же быстрый классический алгоритм не может быть обнаружен, хотя это считается маловероятным. Некоторые проблемы оракула , как проблема Саймона и проблемы Бернштейна Вазирани действительно дают доказуемые ускорений, хотя это в модели квантового запроса , который является ограниченной моделью , в которой нижние границах гораздо проще доказать , и не обязательно приводят к ускорениям для практических задач .

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

Некоторые квантовые алгоритмы, такие как алгоритм Гровера и усиление амплитуды , дают полиномиальное ускорение по сравнению с соответствующими классическими алгоритмами. Хотя эти алгоритмы дают сравнительно скромное квадратичное ускорение, они широко применяются и, таким образом, дают ускорение для широкого круга задач. Многие примеры доказуемого квантового ускорения для задач запросов связаны с алгоритмом Гровера, включая алгоритм Брассарда, Хёйера и Таппа для поиска коллизий в функциях два к одному, который использует алгоритм Гровера, и алгоритм Фархи, Голдстоуна и Гутмана для оценки NAND. деревья, что является вариантом задачи поиска.

Возможные приложения

Криптография

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

открытым ключом , считается вычислительно невыполнимой с обычным компьютером для больших целых чисел, если они являются произведением нескольких простых чисел (например, произведения двух 300-значных простых чисел). Для сравнения: квантовый компьютер мог бы эффективно решить эту проблему, используя алгоритм Шора, чтобы найти ее факторы. Эта способность позволила бы квантовому компьютеру взломать многие криптографические системы, используемые сегодня, в том смысле, что для решения проблемы существовал бы алгоритм с полиномиальным временем (в количестве цифр целого числа). В частности, большинство популярных шифров с открытым ключом основаны на сложности факторизации целых чисел или проблеме дискретного логарифмирования , которые могут быть решены с помощью алгоритма Шора. В частности, могут быть нарушены алгоритмы RSA , Диффи – Хеллмана и Эллиптической кривой Диффи – Хеллмана . Они используются для защиты защищенных веб-страниц, зашифрованной электронной почты и многих других типов данных. Их нарушение может иметь серьезные последствия для электронной конфиденциальности и безопасности.

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

скрытой диэдральной подгруппы , который сломал бы многие криптосистемы на основе решеток, является хорошо изученной открытой проблемой. Было доказано, что применение алгоритма Гровера для взлома симметричного (секретного ключа) алгоритма грубой силой требует времени, равного примерно 2 n / 2 вызовов базового криптографического алгоритма, по сравнению с примерно 2 n в классическом случае, что означает, что симметричный ключ длины фактически уменьшаются вдвое: AES-256 будет иметь такую ​​же защиту от атак с использованием алгоритма Гровера, что и AES-128 против классического поиска методом перебора (см. Размер ключа ).

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

Проблемы с поиском

Самый известный пример проблемы, допускающей полиномиальное квантовое ускорение, - это неструктурированный поиск , поиск отмеченного элемента из списка элементов в базе данных. Эту проблему можно решить с помощью алгоритма Гровера, используя запросы к базе данных, количество которых в квадратическом порядке меньше, чем количество запросов, требуемых для классических алгоритмов. В этом случае преимущество не только доказуемо, но и оптимально: было показано, что алгоритм Гровера дает максимально возможную вероятность нахождения искомого элемента для любого числа поисков оракула.

Проблемы, которые можно решить с помощью алгоритма Гровера, обладают следующими свойствами:

  1. В коллекции возможных ответов нет структуры с возможностью поиска,
  2. Количество возможных ответов для проверки совпадает с количеством входов в алгоритм, и
  3. Существует логическая функция, которая оценивает каждый ввод и определяет, является ли это правильным ответом.

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

Моделирование квантовых систем

Поскольку химия и нанотехнология полагаются на понимание квантовых систем, а такие системы невозможно эффективно смоделировать классическим способом, многие считают, что квантовое моделирование будет одним из наиболее важных приложений квантовых вычислений. Квантовое моделирование можно также использовать для моделирования поведения атомов и частиц в необычных условиях, таких как реакции внутри коллайдера . Квантовое моделирование может быть использовано для предсказания будущих траекторий частиц и протонов при суперпозиции в эксперименте с двумя щелями . Около 2% годовой мировой выработки энергии используется для фиксации азота для производства аммиака для процесса Габера в производстве сельскохозяйственных удобрений, в то время как естественные организмы также производят аммиак. Чтобы понять, как этот процесс увеличивает производство, можно использовать квантовое моделирование.

Квантовый отжиг и адиабатическая оптимизация

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

Машинное обучение

Поскольку квантовые компьютеры могут производить выходные данные, которые классические компьютеры не могут производить эффективно, и поскольку квантовые вычисления в основе своей являются линейно-алгебраическими, некоторые выражают надежду на разработку квантовых алгоритмов, которые могут ускорить задачи машинного обучения. Например, считается , что квантовый алгоритм для линейных систем уравнений или «алгоритм HHL», названный в честь его первооткрывателей Харроу, Хассидима и Ллойда, обеспечивает ускорение по сравнению с классическими аналогами. Некоторые исследовательские группы недавно исследовали использование оборудования квантового отжига для обучения машин Больцмана и глубоких нейронных сетей .

Вычислительная биология

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

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

Модели глубокой генеративной химии становятся мощным инструментом для ускорения открытия лекарств. Однако огромный размер и сложность структурного пространства всех возможных молекул, подобных лекарствам, создают значительные препятствия, которые в будущем могут быть преодолены с помощью квантовых компьютеров. Квантовые компьютеры, естественно, хороши для решения сложных квантовых задач многих тел и, таким образом, могут быть полезны в приложениях, связанных с квантовой химией. Следовательно, можно ожидать, что генеративные модели с квантовым усилением, включая квантовые GAN, могут в конечном итоге быть развиты в окончательные алгоритмы генеративной химии. Гибридные архитектуры, сочетающие квантовые компьютеры с глубокими классическими сетями, такие как квантово-вариационные автоэнкодеры, уже можно обучить на коммерчески доступных отжигателях и использовать для создания новых молекулярных структур, подобных лекарствам.

Квантовое превосходство

Джон Прескилл ввел термин « квантовое превосходство» для обозначения гипотетического преимущества в ускорении, которое квантовый компьютер имел бы перед классическим компьютером в определенной области. В 2017 году Google объявил, что к концу года рассчитывает достичь квантового превосходства, однако этого не произошло. В 2018 году IBM заявила, что лучшие классические компьютеры будут побеждены в некоторых практических задачах в течение примерно пяти лет, и рассматривает тест квантового превосходства только как потенциальный будущий эталон. Хотя скептики, такие как Гил Калаи, сомневаются в том, что квантовое превосходство когда-либо будет достигнуто, в октябре 2019 года сообщалось , что процессор Sycamore, созданный совместно с Google AI Quantum, достиг квантового превосходства, с расчетами более чем в 3000000 раз быстрее, чем у Summit , как правило. считается самым быстрым компьютером в мире. В декабре 2020 года группа в USTC реализовала тип отбора проб бозона на 76 фотонах с помощью фотонного квантового компьютера Jiuzhang, чтобы продемонстрировать квантовое превосходство. Авторы утверждают, что классическому современному суперкомпьютеру потребуется вычислительное время в 600 миллионов лет, чтобы сгенерировать количество отсчетов, которое их квантовый процессор может сгенерировать за 20 секунд. Билл Унру сомневался в практичности квантовых компьютеров в статье, опубликованной еще в 1994 году. Пол Дэвис утверждал, что компьютер с 400 кубитами даже вступит в конфликт с космологической информацией, связанной с голографическим принципом .

Препятствия

При создании крупномасштабного квантового компьютера возникает ряд технических проблем. Физик Дэвид Ди Винченцо перечислил эти требования к практическому квантовому компьютеру:

  • Физически масштабируемый для увеличения количества кубитов
  • Кубиты, которые можно инициализировать произвольными значениями
  • Квантовые ворота, которые быстрее времени декогеренции
  • Универсальный комплект ворот
  • Кубиты, которые легко читаются

Также очень сложно закупить запчасти для квантовых компьютеров. Многим квантовым компьютерам, например созданным Google и IBM , нужен гелий-3 , побочный продукт ядерных исследований, и специальные сверхпроводящие кабели, производимые только японской компанией Coax Co.

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

Квантовая декогеренция

Одна из величайших проблем, связанных с созданием квантовых компьютеров, - это контроль или устранение квантовой декогеренции . Обычно это означает изоляцию системы от окружающей среды, поскольку взаимодействие с внешним миром приводит к декогеренции системы. Однако существуют и другие источники декогеренции. Примеры включают квантовые вентили, колебания решетки и фоновый термоядерный спин физической системы, используемой для реализации кубитов. Декогеренция необратима, поскольку фактически не является унитарной, и обычно это то, что следует строго контролировать, если не избегать. Время декогеренции для систем-кандидатов, в частности время поперечной релаксации T 2 (для технологии ЯМР и МРТ , также называемое временем дефазировки ), обычно находится в диапазоне от наносекунд до секунд при низкой температуре. В настоящее время некоторые квантовые компьютеры требуют охлаждения своих кубитов до 20 милликельвинов, чтобы предотвратить значительную декогеренцию. В исследовании 2020 года утверждается, что ионизирующее излучение, такое как космические лучи, тем не менее может вызвать декогеренцию определенных систем в течение миллисекунд.

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

Эти проблемы более сложны для оптических подходов, поскольку временные рамки на порядки короче, и часто упоминаемым подходом к их преодолению является формирование оптического импульса . Частота ошибок обычно пропорциональна отношению времени работы к времени декогеренции, поэтому любая операция должна выполняться намного быстрее, чем время декогеренции.

Как описано в квантовой теореме о пороге , если частота ошибок достаточно мала, считается возможным использовать квантовую коррекцию ошибок для подавления ошибок и декогеренции. Это позволяет общему времени вычислений быть больше времени декогеренции, если схема исправления ошибок может исправлять ошибки быстрее, чем их вносит декогеренция. Часто цитируемая цифра для требуемой частоты ошибок в каждом логическом элементе для отказоустойчивых вычислений составляет 10 −3 , предполагая, что шум деполяризующий.

Выполнение этого условия масштабируемости возможно для широкого спектра систем. Однако использование исправления ошибок приводит к значительному увеличению количества требуемых кубитов. Число, необходимое для факторизации целых чисел с использованием алгоритма Шора, по-прежнему является полиномиальным, и считается, что оно находится между L и L 2 , где L - количество цифр в числе, подлежащем разложению; алгоритмы коррекции ошибок будут раздувать эту цифру на дополнительном факторе L . Для 1000-битного числа это означает необходимость около 10 4 бит без исправления ошибок. С исправлением ошибок цифра увеличится примерно до 10 7 бит. Время вычислений составляет около L 2 или приблизительно 10 7 шагов и на частоте 1 МГц, около 10 секунд.

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

Физик Михаил Дьяконов выразил скептическое отношение к квантовым вычислениям следующим образом:

«Таким образом, количество непрерывных параметров, описывающих состояние такого полезного квантового компьютера в любой данный момент, должно быть ... около 10 300 ... Сможем ли мы когда-нибудь научиться управлять более чем 10 300 непрерывно изменяемыми параметрами, определяющими квантовое состояние такая система? Мой ответ прост. Нет, никогда ".

Разработки

Квантовые вычислительные модели

Существует ряд моделей квантовых вычислений, отличающихся базовыми элементами, в которых вычисление декомпозировано. Четыре основные модели, имеющие практическое значение:

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

Физические реализации

Для физической реализации квантового компьютера ищется множество различных кандидатов, среди которых (различаются физической системой, используемой для реализации кубитов):

Большое количество кандидатов демонстрирует, что квантовые вычисления, несмотря на быстрый прогресс, все еще находятся в зачаточном состоянии.

Отношение к теории вычислимости и сложности

Теория вычислимости

Любая вычислительная задача, решаемая классическим компьютером, также решается квантовым компьютером. Интуитивно это связано с тем, что считается, что все физические явления, включая работу классических компьютеров, можно описать с помощью квантовой механики , которая лежит в основе работы квантовых компьютеров.

И наоборот, любая задача, решаемая с помощью квантового компьютера, также может быть решена с помощью классического компьютера; или, более формально, любой квантовый компьютер можно смоделировать с помощью машины Тьюринга . Другими словами, квантовые компьютеры не предоставляют дополнительных возможностей по сравнению с классическими компьютерами с точки зрения вычислимости . Это означает, что квантовые компьютеры не могут решить неразрешимые проблемы, такие как проблема остановки, и существование квантовых компьютеров не опровергает тезис Черча – Тьюринга .

Пока что квантовые компьютеры не удовлетворяют сильному тезису Черча . Хотя гипотетические машины были реализованы, универсальный квантовый компьютер еще не был построен физически. Для сильной версии тезиса Чёрча требуется физический компьютер, и поэтому нет квантового компьютера, который бы удовлетворял сильному тезису Чёрча.

Квантовая теория сложности

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

Класс задач, которые могут быть эффективно решены квантовым компьютером с ограниченной ошибкой, называется BQP , что означает «ограниченная ошибка, квантовое, полиномиальное время». Более формально, BQP - это класс задач, которые могут быть решены с помощью квантовой машины Тьюринга с полиномиальным временем с вероятностью ошибки не более 1/3. Как класс вероятностных задач, BQP является квантовым аналогом BPP («ограниченная ошибка, вероятностное, полиномиальное время»), класса задач, которые могут быть решены с помощью вероятностных машин Тьюринга с полиномиальным временем и ограниченной ошибкой. Известно, что BPP BQP и многие подозревают, что BQP BPP, что интуитивно означало бы, что квантовые компьютеры более мощные, чем классические компьютеры, с точки зрения временной сложности.

Предполагаемая связь BQP с несколькими классическими классами сложности.

Точная связь BQP с P , NP и PSPACE неизвестна. Однако известно, что P BQP PSPACE; то есть все проблемы, которые могут быть эффективно решены с помощью детерминированного классического компьютера, также могут быть эффективно решены с помощью квантового компьютера, и все проблемы, которые могут быть эффективно решены с помощью квантового компьютера, также могут быть решены с помощью детерминированного классического компьютера с полиномиальными пространственными ресурсами. . Кроме того, предполагается, что BQP является строгим надмножеством P, что означает, что есть проблемы, которые эффективно решаются квантовыми компьютерами, но не решаются с помощью детерминированных классических компьютеров. Например, известно, что целочисленная факторизация и проблема дискретного логарифмирования находятся в BQP и предположительно находятся за пределами P. P также находятся в BQP (например, целочисленная факторизация и задача дискретного логарифмирования находятся в NP). Есть подозрение, что НП BQP; то есть считается, что существуют эффективно проверяемые проблемы, которые не могут эффективно решить квантовый компьютер. Как прямое следствие этого убеждения, также предполагается, что BQP не пересекается с классом NP-полных задач (если NP-полная проблема была в BQP, то из NP- сложности следовало бы, что все проблемы в NP находятся в BQP).

Связь BQP с базовыми классическими классами сложности можно резюмировать следующим образом:

Также известно, что BQP содержится в классе сложности #P (или, точнее, в ассоциированном классе задач решения P #P ), который является подклассом PSPACE .

Было высказано предположение, что дальнейшие достижения в области физики могут привести к созданию еще более быстрых компьютеров. Например, было показано, что нелокальный квантовый компьютер со скрытыми переменными, основанный на Бомовской механике, может реализовать поиск в базе данных -элементов не более чем за несколько шагов, что является небольшим ускорением по сравнению с алгоритмом Гровера , который выполняется поэтапно. Обратите внимание, однако, что ни один из методов поиска не позволит квантовым компьютерам решать NP-полные задачи за полиномиальное время. Теории квантовой гравитации , такие как М-теория и петлевая квантовая гравитация , могут позволить построить еще более быстрые компьютеры. Однако определение вычислений в этих теориях - открытая проблема из-за проблемы времени ; то есть в рамках этих физических теорий в настоящее время не существует очевидного способа описать, что означает для наблюдателя представить ввод в компьютер в один момент времени, а затем получить вывод в более поздний момент времени.

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

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

дальнейшее чтение

Учебники

Академические работы

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

Лекции