Алгоритм Дойча — алгоритм, разработанный Дойчем в 1985 году, и ставший одним из первых квантовых алгоритмов. В нём рассматривается функция булевая f(x) от одной переменной.

Постановка задачи

Пусть известно, что булевая функция f(x) является:

1. либо постоянной (принимает одно и то же значение при любом значении аргумента)

2. либо сбалансированной (то есть для половины значений аргумента она приминает значение 0, а для другой половины значений аргумента она принимает значение 1)

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

Что нам говорит Википедия?

Алгоритму Дойча — Йожи достаточно однократного обращения к квантовому оракулу для достоверного решения задачи.

А джентельменам принято верить на слово, значит решим эту задачу, как первый опыт программирования на Q# ...

Чтобы кодить на Q# нам потребуется QDK, что в принципе логично.

Сайт Майкрософт содержит подробные инструкции по установке QDK и под VS, и под VS Code и под много разное со всеми ссылками на нужные версии и т.д..

Но мы не ищем сложных/простых (нужное подчекнуть) путей и воспользуемся установкой под VS Code.

• Шаг первый. Скачиваем и устанавливаем VS Code.

• Шаг второй. Запускаем VS Code, идём в настройку расширений и устанавливаем расширение Microsoft Quantum Development Kit for Visual Studio Code.

• Потом, когда нам предложат скачать .Net, перейдём по ссылке и установим .Net (на момент написания статьи для Q# требовался .Net 6.0).

• Все остально расширение само докачает.

Таким образом с развёртываением среды программирования и отладки покончено.

Как выглядит алгоритм Дойча?

Всё просто - вот он:

Н — преобразование Адамара

Uf — оракул

M — измерение значения кубита

И если результат измерения:

• |0> то функция постоянная

• |1> то функция сбалансированная

Окей - кодим

В VS Code

• Идём в меню Command Palette (Ctrl+Shift+P)

• Выбираем "Q#: create new project"

• В предложенном типе проектов выбираем standalone

• Указываем папку для проекта

• Заменяем в сгенерированном файле Program.qs код на следующий

namespace qq {

    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Measurement;
    
    operation SetQubitState(desired : Result, target : Qubit) : Unit {
        if desired != M(target) {
            X(target);
        }
    }

    // Алгоритм Дойча для булевая функции одного аргумента
    // Параметром передаётся оракул для произвольной булевой функции одного аргумента
    operation Deutsch(Oracle : (Qubit, Qubit) => Unit) : Result {

        // Аллокирование кубитов
        use (x,y) = (Qubit(), Qubit()); 

        // Задание начальных значений кубитов, согласно алгритму Дойча
        SetQubitState(Zero, x);
        SetQubitState(One, y);

        //  Применение преобразований Адамара к кубитам
        H(x);
        H(y);

        // Применение оракула
        Oracle(x,y);

        //  Применение преобразований Адамара к кубиту x
        H(x);

        // Измерение значения кубита x
        let result = M(x);  

        // Очиска значений кубитов перед высвобождением
        SetQubitState(Zero, x);
        SetQubitState(Zero, y);
        
        return result;
    }

    // Оракул булевой функции одного аргумента может быть одним из следующих
    operation Uf0(x:Qubit,y:Qubit): Unit {} // f(x)=0
    operation Uf1(x:Qubit,y:Qubit): Unit { X(y); } // f(x)=1
    operation Uf2(x:Qubit,y:Qubit): Unit { CNOT(x,y); } // f(x)=x
    operation Uf3(x:Qubit,y:Qubit): Unit { X(x); CNOT(x,y); X(x); } //f(x)=!x

    @EntryPoint()
    operation Main(): Unit {

        // Результат алгоритма Дойча
        // Значение |0> если булевая функции одного аргумента постоянна (то есть константа)
        // Значение |1> если булевая функции одного аргумента сбалансированная

        Message($"f(x)=0  : {Deutsch(Uf0)}");
        Message($"f(x)=1  : {Deutsch(Uf1)}");
        Message($"f(x)=x  : {Deutsch(Uf2)}");
        Message($"f(x)=!x : {Deutsch(Uf3)}");
    }
}

В терминале пишем

dotnet run

и получаем то что и ожидали

f(x)=0  : Zero
f(x)=1  : Zero
f(x)=x  : One
f(x)=!x : One

Успех! Работает машинка ...

NB. КДПВ - не просто картинка - это тоже реализация алгоритма Дойча на квантовом компьютере на фотонах - да, это тоже квантовый компьютер ... и он работает!

Всем спасибо, до свидания.

UPD. https://habr.com/ru/posts/759506/