Руководство по реализация поиска по алгоритму Гровера на Q#

Статья
01/13/2024

Примечание

Microsoft Quantum Development Kit (классический QDK) больше не будет поддерживаться после 30 июня 2024 г. Если вы уже являетесь разработчиком QDK, рекомендуется перейти на новую версию Azure Quantum Development Kit (современный QDK), чтобы продолжить разработку квантовых решений. Дополнительные сведения см. в статье Перенос Q# кода в современный QDK.

В этом руководстве вы реализуете алгоритм Гровера в Q# для решения задач на основе поиска. Подробное теоретическое описание алгоритма Гровера см. в статье Теория алгоритма Гровера.

В этом руководстве вы выполните следующие действия.

Определите алгоритм Гровера для задачи поиска.
Реализуйте алгоритм Гровера в Q#.

Совет

Если вы хотите ускорить путь квантовых вычислений, проверка из code с помощью Azure Quantum, уникальной функции веб-сайта Azure Quantum. Здесь можно запускать встроенные Q# примеры или собственные Q# программы, создавать новый Q# код на основе запросов, открывать и запускать код в VS Code для Интернета одним щелчком мыши и задавать Copilot любые вопросы о квантовых вычислениях.

Предварительные требования

Чтобы запустить пример кода в Copilot в Azure Quantum, выполните следующие действия:
- Учетная запись электронной почты Майкрософт (MSA).
Чтобы разработать и запустить пример кода в Visual Studio Code:
- Последняя версия Visual Studio Code или откройте VS Code в Интернете.
- Последняя версия расширения Azure Quantum 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}}$ раз:
1. Фазовый оракул $O_f$, который применяет условный сдвиг фазы $-1$ к элементам решения.
2. Применение $H$ к каждому кубиту в регистре.
3. Применение $-O_0$, условного сдвига фазы $-1$, к каждому базисному состоянию вычисления, за исключением $\ket{0}$.
4. Применение $H$ к каждому кубиту в регистре.
Измерьте регистр, чтобы получить индекс элемента, который является решением с очень высокой вероятностью.
Проверьте, является ли элемент допустимым решением. Если решение не является допустимым, начните снова.

Написание кода для алгоритма Гровера в Q#

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

Определение помеченного состояния

Сначала определите, какие входные данные вы пытаетесь найти в поиске. Для этого напишите операцию, которая применяет шаги b, c и d из алгоритма Гровера.

Вместе эти шаги также называются оператором диффузии Гровера $-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{0}-\ket{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{optimal}}$. После этого вероятность снова возрастает до итерации $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}$, подготавливает регистр к однородной суперпозиции, а затем применяет алгоритм Гровера для указанного числа итераций. Сам поиск состоит из многократного отражения помеченного состояния и начального состояния, которые можно записать в Q# цикл for. Наконец, он измеряет регистр и возвращает результат.

Код использует три вспомогательные операции: 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 отражает состояние равномерной суперпозиции. Во-первых, он преобразует единую суперпозицию в all-zero. Затем он преобразует состояние "все ноль" в состояние "все". Наконец, он отражает состояние "все единицы". Операция называется 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 в браузере.

Скопируйте и вставьте следующий код в редактор кода.

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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 Quantinuum

Вы также можете отправить программу в бесплатный эмулятор Quantinuum серии H. Эмулятор имитирует квантовый компьютер с 20 кубитами.

Выберите раскрывающийся список Симулятор в памяти и выберите Quantinuum H-Series Emulator.
Выберите количество снимков (в настоящее время ограничено 20) и нажмите кнопку Выполнить.

Откройте Visual Studio Code и выберите Файл > Создать текстовый файл, чтобы создать новый файл.
Сохраните файл как GroversAlgorithm.qs. Этот файл будет содержать код вашей Q# программы.

Скопируйте следующий код в GroversAlgorithm.qs файл .

namespace GroversTutorial {
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Diagnostics;

    @EntryPoint()
    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);
        }
    }
}

Перед запуском программы необходимо задать target для профиля значение Неограниченную. Выберите Вид —> палитра команд, выполните поиск по запросу QIR, выберите Q#: Задайте профиль QIR target Azure Quantum, а затем выберите Q#: неограниченный.
Чтобы запустить программу, выберите Запустить Q# файл в раскрывающемся списке значок воспроизведения в правом верхнем углу или нажмите клавиши CTRL+F5. Программа запускает операцию или функцию, помеченную атрибутом в @EntryPoint() симуляторе по умолчанию.
Выходные данные отобразятся в консоли отладки.