company_banner

Демистификация принципов квантовых вычислений

Автор оригинала: Leo Whitehead
  • Перевод

«Думаю, я смело могу сказать, что квантовую механику никто не понимает», — Ричард Фейнман


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

В научно-популярных статьях опускаются описания квантовых систем и приводятся утверждения типа:

Обычный бит может быть равен «1» или «0», но кубит может быть одновременно равен «1» и «0».

Если вам сильно повезет (в чем я не уверен), то вам расскажут, что:

Кубит находится в суперпозиции между «1» и «0».

Ни одно из этих объяснений не выглядит правдоподобным, поскольку мы пытаемся сформулировать квантовомеханический феномен при помощи языковых средств, созданных в очень традиционном мире. Чтобы понятно объяснить принципы квантовых вычислений, необходимо применить другой язык — математический. 

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

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

Для начала давайте пробежимся по принципам цифровой логики. Она основана на использовании электрических схем для проведения вычислений. Чтобы сделать наше описание более абстрактным, упростим состояние электропровода до «1» или «0», что будет соответствовать состояниям «вкл» или «выкл». Выстроив транзисторы в определенной последовательности, мы создадим так называемые логические элементы, принимающие одно или несколько значений входных сигналов и преобразующие их в выходной сигнал на основе определенных правил булевой логики.


Распространенные логические элементы и таблицы их состояний


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

Как я уже упоминал ранее, нам необходим способ математического отображения цифровой логики. Для начала давайте представим математическую традиционную логику. С помощью линейной алгебры классические биты со значениями «1» и «0» можно представить в виде двух вектор-столбцов:

где цифры слева являются дираковскими обозначениями вектора. Представив наши биты таким образом, мы можем моделировать логические операции над битами с использованием векторных трансформаций. Обратите внимание: несмотря на то, что при использовании двух битов в логических элементах можно выполнять множество операций («И» (AND), «Не» (NOT), «Искл. Или» (XOR) и др.), при использовании одного бита возможно выполнение только четырех операций: тождественное преобразование, отрицание, вычисление константы «0» и вычисление константы «1». При тождественном преобразовании бит остается неизменным, при отрицании значение бита изменяется на противоположное (с «0» на «1» или с «1» на «0»), а вычисление константы «1» или «0» устанавливают бит в «1» или «0» вне зависимости от его предыдущего значения.

Identity
Тождественное преобразование
Negation
Отрицание
Constant-0
Вычисление константы «0»
Constant-1
Вычисление константы «1»

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



Прежде чем двинуться дальше, давайте обратимся к понятию обратимых вычислений, которое всего лишь подразумевает, что для обеспечения обратимости операции или логического элемента необходимо определить список значений входных сигналов на основании выходных сигналов и названий используемых операций. Таким образом можно заключить, что тождественное преобразование и отрицание являются обратимыми, а операции по вычислению констант «1» и «0» — нет. Благодаря унитарности квантовой механики квантовые компьютеры используют исключительно обратимые операции, поэтому на них мы и сосредоточимся. Далее мы преобразуем необратимые элементы в обратимые, чтобы обеспечить возможность их использования квантовым компьютером.

С помощью тензорного произведения отдельных битов можно представить множество битов:

Теперь, когда у нас имеются почти все необходимые математические представления, перейдем к нашему первому квантовому логическому элементу. Это оператор CNOT, или контролируемое «Не» (NOT), который имеет большое значение в обратимых и квантовых вычислениях. Элемент CNOT применяется к двум битам и возвращает два бита. Первый бит назначается «управляющим», а второй — «контрольным». Если управляющий бит установлен в «1», контрольный бит меняет своё значение; если управляющий бит установлен в «0», контрольный бит не изменяется.

Этот оператор может быть представлен в виде следующего вектора преобразования:

Чтобы продемонстрировать всё, с чем мы уже разобрались, я покажу варианты применения элемента CNOT в отношении множества битов:

Резюмируем уже сказанное: в первом примере мы раскладываем |10⟩ на части его тензорного произведения и используем матрицу CNOT для получения нового соответствующего состояния произведения; затем мы факторизуем его до |11⟩ в соответствии с приведенной ранее таблицей значений CNOT.

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

Если вы дочитали до этого места, то у меня для вас хорошая новость: кубиты легко можно выразить математически. В общем, если классический бит (cbit) может устанавливаться в |1⟩ или |0⟩, кубит просто находится в суперпозиции и до измерения может одновременно быть равен |0⟩ и |1⟩. После измерения он коллапсирует в |0⟩ или |1⟩. Иными словами, кубит можно представить в виде линейной комбинации |0⟩ и |1⟩ в соответствии с приведенной ниже формулой:

где a₀ и a₁ представляют, соответственно, амплитуды |0⟩ и |1⟩. Их можно рассматривать как «квантовые вероятности», которые представляют вероятность коллапсирования кубита в какое-либо из состояний после его измерения, поскольку в квантовой механике объект в суперпозиции коллапсирует в одно из состояний после фиксации. Разложим это выражение и получим следующее:

Чтобы упростить свое объяснение, именно этим представлением я буду пользоваться в настоящей статье.

Для этого кубита шанс коллапсирования в значение a₀ после измерения равен |a₀|², а шанс коллапсирования в значение a₁ равен |a₁|². Например, для следующего кубита:

шанс коллапсирования в «1» равен |1/ √2|², или ½, то есть 50/50.

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

Если вы знакомы с тригонометрией, то заметите, что это уравнение соответствует теореме Пифагора (a²+b²=c²), то есть мы можем графически представить возможные состояния кубита в виде точек на единичной окружности, а именно:

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

Прежде чем мы продолжим, я напомню, что значения амплитуд a₀ и a₁ на самом деле являются комплексными числами, поэтому состояние кубита наиболее точно можно отобразить на трехмерной единичной сфере, также известной как сфера Блоха:

Тем не менее, чтобы упростить объяснение, здесь мы ограничимся действительными числами.

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

Одним из самых важных операторов является «элемент Адамара»: он берет бит в состоянии «0» или «1» и ставит его в соответствующую суперпозицию с 50 %-шансом его коллапсирования в «1» или «0» после измерения. 

Обратите внимание, что в нижней правой части оператора Адамара присутствует отрицательное число. Это связано с тем, что результат применения оператора зависит от значения входного сигнала: — |1⟩ или |0⟩, и потому вычисление является обратимым.

Еще одним важным моментом, связанным с элементом Адамара, является его обратимость, то есть он может принимать кубит в соответствующей суперпозиции и преобразовать его в |0⟩ или |1⟩.

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

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

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

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

То есть, если мы начинаем с бита |0⟩, применяем инверсию бита, а затем — операцию Адамара, затем — еще одну инверсию бита, и еще раз — операцию Адамара, после чего — финальную инверсию бита, в итоге мы получаем вектор, приведенный в правой части цепи. Накладывая различные машины состояний друг на друга, мы сможем начинать с |0⟩ и отслеживать разноцветные стрелки, соответствующие каждого из преобразований, чтобы понять, как это всё работает.

Раз уж мы зашли так далеко, пришло время рассмотреть один из типов квантовых алгоритмов, а именно — алгоритм Дойча-Йожи, и показать его преимущество над классической вычислительной машиной. Стоит отметить, что алгоритм Дойча-Йожи является полностью детерминированным, то есть он возвращает правильный ответ в 100 % случаев (в отличие от многих других квантовых алгоритмов, основанных на вероятностном определении кубитов).

Давайте представим, что у вас есть черный ящик, который содержит функцию/оператор над одним битом (помните — при использовании одного бита возможно выполнение только четырех операций: тождественное преобразование, отрицание, вычисление константы «0» и вычисление константы «1»). Какая именно функция выполняется в ящике? Вы не знаете, какая, однако можете перебрать сколько угодно вариантов входных значений и оценить результаты на выходе.


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

В случае с классическим компьютером потребуется сделать 2 запроса для определения применяемой функции. Например, если при вводе «1» мы получаем на выходе «0», становится понятно, что используется либо функция вычисления константы «0», либо функция отрицания, после чего вам придется изменить значение входного сигнала на «0» и посмотреть, что получится на выходе.

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

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

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

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


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

Применив то же представление квантовой цепи, что мы использовали ранее, посмотрим, как можно реализовать каждый из четырех элементов (тождественное преобразование, отрицание, вычисление константы «0» и вычисление константы «1») с использованием квантовых операторов. 

Например, так можно реализовать функцию вычисления константы «0»:

Вычисление константы «0»:

Здесь нам вообще не нужны операторы. Первый входной кубит (который мы приняли равным |0⟩) возвращается с этим же значением, а второе входное значение возвращает само себя — как обычно.

С функцией вычисления константы «1» ситуация обстоит немного иначе:

Вычисление константы «1»:

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

При отображении оператора тождественного преобразования задача начинает усложняться. Вот как это можно сделать:

Тождественное преобразование:

Использованный здесь символ обозначает элемент CNOT: верхняя линия обозначает контрольный бит, а нижняя — управляющий. Напомню, что при использовании оператора CNOT значение контрольного бита меняется, если управляющий бит равен |1⟩, но остается неизменным, если управляющий бит равен |0⟩. Поскольку мы приняли, что значение верхней линии всегда равно |0⟩, то её значение всегда присваивается нижней линии.

Аналогичным образом действуем с оператором отрицания:

Отрицание:

Мы просто-напросто инвертируем бит в конце выходной линии.

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

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

Элемент Адамара повторно применяется к результату использования функции, чтобы вывести кубиты из суперпозиции и сделать алгоритм детерминированным. Мы запускаем систему в состоянии |00⟩ и по причинам, о которых я сейчас расскажу, получаем результат |11⟩, если применяемая функция является постоянной. Если же функция внутри черного ящика переменная, то после измерения система возвращает результат |01⟩.

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

Использовав оператор инверсии бита, а затем применив элемент Адамара к обоим входным значениям, равным |0⟩, мы обеспечим их перевод в одинаковую суперпозицию |0⟩ и |1⟩, а именно:

На примере передачи этого значения функции в черном ящике легко продемонстрировать, что обе функции постоянного значения дают на выходе |11⟩.

Вычисление константы «0»:

Аналогично, мы видим, что функция вычисления константы «1» также дает на выходе |11⟩, то есть:

Вычисление константы «1»:

Обратите внимание: на выходе оба значения будут равны |1⟩, поскольку -1² = 1.

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

Тождественное преобразование:

Поскольку CNOT является двухкубитным оператором, его нельзя представить в виде простой машины состояний, и потому необходимо определить два выходных сигнала на основании тензорного произведения обоих входных кубитов и умножения на матрицу CNOT по описанному ранее принципу:

С помощью этого метода мы также можем подтвердить получение на выходе значения |01⟩, если в черном ящике скрыта функция отрицания:

Отрицание:

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

Что же дальше?


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

Мое описание сложно назвать полноценным руководством по квантовым вычислениям и алгоритмам — это, скорее, краткое введение в математику и систему обозначений, призванное развеять у читателей навязываемые научно-популярными источниками представления о предмете (серьезно, многие действительно не могут разобраться в ситуации!). Я не успел затронуть многие важные темы — например, такие как квантовая запутанность кубитов, комплексность значений амплитуды |0⟩ и |1⟩ и функционирование различных квантовых логических элементов при трансформации сферой Блоха.

Если вы хотите систематизировать и структурировать свои знания о квантовых компьютерах, настоятельно рекомендую вам прочитать «Введение в квантовые алгоритмы» (An Introduction to Quantum Algorithms) Эммы Штрубель: несмотря на обилие математических формул, в этой книге квантовые алгоритмы рассматриваются куда более подробно.
Mail.ru Group
1 119,57
Строим Интернет
Поделиться публикацией

Комментарии 32

    0

    Позволите глупый вопрос?


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

    Как унитарность квантовых операторов связана с их обратимостью?

      +6

      У унитарной матрицы всегда есть обратная матрица. Применяя обратные операции в обратном порядке вы вернётесь в исходное состояние.

        0
        Детерминант унитарного преобразования по модулю равен единице (это, кажется, и есть определение унитарного преобразования). Для обратимости нужно чтобы детерминант был не ноль.
        +13

        Автор конечно старался объяснить пользу квантовых вычислений максимально понятно. Но, как мне кажется, всё равно не избежал ловушки с "троллейбусом из буханки хлеба". Хорошо что квантовые вычисления могут за одно измерение определить тип функции. Только вот зачем это делать? Как это можно использовать? И зачем изучать функцию в "чёрном ящике" вместо того, что бы вычислять известные функции?
        Ответов на эти вопросы автор не дал. И потому у меня, человека не обременённого знаниями о квантовых вычислениях, так и не сложилось до конца хотя бы одного фрагмента всей картины. Я только понял, что квантовые вычисления позволяют более эффективно делать "троллейбусы".

          +1
          Хорошо что квантовые вычисления могут за одно измерение определить тип функции. Только вот зачем это делать?


          Друг, определение типа функции — это просто пример, алгоритм Дойча. Если ты покуришь вики, ты набредешь на алгоритм Дойча-Йожи, потом алгоритм Саймона, а там уже и алгоритм Шора недалеко. А это быстрая факторизация чисел.

          Сейчас пример с определением типа функции не впечатляет. Ну, какая-то функция. Тривиальная. Вход-выход по биту, вообще не серьезно. А вот 34 года назад определение типа функции была прорывом. На классическом компе тип функции вычислялся за два применения черного ящика, а на квантовом — за одно. Первый пример квантового превосходства.

          Увы, нет простых примеров, на которых можно продемонстрировать «квантовое превосходство». Поэтому при любой попытке «разжевать» КВ народ использует Дойча с его вычислением типа функции.
            +2

            Вот польза алгоритма Шора мне больше понятна, чем Дойча. Я хотя бы знаю про задачу разложения на простые множители. А Дойч, в рамках этой статьи, для меня выглядит как: "мы специально подобрали такой бенчмарк, на котором наш процессор обгоняет всех конкурентов".
            Автор статьи хотел более понятно объяснить КВ, и вроде бы я даже всё понял в приведённой "математике". Только одно не понял из его примера с Дойчем — зачем это надо?
            Конечно же я знаю (по опыту школьной математики), что где-то "там" есть реальные и полезные задачи, которые хорошо решаются КВ. Но конкретно данная статья оставила у меня ощущение непонимания. Такое же ощущение, наверное, возникает у многих школьников, которым не достаточно наглядно объяснили где и как используются полученные ими знания.

              –6

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

                +1
                на текущий момент нет реальных и полезных задач

                Эти задачи знал еще Фейнман. В частности симуляция квантовомеханических систем, например для квантовой химии www.ncbi.nlm.nih.gov/pmc/articles/PMC2596249
                  +1

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


                  По поводу статьи, что Вы кинули. Безусловно, алгоритм полиномиальный, но Вы видели его временную сложность? Для симуляции системы из 4-5 атомов с весом не меньше 15 моль требуется порядка 10^12 квантовых вентилей для симуляции ОДНОГО ядерного шага. Этот алгоритм интересен больше с точки зрения теории, чем практики. Даже на классических машинах мы иногда отдаем предпочтение экспоненциальным алгоритмам перед полиномиальными.

                  0

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

                    0

                    Тогда Вам не составит труда привести хоть один пример индустриально важной проблемы, которую квантовые машины могут решить быстро (и это доказано! а не просто мечты Фейнмана 50-летней давности), а вот классический компьютер не может этого (тут уже можно без доказательств).


                    PS. К слову, ту статью, что мне кинули сверху, там полиномиальный алгоритм расчета положения атомов за один шаг image, но количество шагов может быть экспоненциальным, так как пространство дискретизировано на 2^(dn) "ячеек", где n — это количество кубитов, a d — размерность пространства. И каждый атом в процессе симуляции может менять свое положение в этой "решетке".


                    То есть рассчитать что-то здравое с таким алгоритмом все так же не выйдет. Да, он быстрей классических алгоритмов (полу-)квантовых расчетов. Но все равно неприменим. На данный момент этот алгоритм представляет собой чисто теоретический интерес.


                    PPS. Когда я писал, что алгоритм становится очень дорогим для атомов с молярной массой 15, я на самом деле имел в виду атомное число. Прошу прощения за ошибку.

                  +1
                  По крайней мере это доказывает, что существуют задачи, на которых квантовый компьютер лучше. Это уже важный факт. Скорее всего, если взять полезную задачу, то статья перешла бы из разряда «для новичков» в разряд «для тех, кто и так в теме»
                0
                Только вот зачем это делать? Как это можно использовать? И зачем изучать функцию в «чёрном ящике» вместо того, что бы вычислять известные функции?
                Ответов на эти вопросы автор не дал.

                Вроде и не обещал дать…
                Чтобы понятно объяснить принципы квантовых вычислений, необходимо применить другой язык — математический.

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

                Я приложу все усилия, чтобы рассказать обо всем этом понятным языком

                А что обещал вроде всё сделал… Ну по крайней мере я считаю что автор вполне попытался объяснить КВ понятным языком.
                  0
                  Я только понял, что квантовые вычисления позволяют более эффективно делать «троллейбусы».

                  Квантовые вычисления позволяют более эффективно решать задачи, которые лежат в классе сложности BQP. Считается, хотя это не доказано, что BQP>BPP в котором лежат задачи, которые могут эффективно решать обычные компьютеры (с источником случайности). Это значит, что существуют алгоритмы, которые квантовые компьютеры могут решать быстро, а остальные не могут. И сейчас несколько таких алгоритмов уже известны.
                    0

                    А Вы не приведете примеры проблем, которые квантовые компьютеры способны решать быстро, а вот классические машины этого не могут?

                      0
                      Можно ужаснуться посмотреть тут.
                        0

                        И какие из этих проблем гарантированно не имеют эффективного решения на классических компьютерах?

                          0
                          Первый же пример по ссылке, факторизация. O(n^3) операций для квантовых компьютеров, O(2^(n/3)). n^3 для 2048 бит это что-то около 8 миллиардов операций. Берем 200нс на двухкубитную операцию, умножаем на 2048^2 (для перевода двухкубитных операций в трансформации Фурье), получаем пару недель на факторизацю.

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

                            +1

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


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

                            Но это пока неизвестно. То что мы сейчас не можем быстро посчитать дискретный логарифм на обычном компьютере не означает, что эффективного алгоритма для классической машины не существует. Это значит, что он нам пока неизвестен, хотя и маловероятно, что он существует. Но тем не менее, пока не будет ДОКАЗАНО, что есть задача, которую квантовый компьютер решает эффективно, а классический — нет, до тех пор нельзя утверждать, будто


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

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

                      +1
                      Ну не совсем. Чтобы объяснить как оно работает, то достаточно узнать о позиционных системах счисления и научиться считать до 2х, в этом и есть простота современных компьютеров. А с квантовыми пока правда буханка-тролейбус.
                      Двоичные компьютеры спокойно объясняются таблицами истинности, по которым всё проверяется при минимальных знаниях арифметики, плюс это просто проверяется на обычном листе размером А4, переносится на краны с водой и выключатели-переключатели.
                    +2
                    >> чтобы упростить объяснение, здесь мы ограничимся действительными числами.
                    Ну вот :(
                      0
                      Скажите пожалуйста, все эти квантовые компьютеры что значат для обычных людей? Можно ли утверждать, что с появлением оного будет прорыв в ML? Появятся ИИ? Или наконец НПЦ в играх будут вести себя более осмысленно?
                        0

                        https://habr.com/ru/company/dentsuaegisnetworkrussia/blog/472760/ вот про машинное обучение. Если научимся сводить эти задачи к оптимизации, которая хорошо решается на адиабатических (частный случай аналоговых) машинах, то возможен хороший прирост эффективности вычислений, а если еще и развивать квантовые алгоритмы, то ящик будет все менее черным

                          0
                          Но это ведь для узкого круга людей, а для широкого круга людей, что это будет? Вот, купил я для дома квантовый ПК (если такое будущее наступит), что он мне даст? НПЦ в %game_name% будут умнее? Миссии будут генерироваться более интересно? Процедурно-сгенерированные карты/мобы будут выглядет лучше? Физика в играх/симуляторах будет ближе к реалистичной?
                            +1

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

                        +2

                        Это все, конечно, хорошо, но как эти все операции выглядят физически? Что мне такое нужно сотворить со спином электрона, чтобы к нему последовательно применить операцию Адамара, инверсию, неизвестную функцию и потом еще раз операцию Адамара?
                        Как выглядит CNOT-гейт в железе? Над чем он вообще оперирует?

                          +1
                          Если вам не особо принципиально, кубиты на электронах или фотонах, то например здесь обучают как «построить простейший квантовый компьютер на двух кубитах, переносимых фотонами, и запустить на нем алгоритм Дойча» ;)
                          0
                          За старания плюсик, но на главный для меня вопрос я так ответа и не нашел: каким образом квантовые свойства чем-то там нам помогают что-то там быстро высчитывать?
                            +1
                            На этот вопрос нет простого ответа. Самый прямолинейный способ: потратить пару недель и разобраться с алгоритмом Шора самостоятельно.
                            0
                            (Автору) извините, но ваш пост — это вот как данный известный мем:

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

                            Самое читаемое