Руководство по реализация поиска по алгоритму Гровера на Q#
В этом руководстве описано, как реализовать алгоритм Grover для Q# решения проблем на основе поиска. Подробное теоретическое описание алгоритма Гровера см. в статье Теория алгоритма Гровера.
Изучив это руководство, вы:
- Определение алгоритма Grover для задачи поиска
- Реализация алгоритма Гровера в Q#
Совет
Если вы хотите ускорить путешествие квантовых вычислений, ознакомьтесь с кодом с помощью Azure Quantum, уникальной функцией веб-сайта Azure Quantum. Здесь можно запустить встроенные Q# примеры или Q# собственные программы, создать новый Q# код из запросов, открыть и запустить код в VS Code для Интернета с помощью одного щелчка мыши и задать Copilot любые вопросы о квантовых вычислениях.
Необходимые компоненты
Чтобы запустить пример кода в Copilot в Azure Quantum:
- Учетная запись электронной почты Майкрософт (MSA).
Чтобы разработать и запустить пример кода в Visual Studio Code, выполните следующие действия.
- Последняя версия Visual Studio Code или откройте VS Code в Интернете.
- Последняя версия расширения AzureQuantum Development Kit. Дополнительные сведения об установке см. в разделе "Установка QDK" в VS Code.
Определение проблемы
Алгоритм поиска Гровера — один из самых известных алгоритмов в квантовых вычислениях. Тип проблемы, которую он решает, часто называется "поиском базы данных", но более точно думать об этом с точки зрения проблемы поиска.
Любую задачу поиска можно сформулировать математически с помощью абстрактной функции $f(x)$, принимающей элементы поиска $x$. Если элемент $x$ является решением задачи поиска, $f(x)=1$. Если элемент $x$ не является решением, то $f(x)=0$. Задача поиска состоит в поиске любого элемента $x_0$, для которого $f(x_0)=1$.
Таким образом, можно сформулировать любую проблему поиска следующим образом: учитывая классическую функцию $f(x):\{0,1\}^n \rightarrow\{0,1\}$, где $n$ — это битовый размер пространства поиска, найти входной $x_0$, для которого $f(x_0)=1$.
Чтобы реализовать алгоритм Гровера для решения задачи поиска, необходимо выполнить следующие действия.
- Преобразовать задачу в форму задачи Гровера. Например, предположим, что нам нужно найти простые множители для целого числа $M$ с помощью алгоритма Гровера. Чтобы преобразовать задачу разложения на простые множители в задачу Гровера, можно создать функцию $$f_M(x)=1[r],$$ где $1[r]=1$, если $r=0$, и $1[r]=0$, если $r\neq0$, а $r$ — остаток от деления $M/x$. Таким образом, целые числа $x_i$, образующие $f_M(x_i)=1$, представляют собой простые множители $M$, и задача преобразована в задачу Гровера.
- Реализовать функцию задачи Гровера в виде квантового оракула. Для реализации алгоритма Гровера необходимо реализовать функцию $f(x)$ задачи Гровера в виде квантового оракула.
- Использовать алгоритм Гровера с оракулом для решения этой задачи. После создания квантового оракула можно подключить его к реализации алгоритма Гровера, чтобы решить задачу и интерпретировать выходные данные.
Алгоритм Гровера
Предположим, есть $N=2^n$ подходящих элементов для задачи поиска и они индексируются путем присвоения каждому элементу целого числа от $0$ до $N-1$. Алгоритм включает следующие шаги.
- Начните с регистра из $n$ кубитов, находящихся в состоянии $\ket{0}$.
- Преобразуйте регистр в унифицированную суперпозицию, применив $H$ к каждому кубиту в регистре: $$|\psi\rangle=\frac{1}{N^{1 / 2}} \sum_{x=0}^{N-1}|x\rangle$$
- Примените следующие операции к регистру $N_{\text{optimal}}$:
- Фазовый оракул $O_f$, который применяет условный сдвиг фазы $-1$ к элементам решения.
- Применение $H$ к каждому кубиту в регистре.
- Применение $-O_0$, условного сдвига фазы $-1$, к каждому базисному состоянию вычисления, за исключением $\ket{0}$.
- Применение $H$ к каждому кубиту в регистре.
- Измерьте регистр, чтобы получить индекс элемента, который является решением с очень высокой вероятностью.
- Проверьте, является ли элемент допустимым решением. Если нет, начните снова.
Написание кода для алгоритма Гровера в Q#
В этом разделе описывается реализация алгоритма на Q#. При реализации алгоритма Гровера существует несколько аспектов. Необходимо определить, что такое помеченное состояние, как отразить его и сколько итерации для выполнения алгоритма. Кроме того, необходимо определить оракул, реализующий функцию задачи Гровера.
Определение помеченного состояния
Во-первых, вы определяете, какие входные данные вы пытаетесь найти в поиске. Для этого напишите операцию, которая применяет шаги b, c и d из алгоритма Гровера.
Вместе эти шаги также называются оператором диффузии Grover $-H^{\otimes n} O_0 H^{\otimes n}$.
operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit {
Message("Reflecting about marked state...");
use outputQubit = Qubit();
within {
// We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that
// toggling it results in a (-1) phase.
X(outputQubit);
H(outputQubit);
// Flip the outputQubit for marked states.
// Here, we get the state with alternating 0s and 1s by using the X
// operation on every other qubit.
for q in inputQubits[...2...] {
X(q);
}
} apply {
Controlled X(inputQubits, outputQubit);
}
}
Операция ReflectAboutMarked отражает состояние основы, помеченное чередующимися нулями и теми. Это делает, применяя оператор диффузии Гровера к входным кубитам. Операция использует вспомогательный кубит, outputQubitкоторый инициализирован в состоянии $\ket{-}=\frac{1}{\sqrt{2}}(\ket-\ket{0}{1})$ путем применения $X$ и $H$. Затем операция применяет шлюз $X$ к каждому другому кубитам в регистре, который перевернут состояние кубита. Наконец, он применяет контролируемые $X$ ворота к вспомогательному кубите и входным кубитам. Эта операция перевернула вспомогательный кубит, если и только если все входные кубиты находятся в состоянии $\ket{1}$, которое является помеченным состоянием.
Определение количества оптимальных итераций
Поиск с помощью алгоритма Гровера имеет оптимальное число итераций, которое позволяет получить наибольшую вероятность измерения допустимых входных данных. Если задача имеет $N=2^n$ возможных допустимых элементов и $M$ из них являются решениями задачи, оптимальным числом итераций является следующее:
$$N_{\text{optimal}}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$$
Продолжая итерировать прошлое оптимальное количество итераций, начинает уменьшать эту вероятность, пока не достигнет почти нулевой вероятности успешности при итерации $2 N_{\text{оптим}}$. После этого вероятность снова возрастает до итерации $3 N_{\text{optimal}}$ и т. д.
В практических приложениях обычно неизвестно, сколько решений имеет ваша задача, прежде чем вы решите ее. Эффективной стратегией для решения этой проблемы является "предположение" количества решений $M$ путем постепенного увеличения степени двойки (т. е. $1, 2, 4, 8, 16, … 2^n$). Одно из этих предположений будет достаточно близким для того, чтобы алгоритм нашел решение со средним числом итераций около $\sqrt{\frac{N}{M}}$.
Q# Следующая функция вычисляет оптимальное количество итераций для заданного количества кубитов в регистре.
function CalculateOptimalIterations(nQubits : Int) : Int {
if nQubits > 63 {
fail "This sample supports at most 63 qubits.";
}
let nItems = 1 <<< nQubits; // 2^nQubits
let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems)));
let iterations = Round(0.25 * PI() / angle - 0.5);
return iterations;
}
Функция CalculateOptimalIterations использует приведенную выше формулу для вычисления количества итераций, а затем округляет его до ближайшего целого числа.
Определение операции Гровера
Операция Q# для алгоритма поиска Гровера имеет три входных данных:
- Количество кубитов в
nQubits : Intрегистре кубитов. Этот регистр кодирует предварительное решение задачи поиска. После операции она будет измеряться. - Число оптимальных итераций.
iterations : Int - Операция,
phaseOracle : Qubit[] => Unit) : Result[]представляющая фазовый оракул для задачи Гровера. Эта операция применяет единое преобразование к общему регистру кубитов.
operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] {
use qubits = Qubit[nQubits];
PrepareUniform(qubits);
for _ in 1..iterations {
phaseOracle(qubits);
ReflectAboutUniform(qubits);
}
// Measure and return the answer.
return MResetEachZ(qubits);
}
Операция GroverSearch инициализирует регистр кубитов $n$ в состоянии $\ket{0}$, подготавливает регистр в единую суперпозицию, а затем применяет алгоритм Grover для указанного количества итераций. Сам поиск состоит из многократного отражения отмеченного состояния и начального состояния, которое можно записать в Q# виде цикла. Наконец, он измеряет регистр и возвращает результат.
Код использует три вспомогательные операции: PrepareUniform, ReflectAboutUniformи ReflectAboutAllOnes.
Учитывая регистр в состоянии "все ноль", PrepareUniform операция подготавливает единую суперпозицию для всех базовых состояний.
operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl {
for q in inputQubits {
H(q);
}
}
Операция "ReflectAboutAllOnes" отражает состояние всех.
operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit {
Controlled Z(Most(inputQubits), Tail(inputQubits));
}
ReflectAboutUniform Операция отражает однородное состояние суперпозиции. Во-первых, он преобразует однородную суперпозицию на все ноль. Затем он преобразует все нулевое состояние на все. Наконец, он отражает о состоянии всех. Операция называется ReflectAboutUniform, так как ее можно геометрически интерпретировать как отражение в пространстве вектора, связанное с унифицированной суперпозицией.
operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
within {
Adjoint PrepareUniform(inputQubits);
// Transform the all-zero state to all-ones
for q in inputQubits {
X(q);
}
} apply {
ReflectAboutAllOnes(inputQubits);
}
}
Выполнение окончательного кода
Теперь у вас есть все необходимое, чтобы реализовать конкретный экземпляр алгоритма поиска Гровера и решить задачу по разложению числа на простые множители. Чтобы завершить работу, операция настраивает проблему, Main указывая количество кубитов и количество итерации
operation Main() : Result[] {
let nQubits = 5;
let iterations = CalculateOptimalIterations(nQubits);
Message($"Number of iterations: {iterations}");
// Use Grover's algorithm to find a particular marked state.
let results = GroverSearch(nQubits, iterations, ReflectAboutMarked);
return results;
}
Запуск программы
Выберите нужную платформу для запуска программы.
Вы можете протестировать Q# код с помощью Copilot в Azure Quantum бесплатно. Все, что вам нужно, это учетная запись электронной почты Майкрософт (MSA). Дополнительные сведения о Copilot в Azure Quantum см. в статье "Обзор Azure Quantum".
Откройте Copilot в Azure Quantum в браузере.
Скопируйте и вставьте следующий код в редактор кода.
import Microsoft.Quantum.Convert.*; import Microsoft.Quantum.Math.*; import Microsoft.Quantum.Arrays.*; import Microsoft.Quantum.Measurement.*; import Microsoft.Quantum.Diagnostics.*; operation Main() : Result[] { let nQubits = 5; let iterations = CalculateOptimalIterations(nQubits); Message($"Number of iterations: {iterations}"); // Use Grover's algorithm to find a particular marked state. let results = GroverSearch(nQubits, iterations, ReflectAboutMarked); return results; } operation GroverSearch( nQubits : Int, iterations : Int, phaseOracle : Qubit[] => Unit) : Result[] { use qubits = Qubit[nQubits]; PrepareUniform(qubits); for _ in 1..iterations { phaseOracle(qubits); ReflectAboutUniform(qubits); } // Measure and return the answer. return MResetEachZ(qubits); } function CalculateOptimalIterations(nQubits : Int) : Int { if nQubits > 63 { fail "This sample supports at most 63 qubits."; } let nItems = 1 <<< nQubits; // 2^nQubits let angle = ArcSin(1. / Sqrt(IntAsDouble(nItems))); let iterations = Round(0.25 * PI() / angle - 0.5); return iterations; } operation ReflectAboutMarked(inputQubits : Qubit[]) : Unit { Message("Reflecting about marked state..."); use outputQubit = Qubit(); within { // We initialize the outputQubit to (|0⟩ - |1⟩) / √2, so that // toggling it results in a (-1) phase. X(outputQubit); H(outputQubit); // Flip the outputQubit for marked states. // Here, we get the state with alternating 0s and 1s by using the X // operation on every other qubit. for q in inputQubits[...2...] { X(q); } } apply { Controlled X(inputQubits, outputQubit); } } operation PrepareUniform(inputQubits : Qubit[]) : Unit is Adj + Ctl { for q in inputQubits { H(q); } } operation ReflectAboutAllOnes(inputQubits : Qubit[]) : Unit { Controlled Z(Most(inputQubits), Tail(inputQubits)); } operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit { within { // Transform the uniform superposition to all-zero. Adjoint PrepareUniform(inputQubits); // Transform the all-zero state to all-ones for q in inputQubits { X(q); } } apply { // Now that we've transformed the uniform superposition to the // all-ones state, reflect about the all-ones state, then let the // within/apply block transform us back. ReflectAboutAllOnes(inputQubits); } }
Совет
В Copilot в Azure Quantum вы можете открыть программу в VS Code для Интернета , нажав кнопку с логотипом VS Code в правом углу редактора кода.
Запустите программу с помощью симулятора в памяти
- Выберите симулятор в памяти.
- Выберите количество выстрелов для выполнения и нажмите кнопку "Выполнить".
- Результаты отображаются в гистограмме и в полях результатов .
- Выберите "Объяснить код", чтобы предложить Copilot объяснить вам код.
Запустите программу с помощью эмулятора серии H-Series Quantinuum
Вы также можете отправить программу в бесплатный эмулятор серии H-Series Quantinuum. Эмулятор имитирует квантовый компьютер с 20 кубитами.
- Выберите раскрывающийся список симулятора в памяти и выберите эмулятор H-series Quantinuum.
- Выберите количество выстрелов (в настоящее время ограничено 20) и нажмите кнопку "Выполнить".
Связанный контент
Ознакомьтесь с другими учебниками по Q#:
- Квантовое запутание показывает, как писать Q# программу, которая управляет кубитами и измеряет кубиты и демонстрирует эффекты суперпозиции и запутанности.
- Генератор квантовых случайных чисел показывает, как написать Q# программу, которая создает случайные числа из кубитов в суперпозиции.
- Quantum Fourier Transform изучает, как писать программу, которая напрямую Q# обращается к определенным кубитам.
- Квантовые Катас — это самоуправляемые учебники и упражнения по программированию, направленные на обучение элементам квантовых вычислений и Q# программирования одновременно.