Квантовые алгоритмы
Как уже говорилось, обычные алгоритмы, основанные на бинарной логике, неприменимы к квантовому компьютеру, использующему квантовую логику (квантовые вентили). Для него пришлось придумывать новые, в полной мере использующие потенциал, заложенный в квантовую природу вычислений.
Наиболее известные на сегодняшний день алгоритмы это:
В отличие от классических, квантовые компьютеры не универсальны.
До сих пор найдено лишь небольшое число квантовых алгоритмов.(С)
Спасибо oxoron за ссылку на Quantum Algorithm Zoo, место, где, по уверениям автора (“Stephen Jordan”), собраны и продолжают собираться лучшие представители квантово-алгоритмического мира.
В данной статье мы не будем подробно разбирать квантовые алгоритмы, в Сети много прекрасных материалов на любой уровень сложности, но кратко пробежаться по трем самым известным все-таки надо.
Резюме
Квантовые компьютеры и квантовые вычисления — очень многообещающая, очень молодая и пока малоприменимая в промышленном плане область информационных технологий.
Развитие квантовых вычислений позволит (когда-нибудь) решать задачи:
Основные проблемы при создании и эксплуатации квантовых компьютеров:
Состояние дел на текущий момент:
Что может помочь:
На мой взгляд (исключительно личное мнение), в текущей научной парадигме знаний мы не добьемся значительных успехов в развитии квантовых технологий, тут нужен качественный прорыв в какой-либо области фундаментальной или прикладной науки, который даст толчок новым идеям и методам.
Ну а пока — нарабатываем опыт в квантовом программировании, собираем и создаем квантовые алгоритмы, тестируем идеи и прочее и прочее. Ждем прорыва.
Алгоритм Гровера
Алгоритм Гровера — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения F(X) = 1, где F — есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году.
Алгоритм Гровера может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.(С)
Подробнее можно почитать вот тут, или тут. Еще вот тут есть хорошее объяснение алгоритма на примере ящиков и мяча, но, к сожалению, по независящим ни от кого причинам, данный сайт у меня из России не открывается. Если у вас этот сайт тоже заблокирован, то вот краткая выжимка:
Алгоритм Гровера. Представьте, что у вас имеется N штук пронумерованных закрытых коробок. Они все пустые кроме одной, в которой находится мячик. Ваша задача: узнать номер коробки, в которой находится мячик (этот неизвестный номер часто обозначают буквой w).
Как решать эту задачу? Самым тупым способом, по очереди открывать коробки, и рано или поздно вы наткнетесь на коробку с мячиком. А сколько в среднем коробок нужно проверить до того, как будет обнаружена коробка с мячиком? В среднем нужно открыть примерно половину коробок N/2. Главное здесь то, что если мы увеличим число коробок в 100 раз, то в те же 100 раз увеличится и среднее число коробок, которые нужно открыть до того, как будет найдена коробка с мячиком.
Теперь сделаем ещё одно уточнение. Пусть мы не сами открываем коробки руками и проверяем наличие мячика в каждой, а имеется некий посредник, назовем его Оракул (Oracle). Мы говорим Оракулу — «проверь коробку номер 732», и Оракул честно проверяет и отвечает «в коробке номер 732 мячика нет». Теперь вместо слов о том, сколько коробок нам нужно в среднем открыть, мы говорим «сколько раз в среднем мы должны обратиться к Оракулу для того, чтобы найти номер коробки с мячиком»
Оказывается, что если перевести эту задачу с коробками, мячиком и Оракулом на квантовый язык, то выходит замечательный результат: для поиска номера коробки с мячиком среди N коробок нам нужно потревожить Оракула всего примерно SQRT(N) раз!
То есть сложность задачи перебора используя алгоритм Гровера снижается в квадратный корень раз.
Какие квантовые компьютеры уже есть в мире и в России?
Собственные квантовые компьютеры строят корпорации Google, IBM, Intel, а также компании поменьше — D-Wave и стартап Rigetti. Компания D-Wave создала машину для квантового отжига на 5 тыс. кубитах, которая превосходит прошлое поколение устройств по размеру, количеству связей между кубитами и скорости работы. Устройство является важным инженерным достижением, в будущем используемым для универсальных квантовых компьютеров. Национальные программы по разработке квантовых компьютеров также созданы и на уровне стран — в Евросоюзе, США, Китае и России.
«Квантового превосходства» в лабораторных условиях первой в мире достигла Google: компьютер Sycamore смог выполнить вычисление за 200 секунд, в то время как традиционный суперкомпьютер справился бы с этой операцией за 10 тыс. лет, описывал журнал Nature итоги эксперимента компании.
В России ученые работают над созданием квантового компьютера сразу на четырех платформах: сверхпроводниках, ионах, нейтральных атомах и фотонах. Согласно утвержденной правительством нашей страны дорожной карте по квантовым вычислениям, первые отечественные квантовые вычислительные устройства появятся уже в 2024 году. Квантовый процессор на основе сверхпроводников будет состоять из 30 кубитов, на основе нейтральных атомов и ионов — из 100, фотонов — из 50.
Сегодня в России работают прототипы квантовых компьютеров с 2-10 кубитами и квантовые симуляторы с 10-20 кубитами. Отечественные компьютеры способны демонстрировать простейшие алгоритмы, решать задачи моделирования простейших молекул. Эти мощности соответствуют уровню развития квантовых вычислений QTRL-4 (метрика зрелости технологий квантовых вычислений, наивысшим уровнем в ней считается QTRL-9).
Дисклеймер
Автор не является специалистом в квантовых вычислениях, и целевая аудитория статьи — такие же ИТ-шники, не квантовые специалисты, которые тоже хотят собрать в голове картинку под названием “Как работают квантовые компьютеры”. Из-за этого многие понятия в статье сознательно упрощены для лучшего понимания квантовых технологий на “базовом” уровне, но без совсем уж сильного упрощения с потерей информативности и адекватности.
В статье, в некоторых местах используются материалы из других источников, список которых приведен в конце статьи. Везде где это было возможно, вставлены прямые ссылки и указания на оригинал текста, таблицы или рисунка. Если где-то что-то (или кого-то) забыл, пишите — поправлю.
Simulation of quantum systems
Поздравляю всех самых терпеливых читателей, пройдя долгий путь непонимания мы добрались до самой сути квантовых компьютеров. Когда мы вычисляем формулу F=axmod(N) на обычном компьютере, мы ждем появления значения F=1, чтобы объявить о взломе ключа RSA. Но когда мы работаем на квантовой машине, нам на самом деле не важно, что по итогу хранится в регистре F, решение задачи будет хранится во входном регистре X.
В классическом компьютере в операторе XOR (аналог CNOT) значение контролирующей переменной не меняется, но напомню, что когда в квантовой машине мы выполняем операцию CNOT, она меняет оба кубита:
Отклонения кубита по оси Z называется фазой. За время выполнения квантовой программы все кубиты накапливают некоторое изменение фазы. Математики доказали, что, измерив итоговую фазу всех кубитов во входном регистре, можно с очень высокой вероятностью найти делители числа N (взломать RSA), даже если в F получилась не единица. Для RSA-512 нужно всего порядка 2000 запусков алгоритма на квантовом компьютере. Но есть подвох. Даже два.
Первая проблема заключается в том, что надо как-то суметь измерить фазу. Для этого используется алгоритм QFE (Quantum Phase Estimation), который требует дополнительных вращений кубитов на очень маленькие углы поворота. Для N=15 нужно вращать кубиты на 1.4o, для N=35 повороты будут уже 0.175o. Для RSA-512 нужно повернуть кубит на ничтожные 180/21022 градуса, сделав это 1022 раза. Кубиты – это аналоговая система, если ошибиться с углом поворота – на выходе мы получим ошибку. Современные квантовые компьютеры не могут справиться с числом N=35, им уже на этом этапе не хватает точности поворотов. Но это еще не так страшно, совсем ничтожными поворотами можно просто пренебречь, почти не потеряв точность всего алгоритма.
Вторая проблема заключается в вычислении axmod(N). Да, для RSA-512 надо вычислить ее всего лишь 2000 раз, но посмотрите еще раз на два вложенных цикла: одно такое вычисление – это более 21022 последовательных вращений кубитов. Это более чем фуфло. Квантовые компьютеры не способны взломать RSA, даже если они вырастут до миллиона кубитов. Есть большое количество научных статей, которые рассказывают нам, как им удалось оптимизировать эту часть и выполнить ее в сотни раз быстрее, но они всегда скромно умалчивают, сколько именно операций требуется, когда N = 2512.
Заявление Google о достижении квантового превосходства
54-кубитный процессор Sycamore
Итак, в октябре 2019 года разработчики Google опубликовали в научном издании Nature статью «Квантовое превосходство с применением программируемого сверхпроводящего процессора». Авторы объявили о достижении впервые в истории квантового превосходства с помощью 54-кубитного процессора «Sycamore».
В сети в статьях Sycamore часто упоминают то как 54-х кубитный процессор, то как 53-х. Истина в том, что согласно оригинальной статье, процессор физически состоит из 54-х кубитов, но один из них нерабочий и выведен из эксплуатации. Таким образом, в реальности мы имеем 53-х кубитный процессор.
В Сети тут же появилось множество материалов на эту тему, градус которых варьировался от восторженных до скептических.
Позднее сотрудники отдела квантовых вычислений компании IBM заявили, что Google ложно сообщила о достижении квантового превосходства. В компании утверждают, что обычный вычислитель справится с этой задачей в худшем случае за 2,5 дня, и при этом полученный ответ будет точнее, чем у квантового компьютера. Такой вывод был сделан по итогам проведенного теоретического анализа нескольких способов оптимизации.
Что же в реальности сделал Google? Для детального понимания почитайте Ааронсона, а кратко вот:
То есть Google реализовал синтетическую задачу на 53-х кубитном процессоре, и свое заявление о достижении квантового превосходства основывает на факте невозможности эмуляции такого процессора на стандартных системах за разумное время.
Для понимания — в этом разделе нисколько не умаляется достижение Google, инженеры действительно молодцы, а вопрос о том можно считать это реальным квантовым превосходством или нет, как уже говорилось ранее, скорее философский, чем инженерный. Но надо понимать, что достигнув такого вычислительного превосходства мы ни на шаг не продвинулись к возможности запускать алгоритм Шора на 2048-и битных числах.
Физические реализации кубитов
Как мы уже говорили, кубит может быть представлен квантовым объектом, то есть таким физическим объектом, который реализует описанные выше квантовые свойства. То есть грубо говоря, любой физический объект, в котором есть два состояния и эти два состояния находятся в состоянии суперпозиции можно использовать для построения квантового компьютера.
“Если мы умеем помещать атом в два разных уровня и управлять ими, то вот вам и кубит. Если мы можем это сделать с ионом, — кубит. С током то же самое. Если мы запускаем его по часовой стрелке и против часовой стрелки одновременно, вот вам кубит.” (С)
Из всего этого многообразия наиболее проработанным является первый метод получения кубитов, основанный на сверхпроводниках. Google, IBM, Intel и прочие ведущие игроки используют именно его для построения своих систем.
Ну и еще почитайте обзор возможных физических реализаций кубитов от Andrew Daley,2014.
Как работает квантовый компьютер
Квантовые компьютеры для вычислений используют такие свойства квантовых систем, как суперпозиция и запутанность. В суперпозиции квантовые частицы представляют собой комбинацию всех возможных состояний, пока не произойдет их наблюдение и измерение. Запутанные кубиты образуют единую систему и влияют друг на друга. Измерив состояние одного кубита, возможно сделать вывод об остальных. С увеличением числа запутанных кубитов экспоненциально растет способность квантовых компьютеров обрабатывать информацию.
Базовым элементом, выполняющим логические операции в классическом компьютере, является вентиль. Для работы квантового компьютера используются квантовые вентили, собранные из кубитов. Они бывают однокубитные и двухкубитные. Также существуют универсальные наборы вентилей, с помощью которых можно выполнить любое квантовое вычисление
Кроме того, квантовые компьютеры не могут работать со стандартным софтом вроде Windows. Для них требуется своя операционная система и приложения. Некоторые технологические гиганты уже предлагают организациям опцию квантовых вычислений в облаке. Облачные квантовые вычисления обеспечивают прямой доступ к эмуляторам, симуляторам и квантовым процессорам.
Поставщики также предоставляют платформы разработки и документацию для языков и инструментов вычислений. I BM уже представила программную платформу для квантовых вычислений с открытым исходным кодом под названием Qiskit. А Microsoft выпустила инструмент бесплатного разработчика вычислительной техники на языке Q# и симулятор квантовых вычислений. Над разработкой ПО для квантовых компьютеров работают также 1QBit, Cambridge Quantum Computing, QSimulate, Rahko, Zapata и другие компании.
Платформа Orquestra от Zapata предлагает набор вычислительных методов для квантовых компьютеров
Для работы квантовых компьютеров требуются квантовые алгоритмы. Из наиболее известных квантовых алгоритмов можно выделить три:
Квантовый компьютер работает на вероятностном принципе. Его результатом работы является распределение вероятностей возможных ответов, наиболее вероятный ответ обычно является лучшим решением.
Квантовые кубиты в физической реализации бывают нескольких типов: сверхпроводниковые, зарядовые, ионные ловушки, квантовые точки и другие.
Настоящий уровень развития технологий позволяет создать большое количество кубитов, сложность возникает с устойчивостью такой системы. Как и все квантовые системы, кубиты легко теряют заданное квантовое состояние при взаимодействии с окружением (происходит их декогеренция). При этом в работе квантового компьютера растет количество ошибок вычислений. Чтобы обеспечить ее устойчивость при проведении вычислений, требуется оградить систему от любого фонового шума, например, в случае сверхпроводниковых систем, охлаждая их до температур, близких к нулю по Кельвину (-273,1 °C). Разработчики используют сверхтекучие жидкости, чтобы добиться такого охлаждения.
Как объяснил Руслан Юнусов, исторически сверхпроводники считались наиболее перспективным направлением благодаря хорошей масштабируемости, стабильности во времени, контроле параметров и относительной легкости управления ими. Именно на этой платформе построены квантовые компьютеры IBM, Google и Rigetti. Однако, по его словам, в последнее время все большую популярность приобретают альтернативные квантовые платформы: ионы, демонстрирующие высочайшие на сегодняшний день показатели стабильности и точности операций (Honeywell, IonQ), и фотоны, преимуществами которых являются малый размер фотонного процессора и возможность работы при комнатных температурах (Xanadu, PsiQuantum, Quix).
Кроме того, развиваются новые концепции: системы на поляритонах или магнонах, системы бозе-эйнштейновских конденсатов, когерентные машины Изинга, когерентные CMOS-архитектуры. Так, в поляритонной архитектуре битом служит поляритон — квазичастица, сочетающая свойства света и вещества. Теоретически, поляритонный квантовый компьютер сможет работать при комнатной температуре, что снизит его стоимость и упростит изготовление. В настоящее время изучением поляритонных структур занимается Сколтех.
Quantum information processing
Computer engineers typically describe a modern computer’s operation in terms of classical electrodynamics.
Within these “classical” computers, some components (such as semiconductors and random number generators) may rely on quantum behavior, but these components are not isolated from their environment, so any quantum information quickly decoheres.
While programmers may depend on probability theory when designing a randomized algorithm, quantum mechanical notions like superposition and interference are largely irrelevant for program analysis.
Quantum programs, in contrast, rely on precise control of coherent quantum systems. Physicists describe these systems mathematically using linear algebra. Complex numbers model probability amplitudes, vectors model quantum states, and matrices model the operations that can be performed on these states. Programming a quantum computer is then a matter of composing operations in such a way that the resulting program computes a useful result in theory and is implementable in practice.
The state of this one-qubit quantum memory can be manipulated by applying quantum logic gates, analogous to how classical memory can be manipulated with classical logic gates. One important gate for both classical and quantum computation is the NOT gate, which can be represented by a matrix
Mathematically, the application of such a logic gate to a quantum state vector is modelled with matrix multiplication. Thus
The mathematics of single qubit gates can be extended to operate on multi-qubit quantum memories in two important ways. One way is simply to select a qubit and apply that gate to the target qubit while leaving the remainder of the memory unaffected. Another way is to apply the gate to its target only if another part of the memory is in a desired state. These two choices can be illustrated using another example. The possible states of a two-qubit quantum memory are
In summary, quantum computation can be described as a network of quantum logic gates and measurements. Однако любое измерение можно отложить до конца квантовых вычислений, хотя эта отсрочка может потребовать вычислительных затрат, поэтому большинство квантовых схем изображают сеть, состоящую только из квантовых логических элементов и без каких-либо измерений.
Существует ряд моделей вычислений для квантовых вычислений, отличающихся основными элементами, на которые разлагаются вычисления.
Квантовая схема, реализующая вентиль Тоффоли из более примитивных вентилей
Массив квантовых вентилей разбивает вычисления на последовательность квантовых вентилей размером в несколько кубитов. Квантовые вычисления можно описать как сеть квантовых логических элементов и измерений. Однако любое измерение можно отложить до конца квантовых вычислений, хотя эта отсрочка может потребовать вычислительных затрат, поэтому большинство квантовых схем изображают сеть, состоящую только из квантовых логических элементов и без каких-либо измерений.
Любое квантовое вычисление (которое в приведенном выше формализме представляет собой любую унитарную матрицу размера над кубитами) может быть представлено как сеть квантовых логических элементов из довольно небольшого семейства элементов. Выбор семейства вентилей, обеспечивающий такую конструкцию, известен как универсальный набор вентилей, поскольку компьютер, который может запускать такие схемы, является универсальным квантовым компьютером. Один общий такой набор включает в себя все однокубитные вентили, а также вентиль CNOT сверху. Это означает, что любые квантовые вычисления могут быть выполнены путем выполнения последовательности однокубитных вентилей вместе с вентилями CNOT. Хотя этот набор вентилей бесконечен, его можно заменить конечным набором вентилей, обратившись к теореме Соловея-Китаева.
Квантовые вычисления на основе измерений
Квантовый компьютер, основанный на измерениях, разлагает вычисления на последовательность измерений состояния Белла и однокубитных квантовых вентилей, применяемых к сильно запутанному начальному состоянию (состоянию кластера), используя метод, называемый телепортацией квантовых вентилей.
Адиабатические квантовые вычисления
Наиболее известным квантовым алгоритмом является алгоритм Шора (придуманный в 1994 году английской математикой Питером Шором), который занимается решением задач разложения чисел на простые множители (задачи факторизации, детальной логарифмы).
Именно этот метод приводится, например, когда пишете о том, что ваши банковские системы и пароли скоро будут взломаны. Учитывая, что длина текущего ключа не менее 2048 бит, время для шапочки еще не пришло.
На сегодняшний день результаты более чем скромные. Лучшие результаты факторизации с помощью алгоритма Шора — числа 15 и 21, что сильно меньше, чем 2048 бит. Для остальных результатов из таблиц применялся иной метод расчетов, но даже лучший результат по этому алгоритму (291311) сильно далек от реального применения.
Подробнее про алгоритм Шора можно почитать, например, вот тут. О практической реализации — тут.
Одна из текущих оценок сложности и производительности для факторизации чисел из 2048 бит это компьютер с 20 миллионами кубитов. Спим спокойно.
Управление развития
В текущий момент (могу ошибиться, поправить) основные усилия (и более-менее значимые результаты) у всех ведущих игроков консолидации на двух направлениях:
Прочие же вектора развития, которые дают нам квантовую физику, такие как:
определенно тоже в списке исследований, но каких-то более-менее значимых результатов в настоящее время вроде как еще нет.
Дополнительно можно почитать дорожную карту развития квантовых технологий, ну и гуглите «развитие квантовых технологий», например, вот, вот и вот.
Алгоритм Дойча-Йожи
Еще можно почитать тут. Более простое объяснение:
Алгоритм Дойча (Дойча — Йожи) основан на переборе, но позволяет сделать его быстрее обычного. Представьте, что на столе лежит монета, и необходимо узнать фальшивая ли она или нет. Для этого нужно дважды просмотреть монету и определить: «орел» и «решка» – настоящие, два «орла», две «решки» – фальшивая. Так вот, если использовать квантовый алгоритм Дойча, то это определение можно сделать одним взглядом – измерениями. ( С)
Немного об эмуляции квантовых компьютеров
Квантовые вычисления можно эмулировать на обычном компьютере. Ведь действительно, смотрите:
Для сравнения Summit (Топ-1 из Топ-500) имеет всего 2,8 Петабайт памяти.
Текущий рекорд симуляций — 49 кубитов, поставленный в прошлом году на крупнейшем китайском суперкомпьютере (Sunway Taihu Light)
Предел моделирования квантового компьютера на классических условиях с учетом объема оперативной памяти, необходимой для хранения состояния кубитов.
По операциям — для точной эмуляции схемы на 49 кубитов из каких-то 39 “тактов” (независимых слоев вентилей) потребовалось 2^63 комплексных умножений — 4 Пфлопс суперкомпьютера на протяжении 4 часов
Эмуляция квантового компьютера из 50+ кубит на классических системах считается невыполнимой за разумное время. В том числе из-за этого факта Google использовал для своего эксперимента с квантовым превосходством процессор с 53-мя кубитами.
Запутанность
Квантовая запутанность – второй кит, на котором держится квантовый компьютер, и это действительно любопытный эффект, который современная наука пока не может объяснить. Но мы пойдем издалека. Давайте взглянем на типичный кусок исходного кода для традиционного компьютера:
Данная операция позволяет выполнять банальное сложение целых чисел для двух регистров кубитов. Чтобы выполнить эту операцию два кубита кратковременно подносят поближе друг к другу, после чего выполняют серию отдельных вращений. Измерения не требуются, т.е. с кубитами можно работать дальше. После этой операции кубиты запутаны. Как это проявляется? Начнем с банального:
После того, как мы запутали кубиты, они становятся зависимыми друг от друга. Если кубит Q1 был измерен как Единица, то кубит Q2 будет измерен как Ноль. Но этот случай очевиден и не интересен, давайте перед CNOT уложим кубиты на бок:
Если контролирующий кубит лежит на боку, то контролируемый будет либо повернут на 180 градусов с вероятностью 50%, либо останется в прежнем состоянии. Точное итоговое положение кубитов в 3D пространстве после такой операции не известно (они якобы сразу во многих состояниях), ведь на кубиты нельзя посмотреть непосредственно. Но если запутанные кубиты измерить, то Q1 будет рандомно падать на сенсор 0 или 1, а Q2 будет всегда падать на противоположный сенсор.
Почему так происходит никто не знает. По логике, оба кубита лежат на боку, после операции CNOT они оба должны рандомно падать на оба сенсора, без какой-либо зависимости. По факту же прослеживается четкая связь при измерении (с некоторой погрешностью, система все-таки аналоговая). На этот счет есть две теории:
На мой взгляд само явление Запутанности является главным доказательством, что Суперпозиции не существует, но я не физик-теоретик, поэтому оставим эту тему. В конце концов когда-то официальная наука высмеивала теорию движения литосферных плит, но в конце концов ребята во всем разобрались.
Пара заключительных моментов про запутанность:
Оглавление
Время на прочтение
В этой статье я разберу по косточкам все тайны квантовых компьютеров: что такое суперпозиция (бесполезна) и запутанность (интересный эффект), могут ли они заменить обычные компьютеры (нет) и могут ли они взломать RSA (нет). При этом я не буду упоминать волновую функцию и столь раздражающих Bob и Alice, которых вы могли встречать в других статьях про квантовые машины.
Первое и самое главное, что нужно знать – квантовые компьютеры не имеют ничего общего с обычными. Квантовые компьютеры по своей природе – аналоговые, там нет бинарных операций. Вероятно, вы уже слышали про Кубиты, что у них есть состояние 0, 1 и 0-1 одновременно, и благодаря этому вычисления выполняются очень быстро: это заблуждение. Кубит – это магнит (обычно атом или электрон), подвешенный в пространстве, который может вращаться по всем трем осям. Собственно, вращение магнита в пространстве – это и есть операции квантового компьютера. Почему это может ускорить вычисления? Было очень сложно найти ответ, но самые стойкие читатели увидят его в конце статьи. Начнем разоблачения.
История квантовых вычислений началась в начале 1980-х годов, когда физик Пол Бениофф предложил квантово-механическую модель машины Тьюринга в 1980 году.
Необходимость в квантовом компьютере возникает тогда, когда мы пытаемся исследовать методами физики сложные многочастичные системы, подобные биологическим. Пространство квантовых состояний таких систем растёт как экспонента от числа составляющих их реальных частиц, что делает невозможным моделирование их поведения на классических компьютерах уже для . Поэтому Визнер и Фейнман высказали идею построения квантового компьютера.
Квантовый компьютер использует для вычисления не обычные (классические) алгоритмы, а процессы квантовой природы, так называемые квантовые алгоритмы, использующие квантовомеханические эффекты, — такие как квантовый параллелизм и квантовая запутанность.
Если классический процессор в каждый момент может находиться ровно в одном из состояний (обозначения Дирака), то квантовый процессор в каждый момент находится одновременно во всех этих базисных состояниях, при этом в каждом состоянии — со своей комплексной амплитудой . Это квантовое состояние называется «квантовой суперпозицией» данных классических состояний и обозначается как
Квантовое состояние может изменяться во времени двумя принципиально различными путями:
Если классические состояния есть пространственные положения группы электронов в квантовых точках, управляемых внешним полем , то унитарная операция есть решение уравнения Шрёдингера для этого потенциала.
Измерение есть случайная величина, принимающая значения с вероятностями соответственно. В этом состоит квантовомеханическое правило Борна. Измерение есть единственная возможность получения информации о квантовом состоянии, так как значения нам непосредственно недоступны. Измерение квантового состояния не может быть сведено к унитарной шрёдингеровской эволюции, так как, в отличие от последней, оно необратимо. При измерении происходит так называемый коллапс волновой функции , физическая природа которого до конца не ясна. Спонтанные вредоносные измерения состояния в ходе вычисления ведут к декогерентности, то есть отклонению от унитарной эволюции, что является главным препятствием при построении квантового компьютера (см. физические реализации квантовых компьютеров).
Квантовое вычисление есть контролируемая классическим управляющим компьютером последовательность унитарных операций простого вида (над одним, двумя или тремя кубитами). В конце вычисления состояние квантового процессора измеряется, что и даёт искомый результат вычисления.
A wafer of adiabatic quantum computers
These issues are more difficult for optical approaches as the timescales are orders of magnitude shorter and an often-cited approach to overcoming them is optical pulse shaping. Error rates are typically proportional to the ratio of operating time to decoherence time, hence any operation must be completed much more quickly than the decoherence time.
As described by the threshold theorem, if the error rate is small enough, it is thought to be possible to use quantum error correction to suppress errors and decoherence. This allows the total calculation time to be longer than the decoherence time if the error correction scheme can correct errors faster than decoherence introduces them. An often-cited figure for the required error rate in each gate for fault-tolerant computation is 10−3, assuming the noise is depolarizing.
This state of affairs can be traced to several current and long-term considerations.
In particular, building computers with large numbers of qubits may be futile if those qubits are not connected well enough and cannot maintain sufficiently high degree of entanglement for long time. When trying to outperform conventional computers, quantum computing researchers often look for new tasks that can be solved on quantum computers, but this leaves the possibility that efficient non-quantum techniques will be developed in response, as seen for Quantum supremacy demonstrations. Therefore, it is desirable to prove lower bounds on the complexity of best possible non-quantum algorithms (which may be unknown) and show that some quantum algorithms asymptomatically improve upon those bounds.
Some researchers have expressed skepticism that scalable quantum computers could ever be built, typically because of the issue of maintaining coherence at large scales, but also for other reasons.
Candidates for physical realizations
This section needs expansion. You can help by adding to it.
The Mach–Zehnder interferometer shows that photons can exhibit wave-like interference.
Peter Shor (pictured here in 2017) showed in 1994 that a scalable quantum computer would be able to break RSA encryption.
As a mathematical consequence of this definition, , , , and . In other words, the CNOT applies a NOT gate ( from before) to the second qubit if and only if the first qubit is in the state . If the first qubit is , nothing is done to either qubit.
Any quantum computation (which is, in the above formalism, any unitary matrix of size over qubits) can be represented as a network of quantum logic gates from a fairly small family of gates. A choice of gate family that enables this construction is known as a universal gate set, since a computer that can run such circuits is a universal quantum computer. One common such set includes all single-qubit gates as well as the CNOT gate from above. This means any quantum computation can be performed by executing a sequence of single-qubit gates together with CNOT gates. Though this gate set is infinite, it can be replaced with a finite gate set by appealing to the Solovay-Kitaev theorem.
Квантовые компьютеры довольно медленные, типичная рабочая частота 100 МГц, но это поправимо. Они также довольно маленькие, 66 кубитов считается мега круто (можно разместить в памяти пару int), но это тоже поправимо. На физическом уровне квантовые компьютеры не поддерживают (и возможно, никогда не поддержат):
Все взаимодействие между кубитами сводится к операции CNOT, на которой далеко не уедешь. Но если они такие ограниченные, то почему вокруг них столько шума? При решении задачи в лоб никакого превосходства над классическими компьютерами не будет, но есть очень узкий перечень алгоритмов, где квантовый компьютер может себя проявить. Напомню, каждая квантовая операция – это вращение одного или двух кубитов, для ее выполнения достаточно одного кратковременного импульса. С другой стороны для моделирования вращения магнита на классическом компьютере нужно вычислить много синусов и косинусов. Примерно на этой особенности и строятся эффективные квантовые алгоритмы.