Алгоритм Дойча–Йожи
Детерминированный квантовый алгоритм

Алгоритм Дойча–Йожи — это детерминированный квантовый алгоритм, предложенный Дэвидом Дойчем и Ричардом Йожой в 1992 году с улучшениями Ричарда Клива , Артура Экерта , Кьяры Маккиавелло и Микеле Моски в 1998 году. [1] [2] Несмотря на небольшую практическую пользу, это один из первых примеров квантового алгоритма, который экспоненциально быстрее любого возможного детерминированного классического алгоритма. [3]

Задача Дойча–Йожи специально разработана так, чтобы быть простой для квантового алгоритма и сложной для любого детерминированного классического алгоритма. Это задача черного ящика , которая может быть эффективно решена квантовым компьютером без ошибок, тогда как детерминированному классическому компьютеру потребовалось бы экспоненциальное число запросов к черному ящику для решения задачи. Более формально, она дает оракул, относительно которого EQP , класс задач, которые могут быть решены точно за полиномиальное время на квантовом компьютере, и P различны. [4]

Поскольку задача легко решается на вероятностном классическом компьютере, она не дает оракульного разделения с BPP , классом задач, которые могут быть решены с ограниченной ошибкой за полиномиальное время на вероятностном классическом компьютере. Задача Саймона является примером задачи, которая дает оракульное разделение между BQP и BPP .

Постановка проблемы

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

ф : { 0 , 1 } н → { 0 , 1 } {\displaystyle f\двоеточие \{0,1\}^{n}\rightarrow \{0,1\}}

Функция принимает n-битные двоичные значения в качестве входных данных и выдает либо 0, либо 1 в качестве выходных данных для каждого такого значения. Нам обещают , что функция либо постоянна (0 на всех входных данных или 1 на всех входных данных), либо сбалансирована (1 для ровно половины входной области и 0 для другой половины). [1] Затем задача состоит в том, чтобы определить, является ли она постоянной или сбалансированной, используя оракул. ф {\displaystyle f}

Классическое решение

Для обычного детерминированного алгоритма, где — число бит, в худшем случае потребуются оценки . Чтобы доказать, что является константой, необходимо оценить чуть более половины набора входов и найти их выходы идентичными (потому что функция гарантированно будет либо сбалансированной, либо постоянной, а не где-то посередине). Лучший случай имеет место, когда функция сбалансирована, а первые два выходных значения различны. Для обычного рандомизированного алгоритма достаточно постоянной оценки функции, чтобы получить правильный ответ с высокой вероятностью (неудачный с вероятностью ) . Однако оценки все еще требуются, если мы хотим получить ответ, в котором нет возможности ошибки. Квантовый алгоритм Дойча-Йожи дает ответ, который всегда верен, с одной оценкой . н {\displaystyle n} 2 н − 1 + 1 {\displaystyle 2^{n-1}+1} ф {\displaystyle f} ф {\displaystyle f} к {\displaystyle к} ϵ ≤ 1 / 2 к {\displaystyle \epsilon \leq 1/2^{k}} к ≥ 1 {\displaystyle k\geq 1} к = 2 н − 1 + 1 {\displaystyle k=2^{n-1}+1} ф {\displaystyle f}

История

Алгоритм Дойча–Йожи обобщает более раннюю (1985) работу Дэвида Дойча, которая предоставила решение для простого случая, когда . В частности, если задана булева функция, вход которой составляет один бит, , является ли она константой? [5] н = 1 {\displaystyle n=1}
ф : { 0 , 1 } → { 0 , 1 } {\displaystyle f:\{0,1\}\rightarrow \{0,1\}}

Алгоритм, как его изначально предложил Дойч, не был детерминированным. Алгоритм был успешным с вероятностью одна половина. В 1992 году Дойч и Йожа создали детерминированный алгоритм, который был обобщен до функции, принимающей биты на вход. В отличие от алгоритма Дойча, этот алгоритм требовал двух оценок функции вместо одной. н {\displaystyle n}

Дальнейшие усовершенствования алгоритма Дойча–Йожи были сделаны Клеве и др. [2], в результате чего был создан алгоритм, который является одновременно детерминированным и требует только одного запроса . Этот алгоритм до сих пор называют алгоритмом Дойча–Йожи в честь новаторских методов, которые они использовали. [2] ф {\displaystyle f}

Алгоритм

Для работы алгоритма Дойча-Йожи оракул, вычисляющий из , должен быть квантовым оракулом, который не декогерирует . В своих вычислениях он не может сделать копию , поскольку это нарушило бы теорему о запрете клонирования . Точка зрения алгоритма Дойча-Йожи как оракула означает, что неважно, что делает оракул, поскольку он просто должен выполнить обещанное преобразование. ф ( х ) {\displaystyle f(x)} х {\displaystyle x} х {\displaystyle x} х {\displaystyle x} ф {\displaystyle f}

Квантовая схема алгоритма Дойча-Йожсы

Алгоритм начинается с битового состояния . То есть, первые n битов находятся в состоянии , а последний бит — . К каждому биту применяется вентиль Адамара для получения состояния н + 1 {\displaystyle n+1} | 0 ⟩ ⊗ н | 1 ⟩ {\displaystyle |0\rangle ^{\otimes n}|1\rangle } | 0 ⟩ {\displaystyle |0\rangle } | 1 ⟩ {\displaystyle |1\rangle }

1 2 н + 1 ∑ х = 0 2 н − 1 | х ⟩ ( | 0 ⟩ − | 1 ⟩ ) {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )} ,

где пробегает все -битные строки, каждая из которых может быть представлена ​​числом от до . У нас есть функция, реализованная как квантовый оракул. Оракул отображает свое входное состояние в , где обозначает сложение по модулю 2. Применение квантового оракула дает; х {\displaystyle x} н {\displaystyle n} 0 {\displaystyle 0} 2 н − 1 {\displaystyle 2^{n}-1} ф {\displaystyle f} | х ⟩ | у ⟩ {\displaystyle |x\rangle |y\rangle } | х ⟩ | у ⊕ ф ( х ) ⟩ {\displaystyle |x\rangle |y\oplus f(x)\rangle } ⊕ {\displaystyle \oplus}

1 2 н + 1 ∑ х = 0 2 н − 1 | х ⟩ ( | 0 ⊕ ф ( х ) ⟩ − | 1 ⊕ ф ( х ) ⟩ ) {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle )} .

Для каждого из них есть либо 0, либо 1. Проверяя эти две возможности, мы видим, что указанное выше состояние равно х , ф ( х ) {\displaystyle x,f(x)}

1 2 н + 1 ∑ х = 0 2 н − 1 ( − 1 ) ф ( х ) | х ⟩ ( | 0 ⟩ − | 1 ⟩ ) {\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x )}|x\rangle (|0\rangle -|1\rangle )} .

На этом этапе последний кубит можно проигнорировать, и останется следующее: | 0 ⟩ − | 1 ⟩ 2 {\displaystyle {\frac {|0\rangle -|1\rangle {\sqrt {2}}}}

1 2 н ∑ х = 0 2 н − 1 ( − 1 ) ф ( х ) | х ⟩ {\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle } .

Далее мы пропустим каждый кубит через вентиль Адамара . Полное преобразование по всем кубитам можно выразить с помощью следующего тождества: н {\displaystyle n}

ЧАС ⊗ н | к ⟩ = 1 2 н ∑ дж = 0 2 н − 1 ( − 1 ) к ⋅ дж | дж ⟩ {\displaystyle H^{\otimes n}|k\rangle = {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1 }(-1)^{k\cdot j}|j\rangle }

( это сумма побитового произведения). Это приводит к дж ⋅ к = дж 0 к 0 ⊕ дж 1 к 1 ⊕ ⋯ ⊕ дж н − 1 к н − 1 {\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}

1 2 н ∑ х = 0 2 н − 1 ( − 1 ) ф ( х ) [ 1 2 н ∑ у = 0 2 н − 1 ( − 1 ) х ⋅ у | у ⟩ ] = ∑ у = 0 2 н − 1 [ 1 2 н ∑ х = 0 2 н − 1 ( − 1 ) ф ( х ) ( − 1 ) х ⋅ у ] | у ⟩ {\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle } .

Из этого мы видим, что вероятность измерения состояния равна к {\displaystyle к}

| 1 2 н ∑ х = 0 2 н − 1 ( − 1 ) ф ( х ) ( − 1 ) х ⋅ к | 2 {\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot k}\right|^{2}}

Вероятность измерения , соответствующая , равна k = 0 {\displaystyle k=0} | 0 ⟩ ⊗ n {\displaystyle |0\rangle ^{\otimes n}}

| 1 2 n ∑ x = 0 2 n − 1 ( − 1 ) f ( x ) | 2 {\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}

который оценивается как 1, если является постоянным ( конструктивная интерференция ) и 0, если является сбалансированным ( деструктивная интерференция ). Другими словами, окончательное измерение будет (все нули) тогда и только тогда, когда является постоянным, и даст некоторое другое состояние, если является сбалансированным. f ( x ) {\displaystyle f(x)} f ( x ) {\displaystyle f(x)} | 0 ⟩ ⊗ n {\displaystyle |0\rangle ^{\otimes n}} f ( x ) {\displaystyle f(x)} f ( x ) {\displaystyle f(x)}

Алгоритм Дойча

Алгоритм Дойча является частным случаем общего алгоритма Дойча–Йожи, где n = 1 в . Нам нужно проверить условие . Это эквивалентно проверке (где — сложение по модулю 2, которое также можно рассматривать как квантовый вентиль XOR, реализованный как управляемый вентиль NOT ), если ноль, то константа, в противном случае константа не является. f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}} f ( 0 ) = f ( 1 ) {\displaystyle f(0)=f(1)} f ( 0 ) ⊕ f ( 1 ) {\displaystyle f(0)\oplus f(1)} ⊕ {\displaystyle \oplus } f {\displaystyle f} f {\displaystyle f}

Мы начинаем с двухкубитного состояния и применяем вентиль Адамара к каждому кубиту. Это дает | 0 ⟩ | 1 ⟩ {\displaystyle |0\rangle |1\rangle }

1 2 ( | 0 ⟩ + | 1 ⟩ ) ( | 0 ⟩ − | 1 ⟩ ) . {\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}

Нам дана квантовая реализация функции , которая отображается на . Применяя эту функцию к нашему текущему состоянию, получаем f {\displaystyle f} | x ⟩ | y ⟩ {\displaystyle |x\rangle |y\rangle } | x ⟩ | f ( x ) ⊕ y ⟩ {\displaystyle |x\rangle |f(x)\oplus y\rangle }

1 2 ( | 0 ⟩ ( | f ( 0 ) ⊕ 0 ⟩ − | f ( 0 ) ⊕ 1 ⟩ ) + | 1 ⟩ ( | f ( 1 ) ⊕ 0 ⟩ − | f ( 1 ) ⊕ 1 ⟩ ) ) {\displaystyle {\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))}
= 1 2 ( ( − 1 ) f ( 0 ) | 0 ⟩ ( | 0 ⟩ − | 1 ⟩ ) + ( − 1 ) f ( 1 ) | 1 ⟩ ( | 0 ⟩ − | 1 ⟩ ) ) {\displaystyle ={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))}
= ( − 1 ) f ( 0 ) 1 2 ( | 0 ⟩ + ( − 1 ) f ( 0 ) ⊕ f ( 1 ) | 1 ⟩ ) ( | 0 ⟩ − | 1 ⟩ ) . {\displaystyle =(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).}

Мы игнорируем последний бит и глобальную фазу и поэтому имеем состояние

1 2 ( | 0 ⟩ + ( − 1 ) f ( 0 ) ⊕ f ( 1 ) | 1 ⟩ ) . {\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}

Применяя к этому состоянию вентиль Адамара, мы имеем

1 2 ( | 0 ⟩ + | 1 ⟩ + ( − 1 ) f ( 0 ) ⊕ f ( 1 ) | 0 ⟩ − ( − 1 ) f ( 0 ) ⊕ f ( 1 ) | 1 ⟩ ) {\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )}
= 1 2 ( ( 1 + ( − 1 ) f ( 0 ) ⊕ f ( 1 ) ) | 0 ⟩ + ( 1 − ( − 1 ) f ( 0 ) ⊕ f ( 1 ) ) | 1 ⟩ ) . {\displaystyle ={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).}

f ( 0 ) ⊕ f ( 1 ) = 0 {\displaystyle f(0)\oplus f(1)=0} если и только если мы измеряем и если и только если мы измеряем . Таким образом, мы с уверенностью знаем, является ли константой или сбалансированной. | 0 ⟩ {\displaystyle |0\rangle } f ( 0 ) ⊕ f ( 1 ) = 1 {\displaystyle f(0)\oplus f(1)=1} | 1 ⟩ {\displaystyle |1\rangle } f ( x ) {\displaystyle f(x)}

Реализация Qiskit алгоритма Дойча – Йожи

Ниже приведен простой пример того, как алгоритм Дойча–Йожи может быть реализован на Python с использованием Qiskit , среды разработки программного обеспечения для квантовых вычислений с открытым исходным кодом от IBM. Мы пройдемся по каждой части кода шаг за шагом, чтобы показать, как он преобразует теорию в работающую квантовую схему.

1. Импортировать необходимые библиотеки

из  qiskit  импорт  QuantumCircuit ,  транспилирование из  qiskit_aer  импорт  Aer

2. Определить вспомогательные функции для создания оракулов

def  create_constant_oracle ( n_qubits ,  output ): """  Создает «константный» оракул.  Если `output` равен 0, оракул всегда возвращает 0.  Если `output` равен 1, оракул всегда возвращает 1. Args:  n_qubits (int): Количество входных кубитов.  output (int): Постоянное выходное значение функции (0 или 1). Возвращает:  QuantumCircuit: квантовая схема, реализующая константный оракул.  """  oracle  =  QuantumCircuit ( n_qubits  +  1 ) # Если оракул всегда должен выводить 1, мы инвертируем "выходной" кубит  # с помощью X-вентиля (представьте его как вентиль НЕ на кубите).  if  output  ==  1 :  oracle . x ( n_qubits ) обратный  оракулdef  create_balanced_oracle ( n_qubits ): """  Создает «сбалансированный» оракул.  Половина входных битовых комбинаций выводит 0, а другая половина выводит 1. Для демонстрации эта функция реализует простую сбалансированную функцию,  помещая X-вентили на первый кубит входа в качестве элемента управления,  инвертируя выходной кубит для половины входов. Аргументы:  n_qubits (int): Количество входных кубитов. Возвращает:  QuantumCircuit: квантовая схема, реализующая сбалансированный оракул.  """  oracle  =  QuantumCircuit ( n_qubits  +  1 ) # Мы будем использовать простой шаблон: если первый кубит равен 1, инвертируем выход.  # Это означает, что для половины возможных входов выход меняется.  oracle . cx ( 0 ,  n_qubits ) обратный  оракул

3. Функция сборки схемы Дойча-Йожи

def  deutsch_jozsa_circuit ( oracle ,  n_qubits ): """  Собирает полную квантовую схему Дойча-Йожи.  Схема выполняет следующие шаги:  1. Запускает все «входные» кубиты в |0>.  2. Запускает «выходной» кубит в |1>.  3. Применяет вентили Адамара ко всем кубитам.  4. Применяет оракул.  5. Снова применяет вентили Адамара к входным кубитам.  6. Измеряет входные кубиты. Args:  oracle (QuantumCircuit): Схема, кодирующая «загадочную» функцию f(x).  n_qubits (int): Количество входных кубитов. Возвращает:  QuantumCircuit: Полная схема Дойча-Йожи, готовая к запуску.  """  # Общее количество n_qubits для ввода, плюс 1 для выходного кубита  dj_circuit  =  QuantumCircuit ( n_qubits  +  1 ,  n_qubits ) # 1. Входные кубиты уже установлены в |0>.  # 2. Выходной кубит установлен в |1>. Мы достигаем этого с помощью X-вентиля.  dj_circuit . x ( n_qubits ) # 3. Применить вентили Адамара ко всем кубитам (вход + выход).  для  кубита  в  диапазоне ( n_qubits  +  1 ):  dj_circuit . h ( qubit ) # 4. Добавить схему оракула.  ​​dj_circuit . compose ( oracle ,  inplace = True ) # 5. Применить вентили Адамара снова ТОЛЬКО к входным кубитам.  для  кубита  в  диапазоне ( n_qubits ):  dj_circuit . h ( qubit ) # 6. Наконец, измерьте входные кубиты.  для  кубита  в  диапазоне ( n_qubits ):  dj_circuit . measure ( qubit ,  qubit ) вернуть  dj_circuit

4. Собираем все вместе, чтобы проверить константу против сбалансированной

def  run_deutsch_jozsa_test ( n_qubits ,  oracle_type = 'constant' ,  constant_output = 0 ): """  Создает и запускает схему Дойча-Йожи для постоянного оракула  или сбалансированного оракула, затем выводит результаты.  Args:  n_qubits (int): Количество входных кубитов.  oracle_type (str): Указывает тип оракула, «константный» или «сбалансированный».  constant_output (int): Если оракул константный, определяет, возвращает ли он 0 или 1.  """  # Создать выбранный оракул  if  oracle_type  ==  'constant' :  oracle  =  create_constant_oracle ( n_qubits ,  constant_output )  print ( f "Использование КОНСТАНТНОГО оракула, который всегда возвращает { constant_output } " )  else :  oracle  =  create_balanced_oracle ( n_qubits )  print ( "Использование СБАЛАНСИРОВАННОГО оракула." ) # Создаем схему Дойча-Йожи  dj_circ  =  deutsch_jozsa_circuit ( oracle ,  n_qubits ) # Нарисуйте схему для визуального  отображения ( dj_circ . draw ())  # Используйте бэкэнд симулятора для запуска схемы simulator  =  Aer.get_backend ( ' aer_simulator ' ) transpiled_circ = transpile ( dj_circ , simulator ) job = simulator.run ( transpiled_circ , shots = 1 ) result = job.result ( ) counts = result.get_counts ( transpiled_circ )               print ( "Результаты измерений:" ,  counts ) # Интерпретировать измерение  # Если все измеренные биты равны 0 (например, '000' для 3 кубитов), то  # функция постоянна. В противном случае она сбалансирована.  measured_result  =  max ( counts ,  key = counts . get )  # Наиболее вероятный результат  , если  measured_result  ==  '0'  *  n_qubits :  print ( "Вывод: f(x) КОНСТАНТА." )  else :  print ( "Вывод: f(x) СБАЛАНСИРОВАНА." )

5. Примеры запусков

# Тест с 3 кубитами run_deutsch_jozsa_test ( n_qubits = 3 ,  oracle_type = 'constant' ,  constant_output = 0 )печать ( " \n "  +  "=" * 50  +  " \n " )run_deutsch_jozsa_test ( n_qubits = 3 ,  oracle_type = 'balanced' )

Выход:

Использование КОНСТАНТНОГО оракула, который всегда возвращает 0 ┌───┐┌───┐┌─┐ q_0: ┤ Ч ├┤ Ч ├┤М├────── ├───┤├───┤└╥┘┌─┐ q_1: ┤ Н ├┤ Н ├─╫─┤М├─── ├───┤├───┤ ║ └╥┘┌─┐q_2: ┤ Ч ├┤ Ч ├─╫──╫─┤М├ ├───┤├───┤ ║ ║ └╥┘q_3: ┤ Х ├┤ Ч ├─╫──╫──╫─ └───┘└───┘ ║ ║ ║с: 3/═══════════╩══╩══╩═ 0 1 2Результаты измерений: {'000': 1}Вывод: f(x) — ПОСТОЯННАЯ.===============================================Использование СБАЛАНСИРОВАННОГО оракула. ┌───┐ ┌───┐ ┌─┐q_0: ┤ Ч ├───────■──┤ Ч ├───┤М├ ├───┤┌───┐ │ └┬─┬┘ └╥┘q_1: ┤ H ├┤ H ├──┼───┤M├─────╫─ ├───┤├───┤ │ └╥┘ ┌─┐ ║q_2: ┤ H ├┤ H ├──┼────╫──┤M├─╫─ ├───┤├───┤┌─┴─┐ ║ └╥┘ ║q_3: ┤ X ├┤ H ├┤ X ├──╫───╫──╫─ └───┘└───┘└───┘ ║ ║ ║с: 3/═════════════════╩═══╩══╩═ 1 2 0Результаты измерения: {'001': 1}Вывод: f(x) СБАЛАНСИРОВАНА.

Пояснение к коду

1. Импорт библиотек

Мы используем основные элементы Qiskit:

  • QuantumCircuitдля создания квантовых схем
  • Aer, transpileи runзапустить нашу схему на классическом симуляторе

2. Создание Оракулов

  • Константный оракул : возвращает одно и то же значение (0 или 1) для каждого возможного ввода. В коде мы переворачиваем выходной кубит, если оракул должен всегда возвращать 1.
  • Сбалансированный Oracle : возвращает 0 для половины входов и 1 для другой половины. В нашем примере используется CNOTвентиль ( cx), который переворачивает выходной кубит, когда первый входной кубит равен 1.

3. Строительство трассы Дойч-Йожа

  1. Начинаем со всех входных кубитов в состоянии . Выходной кубит переводится в состояние с помощью X-вентиля. | 0 ⟩ {\displaystyle \vert 0\rangle } | 1 ⟩ {\displaystyle \vert 1\rangle }
  2. Применяем вентили Адамара ( dj_circuit.h(qubit)) ко всем кубитам. Напомним, что вентиль Адамара распределяет амплитуды «равномерно» между и , создавая суперпозиции. | 0 ⟩ {\displaystyle \vert 0\rangle } | 1 ⟩ {\displaystyle \vert 1\rangle }
  3. Подключаем схему оракула, которая изменяет выходной кубит в соответствии с функцией (f).
  4. Мы снова применяем вентиль Адамара только к входным кубитам, вызывая интерференционную картину, которая покажет, является ли (f) постоянным или сбалансированным.
  5. Наконец, мы измеряем все входные кубиты.

4. Интерпретация результатов

  1. Если (f) является постоянным , схема выдает выходной сигнал (все нули в измерении) с вероятностью 100%. | 0...0 ⟩ {\displaystyle \vert 0...0\rangle }
  2. Если (f) сбалансировано , мы ожидаем увидеть любую другую закономерность в измерении (т.е. не все нули).

5. Запуск алгоритма

Мы запускаем схему с помощью встроенного в Aer aer_simulator. Поскольку алгоритму Deutsch–Jozsa требуется только одно выполнение (один набор выстрелов), чтобы со 100% уверенностью отличить константу от сбалансированной, запуск нескольких выстрелов всегда даст тот же результат.

Почему он быстрее классического детерминированного компьютера

Классически вам, возможно, придется «вызвать» функцию (f) (наш «таинственный» черный ящик) много раз — потенциально до раз — чтобы быть абсолютно уверенным, является ли она постоянной или сбалансированной. Однако квантовую версию этой проблемы можно решить всего одним вызовом оракула плюс несколькими дополнительными квантовыми вентилями. Хотя сам Дойч-Йожа считается скорее «учебным примером», чем практическим применением, он демонстрирует одну из ключевых идей квантовых алгоритмов: использование суперпозиции и интерференции для значительного сокращения количества требуемых вызовов функций. 2 n − 1 + 1 {\displaystyle 2^{n-1}+1}

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

Ссылки

  1. ^ ab Дэвид Дойч и Ричард Йожа (1992). «Быстрые решения проблем с помощью квантовых вычислений». Труды Лондонского королевского общества A. 439 ( 1907): 553– 558. Bibcode :1992RSPSA.439..553D. CiteSeerX  10.1.1.655.5997 . doi :10.1098/rspa.1992.0167. S2CID  121702767.
  2. ^ abc R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). «Квантовые алгоритмы снова». Труды Королевского общества Лондона A . 454 (1969): 339– 354. arXiv : quant-ph/9708016 . Bibcode :1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID  16128238.
  3. ^ Саймон, Дэниел (ноябрь 1994 г.). «О силе квантовых вычислений». Труды 35-го ежегодного симпозиума по основам компьютерной науки . стр.  116–123 . doi :10.1109/SFCS.1994.365701. ISBN 0-8186-6580-7. S2CID  7457814.
  4. ^ Йоханссон, Н.; Ларссон, Й. (2017). «Эффективное классическое моделирование алгоритмов Дойча–Йожи и Саймона». Quantum Inf Process (2017) . 16 (9): 233. arXiv : 1508.05027 . Bibcode : 2017QuIP...16..233J. doi : 10.1007/s11128-017-1679-7. S2CID  28670540.
  5. ^ Дэвид Дойч (1985). «Квантовая теория, принцип Чёрча-Тьюринга и универсальный квантовый компьютер». Труды Лондонского королевского общества A. 400 ( 1818): 97– 117. Bibcode : 1985RSPSA.400...97D. CiteSeerX 10.1.1.41.2382 . doi : 10.1098/rspa.1985.0070. S2CID  1438116. 
  • Лекция Дойча об алгоритме Дойча-Йожи
Retrieved from "https://en.wikipedia.org/w/index.php?title=Deutsch–Jozsa_algorithm&oldid=1273031260"