Квантовые вычисления - Quantum computing
Квантовые вычисления - это тип вычислений, который использует коллективные свойства квантовых состояний, такие как суперпозиция , интерференция и запутанность , для выполнения вычислений. Устройства, выполняющие квантовые вычисления, известны как квантовые компьютеры . Считается, что они способны решать определенные вычислительные задачи , такие как целочисленная факторизация (которая лежит в основе шифрования RSA ), значительно быстрее, чем классические компьютеры. Изучение квантовых вычислений - это одна из областей квантовой информатики . Расширение ожидается в ближайшие несколько лет, поскольку область смещается в сторону реального использования в фармацевтике, защите данных и других приложениях.
Квантовые вычисления начались в 1980 году, когда физик Пол Бениофф предложил квантово-механическую модель машины Тьюринга . Ричард Фейнман и Юрий Манин позже предположили, что квантовый компьютер может моделировать то, что классический компьютер не может сделать. В 1994 году Питер Шор разработал квантовый алгоритм разложения целых чисел на множители, способный расшифровать данные, зашифрованные RSA . Несмотря на продолжающийся экспериментальный прогресс с конца 1990-х годов, большинство исследователей считают, что « отказоустойчивые квантовые вычисления [являются] все еще довольно далекой мечтой». В последние годы инвестиции в исследования квантовых вычислений увеличились в государственном и частном секторах. 23 октября 2019 года Google AI в партнерстве с Национальным управлением США по аэронавтике и исследованию космического пространства ( НАСА ) заявил, что выполнил квантовые вычисления, которые невозможно было выполнить на любом классическом компьютере , но было ли это утверждение справедливым или до сих пор остается предметом обсуждения. активные исследования.
Существует несколько типов квантовых компьютеров (также известных как квантовые вычислительные системы), включая модель квантовой схемы , квантовую машину Тьюринга , адиабатический квантовый компьютер , односторонний квантовый компьютер и различные квантовые клеточные автоматы . Наиболее широко используемой моделью является квантовая схема , основанная на квантовом бите или « кубите », который в некоторой степени аналогичен биту в классических вычислениях. Кубит может находиться в квантовом состоянии 1 или 0 или в суперпозиции состояний 1 и 0. Однако при измерении он всегда равен 0 или 1; вероятность либо результат , зависит от квантового состояния кубитов непосредственно перед измерением.
Усилия по созданию физического квантового компьютера сосредоточены на таких технологиях, как трансмоны , ионные ловушки и топологические квантовые компьютеры , целью которых является создание высококачественных кубитов. Эти кубиты могут быть спроектированы по-разному, в зависимости от вычислительной модели полного квантового компьютера, будь то квантовые логические вентили , квантовый отжиг или адиабатические квантовые вычисления . В настоящее время существует ряд серьезных препятствий для создания полезных квантовых компьютеров. Особенно сложно поддерживать квантовые состояния кубитов, поскольку они страдают от квантовой декогеренции и точности состояний . Поэтому квантовые компьютеры требуют исправления ошибок .
Любая вычислительная задача, которую может решить классический компьютер, также может быть решена с помощью квантового компьютера. И наоборот, любая проблема, которую может решить квантовый компьютер, может быть решена и классическим компьютером, по крайней мере, в принципе, при наличии достаточного времени. Другими словами, квантовые компьютеры подчиняются тезису Чёрча – Тьюринга . Это означает, что, хотя квантовые компьютеры не обеспечивают дополнительных преимуществ перед классическими компьютерами с точки зрения вычислимости , квантовые алгоритмы для определенных задач имеют значительно меньшую временную сложность, чем соответствующие известные классические алгоритмы. Примечательно, что квантовые компьютеры, как полагают, способны быстро решать определенные проблемы, которые ни один классический компьютер не мог решить за любой возможный промежуток времени - подвиг, известный как «квантовое превосходство». Изучение вычислительной сложности задач применительно к квантовым компьютерам известно как квантовая теория сложности .
Квантовая схема
Определение
Преобладающая модель квантовых вычислений описывает вычисления в терминах сети квантовых логических вентилей . Эту модель можно рассматривать как абстрактное линейно-алгебраическое обобщение классической схемы . Поскольку эта схемная модель подчиняется квантовой механике , считается, что квантовый компьютер, способный эффективно управлять этими схемами, физически реализуем.
Память, состоящая из битов информации, имеет возможные состояния. Таким образом, вектор, представляющий все состояния памяти, имеет записи (по одной для каждого состояния). Этот вектор рассматривается как вектор вероятности и представляет тот факт, что память должна быть найдена в определенном состоянии.
В классическом представлении одна запись будет иметь значение 1 (т.е. 100% вероятность нахождения в этом состоянии), а все остальные записи будут нулевыми. В квантовой механике векторы вероятности могут быть обобщены на операторы плотности . Формализм вектора квантового состояния обычно вводится первым, потому что он концептуально проще и потому, что его можно использовать вместо формализма матрицы плотности для чистых состояний, когда известна вся квантовая система.
Начнем с рассмотрения простой памяти, состоящей только из одного бита. Эта память может находиться в одном из двух состояний: нулевом или единичном. Мы можем представить состояние этой памяти, используя нотацию Дирака, так что
Состоянием этой однокубитовой квантовой памяти можно управлять, применяя квантовые логические вентили , аналогично тому, как классической памятью можно манипулировать с помощью классических логических вентилей . Одним из важных ворот как для классических, так и для квантовых вычислений является вентиль НЕ, который может быть представлен матрицей
Математика вентилей с одним кубитом может быть расширена для работы с квантовой памятью с несколькими кубитами двумя важными способами. Один из способов - просто выбрать кубит и применить этот вентиль к целевому кубиту, не затрагивая остальную часть памяти. Другой способ - применить вентиль к его цели, только если другая часть памяти находится в желаемом состоянии. Эти два варианта можно проиллюстрировать на другом примере. Возможные состояния двухкубитной квантовой памяти:
Таким образом, квантовые вычисления можно описать как сеть квантовых логических вентилей и измерений. Однако любое измерение можно отложить до конца квантовых вычислений, хотя эта отсрочка может быть связана с вычислительными затратами, поэтому большинство квантовых схем изображают сеть, состоящую только из квантовых логических вентилей и никаких измерений.
Любое квантовое вычисление (которое в приведенном выше формализме представляет собой любую унитарную матрицу над кубитами) может быть представлено как сеть квантовых логических вентилей из довольно небольшого семейства вентилей. Выбор семейства вентилей, обеспечивающий такую конструкцию, известен как
универсальный набор вентилей , поскольку компьютер, который может запускать такие схемы, является универсальным квантовым компьютером . Один общий такой набор включает в себя все однокубитовые вентили, а также вентиль CNOT сверху. Это означает, что любое квантовое вычисление может быть выполнено путем выполнения последовательности однокубитных вентилей вместе с вентилями CNOT. Хотя этот набор вентилей бесконечен, его можно заменить конечным множеством вентилей, обратившись к теореме Соловая-Китаева .Квантовые алгоритмы
Прогресс в поиске квантовых алгоритмов обычно сосредоточен на этой модели квантовой схемы, хотя существуют исключения, такие как квантовый адиабатический алгоритм . Квантовые алгоритмы можно грубо разделить на категории по типу ускорения, достигаемого по сравнению с соответствующими классическими алгоритмами.
Квантовые алгоритмы, которые предлагают более чем полиномиальное ускорение по сравнению с наиболее известным классическим алгоритмом, включают алгоритм Шора для факторизации и связанные квантовые алгоритмы для вычисления дискретных логарифмов , решения уравнения Пелла и , в более общем плане, решения проблемы скрытых подгрупп для абелевых конечных групп. Эти алгоритмы зависят от примитива квантового преобразования Фурье . Не было найдено никаких математических доказательств, показывающих, что такой же быстрый классический алгоритм не может быть обнаружен, хотя это считается маловероятным. Некоторые проблемы оракула , как проблема Саймона и проблемы Бернштейна Вазирани действительно дают доказуемые ускорений, хотя это в модели квантового запроса , который является ограниченной моделью , в которой нижние границах гораздо проще доказать , и не обязательно приводят к ускорениям для практических задач .
Другие задачи, включая моделирование квантовых физических процессов из химии и физики твердого тела, приближение некоторых полиномов Джонса и квантовый алгоритм для линейных систем уравнений, имеют квантовые алгоритмы, которые дают суперполиномиальное ускорение и являются BQP- полными. Поскольку эти задачи являются BQP-полными, такой же быстрый классический алгоритм для них означал бы, что ни один квантовый алгоритм не дает сверхполиномиального ускорения, что считается маловероятным.
Некоторые квантовые алгоритмы, такие как алгоритм Гровера и усиление амплитуды , дают полиномиальное ускорение по сравнению с соответствующими классическими алгоритмами. Хотя эти алгоритмы дают сравнительно скромное квадратичное ускорение, они широко применяются и, таким образом, дают ускорение для широкого круга задач. Многие примеры доказуемого квантового ускорения для задач запросов связаны с алгоритмом Гровера, включая алгоритм Брассарда, Хёйера и Таппа для поиска коллизий в функциях два к одному, который использует алгоритм Гровера, и алгоритм Фархи, Голдстоуна и Гутмана для оценки NAND. деревья, что является вариантом задачи поиска.
Возможные приложения
Криптография
Заметным применением квантовых вычислений являются атаки на криптографические системы, которые используются в настоящее время. Целочисленная факторизация , которая лежит в основе безопасности криптографических систем с
открытым ключом , считается вычислительно невыполнимой с обычным компьютером для больших целых чисел, если они являются произведением нескольких простых чисел (например, произведения двух 300-значных простых чисел). Для сравнения: квантовый компьютер мог бы эффективно решить эту проблему, используя алгоритм Шора, чтобы найти ее факторы. Эта способность позволила бы квантовому компьютеру взломать многие криптографические системы, используемые сегодня, в том смысле, что для решения проблемы существовал бы алгоритм с полиномиальным временем (в количестве цифр целого числа). В частности, большинство популярных шифров с открытым ключом основаны на сложности факторизации целых чисел или проблеме дискретного логарифмирования , которые могут быть решены с помощью алгоритма Шора. В частности, могут быть нарушены алгоритмы RSA , Диффи – Хеллмана и Эллиптической кривой Диффи – Хеллмана . Они используются для защиты защищенных веб-страниц, зашифрованной электронной почты и многих других типов данных. Их нарушение может иметь серьезные последствия для электронной конфиденциальности и безопасности.Идентификация криптографических систем, которые могут быть защищены от квантовых алгоритмов, является активно исследуемой темой в области постквантовой криптографии . Некоторые алгоритмы с открытым ключом основаны на задачах, отличных от задач целочисленной факторизации и дискретного логарифмирования, к которым применяется алгоритм Шора, например криптосистема Мак-Элиса, основанная на проблеме теории кодирования . Криптосистемы на основе решеток также не могут быть взломаны квантовыми компьютерами, и поиск алгоритма с полиномиальным временем для решения проблемы
скрытой диэдральной подгруппы , который сломал бы многие криптосистемы на основе решеток, является хорошо изученной открытой проблемой. Было доказано, что применение алгоритма Гровера для взлома симметричного (секретного ключа) алгоритма грубой силой требует времени, равного примерно 2 n / 2 вызовов базового криптографического алгоритма, по сравнению с примерно 2 n в классическом случае, что означает, что симметричный ключ длины фактически уменьшаются вдвое: AES-256 будет иметь такую же защиту от атак с использованием алгоритма Гровера, что и AES-128 против классического поиска методом перебора (см. Размер ключа ).Квантовая криптография потенциально может выполнять некоторые функции криптографии с открытым ключом. Следовательно, квантовые криптографические системы могут быть более безопасными, чем традиционные системы, от квантового взлома.
Проблемы с поиском
Самый известный пример проблемы, допускающей полиномиальное квантовое ускорение, - это неструктурированный поиск , поиск отмеченного элемента из списка элементов в базе данных. Эту проблему можно решить с помощью алгоритма Гровера, используя запросы к базе данных, количество которых в квадратическом порядке меньше, чем количество запросов, требуемых для классических алгоритмов. В этом случае преимущество не только доказуемо, но и оптимально: было показано, что алгоритм Гровера дает максимально возможную вероятность нахождения искомого элемента для любого числа поисков оракула.
Проблемы, которые можно решить с помощью алгоритма Гровера, обладают следующими свойствами:
- В коллекции возможных ответов нет структуры с возможностью поиска,
- Количество возможных ответов для проверки совпадает с количеством входов в алгоритм, и
- Существует логическая функция, которая оценивает каждый ввод и определяет, является ли это правильным ответом.
Для задач со всеми этими свойствами время работы алгоритма Гровера на квантовом компьютере масштабируется как квадратный корень из числа входных данных (или элементов в базе данных), в отличие от линейного масштабирования классических алгоритмов. Общий класс проблем, к которым может быть применен алгоритм Гровера, - это проблема логической выполнимости , где база данных, по которой алгоритм выполняет итерацию, представляет собой базу всех возможных ответов. Пример и (возможное) применение этого - взломщик паролей, который пытается угадать пароль. Симметричные шифры, такие как 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 непрерывно изменяемыми параметрами, определяющими квантовое состояние такая система? Мой ответ прост. Нет, никогда ".
Разработки
Квантовые вычислительные модели
Существует ряд моделей квантовых вычислений, отличающихся базовыми элементами, в которых вычисление декомпозировано. Четыре основные модели, имеющие практическое значение:
- Массив квантовых вентилей (вычисление разложено на последовательность квантовых вентилей по несколько кубитов )
- Односторонний квантовый компьютер (вычисление разложено на последовательность однокубитных измерений, применяемых к сильно запутанному начальному состоянию или состоянию кластера )
- Адиабатический квантовый компьютер , основанный на квантовом отжиге (вычисление разложено на медленное непрерывное преобразование начального гамильтониана в конечный гамильтониан, основные состояния которого содержат решение)
- Топологический квантовый компьютер (вычисление, разложенное на сплетение анионов в двумерной решетке)
Квантовая машина Тьюринга теоретически важна , но физическая реализация этой модели не представляется возможным. Было показано, что все четыре модели вычислений эквивалентны; каждый из них может имитировать другой с не более чем полиномиальными накладными расходами.
Физические реализации
Для физической реализации квантового компьютера ищется множество различных кандидатов, среди которых (различаются физической системой, используемой для реализации кубитов):
- Сверхпроводящие квантовые вычисления (кубит, реализованный состоянием малых сверхпроводящих цепей [ переходы Джозефсона ])
- Квантовый компьютер с захваченными ионами (кубит реализуется внутренним состоянием захваченных ионов)
- Нейтральные атомы в оптических решетках (кубит, реализованный внутренними состояниями нейтральных атомов, заключенных в оптическую решетку)
- Квантовая точка компьютер, спин на основе (например, Loss-DiVincenzo квантовый компьютер ) (кубит дается спиновых состояний захваченных электронов)
- Компьютер с квантовыми точками, пространственно-ориентированный (кубит задается положением электрона в двойной квантовой точке)
- Квантовые вычисления с использованием искусственно созданных квантовых ям, которые в принципе могут позволить создавать квантовые компьютеры, работающие при комнатной температуре.
- Связанный квантовый провод (кубит, реализованный парой квантовых проводов, соединенных квантовым точечным контактом )
- Квантовый компьютер ядерного магнитного резонанса (NMRQC), реализованный с помощью ядерного магнитного резонанса молекул в растворе, где кубиты создаются ядерными спинами внутри растворенной молекулы и исследуются с помощью радиоволн.
- Твердотельные ЯМР квантовые компьютеры Кейна (кубит, реализованный ядерным спиновым состоянием доноров фосфора в кремнии )
- Квантовые компьютеры электронов на гелии (кубит - спин электрона)
- Квантовая электродинамика резонатора (CQED) (кубит, обеспечиваемый внутренним состоянием захваченных атомов, связанных с высокоточными резонаторами)
- Молекулярный магнит (кубит, заданный спиновыми состояниями)
- Квантовый компьютер ESR на основе фуллеренов (кубит, основанный на электронном спине атомов или молекул, заключенных в фуллерены )
- Нелинейно-оптический квантовый компьютер (кубиты, реализованные путем обработки состояний различных мод света с помощью как линейных, так и нелинейных элементов)
- Линейный оптический квантовый компьютер (кубиты, реализованные путем обработки состояний различных мод света с помощью линейных элементов, например зеркал, светоделителей и фазовращателей )
- Квантовый компьютер на основе алмаза (кубит, реализованный посредством электронного или ядерного спина азотно-вакансионных центров в алмазе)
- Квантовый компьютер на основе конденсата Бозе-Эйнштейна
- Квантовый компьютер на основе транзисторов - струнные квантовые компьютеры с захватом положительных дырок с помощью электростатической ловушки
- Квантовые компьютеры на основе неорганических кристаллов, легированных ионами редкоземельных металлов (кубит, реализуемый внутренним электронным состоянием легирующих примесей в оптических волокнах )
- Металлические квантовые компьютеры на основе углеродных наносфер
Большое количество кандидатов демонстрирует, что квантовые вычисления, несмотря на быстрый прогресс, все еще находятся в зачаточном состоянии.
Отношение к теории вычислимости и сложности
Теория вычислимости
Любая вычислительная задача, решаемая классическим компьютером, также решается квантовым компьютером. Интуитивно это связано с тем, что считается, что все физические явления, включая работу классических компьютеров, можно описать с помощью квантовой механики , которая лежит в основе работы квантовых компьютеров.
И наоборот, любая задача, решаемая с помощью квантового компьютера, также может быть решена с помощью классического компьютера; или, более формально, любой квантовый компьютер можно смоделировать с помощью машины Тьюринга . Другими словами, квантовые компьютеры не предоставляют дополнительных возможностей по сравнению с классическими компьютерами с точки зрения вычислимости . Это означает, что квантовые компьютеры не могут решить неразрешимые проблемы, такие как проблема остановки, и существование квантовых компьютеров не опровергает тезис Черча – Тьюринга .
Пока что квантовые компьютеры не удовлетворяют сильному тезису Черча . Хотя гипотетические машины были реализованы, универсальный квантовый компьютер еще не был построен физически. Для сильной версии тезиса Чёрча требуется физический компьютер, и поэтому нет квантового компьютера, который бы удовлетворял сильному тезису Чёрча.
Квантовая теория сложности
Хотя квантовые компьютеры не могут решить какие-либо проблемы, которые классические компьютеры уже не могут решить, есть подозрение, что они могут решать определенные проблемы быстрее, чем классические компьютеры. Например, известно, что квантовые компьютеры могут эффективно определять множители целых чисел , в то время как для классических компьютеров это не так.
Класс задач, которые могут быть эффективно решены квантовым компьютером с ограниченной ошибкой, называется BQP , что означает «ограниченная ошибка, квантовое, полиномиальное время». Более формально, BQP - это класс задач, которые могут быть решены с помощью квантовой машины Тьюринга с полиномиальным временем с вероятностью ошибки не более 1/3. Как класс вероятностных задач, BQP является квантовым аналогом BPP («ограниченная ошибка, вероятностное, полиномиальное время»), класса задач, которые могут быть решены с помощью вероятностных машин Тьюринга с полиномиальным временем и ограниченной ошибкой. Известно, что BPP BQP и многие подозревают, что BQP BPP, что интуитивно означало бы, что квантовые компьютеры более мощные, чем классические компьютеры, с точки зрения временной сложности.
Точная связь 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-полные задачи за полиномиальное время. Теории квантовой гравитации , такие как М-теория и петлевая квантовая гравитация , могут позволить построить еще более быстрые компьютеры. Однако определение вычислений в этих теориях - открытая проблема из-за проблемы времени ; то есть в рамках этих физических теорий в настоящее время не существует очевидного способа описать, что означает для наблюдателя представить ввод в компьютер в один момент времени, а затем получить вывод в более поздний момент времени.
Смотрите также
- Химический компьютер
- Системы D-Wave
- ДНК-вычисления
- Электронная квантовая голография
- Деятельность в области перспективных исследовательских проектов разведки
- Квантовый компьютер Кейна
- Список новых технологий
- Список квантовых процессоров
- Магическая государственная дистилляция
- Естественные вычисления
- Фотонные вычисления
- Постквантовая криптография
- Квантовый алгоритм
- Квантовый отжиг
- Квантовый автобус
- Квантовое познание
- Квантовая схема
- Квантовая теория сложности
- Квантовая криптография
- Квантовый логический вентиль
- Квантовое машинное обучение
- Квантовое превосходство
- Квантовая пороговая теорема
- Квантовый объем
- Rigetti Computing
- Суперкомпьютер
- Суперпозиция
- Теоретическая информатика
- Хронология квантовых вычислений
- Топологический квантовый компьютер
- Valleytronics
использованная литература
дальнейшее чтение
Учебники
- Нильсен, Майкл ; Чуанг, Исаак (2000). Квантовые вычисления и квантовая информация . Кембридж: Издательство Кембриджского университета. ISBN 978-0-521-63503-5. OCLC 174527496 .
- Мермин, Н. Дэвид (2007). Квантовая информатика: введение . Издательство Кембриджского университета. ISBN 978-0-521-87658-2.
- Акама, Сэйки (2014). Элементы квантовых вычислений: история, теории и инженерные приложения . Издательство Springer International. ISBN 978-3-319-08284-4.
- Бененти, Джулиано (2004). Принципы квантовых вычислений и информация Том 1 . Нью-Джерси: World Scientific. ISBN 978-981-238-830-8. OCLC 179950736 .
- Штольце, Иоахим; Сутер, Дитер (2004). Квантовые вычисления . Wiley-VCH. ISBN 978-3-527-40438-4.
- Вихерт, Андреас (2014). Принципы квантового искусственного интеллекта . ISBN World Scientific Publishing Co. 978-981-4566-74-2.
- Хироши, Имаи; Масахито, Хаяси (2006). Квантовые вычисления и информация . Берлин: Springer. ISBN 978-3-540-33132-2.
- Джегер, Грегг (2006). Квантовая информация: обзор . Берлин: Springer. ISBN 978-0-387-35725-6. OCLC 255569451 .
Академические работы
- Аббат, Дерек ; Деринг, Чарльз Р .; Пещеры, Карлтон М .; Лидар, Дэниел М .; Брандт, Ховард Э .; Гамильтон, Александр Р .; Ферри, Дэвид К .; Хеа-Банаклоче, Хулио ; Безруков, Сергей М .; Киш, Ласло Б. (2003). «Мечты против реальности: пленарная дискуссия по квантовым вычислениям». Квантовая обработка информации . 2 (6): 449–472. arXiv : квант-ph / 0310130 . DOI : 10,1023 / Б: QINP.0000042203.24782.9a . ЛВП : 2027,42 / 45526 . S2CID 34885835 .
- Ди Винченцо, Дэвид П. (2000). «Физическая реализация квантовых вычислений». Fortschritte der Physik . 48 (9–11): 771–783. arXiv : квант-ph / 0002077 . Bibcode : 2000ForPh..48..771D . DOI : 10.1002 / 1521-3978 (200009) 48: 9/11 <771 :: АИД-PROP771> 3.0.CO; 2-Е .
- Berthiaume, Андре (1997). «Квантовые вычисления» .
- Ди Винченцо, Дэвид П. (1995). «Квантовые вычисления». Наука . 270 (5234): 255–261. Bibcode : 1995Sci ... 270..255D . CiteSeerX 10.1.1.242.2165 . DOI : 10.1126 / science.270.5234.255 . S2CID 220110562 . В таблице 1 перечислены времена переключения и дефазирования для различных систем.
- Фейнман, Ричард (1982). «Моделирование физики с помощью компьютеров». Международный журнал теоретической физики . 21 (6–7): 467–488. Bibcode : 1982IJTP ... 21..467F . CiteSeerX 10.1.1.45.9310 . DOI : 10.1007 / BF02650179 . S2CID 124545445 .
- Митчелл, Ян (1998). «Вычислительная мощность в 21 веке: закон Мура и за его пределами» .
- Саймон, Дэниел Р. (1994). «О силе квантовых вычислений» . Институт инженеров по электротехнике и радиоэлектронике Computer Society Press.
внешние ссылки
- Стэнфордская энциклопедия философии : « Квантовые вычисления » Амита Хагара и Майкла Э. Каффаро.
- "Квантовые вычисления, теория" , Энциклопедия математики , EMS Press , 2001 [1994]
- Квантовые вычисления для очень любопытных Энди Матущак и Майкл Нильсен
- Квантовые вычисления стали проще в блоге Satalia
- Лекции
- Квантовые вычисления для детерминированных - 22 видеолекции Майкла Нильсена
- Видео Лекции по Дэвид Дойч
- Лекции в Институте Анри Пуанкаре (слайды и видео)
- Онлайн-лекция "Введение в квантовые вычисления", Эдвард Герджуа (2008 г.)
- Ломонако, Сэм. Четыре лекции по квантовым вычислениям, прочитанные в Оксфордском университете в июле 2006 г.