<jupyter_start><jupyter_text>Алгоритм поиска квантового блуждания Квантовые блуждания представляют собой квантовую эквивалентность классической цепи Маркова и стали ключевыми во многих квантовых алгоритмах. В этом разделе мы реализуем алгоритм поиска квантового блуждания, который находит отмеченные элементы в графе. Алгоритм имеет квадратичное ускорение по сравнению со своим классическим аналогом. 1.Классические цепи Маркова<NAME> — это стохастический процесс, часто используемый для моделирования реальных процессов. Он состоит из состояний и связанных с ними вероятностей перехода, которые описывают вероятности перехода между состояниями на каждом временном шаге. В цепях Маркова с дискретным временем, с которыми мы здесь работаем, временные шаги дискретны. Цепи Маркова удовлетворяют свойству Маркова, что означает, что следующий шаг процесса зависит только от текущего, а не от любого из предыдущих шагов. Цепь Маркова имеет связанную матрицу перехода P, которая описывает вероятность перехода между каждым из состояний. Ниже мы показываем пример цепи Маркова и связанной с ней переходной матрицы $P$. \begin{equation} P= \begin{pmatrix} 0,1 &amp; 0,3 &amp; 0,3\ 0,1 &amp; 0,1 &amp; 0,2 \ 0,8 &amp; 0,6 &amp; 0,5 \end{pmatrix} \label{eq:matrix_example} \end{equation}Учитывая матрицу перехода $P$, мы можем получить распределение вероятностей после $t$ временных шагов по $P^t$. 2. Квантовые прогулкиКвантовые блуждания — это квантовый эквивалент классической цепи Маркова. Из-за суперпозиции квантовое блуждание будет проходить по всем возможным путям одновременно, пока мы не измерим цепь. Из-за квантовой интерференции некоторое состояние уравновешивается. Это делает алгоритмы квантового блуждания быстрее классических, поскольку мы можем спроектировать их таким образом, чтобы неправильные ответы быстро исключались. Существуют две распространенные модели квантовых блужданий, придуманные квантовые блуждания и квантовые блуждания Сегеди, которые эквивалентны при определенных обстоятельствах. Придуманное квантовое блуждание — это блуждание по вершинам графа, в то время как квантовое блуждание Сегеди происходит по ребрам. Прежде чем мы покажем, как мы можем реализовать квантовое блуждание, мы представим обе модели.$\newcommand{\ket}[1]{\left|{1}\right\rangle}$ $\newcommand{\bra}[1]{\left\langle {1}\right|}$ 2. Придуманные квантовые блужданияПростым примером придуманного квантового блуждания является блуждание по бесконечной целочисленной прямой. В этом случае мы представляем позицию ходока целым числом ${\ket{j} : j \in \mathbb{Z} }$, поскольку ходок может пройти все целые числа в $\mathbb{Z}$. Монета решает, как должен двигаться ходячий. В целочисленной строке ходок может идти как влево, так и вправо. Таким образом, вычислительная база монеты ${\ket{0}, \ket{1}}$, и мы двигаем ходунка в одном направлении, если монета $\ket{0}$, и в другом направлении, если монета составляет $\ket{1}$.Придуманный квант — это обход узлов в графе, и мы называем узлы состояниями. Ходок может перемещаться между состояниями, связанными с ребром. В модели монеты у нас есть два квантовых состояния и два оператора. Первое состояние — это состояние положения, которое представляет положение ходока. Для приведенного выше обхода это целое число, поскольку ходок может находиться в любом месте целочисленной строки. Другое состояние — состояние монеты. Состояние монеты определяет, как ходячий должен двигаться на следующем шаге. Мы можем представить как состояние монеты, так и состояние позиции векторами в гильбертовом пространстве. Если мы можем выразить состояние монеты вектором из $\mathcal{H}_C$, а состояние позиции - вектором из $\mathcal{H}_P$, мы можем выразить квантовое пространство для всего ходунка как $\mathcal {H} = \mathcal{H}_C \otimes \mathcal{H}_P$.Как мы уже упоминали, в модели также есть два оператора; оператор монеты $C$ и оператор сдвига $S$. Оператор монеты действует на $\mathcal{H}_C$ на каждом временном шаге и помещает ходячего в суперпозицию, так что он проходит все возможные пути одновременно. Для обхода целочисленной линии это означает, что она движется как влево, так и вправо на каждом временном шаге. Существуют разные операторы монет, но наиболее распространенными являются монета Адамара и монета Гровера. <NAME> — это ворота Адамара, которые помещают ходячего в равную суперпозицию:\begin{equation} H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 &amp; 1 \ 1 &amp; -1 \end{bmatrix} \end{equation}Монета Гровера — это оператор диффузии Гровера из алг<NAME>. Мы определяем его как\begin{equation} G = \begin{bmatrix} \frac{2}{n} -1 &amp; \frac{2}{n} &amp; \ldots &amp; \frac{2}{n}\ \frac{2}{ n} &amp; \frac{2}{n} - 1 &amp; \ldots &amp; \frac{2}{n} \ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \ \frac{2}{n} &amp; \frac{ 2}{n} &amp; \ldots &amp; \frac{2}{n} -1 \end{bmatrix} \end{уравнение}Как и монета Адамара, монета Гровера помещает ходячего в суперпозицию. Однако ведет себя немного по-другому. Если мы применим монету Гровера к пешеходу в позиции $\ket{000}$, мы получим вероятности вектора состояния, показанные на рисунке ниже. Как мы видим, монета не ставит ходока в равную суперпозицию, как это делает монета Адамара. Вместо этого $\ket{000}$ имеет гораздо большую вероятность, чем другие состояния.Другой оператор в модели, оператор сдвига, действует на $\mathcal{H}_P$ и перемещает обходчик на следующую позицию. Для обхода целочисленной строки оператор сдвига перемещает ходок слева от монеты $\ket{0}$ и справа, если монета $\ket{1}$:\begin{уравнение} S \ket{0}\ket{j} = \ket{0}\ket{j+1} \end{уравнение}\begin{equation} S \ket{1}\ket{j} = \ket{1}\ket{j-1} \end{equation}С оператором сдвига, определенным выше, мы можем представить один шаг придуманного кванта как унитарный оператор $U$, заданный \begin{equation} U = SC, \end{equation}где C — монетный оператор. Для квантового блуждания по целочисленной строке мы используем монету Адамара, но C может быть монетой Адамара, монетой Гровера или любым другим оператором монеты.Мы также можем смотреть на несколько шагов вперед. Мы можем выразить квантовое состояние $\ket{\psi}$ после $t$ временных шагов как \begin{equation} \ket{\psi (t)} = U^t \ket{\psi(0)}, \ end{equation} где $\ket{\psi(0)}$ — начальное состояние, а U — оператор одного шага блуждания [1].Придуманные квантовые блуждания больше всего подходят для регулярных графов, графов, в которых все узлы имеют одинаковое количество соседей [2]. Альтернативной моделью квантового блуждания, которая более удобна для нерегулярных графов, является модель Сегеди, которую мы рассмотрим далее. 2.B Квантовая прогулка СегедиВ то время как придуманное блуждание — это блуждание по узлам графа, блуждание Сегеди — это блуждание по ребрам двудольного двойного покрытия исходного графа. Граф с двойным покрытием — это граф, в котором вершин в два раза больше, чем в исходном графе. Две вершины в двудольном графе с двойным покрытием связаны ребром тогда и только тогда, когда вершины также связаны в исходном графе. Чтобы создать эту модель, мы начнем с матрицы вероятности перехода P для классического блуждания. Как описано в разделе 1, мы представляем классическое случайное блуждание с дискретным временем переходной матрицей $P$. Для любого $N$-вершинного графа с $N \times N$ матрицей перехода $P$ мы можем определить соответствующее квантовое блуждание с дискретным временем как унитарную операцию в гильбертовом пространстве $\mathcal{H}^N \otimes \ математический{H}^N$. Пусть $P_{jk}$ определяет вероятность того, что мы совершим переход из состояния $j$ в $k$. Прежде чем мы определим блуждание, мы определим нормализованные состояния\begin{equation} \ket{\psi_j} := \sum_{k=1}^N \sqrt{P_{kj}} \ket{j,k}, ; j=1,...,N \end{уравнение}и проекцию на ${\ket{\psi_j}}:j=1,...,N$\begin{equation} \Pi := \sum_{j=1}^N \ket{\psi_j} \bra{\psi_j} \label{eq:sz_pi} \end{equation}Введем также оператор сдвига S:\begin{equation} S := \sum_{j,k=1}^N \ket{j,k} \bra{k,j} \label{eq:sz_s} \end{equation}С $S$ и $\Pi$, определенными выше, мы можем ввести один шаг квантового блуждания с дискретным временем:\begin{уравнение} U := S(2 \Pi - 1), \label{eq:sz_op} \end{уравнение}где $(2\Pi - 1)$ — оператор отражения. Мы также определяем $t$ шагов обхода как $U^t$ [2]. 2.C Эквивалентность придуманных квантовых блужданий и квантовых блужданий СегедиИзвестно, что придуманная прогулка с монетой Гровера эквивалентна квантовой прогулке Сегеди. За более подробной информацией мы отсылаем к этой статье [3] Томаса Г. Вонга, где он также показывает эквивалентность между операторами в двух моделях. 3. Пример: реализация квантового блуждания по гиперкубуГиперкуб — это $n$-мерный аналог трехмерного куба. Все узлы имеют степень $n$, всего гиперкуб имеет $N=2^n$ узлов. Мы можем представить узлы гиперкубического графа наборами из $n$ двоичных чисел. Двоичное представление соседей узла будет отличаться только одним двоичным числом. Например, в четырехмерном гиперкубе соседями $0000$ являются $0001$, $0010$, $0100$ и $1000$. Таким образом, узел соединен со всеми узлами, до которых расстояние Хэмминга равно 1. Ребра также помечены. Два соседних узла, различающихся битом a:, соединены ребром, помеченным $a$.Гильбертово пространство, представляющее придуманное квантовое блуждание по гиперкубу, имеет вид $\mathcal{H} = \mathcal{H}^n \otimes \mathcal{H}^{2^n}$, где $\mathcal{H}^n $ обозначает место для монет, а $\mathcal{H}^{2^n}$ - положение ходока. Расчетная база\begin{equation} \big{ \ket{a,\vec{v}}, 0 \leq a \leq n-1, \vec{v} \in {(00...00), (00.. .01), ....., (11...11 )} \big}. \end{уравнение}Значение вычислительного базиса монеты $a$, связанное с ребром $a$, определяет, куда должен двигаться ходок. Если $a=0$, обходчик перейдет к узлу, где первое двоичное значение отличается от текущего узла. Если $a=1$, ходок перейдет к узлу, в котором второе значение отличается от текущего, и так далее. Пусть $\vec{e}_a$ — n-кортеж, в котором все двоичные значения, кроме значения с индексом $a$, равны $0$. Тогда оператор сдвига $S$ переводит ходок из состояния $\ket{a} \ket{\vec{v}}$ в $\ket{\vec{v} \oplus \vec{e}_a}$:\begin{equation} S \ket{a} \ket{\vec{v}} = \ket{a} \ket{\vec{v} \oplus \vec{e}_a}. \end{уравнение}Для этой прогулки мы используем монету Гровера $G$. Таким образом, оператор эволюции\begin{уравнение} U = SG. \end{уравнение}Теперь мы покажем, как мы можем реализовать квантовое блуждание по 4-мерному гиперкубу. Нам нужно реализовать оператор монеты и оператор сдвига. Начнем с импорта всех необходимых библиотек из Qiskit.<jupyter_code># Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ, QuantumRegister, ClassicalRegister
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from qiskit.circuit.library import QFT
from numpy import pi
from qiskit.quantum_info import Statevector
from matplotlib import pyplot as plt
import numpy as np
# Loading your IBM Q account(s)
provider = IBMQ.load_account()<jupyter_output><empty_output><jupyter_text>Схема будет иметь 6 кубитов, 4 из которых представляют позицию, а 2 — монету. Как мы упоминали ранее, монета — это монета Гровера, которая является диффузором в алгоритме Гровера. Начнем с реализации этого.<jupyter_code>one_step_circuit = QuantumCircuit(6, name=' ONE STEP') 
# Coin operator
one_step_circuit.h([4,5])
one_step_circuit.z([4,5])
one_step_circuit.cz(4,5)
one_step_circuit.h([4,5])
one_step_circuit.draw()<jupyter_output><empty_output><jupyter_text>Теперь давайте реализуем оператор сдвига. Мы знаем, что ходок может двигаться только к соседним узлам, а все соседние узлы отличаются всего одним битом. Мы хотим переместить ходок в соответствии с монетой, и мы перемещаем ходок, применяя вентиль НЕ к одному из кубитов узла. Если монета находится в состоянии $\ket{11}$, мы переводим ходок в состояние, в котором отличается кубит первого узла. Если монета равна $\ket{10}$ или $\ket{01}$, ходок переходит в состояние, в котором второй и третий кубит соответственно различаются. Наконец, если монета Гровера равна $\ket{00}$, мы переворачиваем четвертый кубит. Мы реализуем это с помощью CCNOT- и NOT-гейтов после монеты Гровера. Вместе они представляют собой один шаг квантового блуждания по 4-мерному гиперкубу.<jupyter_code># Shift operator function for 4d-hypercube
def shift_operator(circuit):
    for i in range(0,4):
        circuit.x(4)
        if i%2==0:
            circuit.x(5)
        circuit.ccx(4,5,i)

shift_operator(one_step_circuit)

one_step_gate = one_step_circuit.to_instruction() 
one_step_circuit.draw()<jupyter_output><empty_output><jupyter_text>4. Алгоритм поиска квантового блужданияТеперь мы реализуем алгоритм поиска квантового блуждания, который находит отмеченную вершину в графе. Сначала опишем алгоритм, затем пройдемся по его реализации. Алгоритм квантового блуждания решает задачу поиска помеченных вершин в графе с помощью квантового блуждания. То есть мы помечаем некоторый набор вершин $|M|$, начинаем с произвольного узла графа и движемся по обходу, пока не найдем отмеченные узлы. Базисные состояния в алгоритме поиска квантового блуждания имеют два регистра, один из которых соответствует текущему узлу, а другой — предыдущему узлу. То есть базисные состояния соответствуют ребрам графа. Обозначим квантовое блуждание на основе классической цепи Маркова с переходной матрицей $P$ унитарной операцией $W(P)$ на $\mathcal{H}$. Мы также определяем $\ket{p_x} = \sum_y \sqrt{P_{xy}}\ket{y}$ как равномерную суперпозицию по соседям узла $x$. Пусть $\ket{x}\ket{y}$ — базисное состояние. Мы определяем базисное состояние $\ket{x}\ket{y}$ как «хорошее», если $x$ — отмеченный узел. В противном случае мы называем это «плохим». Теперь введем «хорошие» и «плохие» состояния:\begin{equation} \ket{G} = \frac{1}{\sqrt{|M|}} \sum_{x \in M} \ket{x} \ket{p_x}, ; \ket{B} = \frac{1}{\sqrt{N-|M|}} \sum_{x \notin M} \ket{x} \ket{p_x}, \end{equation}которые являются суперпозициями над хорошими и плохими базисными состояниями. Далее определим $\epsilon = |M|/N$ и $\theta = \arcsin(\sqrt{\epsilon})$.Короче говоря, алгоритм состоит из трех шагов:1. Установите начальное состояние $\ket{U} = \frac{1}{\sqrt{N}} \sum_{x} \ket{x} \ket{p_x} = \sin{\theta} \ket{G } + \cos{\theta} \ket{B}$, равномерная суперпозиция по всем ребрам2. Повторите $O(1/\sqrt{\epsilon})$ раз:    (a) Отражение через $\ket{B}$    (b) Отражение через $\ket{U}$3. Сделайте измерение в вычислительной базеМы можем легко реализовать шаг $1$ с вентилями Адамара и отражение через $\ket{B}$ с помощью фазового оракула, который сдвигает фазу $x$, если $x$ находится в первом регистре, и оставляет схему неизменной в противном случае.Шаг 2(b) эквивалентен нахождению унитарного $R(P)$, выполняющего следующее отображение: \begin{align} \label{eq:mapping_1} \ket{U} &amp;\mapsto \ket{U}, : \text{и} \ \\ket{\psi} &amp;\mapsto -\ket{\psi}, : \forall \ket{\psi} \text{в промежутке собственных векторов $W(P)$, ортогональных в $\ket{U}$} \label{eq:mapping_2} \end{align}Чтобы найти этот оператор, мы применяем фазовую оценку на $W(P)$. Выше мы определили $W(P)$ как оператор эволюции случайного блуждания. Как мы видели в разделе 2.A, это унитарный оператор. Отсюда следует, что собственные значения оператора $W(P)$ имеют норму $1$. Благодаря этому мы можем записать собственные значения $W(P)$ в виде $e^{\pm 2i\theta_j}$. Унитарная $W(P)$ имеет один собственный вектор с соответствующим собственным значением $1$, равным $\ket{U}$. Это дается $\theta_1=0$. $R(P)$ найдет этот вектор $\ket{U}$, добавив регистр со вспомогательными кубитами, и выполнит оценку фазы с точностью $O(1/\sqrt{\delta})$, где $\delta$ спектральная щель $P$. Для этого нам нужно применить $W(P)$ $O(1/\sqrt{\delta})$ раз. Пусть $\ket{w}$ — собственный вектор $W(P)$ с собственным значением $e^{\pm 2i\theta_j}$. Предположим, что $\tilde{\theta_j}$ — наилучшее приближение к $\theta_j$, полученное с помощью фазовой оценки. Операция $R(P)$, которая выполняет отображения в для $\ket{w}$ на шаге 2(b), задается формулой [4]\begin{equation} \ket{w} \ket{0} \mapsto \ket{w} \ket{\tilde{\theta_j}} \mapsto (-1)^{|\tilde{\theta_j} \neq 0 |} \ket{w} \ket{\tilde{\theta_j}} \mapsto (-1)^{|\tilde{\theta_j} \neq 0|} \ket{w} \ket{0} \end{ уравнение} 5.Пример: поиск квантового блуждания по 4-мерному гиперкубуАлгоритм квантового блуждания позволяет найти отмеченное множество узлов за $O(1/\sqrt{\epsilon})$ шагов, $\epsilon = |M|/N$, где $M$ — количество отмеченные узлы, а $N$ — общее количество узлов. Этот алгоритм первоначально использовался с квантовыми блужданиями по Сегеди, где мы использовали регистры двух узлов для представления квантового состояния. Однако придуманное блуждание с монетой Гровера эквивалентно квантовому блужданию Сегеди, и, поскольку реализации придуманных блужданий в целом менее сложны, мы решили реализовать алгоритм с придуманным блужданием. Мы будем использовать 4-мерный гиперкуб, который мы реализовали в разделе 3.Вкратце алгоритм будем реализовывать следующим образом. Мы достигаем шага 1, равномерной суперпозиции по всем ребрам, применяя вентили Адамара к кубитам-узлам, а также к кубитам-монетам. Для шага 2(а) мы реализуем фазовый оракул. Шаг 2(b) реализуется оценкой фазы на одном шаге квантового блуждания по гиперкубу с последующей пометкой всех квантовых состояний, где $\theta\neq 0$. Мы делаем это, вращая вспомогательный кубит. В последней части этого шага мы обращаем оценку фазы. Количество тета-кубитов зависит от точности $\theta$.Ниже мы реализуем алгоритм поиска квантового блуждания на 4-мерном гиперкубе.  Для этого алгоритма нам нужно будет использовать обратный одношаговый вентиль, реализованный ранее. Мы получаем это с помощью встроенной в схему функции inverse().<jupyter_code>one_step_circuit.inverse().draw()<jupyter_output><empty_output><jupyter_text>Обратный одношаговый вентиль будет использоваться позже для обращения оценки фазы. Нам нужно сделать управляемые ворота как из одношаговых ворот, которые мы реализовали в разделе 3, так и из их обратных. Позже мы будем использовать их в зависимости от значения управляющего кубита.<jupyter_code># Make controlled gates
inv_cont_one_step = one_step_circuit.inverse().control()
inv_cont_one_step_gate = inv_cont_one_step.to_instruction()
cont_one_step = one_step_circuit.control()
cont_one_step_gate = cont_one_step.to_instruction()<jupyter_output><empty_output><jupyter_text>При оценке фазы будут использоваться как управляемый одношаговый вентиль, так и управляемый инверсный одношаговый вентиль. Еще одна вещь, которую мы будем использовать при оценке фазы, — это квантовое преобразование Фурье. В Qiskit есть функция QFT, реализующая квантовое преобразование Фурье. Для оценки фазы используется обратное квантовое преобразование Фурье, но нам также потребуется использовать обычную КТП для обратной оценки фазы.<jupyter_code>inv_qft_gate = QFT(4, inverse=True).to_instruction()  
qft_gate = QFT(4, inverse=False).to_instruction()

QFT(4, inverse=True).decompose().draw("mpl")<jupyter_output><empty_output><jupyter_text>Прежде чем мы реализуем оценку фазы, мы реализуем фазовый оракул, который отмечает состояния 1011 и 1111. Затем мы создаем схему. Это шаг 2(а) алгоритма.<jupyter_code>phase_circuit =  QuantumCircuit(6, name=' phase oracle ')
# Mark 1011
phase_circuit.x(2)
phase_circuit.h(3)
phase_circuit.mct([0,1,2], 3)
phase_circuit.h(3)
phase_circuit.x(2)
# Mark 1111
phase_circuit.h(3)
phase_circuit.mct([0,1,2],3)
phase_circuit.h(3)
phase_oracle_gate = phase_circuit.to_instruction()
# Phase oracle circuit
phase_oracle_circuit =  QuantumCircuit(11, name=' PHASE ORACLE CIRCUIT ')
phase_oracle_circuit.append(phase_oracle_gate, [4,5,6,7,8,9])
phase_circuit.draw()<jupyter_output><empty_output><jupyter_text>Теперь мы реализуем вентиль, который вращает вспомогательный кубит, если другие кубиты не равны нулю. Мы будем использовать этот вентиль в оценке фазы, где он будет вращать вспомогательный кубит, если $\theta\neq 0$.<jupyter_code># Mark q_4 if the other qubits are non-zero 
mark_auxiliary_circuit = QuantumCircuit(5, name=' mark auxiliary ')
mark_auxiliary_circuit.x([0,1,2,3,4])
mark_auxiliary_circuit.mct([0,1,2,3], 4)
mark_auxiliary_circuit.z(4)
mark_auxiliary_circuit.mct([0,1,2,3], 4)
mark_auxiliary_circuit.x([0,1,2,3,4])

mark_auxiliary_gate = mark_auxiliary_circuit.to_instruction()
mark_auxiliary_circuit.draw()<jupyter_output><empty_output><jupyter_text>Теперь мы реализуем шаг 2(b) алгоритма. Этот шаг состоит из фазовой оценки одного шага квантового блуждания, за которым следует вспомогательный кубит, который мы вращаем, если $\theta \neq 0$. Для этого мы используем только что созданный mark_auxiliary_gate. После этого мы обращаем оценку фазы.<jupyter_code># Phase estimation
phase_estimation_circuit = QuantumCircuit(11, name=' phase estimation ')
phase_estimation_circuit.h([0,1,2,3])
for i in range(0,4):
    stop = 2**i
    for j in range(0,stop):
        phase_estimation_circuit.append(cont_one_step, [i,4,5,6,7,8,9])

# Inverse fourier transform
phase_estimation_circuit.append(inv_qft_gate, [0,1,2,3])

# Mark all angles theta that are not 0 with an auxiliary qubit
phase_estimation_circuit.append(mark_auxiliary_gate, [0,1,2,3,10])

# Reverse phase estimation
phase_estimation_circuit.append(qft_gate, [0,1,2,3])   

for i in range(3,-1,-1):
    stop = 2**i
    for j in range(0,stop):
        phase_estimation_circuit.append(inv_cont_one_step, [i,4,5,6,7,8,9])
phase_estimation_circuit.barrier(range(0,10))
phase_estimation_circuit.h([0,1,2,3])

# Make phase estimation gate
phase_estimation_gate = phase_estimation_circuit.to_instruction()
phase_estimation_circuit.draw()<jupyter_output><empty_output><jupyter_text>Теперь мы реализуем весь алгоритм поиска квантового блуждания, используя вентили, которые мы сделали ранее. Мы начинаем с применения вентилей Адамара к кубитам узла и монеты, что является шагом 1 в алгоритме. После этого мы итеративно применяем вентиль фазового оракула и вентиль оценки фазы (этапы 2(a) и 2(b)). Нам потребуется $O(1/\sqrt{\epsilon})$ итераций, как указано в описании алгоритма в разделе 4. Наконец, мы измеряем кубиты узла.<jupyter_code># Implementation of the full quantum walk search algorithm
theta_q = QuantumRegister(4, 'theta')
node_q = QuantumRegister(4, 'node')
coin_q = QuantumRegister(2, 'coin')
auxiliary_q = QuantumRegister(1, 'auxiliary')
creg_c2 = ClassicalRegister(4, 'c')
circuit = QuantumCircuit(theta_q, node_q, coin_q, auxiliary_q, creg_c2)
# Apply Hadamard gates to the qubits that represent the nodes and the coin
circuit.h([4,5,6,7,8,9])
iterations = 2

for i in range(0,iterations):
    circuit.append(phase_oracle_gate, [4,5,6,7,8,9])
    circuit.append(phase_estimation_gate, [0,1,2,3,4,5,6,7,8,9,10])

circuit.measure(node_q[0], creg_c2[0])
circuit.measure(node_q[1], creg_c2[1])
circuit.measure(node_q[2], creg_c2[2])
circuit.measure(node_q[3], creg_c2[3])
circuit.draw()<jupyter_output><empty_output><jupyter_text>Наконец, мы запускаем реализацию на симуляторе qasm. Мы видим, что в большинстве случаев схема схлопывается до отмеченных состояний.<jupyter_code>backend = Aer.get_backend('qasm_simulator') 
job = execute( circuit, backend, shots=1024 ) 
hist = job.result().get_counts() 
plot_histogram( hist )<jupyter_output><empty_output><jupyter_text>6. Ссылки1. Ренато Португалия. Квантовые блуждания и алгоритмы поиска. Нью-Йорк, штат Нью-Йорк: Springer, Нью-Йорк, 2013 г.2. М<NAME>. Некоторые вводные заметки о квантовых вычислениях. апрель 2000 г.3. Томас Г. Вонг. «Эквивалентность Сегеди и придуманных квантовых блужданий». В: Квантовая обработка информации 16.9 (июль 2017 г.). ISSN: 1573-1332. DOI: 10.1007/s11128-017-1667-y. URL-адрес: http://dx.doi.org/10.1007/s11128-017-1667-y.374. Рональд де Вольф. Квантовые вычисления: конспект лекций. 2021. arXiv: 1907.09415 [квант-ф]<jupyter_code>import qiskit.tools.jupyter
%qiskit_version_table<jupyter_output>/usr/local/anaconda3/envs/terra-unstable/lib/python3.9/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
  warn_package('aqua', 'qiskit-terra')
{'fraction_non_alphanumeric': 0.09960340411468231, 'fraction_numerical': 0.01850780798149219, 'mean_word_length': 5.739142538975501, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 53, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '622263', 'license': 'Apache-2.0', 'n_tokens_mistral': 10017, 'n_tokens_neox': 11593, 'n_words': 2742, 'path': 'ru/notebooks/ch-algorithms/quantum-walk-search-algorithm.ipynb', 'repo_name': 'TanyaJazzTeam/platypus', 'size': '24234'}