Первые шаги в Q#. Алгоритм Дойча

Алгоритм Дойча — алгоритм, разработанный Дойчем в 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/