Getting started with Q#. Deutsch’s algorithm
Deutsch’s algorithm – The algorithm developed by Deutsch in 1985 and became one of the first quantum algorithms. It considers the Boolean function f(x) of one variable.
Contents
Formulation of the problem
Let it be known that the Boolean function f(x) is:
-
or constant (takes the same value for any value of the argument)
-
or balanced (that is, for half of the argument values it applies the value 0, and for the other half of the argument values it acquires the value 1)
It is necessary to determine whether a given function is constant or balanced with the minimum number of calls to the oracle.
What does Wikipedia tell us?
For the Deutsch-Joži algorithm, a one-time appeal to the quantum oracle is enough to reliably solve the problem.
And it is customary for gentlemen to take their word for it, so let’s solve this task as the first experience of programming in Q # …
To code in Q#, we will need QDK, which is logical in principle.
The Microsoft site has detailed instructions for installing QDK for both VS and VS Code and much more with all the links to the required versions, etc.
But we are not looking for complex/simple (need to wait) ways and will use installation under VS Code.
-
Step one. Download and install VS Code
-
Step two. Start VS Code, go to the extension settings and install the extension Microsoft Quantum Development Kit for Visual Studio Code
-
Then, when we are offered to download .Netfollow the link and install .Net (at the time of writing the article for Q# was needed .Net 6.0)
-
All the other extensions just suck
This completes the deployment of the programming and debugging environment.
What does Deutsch’s algorithm look like?
Everything is simple – here it is:
N – Hadamard transformation
Phew – the oracle
M – Measuring the value of a qubit
And if the measurement result:
Okay – code
In VS Code
-
Let’s go to the menu Command Palette (Ctrl+Shift+P)
-
We choose “Q#: create new project”
-
In the proposed type of projects, we choose standalone
-
Specify the folder for the project
-
Replace in the generated file Program.qs code for the next one
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)}");
}
}
We write in the terminal
dotnet run
and we get what we expected
f(x)=0 : Zero
f(x)=1 : Zero
f(x)=x : One
f(x)=!x : One
Success! The machine is working.
Thank you all, goodbye.