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

Обновлено: 07.07.2024

Может ли целочисленная факторизация быть решена за полиномиальное время на классическом компьютере?

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

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

В 2019 году Фабрис Будо, Пьерк Годри, Аврора Гильевич, Надя Хенингер, Эммануэль Томе и Пол Циммерманн факторизовали 240-значное (795-битное) число ( RSA-240 ), используя примерно 900 ядерных лет вычислительной мощности. Исследователи подсчитали, что 1024-битный модуль RSA займет примерно в 500 раз больше времени.

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

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

СОДЕРЖАНИЕ

Разложение на простые числа

Разложение n = 864 на простые числа как 2 5 × 3 3

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

Учитывая общий алгоритм целочисленной факторизации, любое целое число может быть разложено на составляющие его простые множители путем повторного применения этого алгоритма. Ситуация усложняется со специальными алгоритмами факторизации, преимущества которых могут не быть реализованы также или даже не реализованы с факторами, полученными во время декомпозиции. Например, если n = 171 × p × q, где p < q - очень большие простые числа, пробное деление быстро произведет множители 3 и 19, но потребует p делений, чтобы найти следующий множитель. В качестве противоположного примера, если n является произведением простых чисел 13729, 1372933 и 18848997161, где 13729 × 1372933 = 18848997157 , метод факторизации Ферма начнется с того, что немедленно дает и, следовательно, множители a - b = 18848997157 и a + b = 18848997161 . Хотя они легко распознаются как составные и простые соответственно, метод Ферма потребует гораздо больше времени, чтобы разложить составное число на множители, потому что начальное значение для a далеко от 1372933. ⌈ п ⌉ знак равно 18848997159 > \ rceil = 18848997159> б знак равно а 2 - п знак равно 4 знак равно 2 б -n>> = > = 2b> ⌈ 18848997157 ⌉ знак равно 137292 > \ rceil = 137292>

Современное состояние дел

Среди b- битных чисел сложнее всего разложить на множители с использованием существующих алгоритмов те, которые являются произведением двух простых чисел одинакового размера. По этой причине эти целые числа используются в криптографических приложениях. Самым крупным из таких полупростых чисел, который когда-либо учитывался, был RSA-250 , 829-битное число с 250 десятичными знаками, в феврале 2020 года. Общее время вычислений составило примерно 2700 ядерно-лет вычислений с использованием Intel Xeon Gold 6130 на частоте 2,1 ГГц. Как и все недавние записи факторизации, эта факторизация была завершена высокооптимизированной реализацией сита общего числового поля, запущенного на сотнях машин.

Сложность и сложность

Не было опубликовано ни одного алгоритма , который мог бы разложить все целые числа на множители за полиномиальное время , то есть разложить b- битное число n на множители за время O ( b k ) для некоторой константы k . Ни существование, ни отсутствие таких алгоритмов не было доказано, но обычно предполагается, что их не существует и, следовательно, проблема не в классе P. Проблема явно в классе NP, но обычно предполагается, что она не является NP-полным , хотя это не было доказано.

Есть опубликованные алгоритмы, которые быстрее, чем O ((1 + ε ) b ) для всех положительных ε , то есть субэкспоненциальные . По состоянию на 2021-03-12 алгоритм с наилучшим теоретическим асимптотическим временем работы - это решето общего числового поля ( GNFS ), впервые опубликованное в 1993 году, работающее на b- битном числе n во времени:

Для современных компьютеров GNFS - лучший опубликованный алгоритм для больших n (более 400 бит). Для квантового компьютера , однако, Питер Шор обнаружил алгоритм в 1994 году , который решает его в полиномиальное время. Это будет иметь серьезные последствия для криптографии, если квантовые вычисления станут масштабируемыми. Алгоритм Шора занимает только O ( b 3 ) времени и O ( b ) пространства на входных b- битных числах. В 2001 году алгоритм Шора был впервые реализован с использованием методов ЯМР на молекулах, содержащих 7 кубитов.

Неизвестно, какие именно классы сложности содержат вариант решения задачи целочисленной факторизации (то есть: имеет ли n множитель меньше k ?). Известно, что он присутствует как в NP, так и в co-NP , что означает, что оба ответа «да» и «нет» могут быть проверены за полиномиальное время. Ответ «да» может быть подтвержден факторизацией n = d ( n / d ) с d ≤ k . Ответ «нет» может быть подтвержден демонстрацией факторизации n на различные простые числа, все больше k ; можно проверить их простоту с помощью теста на простоту AKS , а затем умножить их, чтобы получить n . Основная теорема арифметики гарантирует , что существует только одна возможная строка увеличивающихся простых чисел , которые будут приняты, что свидетельствует о том , что проблема в обоих UP и со-UP. Известно, что он входит в BQP из-за алгоритма Шора.

Предполагается, что проблема находится вне всех трех классов сложности P, NP-полной и co-NP-полной . Таким образом, он является кандидатом в NP-средний класс сложности. Если бы можно было доказать, что он является либо NP-полным, либо co-NP-полным, это означало бы NP = co-NP, очень неожиданный результат, и поэтому многие подозревают, что целочисленная факторизация находится за пределами обоих этих классов. Многие люди пытались найти для него классические алгоритмы с полиномиальным временем, но потерпели неудачу, поэтому многие подозревают, что он находится за пределами P.

Напротив, проблема решения "Является ли n составным числом?" (или, что эквивалентно: «Является ли n простым числом?») оказывается намного проще, чем проблема определения множителей n . Задача составного / простого числа может быть решена за полиномиальное время (в количестве b цифр n ) с помощью теста на простоту AKS . Кроме того, существует несколько вероятностных алгоритмов, которые могут очень быстро проверить простоту на практике, если кто-то готов допустить исчезающе малую вероятность ошибки. Простота проверки простоты является важной частью алгоритма RSA , поскольку для начала необходимо найти большие простые числа.

Алгоритмы факторинга

Специального назначения

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

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

Общее назначение

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

Другие известные алгоритмы

Эвристическое время выполнения

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

в маленькой и L-нотации . Некоторыми примерами этих алгоритмов являются метод эллиптической кривой и квадратное решето . Другой такой алгоритм - это метод отношений групп классов, предложенный Шнорром, Сейсеном и Ленстрой, который они доказали только в предположении недоказанной обобщенной гипотезы Римана (GRH) .

Жесткое время работы

Ленстра и Померанс строго доказали, что вероятностный алгоритм Шнорра – Зейсена – Ленстры имеет ожидаемое время выполнения путем замены допущения GRH использованием множителей. Алгоритм использует группу классов положительных бинарных квадратичных форм с дискриминантом А обозначаемых G А . G Δ - это набор троек целых чисел ( a , b , c ), в котором эти числа являются относительными простыми числами. L п [ 1 2 , 1 + о ( 1 ) ] \ left [ >, 1 + o (1) \ right]>

Алгоритм Шнорра – Сейсена – Ленстры

Дано целое число n, которое будет факторизовано, где n - нечетное положительное целое число, большее определенной константы. В этом алгоритме факторизации дискриминант Δ выбирается как кратное n , Δ = - dn , где d - некоторый положительный множитель. Алгоритм ожидает, что для одного d существует достаточно гладких форм в G Δ . Ленстра и Померанс показывают, что выбор d может быть ограничен небольшим набором, чтобы гарантировать результат гладкости.

Обозначим через P Δ множество всех простых чисел q с символом Кронекера . Путем построения набора образующих группы G Δ и простых форм f q группы G Δ с q в P Δ получается последовательность отношений между набором образующих и f q . Размер q может быть ограничен для некоторой константы . ( Δ q ) знак равно 1 > \ right) = 1> c 0 ( бревно ⁡ | Δ | ) 2 (\ журнал | \ Delta |) ^ > c 0 >

Отношение , которое будет использовано это отношение между произведением полномочий, которое равно нейтральным элементом из G А . Эти отношения будут использоваться для построения так называемой неоднозначной формы G Δ , которая является элементом G Δ деления порядка 2. Посредством вычисления соответствующей факторизации Δ и взятия НОД эта неоднозначная форма обеспечивает полную факторизацию простых чисел. из п . Этот алгоритм состоит из следующих основных этапов:

Пусть n будет факторизованным числом.

  1. Пусть Δ - отрицательное целое число с Δ = - dn , где d - множитель, а Δ - отрицательный дискриминант некоторой квадратичной формы.
  2. Возьмем т первых простых чисел , для некоторых . п 1 знак равно 2 , п 2 знак равно 3 , п 3 знак равно 5 , … , п т = 2, p_ = 3, p_ = 5, \ dots, p_ > т ∈ N >>
  3. Пусть - случайная простая форма группы GΔ с . ж q > ( Δ q ) знак равно 1 > \ right) = 1>
  4. Найдите порождающий X группы GΔ
  5. Соберите последовательность отношений между множеством X и < f q : q ∈ PΔ >, удовлетворяющую: ( ∏ Икс ∈ Икс Икс р ( Икс ) ) . ( ∏ q ∈ п Δ ж q т ( q ) ) знак равно 1 > x ^ \ right). \ left (\ prod _ > f_ ^ \ right) = 1>
  6. Постройте неоднозначную форму, которая является элементом f ∈ GΔ порядка деления 2, чтобы получить взаимно простую факторизацию наибольшего нечетного делителя Δ, в которой ( а , б , c ) Δ знак равно - 4 а c или а ( а - 4 c ) или ( б - 2 а ) ( б + 2 а ) > a (a-4c) > (b-2a) (b + 2a)>
  7. Если неоднозначная форма обеспечивает факторизацию n, остановитесь, в противном случае найдите другую неоднозначную форму, пока не будет найдено факторизация n . Чтобы предотвратить появление бесполезных неоднозначных форм, создайте 2-силовскую группу Sll 2 (Δ) группы G (Δ).

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

Ожидаемое время работы

Алгоритм, как указано, является вероятностным алгоритмом, поскольку он делает случайный выбор. Ожидаемое время работы - самое большее . L п [ 1 2 , 1 + о ( 1 ) ] \ left [ >, 1 + o (1) \ right]>

Что бы понять, что такое "Квантовый компьютер" мы начнем с того, что появилось раньше - классической механики. Возьмем один БИТ , который может принимать значение либо ноля либо единицы. Это единица измерения информации. В квантовой механике мы имеем квантовый БИТ - Куби́т , так его назвали. Изначально Кубит не принимает точного значения ноля или единицы как в классическом случае. В квантово-механическом случае он будет находиться в состоянии суперпозиции ноля и единицы. Это смешенное состояние - Немного ноль и немного единица. В действительности он может принимать любое значение. Это будет первым фактом. Вторым фактом будет то, что в квантовой механики называется запутанностью . Это означает, что если у нас есть два бита, в классическом случае они могут принимать значения - ноль-ноль, ноль-один, один-ноль, один-один. Любой из четырех возможных вариантов.

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

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

Эти частицы могут взаимодействовать друг с другом. Они могут запутаться, таким образом создаётся квантовый алгоритм. Для вычисления площади поверхности например или для поиска кратчайшего расстояния между двумя точками. Всё это можно вычислить используя правила квантовой механики. Вместо использования правил классической механики. Есть убеждение которое на сто процентов еще не подтверждено, но мы считаем его вполне вероятным, что есть задачи которые очень сложно решить на обычном компьютере. Имеется в веду, что мы можем придумать такую задачу на решение которой обычному компьютеру понадобиться время всей жизни вселенной. Квантовый компьютер может решить подобную задачу намного быстрей и эффективней, но всё это пока еще не доказано. Так почему же мы полагаем, что квантовый компьютер может решать подобные задачи быстрее? Потому что он может обрабатывать большое количество информации. Если в двухбитной системе есть всего лишь четыре варианта, то кубитной их бесконечное множество, потому что кубит может принимать любые значения из этих четырех вариантов. Например 10% этого значения и 20% другого при этом создаются континуум вероятности . Эта система больше аналоговая чем цифровая. Квантовый компьютер позволит использовать эту дополнительную мощность. Вместо манипулирования с каждым отдельным битом, благодаря запутанности, квантовый компьютер позволяет манипулировать всеми битами одновременно.

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

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

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

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

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

Оглавление

Модуль 3. Основные принципы квантового вычисления
Проверочный тест

Традиционные компьютеры, основанные на использовании полупроводниковых логических элементов, уже приблизились к пределу своего развития — дальнейшая миниатюризация транзисторов и «упаковка» еще большего числа вычислительных компонентов в тот же объем скоро станет невозможной. Поэтому инженеры и ученые пытаются создать вычислительные устройства иного типа. В их числе — квантовые вычислительные машины, основанные на использовании ряда квантовых эффектов, таких как квантовая запутанность и квантовая суперпозиция. Благодаря этому они способны решать задачи, на которые «обычные» компьютеры потратили бы миллиарды лет (это, например, расчет поведения сложных молекул, моделирование нейронных связей в мозге или решение сложных логистических задач). Квантовые компьютеры обещают решить эту проблему, однако пока созданы только экспериментальные квантовые установки, еще не показавшие «квантового превосходства» — значимой прибавки в скорости вычислений по сравнению с обычными компьютерами.

История идеи

Идею квантовых вычислительных устройств впервые высказал в 1980 году советский математик Юрий Манин. В книге «Вычислимое и невычислимое», рассуждая о сложности процесса считывания и записи биологической информации с молекул ДНК, он заметил, что для моделирования этого процесса могли бы подойти квантовые устройства. Здесь же Манин указал указал на главное их преимущество — рост числа состояний таких устройств идет по степенному закону:


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

Ученый подчеркнул, что все явления подчиняются квантовым законам (а классическая физика — только приближение). Если поведение одиночного квантового объекта достаточно легко поддается моделированию с помощью компьютера, то нарастание количества элементов ведет к экспоненциальному росту сложности вычислений.

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

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

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


Работа одного из элементов квантового компьютера в представлении Фейнмана

В 1985 году Дэвид Дойч из Оксфордского университета разработал теорию универсального квантового компьютера как квантовой машины Тьюринга.

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

Эйичи назвал свой бит параметроном, и его первый прототип был создан в 1958 году в Токийском университете. Ниже представлен схематический чертеж оригинального устройства Гото.


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

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

Пределы роста классических компьютеров

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

С 1960-х годов, когда началось интенсивное развитие электроники, в мире компьютеров действует закон Мура — замеченная основателем Intel Гордоном Муром закономерность, согласно которой число транзисторов на чипе удваивается каждые два года, а производительность процессоров (как и мощность, доступная за 1 доллар) — каждые 18 месяцев.

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

Согласно расчетам Сета Ллойда из Массачусетского технологического института, умозрительный «окончательный ноутбук», в котором предельная вычислительная мощность «упакована» в объем 1 литр и массу 1 килограмм, мог бы выполнять 10 51 операций в секунду на 10 31 битов, что примерно на 40 порядков выше возможностей современных вычислительных машин. Это означает, что закон Мура должен действовать еще примерно 250 лет, чтобы добраться до этого окончательного предела.

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

Сложности создает и пропускная способность соединений между транзисторами. Еще в 2013 году некоторые ученые объявили о конце закона Мура (пока лишь в области твердотельных накопителей).

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

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

Биты и кубиты

Классические компьютеры оперируют битами — объектами, имеющими всего два возможных состояния, например 1 или 0. В качестве такого максимально простого классического объекта можно рассматривать, например, монету, у которой виден либо аверс, либо реверс, то есть орел или решка.

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

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

Еще одной интересной и очень перспективной сферой являются квантовые вычисления, которые, тем не менее, не получили столь широкого распространения (по крайней мере, пока), как нейросети. Скорее всего, это связано с еще более сложным матаном ( и физикой), а также с чрезмерной дороговизной и сложностью "железа".

Если очень просто, то это устройство, в основе работы которого лежат явления квантовой механики. Среди этих явлений такие великолепные и ̶п̶р̶о̶с̶т̶ы̶е̶ для понимания, как:

  • Квантовая суперпозиция - способность квантовой частицы находиться во всех возможных для нее состояниях сразу. Отличным примером может служить всем известный кот Шрёдингера.
  • Квантовая запутанность - явление, при котором состояния двух и более квантовых частиц становятся зависимыми друг от друга. Причем изменение состояния одной частицы мгновенно сказывается на состоянии другой. То есть как бы далеко не были друг от друга эти частицы, состояние поменяется за неизмеримо малое время. Здесь в качестве примера можно взять "попсовую" и всем известную квантовую телепортацию.
  • Правило Борна (закон) - ̶ ̶ш̶е̶с̶т̶а̶я̶ ̶ч̶а̶с̶т̶ь̶ ̶п̶о̶х̶о̶ж̶д̶е̶н̶и̶й̶ ̶б̶ы̶в̶ш̶е̶г̶о̶. Если вкратце и без тяжелого мат.аппарата, это закон (ну или правило), который рассчитывает вероятность получить какой-либо результат при вычислении, что помогает при работе со следующим пунктом сего списка.
  • Вероятность - в квантовой механике балом правит именно эта госпожа. Любое квантовое явление не есть факт, а есть вероятность того, что оно случится. Но об этом мы еще поговорим.

Справедливости ради, квантовая телепортация не является телепортацией, известной из научной фантастики и прочего сайфая, потому что при передаче квантового состояния (а именно это и происходит) исходное состояние в точке А разрушается и воссоздается в точке Б, при этом не происходит переноса ни материи, ни энергии.

Обновление по комментариям к статье: парадокс кота Шрёдингера был призван показать абсурдность самой идеи суперпозиции. Соответственно, пример кота - не самый лучший для иллюстрации явления суперпозиции.

Спасибо Marat Khamadeev

Преимущества прямо вытекают из самой квантовой механики:

  • Высокий параллелизм - в отличие от классических компьютеров, в которых бит принимает значение либо 0, либо 1 в один момент времени, в квантовом компьютере кубит одновременно и 0, и 1, что позволяет обсчитывать все возможные комбинации параллельно и одновременно на уровне физики без всяких ухищрений с многопоточностью.
  • Высокая масштабируемость и быстрый прирост производительности - при добавлении каждого следующего кубита вычислительная мощность увеличивается экспоненциально. То есть двухкубитный компьютер в 2 раза мощнее однокубитного, 3 - в 8 раз, 4 - в 16 и так далее.

Важно также отметить и недостатки, которым подвержены текущие образцы КК:

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

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

  • Моделирование молекул и прочих химических и биологических процессов, являющихся квантовыми по своей природе. Например, расчет нового лекарства от рака за 500 млн долларов за дозу займет не годы, а доли секунды.
  • Криптография. Во-первых, при появлении достаточно мощного КК падут почти все (если не все) классические алгоритмы шифрования, потому что большинство из них ломаются обычным перебором, а перебор - это то, что КК делает очень быстро. Квантовая же криптография позволяет построить такую зашифрованную систему, которая всегда узнает, если ее попытаются прослушать или взломать из-за лежащего в основе принципа неопределенности (Гейзенберга). То есть в данном случае недостаток измерения (вмешательства) в систему становится преимуществом.
  • Эти ваши нейросеточки. КК способен моделировать нейросеть экспоненциального размера и обрабатывать огромные объемы данных практически мгновенно.

Как верно отметили некоторые в комментариях квантовая криптография построена на несколько иных принципах и не имеет прямого отношения к квантовым же компьютерам.

Так что поиграть со включенным RTX при fps свыше 120 в 4К разрешении на КК пока что не получится, увы.

Квантовые компьютеры начали появляться с начала XXI века, но их производительность и возможности сильно ограничены. И вопреки распространенному заблуждению довольно много его составных частей представляют собой вполне себе обычную электронику, а уж для обработки результатов и вовсе нужен самый обыкновенный ПК (ну или сервер. ну или ЦОД).

Квантовый компьютер на 50 кубит, разработанный IBM Research в Цюрихе.​

Окей, с железом понятно, но что с софтом?

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

С целью решения этой проблемы в 2017 году был описан язык промежуточного представления OpenQASM (ОпенКАЗМ) - Open Quantum Assembly Language (Открытый квантовый язык ассемблера), представляющий собой по сути аналог языка ассемблера из классической электроники.

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

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

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

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

̶В̶а̶ш̶а̶ ̶q̶i̶s̶k̶i̶t̶ ̶к̶у̶п̶и̶л̶а̶ ̶б̶ы̶.̶.̶.̶ Логотип проекта - схематичное представление сферы Блоха (способ представления состояний кубита в виде точек на сфере). ​ А вот так выглядит сама сфера Блоха. "Точка на сфере по оси z вверх соответствует значению 1 классического бита, вниз - значению 0.​

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

  • Terra позволяет создавать квантовые цепи, которые по сути и являются квантовыми программами. Квантовая цепь - это последовательность квантовых вентилей, являющихся аналогом вентилей-операторов из классической логики. Например, здесь есть аналоги логического И (умножения) и ИЛИ (сложение) с поправкой на квантовые законы. Например, самый базовый квантовый вентиль Хадамард (H) при вычислении обеспечивает одинаковую вероятность получить значение 0 и 1.
  • Aqua. Проект-ретранслятор, позволяющий преобразовывать классические алгоритмы в квантовые. В настоящий момент он поддерживает ограниченный набор инструментов для работы с ИИ, химией, оптимизацией и финансами. В перспективе позволит программистам и даже просто пользователям без специальных знаний создавать квантовые алгоритмы.
  • Aer. Симулятор квантового компьютера, который может быть запущен на любом обычном компьютере, но не забывайте, что добавление нового кубита требует увеличения классических вычислительных мощностей в два раза. Aer позволяет понять, насколько ничтожны "силы" вашего ПК, потому что уже при значении в 4-5 кубитов производительность падает практически до нуля, делая симуляцию очень медленной или вовсе невозможной.
  • Ignis. Подпроект, работающий с "шумами". Помним о том, что любое измерение вызывает возмущения в квантовой системе и ошибки. По сути этот проект призван бороться с ошибками.

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

Да-да, ошибки - сквозная тема и боль любого квантового программиста настоящего и даже будущего.

Любой желающий уже может сесть и начать пробовать писать простенькие квантовые алгоритмы. Мощностей обычных домашних ПК хватит на 3-4-кубитную цепь, чего уже достаточно для осуществления квантовой телепортации.

К счастью, добрые дяди из корпорации IBM предоставляют бесплатный доступ в порядке очереди к настоящим квантовым компьютерам (до 15 кубитов) и к симулятору (до 32 кубитов). Для регистрации достаточно принять пользовательское соглашение, заполнить простенькую анкету, указав в ней Institution (например, Amateur Quantum Boy) и цель использования, свое имя и имейл.

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

В качестве инструмента используются обычные Jupyter-ноутбуки, знакомые любителям языка python.

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

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

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

Я *немножко* разочарован, потому что 95% моих знакомых, как и я, знаем упомянутое в статье (возможно, исключая то, что есть публичный компьютер-пробник).

Про разработки от Google: ред.

В сентябре публикация компании ненадолго появлялась на сайте NASA.

А что бы ты хотел увидеть?

Я пришёл раздавать квантовую жвачку и надирать квантовые задницы, и жвачка у меня уже кончилась. Поехали разбирать написанное.

Если очень просто, то это устройство, в основе работы которого лежат явления квантовой механики.

Туннельный транзистор, спинтронные устройства и ещё ряд устройств тоже используют явления КМ, но квантовыми вычислителями не являются
Отличным примером может служить всем известный кот Шрёдингера.

Парадокс кота Шрёдингера был придуман как раз таки для того, чтобы показать абсурдность идеи квантовой суперпозиции. Не задумывались, почему он называется парадоксом?
Любое квантовое явление не есть факт, а есть вероятность того, что оно случится.

То есть, квантовая запутанность - это вероятность, а не факт?
Измерение неизбежно ведет к ошибкам, потому что любое вмешательство в квантовую систему вызывает "возмущения" (шумы), искажающие полученные данные.

Само измерение - это штука нужная, важная и ошибок оно не даёт. К ошибкам приводят декогеренция и дефазировка. В определённом, грубом смысле их можно назвать "паразитным измерением", осуществляемым со стороны окружения (стенок прибора, волокна и тд). Видимо, эту мысль и закладывал автор.
(если не все)

Не все
Квантовая же криптография позволяет построить такую зашифрованную систему, которая всегда узнает, если ее попытаются прослушать

Квантовая криптография не есть производная от квантовых вычислений. Там даже принципы разные. Это независимая область квантовых технологий и квантовые компьютеры здесь не причём, ну вот вообще никак.
Вращение по оси z вверх соответствует значению 1 классического бита

Ничего подобного. Классическому значению 1 соответствует точка на северном полюсе, 0 — на южном. Остальное - суперпозиция.
Хадамард

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

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

Туннельный транзистор, спинтронные устройства и ещё ряд устройств тоже используют явления КМ, но квантовыми вычислителями не являются

Если очень просто

Парадокс кота Шрёдингера был придуман как раз таки для того, чтобы показать абсурдность идеи квантовой суперпозиции

Какой бы абсурдной она не была, но используется.

квантовые компьютеры здесь не причём

Опять же, с повсеместным распространением КК классическая криптография умрет, так что КК все таки имеют к этому отношение

очка на северном полюсе, 0 — на южном

Куда же упирается ось z.

"Адамар"

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

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

Какой бы абсурдной она не была, но используется.

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

Опять же, с повсеместным распространением КК классическая криптография умрет, так что КК все таки имеют к этому отношение

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

Куда же упирается ось z.

Вы пишете "вращение по оси z вверх". Я говорю, вращение тут не причём, до тех пор, пока не рассматривается эволюция во времени или вентиль. Всё проще - состояние кубита - это просто точка на сфере.

Некоторые же выглядят как придирки ради придирок.

Камон, такая была всего одна)

А если серьёзно, текст ваш, вам и карты в руки, моё дело указать на ошибки. Замечу, однако, что большинство из описанных ошибок работают против целей, ради которых написан этот материал, а именно целей просвещения. Мне не раз приходилось исправлять людям неверное понимание некоторых квантовых вещей, которое начиналось со слов "А я вот читал в одном месте. ".
Не стоит пренебрегать нюансами, многие из них формируют квантовое мировоззрение на глубинных уровнях. Взять тот же парадокс кота Шрёдингера. Вопрос суперпозиции состояний макрообъектов до сих пор является предметом спора, разделившего физиков на несколько лагерей и экспериментального конца ему пока не видно (я про интерпретации).
Я не из тех, кто любит говорить "Миша всё фигня, давай по новой". Ищите информацию, пишите, мы с вами по одну сторону баррикад. А мой провокационный тон призван лишь добавить эмоциональной мотивации к исправлению пробелов. Ну и плюсики собрать, куда уж без этого.

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

Добавил несколько замечаний по твоим комментариям

Так объяснение пар. Шрёдингера как раз в том, что создание подобного механизма коллапсирует всю волновую функцию и состояние кота становится классической механикой. Странно приводить это в роли примера.

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

Здравствуйте. А если создать "подвижный" код из двух спаренных фотонов. На базе принципа Паули. И иметь таким образом квантовый компьютер "холодного" типа. Извиняюсь. Чушь.? Можно же построить такой компьютер?

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

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

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

Это я извиняюсь. Это всё, что я понял из вопроса)

То есть если я сейчас составлю программку и встану в очередь, то какая-то морозная частичка из Мельбурна сможет мне взломать страничку бывшей на вк?

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

Читайте также: